[数据结构与算法]考研数据结构手记(六)-树和二叉树

6.1 树

6.1.1 树的定义

树的空树和非空树的定义：
非空树:
有且仅有一个根节点；
没有后继的结点称为“叶子结点”（或终端结点)；
有后继的结点称为“分支结点”（或非终端结点)。
空树：结点数为0的树。
对于树来说，除了根节点外，任何一个结点都有且仅有一个前驱。
树的数学化定义：
树是n(n≥0)个结点的有限集合，n=0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足:
1.有且仅有一个特定的称为根的结点。
2.当n>1时，其余结点可分为m (m>0)个互不相交的有限集合T₁,T₂,.…,T_m，其中每个集合本身又是一棵树，并且称为根结点的子树。

6.1.2 树的相关概念

结点的层次(深度):从上往下数
结点的高度:从下往上数
树的高度(深度):总共多少层
结点的度:有几个孩子(分支)
树的度:各结点的度的最大值
有序树:逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树:逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
森林:森林是m (m≥0) 棵互不相交的树的集合
m为0时的森林称为空森林

6.1.3 树的性质

1.结点数=总度数+1.
2.度为m的树和m叉树的区别：

3.度为m的树第i层至多有m^i-1个结点(i≥1)
m叉树第i层至多有m^i-1个结点(i≥1)
4.高度为h的m叉树至多有m^h-1/m-1个结点
5.高度为h的m叉树至少有h个结点；
高度为h，度为m的树至少有h+m-1个结点。

6.具有n个结点的m叉树的最小高度为[log_m(n(m-1)+1) ]

6.1.4 树的存储结构

6.1.4.1 双亲表示法(顺序存储)

双亲表示法的优点：查指定结点的双亲很方便
双亲表示法的缺点：查指定结点的孩子需要从头遍历
所以可以采用孩子表示法。

6.1.4.2 孩子表示法(顺序+链序存储)

这种方法就是顺序存储各个节点，每个结点中保存孩子链表头指针。

6.1.4.3 孩子兄弟表示法(链式存储)

优点：可以利用二叉树来处理树

6.1.5 森林和二叉树的转换

各个树的根节点视为兄弟关系，按照兄弟孩子表示法进行存储。

6.1.6 树和森林的遍历

6.1.6.1 树的遍历

先根遍历
若树非空，先访问根结点，然后再依次对各个子树进行先序遍历。
先根遍历是深度优先遍历

//树的先根遍历
void Pre0rder(TreeNode *R){
	if (R!=NULL){
		visit(R);//访问根节点
		while(R还有下一个子树T)
			Pre0rder(T);//先根遍历下一棵子树
	}
}

树的先根遍历序列与这棵树相应二叉树的先序遍历序列相同。
后根遍历
若树非空，先依次对各个子树进行后序遍历，最后再访问根结点。
后根遍历是深度优先遍历

//树的后根遍历
void Post0rder(TreeNode *R){
	if (R!=NULL){
		while(R还有下一个子树T)
			Post0rder(T);//后根遍历下一棵子树
		visit(R);//访问根节点
	}
}

树的后根遍历序列与这棵树相应二叉树的后序遍历序列相同。
层次遍历
层次遍历是广度优先遍历
层次遍历用队列实现
①若树非空，则根节点入队
②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
③重复②直到队列为空

6.1.6.2 森林的层次遍历

先序遍历森林
若森林为非空，则按如下规则进行遍历：
①访问森林中第一棵树的根结点。
②先序遍历第一棵树中根结点的子树森林。
③先序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行先根遍历
中序遍历森林
若森林为非空，则按如下规则进行遍历：
①中序遍历森林中第一棵树的根结点的子树森林。
②访问第一棵树的根结点。
③中序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行后根遍历

6.2 二叉树

6.2.1 二叉树的基本概念

6.2.1.1 二叉树的定义

二叉树是有n(n≥0)个结点的有限集合：
①或者是空二叉树，n=0；
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
每个结点至多有两个子树，左右子树不可以颠倒。

6.2.1.2 满二叉树

满二叉树就是指高度为h，节点数为2^h-1的二叉树。
满二叉树的特点：
①只有最后一层有叶子结点；
②不存在度数为1的结点。

6.2.1.3 完全二叉树

完全二叉树就是在满二叉树的基础上删除一些最后一层的编号更大的结点。但和完全二叉树的结点编号是保持一致的。
完全二叉树的特点：
①只有最后两层会有叶子结点；
②最多存在一个度为1的结点。
如果某个结点只有一个孩子结点，那么一定是左孩子，不可能是右孩子。

6.2.1.4 二叉排序树

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

6.2.1.5 平衡二叉树

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

