数据结构第六章：树和二叉树_c++叶子节点后面加两个节点

数据结构第六章：树和二叉树

---

二叉树

• 二叉树中，度为2的结点数+1=叶结点数：初始叶节点数为1，每增加一个度为1的结点，不改变叶节点数，每增加一个度为2的结点，使叶节点数增加1，因此有上述结论
• 满二叉树和完全二叉树：满二叉树是特殊的完全二叉树，指每一层的结点数都是最大结点数的二叉树；完全二叉树指满二叉树的最后一层没有填满，但是最后一层所有结点按从左到右填，缺的全部在右边，的二叉树。再准确点，将满二叉树每个结点从上到下从左到右排序，则完全二叉树每个结点从1排序到n。
• 因此，完全二叉树的叶节点只会在最后两层出现；并且任一结点的左分支层数等于右分支层数或右分支层数+1.；并且任一编号为 i 的结点，其左孩子编号为 2i，右孩子编号为 2i+1，父亲结点编号为 floor(i/2)
• 二叉树可采取顺序存储结构，用完全二叉树的序号进行存储，但该方法仅适用于完全二叉树或接近完全二叉树的二叉树。
• 可以用二叉链表或三叉链表存储二叉树，二叉链表有三个域：左孩子指针，右孩子指针，数据域；三叉链表比二叉链表多了个父亲指针。
• 树的遍历：先序遍历，中序遍历，后序遍历，即访问根节点、左子树、右子树的先后顺序问题，先序遍历是按根左右的顺序，中序遍历是按左根右的顺序，而后序遍历是按左右根的顺序。以先序遍历为例子，对某个根结点，先访问根结点，然后对其左子树进行先序遍历，然后对其右子树进行先序遍历，基本方法为递归。
• 用二叉树表示表达式，左子树表示第一操作数，右子树表示第二操作数，根节点数据域存放操作符，对二叉树进行先序，中序，后序遍历分别可以获得表达式的前缀表示（波兰式），中缀表示（正常看到的式子），后缀表示（逆波兰式）
• 中序遍历的非递归算法——其一：总是先将左子树进栈，左子树全部退栈或无左子树后再访问自身并退栈，再将右子树进栈，由栈的先进先出可知左子树总是先被访问，右子树总是在本结点访问后访问，因此满足中序遍历的定义。

#include<vector>
using namespace std;
typedef struct BiTNode
{
	ElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
} *BiTree;

