数据结构——二叉树的线索化以及线索化输出

二叉树的线索化过程，其遍历过程和中序遍历一致，只不过在遍历过程中顺手将节点的左空指针赋值为前一个节点地址，右空指针顺手赋值为下一个节点地址，所以需要一个pre变量来保存当前遍历的节点，方便对后一时刻的root进行操作。
对于如下二叉树：

线索化程序如下：

void TreeThreaded(Node* root){
    static Node *pre=NULL;//静态局部变量只在第一次使用时初始化，之后只进行调用
    if(root!=NULL){
        TreeThreaded(root->lchild);//递归一直遍历到根节点的最左子孩子
        if(root->lchild==NULL){
            root->lchild=pre;
            root->ltag=THREAD;
        }
        if(pre !=NULL && pre->rchild==NULL){
            pre->rchild = root;
            pre->rtag = THREAD;
        }
        pre=root;//pre节点总是赋值为前一个root节点，即root节点在下一个时刻变成pre
        TreeThreaded(root->rchild);
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

程序的运行过程为：

程序运行：TreeThreaded(root->lchild)，一直遍历到最左子节点H
1

此时root=H;
运行完：TreeThreaded(H->lchild)，执行if(root->lchild==NULL)条件语句，
不满足if(pre !=NULL && pre->rchild==NULL),跳过，
执行pre=H;
执行TreeThreaded(H->rchild)，因为H->rchild为空，什么也不干，程序返回
程序返回，从栈中弹出H
程序运行结果如下：
1
2
3
4
5
6
7

此时root=D,pre=H;
不满足if(root->lchild==NULL);
满足if(pre !=NULL && pre->rchild==NULL);
将H->left赋值为D;
执行pre=D。
程序运行过程如下：
1
2
3
4
5
6

执行 TreeThreaded(D->rchild),即 TreeThreaded(I);
执行TreeThreaded(I->left),因为I->left为空，什么也不干;
执行pre=root=I;
执行TreeThreaded(I->rchild),什么也不干;
从堆栈中弹出I;
从堆栈中弹出D;
1
2
3
4
5
6

#include 
#include 
#include 
#define MAX_OP 8
#define NORMAL 0
#define THREAD 1

typedef struct Node{
    int data;
    int ltag,rtag;
    struct Node *lchild,*rchild;
}Node;
static Node *pre=NULL;
Node* getNewNode(int value){
    Node* node=(Node*)malloc(sizeof(Node));
    node->data=value;
    node->lchild=node->rchild=NULL;
    node->rtag=node->ltag=NORMAL;
    return node;
}
void TreeThreaded(Node* root){
    if(root==NULL)return;
    //static Node *pre=NULL;//静态局部变量只在第一次使用时初始化，之后只进行调用
    TreeThreaded(root->lchild);//递归一直遍历到根节点的最左子孩子
    if(root->lchild==NULL){
        root->lchild=pre;
        root->ltag=THREAD;
    }
    if(pre != NULL && pre->rchild == NULL){
        pre->rchild = root;
        pre->rtag = THREAD;
    }
    pre=root;
    TreeThreaded(root->rchild);
    return;
}
void clear(Node* root){
    if(root==NULL)return;
    if(root->ltag==NORMAL)clear(root->lchild);
    if(root->rtag==NORMAL)clear(root->rchild);
    free(root);
}
Node *leftMost(Node *node){
    while(node != NULL && node->ltag == NORMAL && node->lchild != NULL)node = node->lchild;
    return node;
}
void output(Node* root){
    Node* node=leftMost(root);
    while(node !=NULL){
        printf("%d ",node->data);
        if(node->rtag == THREAD){
            node = node->rchild;
        }else{
            node = leftMost(node->rchild);
        }
    }
    printf("\n");
    return;
}
Node* insert(Node *root,int value){//排序二叉树的插入操作
    if(root==NULL)return getNewNode(value);
    if(root->data==value)return root;
    if(root->data<value)root->rchild=insert(root->rchild,value);
    if(root->data>value)root->lchild=insert(root->lchild,value);
    return root;
}
void inOrder(Node* root){
    if(root==NULL)return;
    if(root->ltag==NORMAL)inOrder(root->lchild);
    printf("%d ",root->data);
    if(root->rtag==NORMAL)inOrder(root->rchild);
    return;
}
int main() {
    srand(time(0));
    Node* root=NULL;
    for(int i=0;i<MAX_OP;i++){
        int value=rand()%50;
        printf("%d\n",value);
        root=insert(root,value);
    }
    TreeThreaded(root);
    inOrder(root);
    printf("\n");
    output(root);
    printf("\n");
    clear(root);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90