线索二叉树的遍历和线索化

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
91
92
93
94
95
96
97
98
99
100
#include <stdio.h>
#include <stdlib.h>

enum
{
    Link,  // 正常指向下一个节点
    Thread  // 指向线索节点
} Tag;

typedef struct TNode
{
    char data;
    struct TNode *lchild;
    struct TNode *rchild;
    unsigned char ltag;
    unsigned char rtag;
} TNode;

TNode *pre = NULL;

TNode *createNode(char data, TNode *lchild, TNode *rchild)
{
    TNode *node = (TNode *)malloc(sizeof(TNode));
    node->data = data;
    node->lchild = lchild;
    node->rchild = rchild;
    node->ltag = Link;
    node->rtag = Link;
    return node;
}

void inThreading(TNode *tree)
{
    if (tree)
    {
        inThreading(tree->lchild);
        if (!tree->lchild) // 没有左孩子
        {
            tree->ltag = Thread;
            tree->lchild = pre;
        }
        if (!pre->rchild)  // 上一个节点没有右孩子
        {
            pre->rtag = Thread;
            pre->rchild = tree;   // 此时pre节点是当前节点的child，所以pre的rchild可以连接到他的父节点
        }
        pre = tree;  // 在处理完之后才设置pre可以确保rchild的正确指向
        inThreading(tree->rchild);
    }
}

void InOrderThreading(TNode *tree, TNode *head)
{
    head->data = 0;
    head->ltag = Link;
    head->lchild = tree;  // 头节点的lchild指向根节点
    if (!tree)
    {
        return;
    }
    pre = tree;
    inThreading(tree);
    pre->rchild = head;  // 树的中序遍历最后一个节点指向头节点
    pre->rtag = Thread;
    head->rchild = pre; // 头节点的rchild指向中序遍历最后一个节点
}

void InOrderTraverse(TNode *head)
{
    TNode *n = head->lchild; // 找到根节点
    while (n != head)
    {
        while (n->ltag == Link)
        {
            n = n->lchild;   // 先找到最左边的节点（开始遍历）
        }
        printf("%c ", n->data);

        while (n->rtag == Thread && n->rchild != head) // 沿着线索找到每一个节点
        {
            n = n->rchild;
            printf("%c ", n->data);
        }
        n = n->rchild; // 从节点的右子树开始遍历
    }
}

int main(int argc, char const *argv[])
{
    TNode *tree = createNode('1',
                             createNode('2', createNode('4', NULL, NULL), createNode('5', NULL, NULL)),
                             createNode('3', createNode('6', NULL, NULL), createNode('7', NULL, NULL)));
    TNode head;
    InOrderThreading(tree, &head);
    InOrderTraverse(&head);

    return 0;
}