🔑数据结构_第五章：树与二叉树

第五章、树与二叉树

（一）树的基本概念

1、基本概念

树是n(n>0)个结点的有限集。

当n=0时，称为空树。在任意一棵空树中应满足：

有且仅有一个特定的称为根的结点。
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T₁，T₂，…，T_m，其中每个集合本身又是一棵树，并且称为根的子树。

显然，根的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。

树作为一种逻辑结构，同时又是一种分层结构，具有以下两个特点：

树的根结点没有前驱，其它所有结点有且只有一个前驱。
树中所有结点都可以有0个或多个后继。

树有n个结点，那它就有n-1条边。

2、基本术语

结点之间的关系描述

祖先结点：从“你”出发到根结点的路径上所经过的所有结点都称为“祖先结点”。

子孙结点：“你”后面的所有结点都可称为子孙结点。

双亲结点——即父节点——即直接前驱。

孩子结点——直接后继。

兄弟节点——同一层的结点。

唐兄弟节点——双亲在同一层的结点。
结点、树的属性描述

路径：自上而下的某两个节点之间的所有结点构成的序列，同一双亲的两个孩子之间不存在路径。

路径长度：路径上所经过的边的个数。

结点的层次/深度：从上往下数在第几层。

结点的高度：从下往上数。

树的深度/高度：总共多少层。注：深度默认从1开始算，但不排除有些题目指明从0开始！

结点的度：孩子/分支/直接后继的个数，是个数字。非叶子节点的度>0，叶子节点的度=0。

树的度：各结点的度的最大值MAX{结点A的度，结点B的度，结点C的度，...，结点N的度}。
有序树、无序树
- 有序树：树中结点的各子树从左到右是有次序的，不能互换。
  
  常见有哈夫曼树（俗称最优二叉树）、族谱（不能交换每一层老大老二老三等的位置）等。
- 无序树：树中结点的各子树从左到右是无次序的，可以互换。
总之，需要用结点的左右位置关系来反映某些逻辑关系的话就是有序树，否则为无序树。
森林

森林是m(m≥0)棵互不相交的树的集合。

3、树的常考性质

常见考点一：结点数 = 总度数 + 1。
常见考点二：度为m的树与m叉树的区别。
常见考点三：度为m的树第i层至多有**m^i-1**个结点(i≥1)。

若层数从0开始，则结点数为**mⁱ**个。
常见考点四和五：高度为h的**m叉树**结点个数的上下限问题。

最多：

$$ 最多为：\frac{m^h-1}{m-1} $$ 涉及到的是等比数列求和公式： $$ a+aq+aq^2+...+aq^{n-1} = \frac{a(1-q^n)}{1-q} $$

最少：

有h个结点：
常见考点六：具有n个结点的m叉树的最小高度为：
$$ 前h-1层最多最多结点数 < n \le 前h层最多最多结点数\\ \frac{m^{h-1}-1}{m-1} < n \le \frac{m^h-1}{m-1}\\ m^{h-1}

（二）二叉树的概念

1、基本概念

二叉树是n个结点的有限集合。（n=0时称为空树）

由一个根结点和两个互不相交的被称为跟的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。

特点：

每个结点最多有两棵子树；

左右子树不能颠倒——二叉树是有序树！

二叉树的五种形态：

空树、只有左子树、只有右子树、只有根结点、完整二叉树。

2、几个特殊的二叉树：

（1）满二叉树

高度为h，且含有2^h-1个结点的二叉树
特点：
- 只有最后一层有叶子结点。
- 不存在度为1的结点。
- 按层序从i=1开始编号，结点i的左孩子编号为2i，右孩子为2i+1；结点i的父结点为[i/2]（向下取整）（如果有的话）。

（2）完全二叉树

定义：当且仅当其每个结点都与高度同样为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。
特点：
- 只有最后两层可能有叶子节点。
- 最多只有一个度为1的结点。
- 同上。
- 总结点数为n的完全二叉树中，编号i≤[n/2]（向下取整）的结点为分支节点，i>[n/2]（向下取整）则为叶子节点。
  
  换句话说：一半是分支节点另一半是叶子结点，n为奇数时多出来的一个一定是叶子结点。

（3）二叉排序树

满足以下特点的树称为二叉排序树：

①左子树上所有结点的数据均小于根结点存储的数据；

②右子树上所有结点的数据均大于根结点存储的数据；

③左子树和右子树又各满足以上条件。

（4）平衡二叉树

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

平衡二叉树是为了解决排序二叉树成链状的情况的。

3、二叉树常考性质

常见考点1

设非空二叉树中度为0、1、2的结点的个数分别为n₀、n₁、n₂，则有：
$$
n_0 = n_2 + 1
$$
即——叶子节点总比二分之结点多一个。

常见考点2

二叉树第i层至多有**2^i-1**个结点（i≧1）。

m叉树第m层至多有**m^i-1**个结点（i≧1）。

常见考点3

高度为h的二叉树至多有2^h-1个结点（满二叉树）。

高度为h的m叉树至多有m^h-1/m-1个结点。

完全二叉树的常见考点

