数据结构与算法——第6章-树-线索二叉树(6.10.1)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
4
1.二叉树遍历
2.什么是线索二叉树
3.线索二叉树的结点结构
4.示例代码

二 二叉树遍历

1
2
3
通过前面对二叉树的学习，了解到二叉树本身是一种非线性结构，
采用任何一种遍历二叉树的方法，都可以得到树中所有结点的一个线性序列。
在这个序列中，除第一个结点外，每个结点都有自己的直接前趋；除最后一个结点外，每个结点都有一个直接后继。

三 什么是线索二叉树

1
2
3
4
5
如果算法中多次涉及到对二叉树的遍历，普通的二叉树就需要使用栈结构做重复性的操作。

线索二叉树不需要如此，在遍历的同时，使用二叉树中空闲的内存空间记录某些结点的前趋和后继元素的位置（不是全部）。
这样在算法后期需要遍历二叉树时，就可以利用保存的结点信息，提高了遍历的效率。
使用这种方法构建的二叉树，即为“线索二叉树”。

四 线索二叉树的结点结构

4.1 存储密度

1
2
3
4
5
如果在二叉树中想保存每个结点前趋和后继所在的位置信息，最直接的想法就是改变结点的结构，
即添加两个指针域，分别指向该结点的前趋和后继。

但是这种方式会降低树存储结构的存储密度。而对于二叉树来讲，其本身还有很多未利用的空间。
存储密度指的是数据本身所占的存储空间和整个结点结构所占的存储量之比。

4.2 线索二叉树

1
2
3
4
5
每一棵二叉树上，很多结点都含有未使用的指向 NULL 的指针域。
除了度为 2 的结点，度为 1 的结点，有一个空的指针域；叶子结点两个指针域都为NULL。

规律：在有 n 个结点的二叉链表中必定存在 n+1 个空指针域。
线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。

4.3 线索二叉树中的结点结构

一、图示

1
2
3
4
线索二叉树中，如果结点有左子树，则 lchild 指针域指向左孩子，否则 lchild 指针域指向该结点的直接前趋；
同样，如果结点有右子树，则 rchild 指针域指向右孩子，否则 rchild 指针域指向该结点的直接后继。

为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，如图 2 所示。

二、变量说明

1
2
3
LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：
1.LTag 值为 0 时，表示 lchild 指针域指向的是该结点的左孩子；为 1 时，表示指向的是该结点的直接前趋结点；
2.RTag 值为 0 时，表示 rchild 指针域指向的是该结点的右孩子；为 1 时，表示指向的是该结点的直接后继结点。

五 示例代码

5.1 结点结构代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link 为 0，Thread 为 1
typedef enum PointerTag {
	Link,
	Thread
} PointerTag;
//结点结构构造
typedef struct BiThrNode {
	TElemType data;//数据域
	struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
	PointerTag Ltag,Rtag;//标志域，枚举类型
} BiThrNode,*BiThrTree;

5.2 说明

1
2
3
表示二叉树时，使用图 2 所示的结点结构构成的二叉链表，被称为线索链表；构建的二叉树称为线索二叉树。
线索链表中的“线索”，指的是链表中指向结点前趋和后继的指针。
二叉树经过某种遍历方法转化为线索二叉树的过程称为线索化。

六 参考

  • C语言中文网—线索二叉树