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

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;
}