线索二叉树是一个二叉树通过如下的方法“穿起来”：所有原本为空的右（孩子）指针改为指向该节点在中序序列中的后继，所有原本为空的左（孩子）指针改为指向该节点的中序序列的前驱。以下为我在学习和实战练习过程中所做的笔记，可供参考。
一、线索二叉树的结构
树结点数据结构：
1
2
3
4
5
6
| typedef char ElemType;
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree;
|
线索二叉树：
1
2
3
4
5
6
7
8
9
10
| int main()
{
ThreadTree T;
ThreadTree p;
BulidThreadTree(T);
CreateInThread(T);
p=Firstnode(T);
printf("最左下结点值为 %c\n",p->data);
system("pause");
}
|
二、线索二叉树的建树
以中序线索二叉树的建立为例，附设指针 pre 指向刚刚访问过的结点，指针 p 指向正在访问的结点，即 pre 指向 p 的前驱。在中序遍历的过程中，检查 ρ 的左指针是否为空，若为空就将它指向 pre，检查 pre 的右指针是否为空，若为空就将它指向 p：
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
|
void BulidThreadTree(ThreadTree &T)
{
ThreadTree arr[5];
int i;
for(i=0;i<5;i++)
{
arr[i]=(ThreadTree)malloc(sizeof(ThreadNode));
memset(arr[i],0,sizeof(ThreadNode));
arr[i]->data='A'+i;
}
arr[0]->lchild=arr[1];
arr[0]->rchild=arr[2];
arr[1]->rchild=arr[3];
arr[2]->lchild=arr[4];
T=arr[0];
}
void InThread(ThreadTree &p,ThreadTree &pre)
{
if(p!=NULL){
InThread(p->lchild,pre);
if(p->lchild==NULL){
p->lchild=pre;
p->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){
pre->rchild=p;
pre->rtag=1;
}
pre=p;
InThread(p->rchild,pre);
}
}
void CreateInThread(ThreadTree T)
{
ThreadTree pre=NULL;
if(T!=NULL){
InThread(T,pre);
pre->rchild=NULL;
pre->rtag=1;
}
}
ThreadNode *Firstnode(ThreadNode *p)
{
while(p->ltag==0)
p=p->lchild;
return p;
}
|