常见考点1：

完全二叉树的结点数为n（n>0），那么高度h为[log₂(n+1)](向上取整)或[log₂n]+1(向下取整)。

常见考点2：

对于完全二叉树，可以由总结点数n推出度为0、1、2的结点个数n₀、n₁、n₂。

4、二叉树的存储结构

（1）顺序存储

只适合存储完全二叉树！

用数组存储，每个数组元素就是一个结点：

# include<stdio.h>

#define MAXSIZE 100
struct TreeNode {
    ElemType value;         //节点中的数据元素
    bool isEmpt;            //结点是否为空
};


int main(){
    //初始化数组
    TreeNode t[MAXSIZE];
    for (int i=0; i<MAXSIZE; i++){
        t[i].isEmpt = true;
    }
}

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

判断是否有并找出指定结点i的左孩子、右孩子、父结点、i所在层次。

（2）链式存储

对于非完全二叉树采用链式存储——也称为“二叉链表”。

//二叉树链式存储
//定义数据域
struct ElemType{
    int value;
};
//定义结点
typedef struct BitNode{
    ElemType data;                      //数据域
    struct BitNode *lchild ,*rchild;    //左右孩子指针
}BitNode, *BiTree;

int main(){
    //定义一棵空树
    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;
}

在该类二叉链表中，由某一结点开始寻找子节点很容易，但是寻找父结点就只能循环遍历了。

当然我们还可以给每个结点多附加一个指向父结点的指针使其成为“三叉链表”，不过考研考的是不带父指针的情况。。。（该遍历害得遍历）

对于有n个结点的二叉树，共有2n个指针域，除去根结点外每个结点头上都有一个指针指向它，所以共有n-1个非空指针，那么空指针就有2n-(n-1)=n-1个。

这些空指针域我们可以用来构造线索二叉树。

（三）二叉树的遍历与线索二叉树

1、根据二叉树的递归特性制定遍历规则

二叉树的递归特性：
- 要么是个空二叉树；
- 要么就是由“根结点+左子树+右子树”组成的二叉树。

对于非空二叉树有三种遍历方式：

先序遍历：根左右NLR

void PreOrder(BiTree){
    if(T != NULL){
        visit(T);				//根
        PreOrder(T->lchild);	//递归遍历左子树
        PreOrder(T->rchild);	//递归遍历右子树
    }
}

中序遍历：左根右LNR

void InOrder(BiTree){
    if(T != NULL){
        InOrder(T->lchild);		//递归遍历左子树
        visit(T);				//根
        InOrder(T->child);		//递归遍历右子树
    }
}

后序遍历：左右根LRN

void PostOrder(BiTree){
    if(T != NULL){
        PostOrder(lchild);		//递归遍历左子树
        PostOrder(rchild);		//递归遍历右子树
        visit(T);				//根
    }
}

eg:

这种递归调用的时间复杂度为：O(h)（h为树的高度）。

求树的深度

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;
    }
}

2、二叉树的层序遍历

层序遍历，即按层级从上到下、从左到右依次遍历。

代码实现过程中还需借助一个辅助队列。

//定义二叉树结点
typedef struct BiTree{
    char data;
    struct BiTree *lchild, *rchild;
}BiTree, *BiTree;

//定义链式队列结点
typedef struct LinkNode{
    BiTNode * data;
    struct LinkNode *next;
}LinkNode;
typedef struct{
    LinkNode *front, *rear;//队头队尾
}LinkQueue;

//层序遍历
void LevelOrder(BiTree T){
    LinkQueue Q;						//声明队列Q
    InitQueue(Q);						//初始化Q
    BiTree p;							//声明指针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);		//刚出队结点的右孩子入队
    }
}

3、由遍历序列构造二叉树

不同二叉树可能得出同一个遍历结果（前、后、中、层序遍历都是如此），而由一个遍历序列可以产生不同的二叉树：

因此我们说，不能仅通过前、中、后、层序遍历系列中的某个序列确定一个二叉树。

但如果给出中序遍历加其他任意一个序列的话，我们可以凭这两个序列确定一个唯一的二叉树：

PS：必须有有中序遍历序列！

eg:

总结：

考试考法：给出中序遍历序列和其他一种序列，让我们求二叉树。

4、线索二叉树

（1）概念及原理

我们把那些左右指针为空的结点加以改造利用起来，使其原本为空的指针域指向它遍历顺序的前、后结点，这样子该二叉树要比原来访问起来（找前驱后继）方便很多。

下图为中序遍历方式生成的线索二叉树：

代码层面：

//原来的结点结构
typedef struct BiTree{
    ElemType data;						//数据域
    Struct BiNode *lchild, *rchild;		//左右孩子指针域
}BiNode, *BiTree;

//加以改造
typedef struct ThreadNode{
    //数据域和指针域不变
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    //添加tag标识，用于标记说明该结点的左右指针指向的它的左右孩子结点、还是前驱和后继
    //tag=0，指向左右孩子结点；tag=1，指向前驱后继。
    int ltag = 0, rtag = 0;
}ThreadNode, *ThreadTree;

