数据结构导论【四】之 树和二叉树_指定反馈树中使用的额外tnode结构字段,并允许从子顶点移动到其直接祖先。

接上一篇：数据结构导论【三】之 栈队列和数组

一、树的基本概念

树形结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。

1.树的定义【递归是树的固有特性】

树是n(n >= 0)个结点的有限集T，满足：

1. 当 n = 0 时，称为空树；
2. 当 n > 0 时，有且仅有一个特定的称为根的结点；其余的结点可分为m(m >= 0)个互不相交的子集T1,T2,T3…Tm,其中每个子集Ti又是一颗树，并称其为子树。

2.树的逻辑表示

小例题：
问: 如果结点B有2个兄弟结点，结点A为B的双亲，则结点A的度为？
答：A的度为3【就是有几个子结点，度就为几】

3.树的相关术语

4.树的基本运算

求根Root(T): 求树T的根结点；
求双亲Parent(T, X): 求结点X在树T上的双亲；若X是树T的根或X不在T上，则结果为一特殊标志；
求孩子Child(T, X, i): 求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志；
建树Create(X, T1, …, Tk),k > 1: 建立一颗以X为根，以T1,…Tk为第1,…k棵子树的树；
剪枝Delete(T, X, i): 删除树T上结点X的第i颗子树；若T无第i颗子树，则为空操作；
遍历TraverseTree(T): 遍历树，即访问树中每个结点，且每个结点仅被访问一次。

二、二叉树

二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

1.二叉树的基本概念

①定义

②特点

1. 二叉树可以是空的，称空二叉树；
2. 每个结点最多只能有俩个孩子；
3. 子树有左、右之分且次序不能颠倒。

③二叉树与树的比较

---

二叉树结点的子树要区分左子树和右子树，即使只有一颗子树也要进行区分，说明它是左子树还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态【图C和图D是不同的俩颗二叉树】。

---

④二叉树的基本运算

初始化Initiate(BT): 建立一颗空二叉树，BT=∅。
说明：∅是表示空集的意思。
求双亲Parent(BT, X): 求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。
求左孩子Lchild(BT, X)和求右孩子Rchild(BT, X): 分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X不在BT上，运算结果为NULL。
建二叉树Create(BT): 建立一颗二叉树BT。
先序遍历PreOrder(BT): 按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。
中序遍历InOrder(BT): 按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。
后序遍历PostOrder(BT): 按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。
层次遍历LevelOrder(BT): 按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。

2.二叉树的性质

二叉树具有下列重要性质：

---

性质1：在二叉树的第i(i >= 1)层上至多有$2^{i-1}$个结点。

---

性质2：深度为k(k >= 1)的二叉树至多有$2^k-1$个结点
比如满二叉树的结点个数：

满二叉树中结点顺序编号：即从第一层结点开始自上而下，从左到右进行连续编号。

PS:完全二叉树必须是从右下开始剪枝的才算是完全二叉树，否则不是。

---

性质3：对任何一颗二叉树，如果其终端结点树为n0，度为2的结点数为n2，则n0 = n2 + 1。
即：叶结点数n0 = 度为2的结点数 n2 + 1。

---

PS:⌊⌋表示向下取整，相当于忽略结果的小数部分

性质4：具有n个结点的完全二叉树的深度为$\lfloor lo{g}_{2}n\rfloor +1$。
符号⌊x⌋ 表示不大于x的最大整数。
假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到： $2^{k-1}-1<n<=2^k-1$ 或 $2^{k-1}<=n<2^k$

取对数得到：$k-1<lo{g}_{2}n<k$。因为k是整数。所以有$\lfloor lo{g}_{2}n\rfloor +1$

---

性质5：对有n个结点的完全二叉树的结点按层编号（从第1层到第$\lfloor lo{g}_{2}n\rfloor +1$层，每层由左到右），则对任一结点i（1 <= i <= n），有：

1. 如果 i = 1，则结点i无双亲，是二叉树的根；如果i > 1，则i的双亲Parent(A)是结点i / 2然后向下取整【比如3的父节点是：3 / 2 = 1.5,向下取整得1】;
2. 如果2i <= n，则其左孩子是结点2i，否则，结点i无左孩子且为叶子结点；
3. 如果2i + 1 <= n，则其右孩子是结点2i + 1，否则，结点i无右孩子。

