一. 线索二叉树结构的设计
叶子结点的左右指针为空, 可以利用这里空链域记录它们前驱和后继结点, 如果 Ltag 或 Rtag 为 1, 说明左右指针指向的不是子树, 而是前驱和后继.1
2
3
4
5
6typedef struct bitree
{
int Ltag, Rtag;
bitree LChild, RChild;
char data;
}BiTree;
二. 二叉树的线索化
分类: 先序线索二叉树, 中序线索二叉树, 后序线索二叉树
思想:
- 类似于二叉树的遍历, 只不过在遍历的过程中, 对结点的访问改成: 修改结点为 NULL
的指针域. - 需要有两个结点, pre(前一个结点) 和 root (当前结点)
- ①如果当前遍历结点 root 的左子域为空,则让左子域指向 pre ;
②如果前驱 pre 的右子域为空,则让右子域指向当前遍历结点 root;
③为下次做准备,当前访问结点 root 作为下一个访问结点的前驱 pre。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20//先序线索化二叉树
void Inthread(BiTree root)
{
if(root!=NULL) //当前结点存在
{
Inthread(root->LChild); //线索化左子树
if(root->LChild==NULL) //如果当前结点的左子树为空, 当前结点的前驱为遍历过程中的前一个结点
{
root->Ltag = 1;
root->LChild = pre;
}
if(pre!=NULL && pre->RChild==NULL) //不知为何, 2017年11月19日 12:27:26
{
pre->RChild=root;
pre->Rtag = 1;
}
pre = root;
Inthread(root->RChild);
}
}
三. 线索二叉树结点前驱后继的查找
功能:给一个结点, 找到它的前驱和后继, 前提是二叉树已经被线索化.
根据先中后的不同, 查找方式也不相同, 这里只是中序线索二叉树的例子: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//在中序线索二叉树中查找 p 的前驱, 并用 pre 指针返回结果
BiTree * InPre(BiTree * p)
{
if(p->Ltag==1)
{
pre = p->LChild;
}
else //Ltag 不为 1, 说明 p 的左子树一定不为空.
{
for(q=p->LChild; q->Rtag==0; q=q->Rtag);
pre = q;
}
return pre;
}
//在中序线索二叉树中查找 p 的后继, 并用 pre 指针返回结果
BiTree * InNext(BiTree * p)
{
if(p->Rtag==1)
{
pre = p->RChild;
}
else
{
if(p->RChild!=NULL) //可能有右子树, 也可能没有右子树
{
for(q=p->RChild; q->Ltag==0; q=q->LChild);
Next = q;
}
else
{
Next = NULL;
}
}
return Next;
}
四. 遍历线索二叉树
功能: 取树中的一个结点, 找出它后面的结点.
这里只是以中序线索二叉树为例子:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23//遍历中序线索二叉树
//第一步, 找出一棵二叉树中序遍历使的第一个结点
BiTree * InFirst(BiTree Bt)
{
BiTree * p = Br;
if(!p) return (NULL);
while(p->Ltag==0)
{
p = p->LChild;
}
return p;
}
//第二步, 不断找出其后继结点
void TInOrder(BiTree Bt)
{
BiTree * p;
p = InFirst(Bt);
while(p)
{
Visit(p);
p = InNext(p);
}
}
五. 总结
线索二叉树存储某个结点的前驱和后继, 可以做到: 取其中任意一个结点, 都可以遍历出它后面的结点. 如果是一般的二叉树, 只能从根完整地遍历一次.
操作有:
- 线索化二叉树, 也就是把原本的空指针域用来指向前驱或后继结点. 有先序线索二叉树, 中序线索二叉树, 后序线索二叉树三种类型, 它们线索化的方式是不同的.
- 查找某个结点的前驱或后继结点. 如果该结点的指针域是线索, 那么就可以马上找到前驱或后继结点. 否则, 需要通过规律来找到前驱或后继结点. 而三类线索树的规律又是不同的, 所以查找方式是不同的.
线索二叉树的缺点是: 太难了, 让我搞不懂. 三种序列索化二叉树的操作不同, 查找前驱和后继结点的操作也不同, 甚至这些操作可以用递归实现也可以用非递归实现…