先序线索二叉树同样如此：

后序线索二叉树同样如此：

总结：

（2）代码实现——二叉树的线索化

①中序线索化

②先序线索化

③后续线索化

（3）在线索二叉树中寻找前驱和后继

中序线索二叉树：

在中序二叉树中找某个结点*p的中序后继next：

①若p->rtag == 1，则next = p->rchild；

②若p->rtag == 0，则遍历寻找后继结点。

同理，找前驱也是如此：

①若p->ltag == 1，则pre = p->lchild；

②若p->ltag == 0，则遍历寻找前驱结点。

先序线索二叉树：

在先序线索二叉树中无法用该方法实现找某个节点的先序前驱！除非能找到其父结点并且：

后序线索二叉树：

同样，在后序线索二叉树中无法用传统方法找某个节点的后序后驱！除非能找到其父结点并且：

（四）树、森林

回顾：树的逻辑结构

1、双亲表示法（顺序存储）

用顺序存储的方式存储每个数据元素，每个结点都有数据域和一个存储父结点位置的”指针“：

//定义节点
typedef struct{
	ElemType data;			//数据域
    int parent;				//父结点位置域
}PTNode;

//定义树
typedef struct{
    PTNode nodes[MAX_TREE_SIZE];	//
    int n;							//树的结点总数
}PTree;

增删改查：
- 增：直接在表的末尾增加结点即可。
- 删：叶子结点随便删，但是非叶子结点就不好删了！
- 改：找到结点即可。
- 查：查某个元素的父结点很容易，但要查子节点就只能遍历了。

2、孩子表示法（顺序+链式）

*讲师没有过多赘述，，，。

3、孩子兄弟表示法（链式）——二叉树与树的转化

最常用！最常考！！！

本质上是二叉链表，不同的是，每个结点的两个指针，一个指向兄弟结点，另一个指向其第一个孩子节点，如下图：

这样存储的结果便是将一棵任意的树转化成了二叉树，实现了二者的转化！

typedef struct CSNode{
    //数据域
    ElemType data;
    //指针域，前者指向第一个孩子，后者指向兄弟
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

4、森林和二叉树之间的转换

同理，森林不过是多个树而已，而多个树的根结点我们又可以看作是同一层的兄弟结点，这样子就可以把整片森林存储为一个二叉树！

森林转化为二叉树：
二叉树转化为森林：

其实本质上还是用二叉链表存储森林。

（五）树、森林的遍历

树的遍历有：
- 先根遍历
- 后根遍历
- 层序遍历
森林的遍历有：
- 先序遍历
- 中序遍历

1、树的先根、后根、层序遍历

树的先根、后根、层序遍历在逻辑上与二叉树的遍历一毛一样！

树的先根遍历的结果序列，与把它转化为二叉树的先序遍历序列结果，是一样的，后根遍历序列又对应中序遍历序列，即：

先根——先序，树后根——二叉树中序，二者属于深度优先遍历。

而层次遍历属于广度优先遍历：

2、森林的遍历

（1）先序遍历

挨个树进行先根遍历，最后依次连起来：

访问森林中第一棵树的根结点；
先序遍历第一棵树中根节点的子树森林；
先序遍历除去第一棵树后剩余的树构成的森林。

或者转化为二叉树进行先序遍历，序列结果一样。

（2）中序遍历

挨个树进行中序遍历，最后依次连起来：

中序遍历森林中第一棵树的根结点的子树森林。
访问第一棵树的根结点。
中序遍历除去第一棵树之后剩余的树构成的森林。

或者转化为二叉树进行中序遍历，序列结果一样。

（六）哈夫曼树

1、哈夫曼树的定义

我们给结点赋予一个新的属性——权值，节点的权是具有某种现实含义的数值（如表示结点的重要性等）。
结点的带权路径长度：从树的根结点到该结点的路径长度（经过的边数）与该结点权值的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和（WPL，Weighted Path Length）。

定义：在含有n个带权结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树、赫夫曼树。

2、哈夫曼树的构造

给定n个不同权值的结点，构造哈夫曼树：

将这些单独的结点看作只有根节点的二叉树，它们构成森林F；
从F中选择两个权值最小的树，作为新的根结点的孩子，构成一个具有新的权值的二叉树；
从F中删除刚才选出的两棵树，同时将新得到的树加入到F中。
重复上述步骤，直到F中只剩一棵树为止。

每个初始给定的结点最终都成为构造的哈夫曼树的叶子结点，且权值越小的结点到根结点的路径长度越大；
哈夫曼树的结点总数为2n - 1；
哈夫曼树中不存在度为1的结点；
哈夫曼树并不唯一，但WPL必然相同且为最优。

3、哈夫曼编码

固定长度编码：每个字符都采用相同长度的二进制位表示。
可变长度编码：允许对不同字符采用不等长的二进制位表示。
在一套可变长度编码中，若任意字符的编码都不是其它任意字符编码的前缀，那么我们称这一套编码为前缀编码。
哈夫曼编码：由哈夫曼树得到——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为叶子结点的权值，由此构造出哈夫曼树。