---

三、二叉树的存储结构

1.二叉树的顺序存储结构

它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，可用编号的方法。

二叉树的顺序存储结构：即对二叉树按完全二叉树进行编号，然后用一维数组存储，其中编号为i的结点存储在数组中下标为i的分量中。 – 该方法称为『以编号为地址』策略。

此方法用于完全二叉树，则：
节省内存、结点位置确定方便

对于非完全二叉树，则用某种方法将其转化为完全二叉树，为此可增设若干个虚拟结点。

如果用于一般二叉树（则存储空间浪费极大，因为会有很多虚拟结点）：

从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树却需要$2^{h-1}$个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好。

---

2.二叉树的链式存储结构

①二叉链表表示法：

二叉链表类型定义：

typedef struct btnode {
	datatype data;
	struct btnode *Lchild, *Rchild;
} *BinTree;
1
2
3
4

PS：在含n个结点的二叉链表中有2n个指针域，其中n-1个用来指向结点的左右孩子，其余n + 1个空链域。

---

②三叉链表表示法：

结点形式：

---

四、二叉树的遍历

1.遍历含义

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。

遍历二叉树：是指按某种次序访问二叉树上的所有结点，使每个结点被访问一次且仅被访问一次。

2.遍历规则

由二叉树的递归定义得知：二叉树的三个基本组成单元是：根节点、左子树和右子树。

1. 先序遍历DLR：首先访问根节点，其次遍历根的左子树，最后遍历根右子树，对每颗子树同样按这三步（先根、后左、再右）进行。
2. 中序遍历LDR：首先遍历根的左子树，其次访问根结点，最后遍历根右子树，对每颗子树同样按这三步（先左、后根、再右）进行。
3. 后序遍历LRD：首先遍历根的左子树，其次遍历根的右子树，最后访问根结点，对每颗子树同样按这三步（先左、后右、最后根）进行。

3.遍历算法

①先序遍历（递归算法）

步骤：
若二叉树为空，执行空操作；
否则：

1. 访问根结点；
2. 先序遍历左子树；
3. 先序遍历右子树。

---

算法：

void preOrder(Bintree bt) {
	// 先序遍历以bt为根的二叉树
	if (bt != NULL) {
		visit(bt); // 访问根结点
		preOrder(bt -> Lchild);
		preOrder(bt -> Rchild);
	}
}
1
2
3
4
5
6
7
8

---

②中序遍历运算（递归算法）

步骤：
若二叉树为空，执行空操作；
否则：

1. 中序遍历左子树；
2. 访问根结点；
3. 中序遍历右子树。

---

算法：

void inOrder(Bintree bt) {
	// 中序遍历以bt为根的二叉树
	if (bt != NULL) {
		inOrder(bt -> Lchild);
		visit(bt); // 访问根结点
		inOrder(bt -> Rchild);
	}
}
1
2
3
4
5
6
7
8

---

③后序遍历运算（递归算法）

步骤：
若二叉树为空，执行空操作；
否则：

1. 后序遍历根的左子树；
2. 后序遍历根的右子树。
3. 访问根结点；

---

算法：

void postOrder(Bintree bt) {
	// 中序遍历以bt为根的二叉树
	if (bt != NULL) {
		postOrder(bt -> Lchild);
		postOrder(bt -> Rchild);
		visit(bt); // 访问根结点
	}
}
1
2
3
4
5
6
7
8

---

对于如下图的二叉树，其先序、中序、后序遍历的序列为：

先序遍历：ABDFGCEH
中序遍历：BFDGACEH
后序遍历：FGDBHECA

④二叉树的层次遍历

二叉树的层次遍历：从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。

上图按照层次遍历，所得到的结点序列为：ABCDEFGH

算法实现：
设立一个队列Q，用于存放结点，以保证二叉树结点按照层次顺序从左往右进入队列。若二叉树bt非空:

1. 将根结点插入队列；
2. 从队列中删除一个结点，访问该结点，并将该结点的孩子（若有的话）插入队列；
3. 若此时队列非空，再从队列中删除一个结点，访问该结点，并将它的孩子结点插入队列。依次重复进行，直到队列为空。