void InOrderTraverse(BiTree T, void(* Visit)(ElemType e))
{
	vector<BiTree> stack;
	stack.push_back(T);
	while(stack.size()>0)
	{
		//关键1：左节点依次进栈直至最左叶节点
		while(stack[stack.size()-1] != nullptr)
			stack.push_back(stack[stack.size()-1]->lchild);
		stack.pop_back();//除去栈顶的空指针
		
		if(stack[stack.size()-1] == nullptr)
			continue;
		// 关键2：访问栈顶结点，出栈，将出栈结点的右结点进栈
		Visit(stack[stack.size()-1]->data);
		BiTNode *rchild = stack[stack.size()-1]->rchild;
		stack.pop_back();
		stack.push_back(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

上述算法其实有一个很巧妙的点，它利用空指针来避免了回溯时重复遍历左子树。也就是说，只有在向下遍历时，栈顶指针非空，因此左子树顺利进栈。回溯时栈顶总是有一个空指针，该空指针来自其左子树的最右结点的“空的右子树指针”，因此内层的while循环条件不满足，避免了左子树重复进栈，这其实也是树的非递归遍历的难点之一：如何判断到达当前状态的前一步是回溯还是向下探索，若是向下探索，应当继续向下探索，若是回溯，应该进访问自身同时右子树进栈。

• 刚刚提到了左子树的最右结点的“空的右子树指针”，这其实是另一个重点，也就是说，如果是中序遍历，那么某个结点被访问的时候，它的前一被访问结点和后一被访问结点其实是有规律的，前一被访问结点一定是其左子树（如果有）的最右结点，也就是说，先向左一步，再一直向右直至没有右孩子的那个结点，就是中序遍历中，根节点的前一被访问结点；先向右一步，再一直向左直至没有左孩子的那个结点，就是中序遍历中，根节点的后一被访问结点，也就是右子树（如果有）的最左结点。

---

线索二叉树

• 上述的讨论引出了另一种存储结构的二叉树——线索二叉树：如果将结点再先序或中序或后序遍历中的前驱结点和后继结点也作为结点的第4、5个域，则可以将树状结构整理成线性结构。但这样其实有点浪费，因此实际的线索二叉树还要再精简一点——若结点有左子树，则lchild域指示左子树，否则指示前驱结点；若结点有右子树，则rchild指示右子树，否则指示后继结点；另外增加两个bool 域用于表明是否有左右子树。这就形成了线索链表。对中序的线索链表进行中序遍历仅需对某个结点不停地往其lchild走直至lchild为空，然后这个lchild为空的结点就是中序遍历第一个被访问的结点，接着只需要依次往每个结点的后继结点走，边走边访问即可实现中序遍历，无需栈和递归，空间复杂度较小，时间复杂度也有小的常数。
• 如何在中序线索二叉树中寻找某个结点 n 的前驱结点和后继结点呢：
  • 前驱结点：若没有左子树，则lchild直接指向前驱结点；若有左子树，则前驱节点为左子树的最右结点（该最右结点的 rchild 指向 n）；若 lchild 为空，则没有前驱结点，n 为中序遍历的起点。
  • 后继结点：若无右子树，则rchild直接指向后继结点；若有右子树，则后继结点为右子树的最左结点（该最左结点的 lchild 指向 n）；若 rchild 为空，则没有前驱结点，n 为中序遍历的终点。
• 若后序遍历，后继结点分三种情况：若自身为根节点，则无后继节点；若自身为父结点的右结点，或为父结点的左结点且父结点无右结点，则后继结点为父节点；若为父节点的左结点且父结点有右结点，则后继结点为父结点的右子树后序遍历的第一个第一个结点。
• 为了方便，为线索二叉树添加一个头结点，其lchild指向根结点，rchild指向中序遍历的最后一个结点，并且将中序遍历的第一个结点的lchild指向头结点，将最后一个结点的rchild指向头节点，形成循环链表的结构。
• 对线索二叉树进行中序遍历如下：

typedef struct BiThrNode
{
	ElemType data;
	BiThrNode *lchild;
	BiThrNode *rchild;
	bool LIsLink; // false means lchild point to forward node; true means lchild point to left child node
	bool RIsLink;
} *BiThrTree;

void InOrderTraverse(BiThrTree T, void(* Visit)(ElemType e))
{
	BiThrNode *p = T->lchild;
	while(p != T)
	{
		// 在循环的第一次遍历中，以下代码可以将p指向中序遍历的第一个结点，也就是根节点一直往左走到尽头的那个结点；
		// 在循环的第二次以及后续遍历中，配合循环体最后一句p = p->rchild，可以用于寻找右子树非空的结点的后继结点
		while(p->LIsLink)
			p = p->lchild;
		// 从下面这一句开始，一直重复的是两件事情——访问自己，找到自己的后继结点。后继结点的两种找法：
		Visit(p->data);
		while(!(p->RIsLink))//1. 若无右子树，rchild直接指向后继结点
		{
			p = p->rchild;
			Visit(p->data);
		}
		p = p.rchild;//2. 若有右子树，后继结点为右子树的最左结点，需要配合下一次循环的开头的while语句。
	}
}
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

• 可以看到，其实线索二叉树的中序遍历的代码也挺绕的，主要是由于把找后继结点这件事拆成两部分分别放到了本次循环的末尾和下次循环的开头。也就是说，还是要背几点，第一：如何找第一个结点（最左结点）；第二，如何找后继结点（两种情况，有右子树和没有右子树，而线索链表仅是方便了没有右子树的情况）
• 另，二叉树的线索化其实很鸡肋，还是需要在遍历的过程中进行线索化，所以其实还是需要借助普通的遍历方法先遍历一遍，线索化二叉树，然后才能利用线索化了的二叉树进行方便快捷的遍历。

---

树

二叉树是树的特例，树可以有多个子结点而不必要只有两个，因此树的存储结构不同于二叉树，二叉树只有两个子节点因此可以用 lchild 和 rchild 两个指针形成二叉链表，而树需要特殊的存储结构：

• 树也可以用线性数组表示，每个结点是数组的一个元素，但每个结点附带一个域，表示其父结点的位置索引（根结点可以置该值为-1，若更好地利用可以置该值为树的结点数的相反数），这构成了树的 “双亲表存储表示”（课本把 parent 翻译成双亲，我觉得不是很合理，只有一个父结点，而且parent也不是复数，不能说“双”，但为了不自己造词，还是搬过来了）。这种存储结构方便找到父结点，但找子结点需要遍历整个数组。
• 为了方便找子结点，需要“孩子表示法”，而孩子的数量变化较大，采取链表的方式来表示孩子，具体是这样的：每棵树仍然是用线性数组表示，树的每个结点就是数组的一个元素。每个结点附带一个域为其孩子链表的头指针。因此产生了不同于树结点的第二种类型的结点——“链表结点”，链表结点有两个域，一个为索引，指向数组的某个结点，表示该孩子对应了树的哪个结点，一个为指向链表下一个孩子的指针，表示该孩子还有哪些亲兄弟（也就是具有共同父结点的结点）。具体如下：

typedef struct CTNode // 链表结点的结构体
{
	int child; //该孩子在数组中的索引
	struct CTNode *next; //指向下一个兄弟
} *ChildPtr;

struct CTBox //树结点的结构体
{
	TElemType data; 
	ChildPtr firstchild; //孩子链表头指针
	int parent; //父结点的索引
}

struct CTree //树的结构体
{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r; //结点数和根结点的索引
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 上述代码的CTBox中加入了父结点的索引，方便寻找父结点，形成了“带双亲的孩子链表”结构。
• 树还有"孩子兄弟表示法"，又称“二叉链表表示法”或“二叉树表示法”，其实和上面的孩子链表差不多，将孩子链表做两步变化就可以变成二叉链表表示法：
  1. 将树结点和链表结点结构体合并，也就是说树节点结构体中加入一个域指向下一个兄弟。
  2. 将数组变成链表，这需要将CTree的数组变成指向根结点的指针，然后将所有的索引域变成指针域
• 做了上述两步变换后，树的表示方法变得非常简洁，只需要一种结构体就可以表示出来（和二叉树一样，因此称为二叉树表示法）：

typedef struct CSNode
{
	ElemType data;
	struct CSNode *firstchild, *nextsibling, *parent;
} *CSTree;
1
2
3
4
5

• 同理，为了方便寻找父亲结点，上述代码也是加了parent指针（变成三叉哈哈哈，二叉是不包含parent指针的所以才叫二叉）
• 树有先序遍历和后序遍历，先序遍历即先访问树的根结点，然后先序遍历树的每一个子结点；后序遍历即先后序遍历树的每一个子结点，然后访问树的根结点。
• 森林即是树的集合，树的线性数组表示法也可以用来表示森林，也就是说数组中包含多个根结点。同时基于需要也可以另设一个数组用于记录每个根结点的索引和树的数量。森林比较简单，这里就不再赘述。

---

树与等价关系

• 离散数学对等价关系和等价类的定义是：
  • 如果集合S中的关系R是自反的（xRx，元素与自身是有R关系的）、对称的（若xRy，则yRx）和传递的（若xRy且yRz，则xRz），则称R为S上的一个等价关系。
  • 设R为S上的一个等价关系。对任何 $x\in S$，由 [ x ] R = { y ∣ y ∈ S ∧ x R y } [x]_{R}=\{y|y\in S \wedge xRy \} [x]R​={y∣y∈S∧xRy}给出的集合$[x{]}_R\subseteq S$称为由$x\in S$生成的一个R等价类。
  • 若R是集合S上的一个等价关系，则由这个等价关系可以产生这个集合的唯一划分，划分为的若干个不相交的子集 $S_1,S_2,...,$他们的并即为S，则这些子集 $S_i$ 便称为S 的 R 等价类。
• 现实世界中经常出现这样一类问题，可以归结为按给定的等价关系划分某集合为等价类，通常称这类问题为等价问题。
• 处理等价问题通常是按下列步骤：
  • 另S中的每个元素形成一个只含单个成员的子集$S_i$
  • 重复读入 m 个偶对，对每个读入的偶对判定是否需要合并其所在集合，当m个偶对全部遍历完，则剩下的集合即为S的R等价类。
• 由上可见就数据结构而言，需要三个操作，一个是构造n个子集，每个子集只含单个成员；一个是确定某个元素所属的集合；一个是合并两个集合。
• 可以将上述问题利用树的归并进行实现：每个集合是一棵树，每个集合由树的根结点作为代表；初始化将每个结点初始化为一个根节点，形成n个树构成的森林；集合的合并即为树的合并。为了方便找到根结点，树可以用带双亲双亲表示法来实现。
• 树的合并有许多种方法，适合等价问题归并集合的方法是将待归并两个集合之一的根结点作为另一个集合根结点的子结点，而且最好是成员多的集合的根节点作为父结点，这样可以避免树太深以至于查找根结点遍历次数太多。

---

赫夫曼树

• 路径长度：从树中一个结点到其子结点的路径称为一个分支，从一个结点到另一个结点之间的分支的数量即为两个结点之间的路径长度。从根结点到每一个叶结点的长度之和称为树的路径长度。完全二叉树是路径长度最小的二叉树。
• 带权路径长度：若为每个叶结点定义一个权重，则每个叶结点的带权路径长度为权重乘以根结点到该叶结点的路径长度。树的带权路径长度为所有叶结点的带权路径长度的和，通常记作WPL。带权路径长度最小的二叉树称为最优二叉树或赫夫曼树
• 有些问题可以转化成赫夫曼树的构建问题，比如最佳判定算法的求取：可以将每个判断作为一个结点，将判断结果作为叶结点，将数据从根结点开始进行判断，将给定数据的分布作为叶结点的权重，求得赫夫曼树即可得到最佳判定算法。
• 那么给定 n 个权值，如何构造赫夫曼树呢：
  • 根据给定的 n 个权值 { ω 1 , ω 2 , . . . ω n } \{\omega_1, \omega_2, ...\omega_n\} {ω1​,ω2​,...ωn​}，初始化一个 n 棵二叉树的森林 F，每棵树中只有一个带权为根结点 ${\omega }_i$，其左右子树都为空。
  • 在F中选择根结点权值最小的两棵树作为左右子树，构造一棵新的二叉树，其根结点权值为左右子树根结点权值之和。在森林中删除这两棵树，并将新树加入森林。
  • 重复上一步骤直至森林中剩下一棵树为止，这棵树就是赫夫曼树。

---

赫夫曼编码

• 给定报文中各个字符的出现频次，我们希望为每个字符设计不等长二进制编码，使得报文长度最短。注意如果要设计不等长的编码，必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码被称为前缀编码。
• 为了解决上述问题，我们可以利用赫夫曼树进行编码的设计，这样设计出来的编码称为赫夫曼编码，是使得报文长度最短的前缀编码。
• 首先定义二叉树进行编码的规则，叶子结点表示字符，非叶子节点的左分支表示编码末尾增加一个0，右分支表示编码末尾增加一个1，从根结点到叶子结点的分支的编码按顺序排列起来，就是叶子结点对应字符的二进制编码，如根结点右孩子的左孩子的右孩子的右孩子为叶子结点‘A’，则字符‘A’的二进制编码为1011。
• 假设每种字符在电文中出现的次数为 ${\omega }_i$，其编码长度为 $l_i$，电文中只有 n 种字符，则电文总长为${\sum }_{i=1}^n{\omega }_i{l}_i$。对应到二叉树上，若置 ${\omega }_i$为叶结点的权，$l_i$恰好为根结点到叶子结点的路径长度，则电文总长即二叉树的带权路径长度。因此求使得报文长度最短的前缀编码的问题，转化为求赫夫曼树，这样设计出来的编码即赫夫曼编码。
• 值得注意的是，赫夫曼树种没有度为1的结点，这类书又称为严格的或正则的二叉树，这种树若有n个叶子结点，则一共有2n-1个结点。因此，赫夫曼编码过程中，可以用动态数组的方式存储结点而不必要用链表。给定n个字符，只需要长为2n-1的数组便可以存储赫夫曼树求取过程中的所有结点。只需要为结点结构体设置几个域，分别为：父结点位置索引，左孩子位置索引，右孩子位置索引，结点权重。
• 虽说知道利用赫夫曼树去求赫夫曼编码已经可以写出八九不离十的代码了，但还是有一些技巧的。
  • 首先是可以把n个叶子结点先放在数组的最后n个位置，然后从后往前填入求得的中间结点，直到第一个位置填上根结点。
  • 求得赫夫曼树后，要得出字符的赫夫曼编码，最好是从叶结点开始往回走。数组的从倒数第n个位置开始遍历每个叶结点，对每个叶结点，先利用parent域找到父结点的索引，然后看看自身是父结点的左孩子还是右孩子，慢慢回溯直到根结点，然后将得到的路径倒过来，就得到了每个字符的赫夫曼编码。
  • 译码过程则想法，从根结点开始根据编码值向下走，即可得到编码对应的字符。

---

应用

• 求幂集（某个集合A的所有子集的集合称为集合A的幂集）的过程可以看成是求一棵满二叉树叶结点的过程。对于一个集合A，遍历A中的每个元素，有两种选择——保留或舍弃。由此作为左右分支，产生左右孩子，左孩子为父结点的copy，右孩子为父结点舍弃掉该元素后剩下的集合 。对左右孩子都继续进行分支，n个元素可以产生一颗深度为n+1的满二叉树，满二叉树的叶结点的集合即为A的幂集。

---

树的计数感觉是数学问题，这里就不赘述了