6.2.2 二叉树的性质

①设非空二叉树中度为0、1和2的结点个数分别为n₀,n₁,n₂,则n₀=n₂+1；
①n=n₀+n₁+n₂
②(节点数等于总度数+1)n=n₁+2n₂+1
②-①
②二叉树的第i层至多有2^n-1个结点；
③高度为h的二叉树至多有2^h-1个结点；
④具有n个(n>0)结点的完全二叉树的高度h为log₂(n+1)或log₂n+ 1
⑤完全二叉树最多只有一个度为1的结点，即
n₁=0或1
n₀=n₂+1可以推出n₀+n₂一定是奇数
若完全二叉树有2k个(偶数)个结点，则必有：n₁=1,n₀= k,n₂= k-1
若完全二叉树有2k-1个(奇数)个结点，则必有：n₁=0，
n₀=k, n₂= k-1

6.2.3 二叉树的存储结构

6.2.3.1 顺序存储

#define MaxSize 100
struct TreeNode {
	ElemType value;//结点中的数据元素
	bool isEmpty;//结点是否为空
};
TreeNode t[MaxSize];
for (int 1=0; i<MaxSize; 1++){
	t[i]. isEmpty=true;
}//初始化所有节点标记为空

定义一个长度为MaxSize的数组t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。

几个重要常考的基本操作:

i的左孩子：2i
i的右孩子：2i+1
i的父节点：i/2
i所在的层次：log₂(n+1)或[log₂n]+1

若完全二叉树中共有n个结点,则：

判断i是否有左孩子就是判断2i是否≤n，
判断i是否有右孩子需要判断2i+1是否≤n，
判断i是否是叶子/分支结点需要判断i是否>[n/2]

二叉树的顺序存储一定要把二叉树的结点编号和完全二叉树对应起来。
顺序存储最坏情况:高度为h且只有h个结点的单支树(所有结点只有右孩子)，也至少需要2^h-1个存储单元
结论:二叉树的顺序存储结构，只适合存储完全二叉树

6.2.3.2 链式存储

//二叉树的结点(链式存储)
typedef struct BiTNode{
	ElemType data;//数据域
	struct BiTNode *lchild, *rchild;//左、右孩子指针
}BiTNode , *BiTree;

n个结点的二叉链表共有n+1个空链域。

struct ElemType{
	int value;
};
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
	struct BiTNode *parent；
}BiTNode, *BiTree;//定义一棵空树
BiTree root = NULL;//插入根节点
root = (BiTree) malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;
//插入新结点
BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root-> lchild = p;
//作为根节点的左孩子

6.2.4 二叉树的遍历

6.2.4.1 先中后序遍历

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

先序遍历：ABDECFG
中序遍历：DBEAFCG
后序遍历：DEBFGCA

先序遍历：ABDGECF
中序遍历：DGBEAFC
后序遍历：GDEBFCA
先序过程的操作方法如下：

1.若二叉树为空，则什么也不做
2.若二叉树非空
①访问根节点
②先序遍历左子树
③先序遍历右子树
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;
void Pre0rder(BiTree T){
	if(T!=NULL){
		visit(T);//访问根结点
		Pre0rder(T->lchild);//递归遍历左子树
		Pre0rder(T->rchild);//递归遍历右子树
	}
)

中序遍历和后序遍历则需牢记规则即可。

例题：求树的深度

int treeDepth(BiTree T){
	if (T ==NULL) {
		return 0;
	}
	else {
		int l=treeDepth(T->lchild);
		int r=treeDepth(T->rchild);
		//树的深度=Max(左子树深度，右子树深度)+1
		return l>r ? l+1 : r+1;
	}
}

6.2.4.2 层次遍历

算法思想:
①初始化一个辅助队列
②根结点入队
③若队列非空，则队头结点出队，访问该结点,并将其左右孩子插入队尾（如果有的话)
④重复③直至队列为空

实现代码：

void Leve l0rder(BiTree T){
	LinkQueue Q;
	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);//右孩子入队
	}
}

6.2.4.3 利用遍历序列构造二叉树

若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树。

前序+中序

例题

前序遍历序列: DAEFBCHGI
中序遍历序列: EAFDHCBGI

后序+中序

层序+中序

6.2.5 线索二叉树

6.2.5.1 作用

就是用来记录各个结点的被访问的前驱和后继的关系。

6.2.5.2 存储结构