void levelOrder(BinTree bt) {
	LkQue Q;
	InitQueue(&Q);
	if (bt != NULL) {
		EnQueue(&Q, bt);
		while(!EmptyQueue(Q)) {
			p = GetHead(&Q);
			outQueue(&Q);
			visit(p);
			if (p -> Lchild != NULL) {
				EnQueue(&Q, p -> Lchild);
			}
			if (p -> Rchild != NULL) {
				EnQueue(&Q, p -> Rchild);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

⑤小总结

任意一颗二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系都相同。

4.遍历二叉树的应用

注：『遍历』是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作。

如：对于一颗已知二叉树

①求二叉树中结点的个数；

int getAllCount(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	int n = getAllCount(bt -> Lchild);
	int m = getAllCount(bt -> Rchild);
	return m + n + 1;
}
1
2
3
4
5
6
7
8

②求二叉树中叶子结点的个数；

// 求二叉树bt中叶子结点的数目
int leafCount(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	if (bt -> Lchild == NULL && bt -> Rchild == NULL) {
		return 1;
	} else {
		int n = leafCount(bt -> Lchild); // 求左子树的叶子数目
		int m = leafCount(bt -> Rchild); // 求右子树的叶子数目
		return m + n;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

③求二叉树中度为1的结点的个数；

int oneSonCount(BinTree t) {
	// 空二叉树
	if (t == NULL) {
		return 0;
	}
	// 度为1
	if (
		(t -> Lchild == NULL && t -> Rchild != NULL) ||
		(t -> Lchild != NULL && t -> Rchild == NULL)
	) {
		return (oneSonCount(t -> Lchild) + oneSonCount(t -> Rchild) + 1);
	}
	// 度不为1，继续递归
	return (oneSonCount(t -> Lchild) + oneSonCount(t -> Rchild));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

④求二叉树中度为2的结点的个数；

int twoSon(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	if (bt -> Lchild == NULL || bt -> Rchild == NULL) {
		return twoSon(bt ->  Lchild) + twoSon(bt -> Rchild);
	}
	if (bt -> Lchild != NULL && bt -> Rchild != NULL) {
		return twoSon(bt -> Lchild) + twoSon(bt -> Rchild) + 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11

⑤求二叉树中非终端结点的个数；

int notLeafCount(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	if (bt -> Lchild == NULL && bt -> Rchild == NULL) {
		return 0;
	}
	int n = notLeafCount(bt -> Lchild);
	int m = notLeafCount(bt -> Rchild);
	return m + n + 1;
}
1
2
3
4
5
6
7
8
9
10
11

⑥交换结点左右孩子；

⑦判定结点所在层次；

⑧求二叉树中值为特定值结点的个数；

设二叉树存储结构采用二叉链表表示，每个结点的数据域中存放一个整数。
试编写一个算法，求此二叉树上数据域的值为 8 的结点个数

int findValue8Count(BinTree bt) {
	if (bt == NULL) {
		return 0;
	}
	if (bt -> data == 8) {
		return findValue8Count(bt -> Lchild) + findValue8Count(bt -> Rchild) + 1;
	} else {
		return findValue8Count(bt -> Lchild) + findValue8Count(bt -> Rchild);
	}
}
1
2
3
4
5
6
7
8
9
10

五、树和森林

1.树的存储结构（三种）

①双亲表示法

以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含俩个域：数据域和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。

根结点没有双亲，双亲域的值为 -1。双亲链表的类型定义如下：

#define size 10

typedef struct {
	datatype data;
	int parent;
} Node;
Node slist[size];
1
2
3
4
5
6
7

②孩子链表表示法

树中每个结点的孩子串成一单链表：孩子链表
n个结点 – n个孩子链表

n个头指针用顺序表存储 – 表头数组：数组元素存储结点本身的信息和该结点的孩子链表的头指针。

---

孩子链表表示法的类型定义：

#define MAXND 20
typedef struct bnode {
	int child;
	struct bnode *next;
} node, *childlink;

typedef struct {
	datatype data;
	childlink hp;
} Headnode;

Headnode; link[MAXND];
1
2
3
4
5
6
7
8
9
10
11
12

---

双亲孩子表示法
树中每个结点的孩子串成一单链表 – 孩子链表
n个结点 – n个孩子链表
同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。

双亲孩子表示法的类型定义：

# define MAXND 20
typedef struct bnode {
	int child;
	struct bnode *next;
} node, *childlink;
typedef struct {
	DataType data;
	int parent;
	childlink hp;
} headnode;
Headnode; link[MAXND];
1
2
3
4
5
6
7
8
9
10
11

---

③孩子兄弟链表表示法（二叉链表表示）

孩子兄弟链表表示法类型定义：

Typedef struct tnode {
	DataType data;
	struct tnode *son, *brother;
} *Tree;
1
2
3
4

---

2.树、森林与二叉树的关系

①一般树转成二叉树

步骤：
1.各兄弟之间加连线
2.对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝；
3.以根为轴心，将连线顺时针转45°。

如下图：

---

注：一棵树唯一对应一颗二叉树

---

②森林转成二叉树

---

森林转换成二叉树的步骤如下：
1.将每颗树转换成相应的二叉树；
2.将步骤1中得到的各颗二叉树的根节点看作是兄弟结点连接起来。

---

③二叉树还原成一般树

步骤：
1.从根节点起
2.该节点左孩和左孩右树枝上的结点依次作为该结点孩子
3.重复步骤1、2

PS：根无右孩的二叉树可以转变成一般树，否则是森林。

---

④二叉树还原成森林

---

3.树和森林的遍历

①普通树的遍历

1.先序遍历：先访问根节点，然后依次先序遍历根的每颗子树；
2.后序遍历：先依次后序遍历每颗子树，最后访问根结点。
3.层次遍历：按层次逐层访问每个结点。

上图的各种遍历方法的次序如下：
先序遍历次序：ABCDE
后序遍历次序：BDCEA
层次遍历次序：ABCED

PS:
普通树的先序遍历与该树的二叉树状态形式的先序遍历之后的次序是一致的。
普通树的后序遍历与该树的二叉树状态形式的中序遍历之后的次序是一致的。

---

②森林的遍历（注意只有俩种）

1.先序遍历森林：
访问森林中每棵树的根结点；先序遍历森林中第一颗树的根节点的子树组成的森林；先序遍历除去第一颗树之外其余的树组成的森林。

2.中序遍历森林：
中序访问森林中第一颗树的根节点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的树组成的森林。

对上图中森林先序遍历的序列为：
ABCDEFGHJI

对上图中森林中序遍历的序列为：
BCDAFEJHIG

---

六、判定树和哈夫曼树

1.分类与判定数

问题：n个学生成绩a1,a2,…,an(百分制)，现要转换成五分制。
即a1,a2,…,an分五类：
一类： < 60 不及格
二类：[60, 70] 及格
三类：[70, 80] 中等
四类：[80, 90] 良好
五类：>= 90 优秀

每类出现的概率：

若按顺序判，得如下判断过程：

判定树：用于描述分类过程的二叉树，其中：每个非终端结点包含一个条件，对应一次比较；每个终端结点包含一个种类标记，对应于一种分类结果。

以上判断存在的问题：
对n个数分类花费时间较多。 因为大多数元素属于中和良，这样大多数数据都得通过3至4次判断，这样总的判断次数就多。

---

基于如上问题，我们进行改进：

这样判断之后我们总的判断次数是最少的。因为属于中、良的数最多，而检验它们的判断少，因此总的判断次数少。

---

2.哈夫曼树与哈夫曼算法

哈夫曼树是为了构造时间性能最高的判定树。

①路径长度

叶结点带权的二叉树：
一组实数{p1, p2,…,pk} -> 每个叶子{n1,n2,…,nk}
例：pi表示输入最终落入ni的概率
每一个实数称为权

结点ni的带权路径长度：
为结点ni到树根的路径长度（ni的祖先的个数Ii）* 结点ni所带的权（Pi）

比如：

②哈夫曼树

结论：
带权路径长最小的二叉树（哈夫曼树【最优二叉树】）其特征是：权大的叶子离根近，权小的叶子离根远。

③哈夫曼算法

3.哈夫曼编码

①哈夫曼编码

可利用哈夫曼树构造用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示’0’码，指向右子树的分支表示’1’码，取每条路径上的’0’或’1’的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。

②哈夫曼编码的应用

---

---

---

下一篇：数据结构导论【五】之 图