王道408数据结构——第五章树与二叉树

一、树的基本概念

树的定义是递归的，树本身也是一种递归的数据结构。其作为一种逻辑结构，同时也是一种分层结构。树适合表示具有层次结构的数据。
度：一个结点的的孩子个数
树的度：树中结点的最大度数
数中的分支是有向的，即从双亲指向孩子，所以数中的路径只能是从上往下的。同一个双亲的孩子间不存在路径。

树的性质

树中结点等于所有结点的度数之和加1，即总边数+1=度数之和
度为 m 的树中，第 i 层上至多有 $m^{i-1}$ 个结点
高度为 h 的 m 叉树至多有 $\frac{m^h-1}{m-1}$ 个结点
具有 n 个结点的 m 叉树最小高度为 $\lceil \log_m(n(m-1)+1)\rceil$

二、二叉树

二叉树是一种特殊的树形结构，特点是每个结点至多只有两棵子树，但其度可以小于2；并且二叉树的子树有左右之分，即使树中结点只有一棵子树，也要区分其是左子树还是右子树。

满二叉树

高度为h，且含有 $2^{h-1}$ 个结点的二叉树称为满二叉树，即树中每层都有最多的结点。
根结点从1开始编号，若结点编号为 i，其双亲为 $\lfloor i/2\rfloor$ 其左孩子为2i，右孩子为2i+1。

完全二叉树

性质：

若结点编号 $i \leq \lfloor n/2 \rfloor$ ，则结点为分支结点，否则为叶子系结点。
叶子结点只可能在层次最大的两层上出现。最有有一个度为1的结点，且该结点只有左孩子。
若n为奇数，则每个分支结点都有左右孩子

二叉排序树

左子树上所有结点的关键字都小于根结点，右子树上的所有结点关键字都大于根结点。

平衡二叉树

树上任一结点的左右子树深度之差不超过1

二叉树的性质

非空二叉树的叶子结点数等于度为2的结点数+1，即 $n_0=n_2+1$
非空二叉树上第 k 层至多有 $2^{k-1}$ 个结点
高度为 h 的二叉树至多有 $2^h-1$ 个结点
结点数为n的二叉树有 $\frac{(2n)!}{n!(n+1)!}$ 种形态（卡特兰数）

完全二叉树的性质

结点 i 的双亲编号为 $\lfloor \frac{i}{2} \rfloor$ ，即当 i 为偶数时（左孩子），其双亲的编号为 i/2，当i为奇数时，其双亲编号为(i-1)/2。
推论：具有n个结点的完全二叉树，编号最大的分支节点为 $\lfloor \frac{n}{2}\rfloor$
结点 i 所在层次为 $\lceil \log_2[i(2-1)+1]\rceil=\lfloor \log_2i\rfloor+1$

三、二叉树的储存结构

顺序储存

用一组地址连续的存储单元依次自上而下、自左至右储存完全二叉树的结点元素。
对于一般的二叉树，必须添加一些空结点。

链式存储

在含有n个结点的二叉链表中，含有n+1个空链域

四、树的储存方式

双亲表示法

采用一组连续空间来储存每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。根结点的下标为0，其伪指针域为-1。
该存储结构可以很快得到每个结点的双亲位置，但求结点孩子时需要遍历整个结构。

孩子表示法

为每个结点创建一个链表，将该结点的孩子都用单链表接起来。再将所有结点顺序存储在一个数组中，数组中每个元素不但储存结点，还设置一个指针域，指向该结点的孩子链表。n个结点就有n个孩子链表（叶子结点的孩子链表为空表）。
这种方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历所有孩子链表。

孩子兄弟表示法（二叉树表示法）

以二叉链表作为树的存储结构。
二叉树的左指针指向其第一个孩子，右指针指向其下一个兄弟。沿着右指针可以找到所有兄弟结点。
最大优点是可以方便实现树到二叉树的转换，易于找到结点的孩子。缺点是查找双亲结点比较麻烦，可以添加一个parent域指向父结点来解决。