//二叉树的结点（链式存储)
typedef struct BiTNode{
	ElemType data;
	struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;
//线索二叉树结点
typedef struct ThreadNode{
	ElemType data;
	struct ThreadNode *lchild,*rchild;
	int ltag,rtag;//左、右线索标志
}ThreadNode,*ThreadTree;

tag = 0,表示指针指向孩子结点；
tag = 1,表示指针是“线索”。

6.2.5.3 三种线索二叉树的比较

中序线索二叉树：线索指向中序前驱，中序后继
先序线索二叉树：线索指向先序前驱，先序后继
后序线索二叉树：线索指向后序前驱，后序后继

6.2.6 二叉排序树

二叉排序树，又称二叉查找树(BST，Binary Search Tree)
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉
树:
①左子树上所有结点的关键字均小于根结点的关键字；
②右子树上所有结点的关键字均大于根结点的关键字；
③左子树和右子树又各是一棵二叉排序树。

6.2.6.1 查找

若树非空，目标值与根结点的值比较：
若相等，则查找成功；
若小于根结点，则在左子树上查找，否则在右子树上查找。查找成功，返回结点指针；查找失败返回NULL。

//在二叉排序树中查找值为key的结点,最坏空间复杂度0(1)
BSTNode *BST_Search(BSTree T,int key){
	while(T!=NULL&&key!=T->key){ 
	//若树空或等于根结点值， 则结束循环
		if(key<T->key) 
			T=T->lchild;
			//小于，则在左子树上查找
		else 
			T=T->rchild;
			//大于，则在右子树上查找
	}
	return T;
}
//在二叉排序树中查找值为key的结点(递归实现)
//最坏空间复杂度0(h)
BSTNode *BSTSearch(BSTree T,int key){
	if (T==NULL)
		return NULL; //查找失败
	if (key==T->key)
		return T;//查找成功
	else if (key < T->key)
		return BSTSearch(T->lchild, key); 
		//在左子树中找
	else
		return BSTSearch(T->rchild, key); 
		//在右子树中找

6.2.6.2 插入

//在二叉排序树插入关键字为k的新结点(递归实现)
//最坏空间复杂度0(h)
int BST_Insert(BSTree&T, int k){
	if(T==NULL){//原树为空， 新插入的结点为根结点
		T=(BSTree)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=T->rchild=NULL;
		return 1;//返回1,插入成功
	}
	else if(k==T->key)//树中存在相同关键字的结点，插入失败
		return 0;
	else if(k<T->key)//插入到T的左子树
		return BST_Insert(T->lchild,k);
	else//插入到T的右子树
		return BST_Insert(T->rchild,k);
}

6.2.6.3 删除

先搜索找到目标结点:
①若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
③若结点z有左、右两棵子树，则令z的直接后继(或直接前驱)替代z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。

6.2.6.4 查找效率分析

若树高h，找到最下层的一个结点需要对比h次；
最好情况:
平均查找长度= O(log₂n)
查找长度是指在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
最坏情况:每个结点只有一个分支，树高h=结点数n，平均查找长度=O(n)；

6.2.7 平衡二叉树

平衡二叉树( Balanced BinaryTree)，简称平衡树(AVL树)，树上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子=左子树高-右子树高。

6.2.7.1 调整最小不平衡子树

LL平衡旋转(右单旋转)

由于在结点A的左孩子(L) 的左子树(L)上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

RR平衡旋转(左单旋转)

由于在结点A的右孩子?的右子树?插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树。

LR平衡旋转(先左后右双旋转)

由于在A的左孩子(L) 的右子树?上插入新结点，A的平衡因
子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。

RL平衡旋转(先右后左双旋转)

由于在A的右孩子?的左子树(L)上插入新结点， A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。

6.2.7.2 查找效率分析

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)。
平衡二叉树上任一结点的左子树和右子树的高度之差不超过1。假设以n_h表示深度为h的平衡树中含有的最少结点数。
则有n₀=0,n₁=1,n₂=2，并且有n_n= n_h-1+ n_h-2+1
可以证明含有n个结点的平衡二叉树的最大深度为O(log2n)，平衡二叉树的平均查找长度为O(log2n).

6.3 哈夫曼树

6.3.1 概念

结点的权：有某种现实含义的数值(如:表示结点的重要性等)
结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点此权值的乘积。

在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称最优二叉树。

6.3.2 构造

给定n个权值分别为w₁, w₂,… w_n,的结点，构造哈夫曼树的算法描述如下:
1)将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
2)构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
3)从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
4)重复步骤2)和3)，直至F中只剩下一棵树为止。
结论：
1)每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2)哈夫曼树的结点总数为2n-1。
3)哈夫曼树中不存在度为1的结点。
4)哈夫曼树并不唯一，但WPL必然相同且为最优。

6.3.3 哈夫曼编码

固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码，有哈夫曼树得到哈夫曼编码—字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前的方法构造哈夫曼树。