五、二叉树的遍历

先序遍历（preOrder、NLR）

void preOrder(BiTree T){
	if(T != NULL){
		visit(T);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

中序遍历（inOrder、LNR）

void inOrder(BiTree T){
	if(T != NULL){
		inOrder(T->lchild);
		visit(T);
		inOrder(T->rchild);
	}
}

后序遍历（postOrder、LRN）

无论哪种遍历，访问左右子树的顺序都是固定的，只是访问根结点的顺序不同。
每个结点都只访问一次，时间复杂度均为O(n)。
递归工作栈的栈深恰为树的高度。在最坏情况下，n个结点的树高为n，空间复杂度为O(n)。

中序遍历的非递归算法

关键是用栈记录当前结点的祖先

void inOrder(BiTree T){
	initStack(S);
	BiTree p = T;  // 遍历指针
	while( !isEmpty(S) || p ){
		if(p){
			push(S, p);
			p = p-> lchild;  // 一路向左
		}else{  // 无法向左下继续前进，访问子树根结点，进入根结点右子树
			pop(S, p);
			visit(p);
			p = p->rchild;
		}
	}
}

先序遍历的非递归算法

先序遍历和中序遍历的基本思想类似，只需把访问结点操作放在入栈操作前

void inOrder(BiTree T){
	initStack(S);
	BiTree p = T;
	while( !isEmpty(S) || p ){
		if(p){
			visit(p);
			push(S, p);
			p = p-> lchild;
		}else{
			pop(S, p);
			p = p->rchild;
		}
	}
}

后序遍历的非递归算法

沿着根的左孩子，依次入栈，直到左孩子为空。
读栈顶元素：若其右孩子不空且未被访问过，进入右孩子并执行1⃣️；否则元素出栈并访问。需要设定一个辅助指针指向最近访问过的结点，用于区分访问该结点时，其上一个结点是它的左子树还是右子树。

void postOrder(BTree T){
    initStack(S);
    BTree p = T;
    BTree r = NULL;    // 记录访问的上一个结点
    while(p || isEmpty(S)){
        if(p){    //一直走到树的最左边
            push(S, p);
            p = p->lchild;
        }else{
            getTop(S, p);
            if(p->rchild && p->rchild != r){    // 若未访问过右子树，进入
                p = p-> rchild;
            }else{    // 右子树已访问过，访问根结点
                pop(S, p);
                visit(p);
                r = p;    // 记录最近访问的结点
                p = NULL;    // 遍历完该子树，置空
            }
        }     
    } 
}

从栈底结点再加上p结点，刚好构成从根结点到p结点的一条路径。

层次遍历

void leverOrder(BiTree T){
	initQueue(Q);
	BiTree p;
	enQueue(Q, T);
	while( !isEmpty(Q) ){
		deQueue(Q, p);
		visit(p);
		if(p->lchild != NULL)
			enQueue(Q, p->lchild);
		if(p->rchild != NULL)
			enQueue(Q, p->rchild);
	}
}

由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一确定一个二叉树
在先序遍历序列中，第一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列。

由二叉树的后序序列和中序序列可以唯一确定一个二叉树
后序序列的最后一个结点一定是二叉树的根结点。

由二叉树的层次遍历和中序遍历可以唯一确定一个二叉树

六、线索二叉树

增加两个标志域表示指针域是指向左（右）孩子还是指向前驱（后继）。
以这种结点结构构成的二叉链表作为二叉树的存储结构，其中指示结点前驱及后继信息的指针称作线索。加上线索的二叉树称为线索二叉树。
引入线索二叉树能够加快查找结点前驱和后继的速度，像遍历单链表那样方便地遍历二叉树。
线索化的实质就是遍历一次二叉树。

二叉线索化

使用指针pre指向刚刚访问过的结点，p指向正在访问的结点，即pre指向p的前驱。
在遍历的过程中，检查p的左指针是否为空，若为空就将其指向pre；同样的检查pre的右指针。
中序遍历线索化代码如下

void creatInThread(ThreadTree T){
	ThreadTree pre = NULL;
	if(T != NULL){
		inThread(T, pre);
		pre->rchild = NULL;  // 处理遍历的最后一个结点
		pre->rtag = 1;
	}
}

void inThread(ThreadTree &p, ThreadTree &pre){
	if( p!= NULL ){  
		inThread(p->lchild, pre);
		// visit
		if( p->lhild == NULL ){
			p->lhild = pre;
			p->ltag = 1;
		}
		if( pre != NULL && pre->rchild == NULL ){
			pre->rchild = p;
			pre->rtag = 1;
		}
		pre = p;
		inThread(p->rchild, pre);
	}
}

为了方便，可以在二叉树的线索链表上添加一个头结点，令其lchild域指向二叉树的根结点，其rchild域指向中序遍历的最后一个结点，再把中序遍历的第一个结点的lchild域指向头结点。这样就为二叉树建立了一个双向线索链表。

建立先序线索二叉树和后序线索二叉树的代码类似，只需变动线索化改造的代码段以及调用左右子树递归函数的位置。

先序线索化与后序线索化最多有1个空指针域；中序线索化最多有2个空指针域。

遍历线索二叉树

中序线索二叉树的结点隐含了线索二叉树的前驱后继信息，在对其进行遍历时，只要先找到序列中的第一个结点，然后依次找结点的后继即可。
不含头结点的中序线索二叉树遍历算法如下

void inOrder(ThreadTree T){
	ThreadTree p = firstNode(T);  // 获取遍历的起始结点
	while( p != NULL ){
		visit(p);
		p = nextNode(p);  // 获得下一个遍历结点
	}
}

ThreadTree firstNode(ThreadTree p){
	while( p->ltag == 0 ){
		p = p->lchild;
	}
	return p;
}

ThreadTree nextNode(ThreadTree p){
	if( p->rtag == 0)
		return firstNode(p->rchild);  // 返回右子树的最左结点，即下一个要遍历的结点
	else
		return p->rchild;
}

对于先序线索二叉树，如果有左孩子，则左孩子就是其直接后继；如果无左孩子但是有右孩子，则右孩子就是其直接后继；如果是叶结点，其右链域指向了结点的后继。

对于后继线索二叉树，其寻找后继需要知道结点双亲，需采用带标志域的三叉链表作为存储结构。

七、森林

森林是m棵互不相交的树的集合。只需把树的根结点删除就成了森林；反之，只要给m棵独立的树加上一个结点，并把这m棵树作为该结点的子树，则森林就成了树。

树转换为二叉树

二叉树和树都可以用二叉链表作为存储结构，给定一棵树，可以找到唯一一棵二叉树与之对应。

对于一棵树，每个结点左指针指向它的第一个孩子，右指针指向它在树中的相邻右兄弟。
这种规则下，根结点只有左孩子。

森林转换为二叉树

先将森林中的每一棵树转换为二叉树，由于任何一棵树对应的二叉树右子树必空，只需把所有二叉树的根结点用其右指针连接起来即可，即将所有树的根结点视为兄弟结点。

二叉树转换为森林

若二叉树非空，则二叉树根的右子树棵视为其余树形成的二叉树，将其与根断开，以此类推，把所有子树释放。再将每棵二叉树依次转换成树，就得到了原森林。
二叉树转换成树或森林也是唯一的。

树的遍历

先根遍历
若树非空，先访问根结点，再依次遍历根结点的每棵子树。
先根遍历的遍历序列与对应二叉树的先序序列相同
后根遍历（中根遍历）
若树非空，先依次遍历根结点的每棵子树，再访问根结点。
后根遍历的遍历序列与对应二叉树的中序序列相同
层次遍历

森林的遍历

先序遍历森林
若森林非空，按如下规则进行遍历：
- 访问森林中第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历其余树的森林
中序遍历森林
若森林非空，按如下规则进行遍历 ~~（实际上就是依次后根遍历森林中的每一棵树）~~ ：
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历其余树的森林

森林的先序遍历和中序遍历即为对应二叉树的先序和中序遍历。

八、二叉排序树（BST）

对于二叉排序树（二叉查找树），若左子树非空，则左子树的所有结点值均小于根结点的值，且也为一棵二叉排序树；若右子树非空，则右子树的所有结点值均大于根结点的值，且也为一棵二叉排序树。
二叉排序树可以是空树。

对二叉排序树进行中序遍历，可以得到一个有序序列。

BST的插入

按照如下规则递归进行：

若树空，则直接插入结点
若关键字k小于根结点，则插入到左子树
若关键字k大于根结点，则插入到右子树

插入的结点一定是一个新添加的叶结点，且是查找失败时路径上访问的最后一个结点的孩子。
若插入序列是有序的，则会形成一个倾斜的单支树，导致二叉树的性能显著变坏。

BST的删除

分为三种情况进行：

若被删除结点z是叶结点，直接删除
若结点z只有左子树或只有右子树，让z的子树成为z父结点的子树替代z的位置
若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）代替z，再按第一或第二种情况考虑。

BST的查找

从根结点开始，将给定值与根结点关键字比较：

若相等，查找成功
若小于根结点关键字，进入左子树进行查找
若大于根结点关键字，进入右子树进行查找

二叉排序树的查找效率，主要取决于树的高度。若二叉树左右子树高度之差不超过1（平衡二叉树），则平均查找长度为 $O(\log_2n)$ ，若二叉排序树每个结点都只有一个结点，平均查找长度为 $O(n)$ 。

BST与二分查找

从查找过程看，二叉排序树与二分查找十分相似，其平均时间性能差不多；但二分查找的判定树唯一，二叉排序树则不唯一。

从结构的维护角度看，二叉排序树无序移动结点，只需修改指针即可完成插入删除操作，平均执行时间是 $O(\log_2n)$ ；二分查找的对象是有序顺序表，若插入删除结点，所花时间是 $O(n)$ 。

若有序表是静态查找表，宜采用顺序表作为存储结构，采用二分查找进行查找操作。
若有序表是动态查找表，宜采用二叉排序树作为其逻辑结构。

九、平衡二叉树

为避免树的高度增长过快，降低二叉排序树的性能，规定插入和删除二叉树的结点时，保证任意结点的左右子树高度差不超过1。

以 $n_h$ 表示深度为h的平衡树中含有的最少结点数，有递推公式 $n_h=n_{h-1}+n_{h-2}+1$ ，且 $n_0=0$ ， $n_1=1$ 。
含有n个结点的平衡二叉树最大深度为 $O(\log_2n)$ ，平均查找长度也为 $O(\log_2n)$ 。

平衡因子：结点左右子树的高度差，取值范围为-1、0、1。

平衡二叉树的插入

保持二叉树平衡的基本思路：每当插入或删除一个结点，检查该结点到根结点路径上的每个结点的平衡因子，调整不平衡的最小子树的结构，在保持二叉排序树特性的前提下，使之重新平衡。

对于一个新结点，先按照普通二叉排序树的规则进行插入操作，再找到其最小不平衡树，分情况进行调整：

LL平衡旋转（右单旋转）：在结点A的左孩子（L）的左子树（L）上插入了新结点，使A的平衡因子增加为2，导致A为根的子树失去平衡。
进行一次向右的旋转操作：将A的左孩子B向右上旋转，代替A成为根结点；将A结点向右下旋转，成为B的右子树的根结点；而B的原右子树则作为A的左子树。
RR平衡旋转（左单旋转）：在结点A的右孩子（R）的右子树（R）上插入了新结点，使A的平衡因子减少为-2，导致A为根的子树失去平衡。
进行一次向左的旋转操作：将A 的右孩子B向左上旋转，代替A成为根结点；将A结点向左下旋转成为B的左子树的根结点；而B的原左子树则成为A的右子树。
LR平衡旋转（向左后右双旋转）：在A的左孩子（L）的右子树（R）上插入了新结点。
进行两次旋转操作，先左旋转再右旋转：先将A结点的左孩子B的右子树根结点C向左上旋转提升到B结点的位置，此时问题转化为情形1，只需将C结点再向右上旋转提升到A结点的位置。
RL平衡旋转（向右后左双旋转）：在A的右孩子（R）的左子树（L）上插入了新结点。
进行两次旋转操作，先右旋转再左旋转：先将A结点的右孩子B的左子树根节点C向右上旋转提升到B结点的位置，此时问题转化为情景2，只需将C结点再向左上旋转提升到A结点的位置。

十、哈夫曼树

为树中结点赋予一个数值，成为该结点的权。从根结点到任意结点的路径长度 $l$ （经过的边数）与该节点上权值 $w$ 的乘积称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为树的带权路径长度。即 $WPL=\sum_{i=1}^nw_il_i$ 。

在含有n个带权叶结点的二叉树中，WPL最小的二叉树称为哈夫曼树，也称最优二叉树。

构造哈夫曼树

给定n个权值分别为 $w_1,w_2...w_n$ 的结点，构造算法如下：

将n个结点分别作为n棵仅含一个结点的二叉树，构成森林F；
构造一个新结点，从F中选取两棵根节点权值最小的树作为新节点的左右子树，新结点的权值置为左右子树根节点权值之和；
从F中删除刚才选出的两棵树，同时将新得到的树加入F中；
重复步骤2、3，直到F仅剩一棵树。

从构造过程可以看出哈夫曼树具有如下特点：

每个初始结点都称为叶结点，且权值越小的结点到根节点的路径越长。
构造过程新建了n-1个结点，因此哈夫曼树的总结点树为2n-1。
哈夫曼树中不存在度为1的结点。

哈夫曼编码

若允许不同字符用不等长的二进制位表示，称这种编码为可变长度编码。
若任何一个编码都不是其余编码的前缀，则称这种编码为前缀编码。
利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

#408 #数据结构 #考研

王道408数据结构——第五章树与二叉树

https://buttering.github.io/EasyBlog/2021/09/25/王道408数据结构——第五章树与二叉树/

作者

Buttering

发布于

2021年9月25日

许可协议

王道408数据结构——第七章查找上一篇

王道408数据结构——第八章排序下一篇

王道408数据结构——第五章 树与二叉树

一、树的基本概念

树的性质

二、二叉树

满二叉树

完全二叉树

二叉排序树

平衡二叉树

二叉树的性质

完全二叉树的性质

三、二叉树的储存结构

顺序储存

链式存储

四、树的储存方式

双亲表示法

孩子表示法

孩子兄弟表示法（二叉树表示法）

五、二叉树的遍历

先序遍历（preOrder、NLR）

中序遍历（inOrder、LNR）

后序遍历（postOrder、LRN）

中序遍历的非递归算法

先序遍历的非递归算法

后序遍历的非递归算法

层次遍历

由遍历序列构造二叉树

六、线索二叉树

二叉线索化

遍历线索二叉树

七、森林

树转换为二叉树

森林转换为二叉树

二叉树转换为森林

树的遍历

森林的遍历

八、二叉排序树（BST）

BST的插入

BST的删除

BST的查找

BST与二分查找

九、平衡二叉树

平衡二叉树的插入

十、哈夫曼树

构造哈夫曼树

哈夫曼编码

王道408数据结构——第五章树与二叉树