数据结构万字总结（超级详细）第五章——树

定义

树是n (n大于等于0）个结点的有限集合，n =0时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足: 1）有且仅有一个特定的称为根的结点。 2）当n> 1时，其余结点可分为m (m>0）个互不相交的有限集合T, .… Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

除了根节点外，任何一个结点都有且仅有一个前驱。

基本概念

空树：不包含任何结点的树

根结点

分支结点：有后继的结点称为“分支结点”(或非终端结点)

叶子结点：沿有后继的结点称为“叶子结点”(或终端结点)

祖先结点、子孙结点、双亲结点、孩子结点、兄弟结点、堂兄弟结点

结点的度：

有几个孩子就是度就为几

树的度：

各结点的度的最大值

路径长度：注意这很重要，和后面的哈弗曼树以及图的带权路径长度有区别。

路径长度的定义：树中每个节点到根节点的唯一路径上的边数定义为该节点的路径长度。所有节点的路径长度加起来就是整棵树的路径长度。

二叉树中的特殊情况：在二叉树中，由于每个节点最多有两个子节点，所以计算路径长度时会考虑这种结构特性。例如，在节点数量相同的条件下，完全二叉树拥有最短的路径长度。

带权路径长度（WPL）：这是对基本路径长度概念的一个扩展，它不仅考虑了路径的长度，还考虑了节点的权值。具体来说，一个节点的带权路径长度是该节点的路径长度乘以它的权值，整棵树的带权路径长度是所有叶节点带权路径长度之和。后面还有图的带权路径长度

有序树和无序树的区别

• 有序树

  从逻辑上看，树重结点的各个子树从左到右是有序的，不能互换

• 无序树

  从逻辑上看，树中结点的各个子树从左至右是无次序的，可以互换

森林

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

树的性质

结点数=总度数+1，总度数即树的边数（最重要一条）

度为m的树、m叉树的区别

度为m的树：

1、至少有一个结点度为m

2、一定是非空树

3、任意结点的度小于等于m

m叉树：

1、允许所有结点的度都小于m

2、可以是空树

3、任意结点的度小于等于m

度为m的树和m叉树第i层至多有m^i-1个结点

高度为h的m叉树至多有(m^h - 1)/(m-1)

高度为h的m叉树至少有h个结点

具有n个结点的m叉树的最小高度为【logm(n(m-1)+1)】

二叉树

性质

1、n0=n1+n2（叶子结点比二分支结点多一个）（最重要的一条）

2、二叉树第i层至多有2^(i-1)个结点，m叉树第i层至多有m^(i-1)个结点

3、高度为h的二叉树至多有2^h-1个结点，高度为h的m叉树至多有m^h-1/(m-1)个结点

4、具有n个节点的完全二叉树的高度h为[log2n]+1（向下取整）或者log2[(n+1)]向上取整

5、完全二叉树最多只有一个度为1的结点

存储结构

• 顺序存储

  i的左孩子为 2i，i的右孩子为 2i+1，i的父结点[i/2]

  • 适合存储完全二叉树

• 链式存储

  • n个结点的二叉链表共有n+1个空链域，注意是二叉链表

遍历

• 先序遍历

  根左右： 技巧：，小人沿着外面那条线一直走，重复的结点跳过

  • 思想

    1、二叉树为空，则什么也不做

  • 2、若二叉树非空：先访问根节点、再先序遍历左子树、最后先序遍历右子树

• 

• 中序遍历

  左根右 技巧：所有节点落下来的顺序就是中序排序

  • 思想

    1、若二叉树为空，则什么也不做

  • 2、若二叉树非空：中序遍历左子树，再访问根结点，最后中序遍历右子树

• 后序遍历

  左右根 技巧：从左下角最左边的结点依次剪枝，直到最后的根节点

  • 思想

    1、若二叉树为空，则什么也不做

  • 2、若二叉树非空，先后序遍历左子树，在后序遍历右子树，最后访问根结点

• 层序遍历

  从上到下，从左到右

• 思想

  1、初始化一个辅助队列

  • 2、根节点入队

  • 3、若队列非空，则队头节点出队，访问该结点，并将其左、右孩子插入队尾

  • 4、重复3直至队列为空

二叉树遍历序列构造二叉树

• 前序+中序遍历序列

• 后序+中序遍历序列

• 层序+中序遍历序列

• 注意：要确定一颗二叉树的形态，必须得有中序遍历

种类

• 满二叉树

  • 一棵高度为h，且含有2^h-1个结点的二叉树

    1、只有最后一层有叶子结点

  • 2、不存在度为1的结点

  • 3、按层从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父节点为i/2（向下取整）

• 完全二叉树

  • 当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应

    1、只有最后两层可能有叶子结点

  • 2、最多只有一个度为1的结点

  • 3、按层从1开始编号，结点i的左孩子为2i，右孩子为2i+1，结点i的父节点为i/2（向下取整）

  • 4、i<=n/2为分支结点，i>n/2为叶子结点（向下取整）

• 二叉排序树

  • 左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树

• 平衡二叉树

  • 树上任一结点的左子树和右子树的深度之差的绝对值不超过1

• 最优二叉树（哈夫曼树）

• WPL最小的树

哈弗曼树

定义

在含有n个带权叶节点的二叉树中，其中带权路径长度最小的二叉树称为哈弗曼树，也叫最优二叉树

概念

• 结点的权

  有某种现实含义的数值

• 结点的带权路径长度

  从树的根到该结点的路径长度（经过的边数)与该结点上权值的乘积

• 树的带权路径长度

  树中所有叶结点的带权路径长度之和

实现

1、将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F

2、构造一个新节点，从F中选取两棵结点权值最小的树作为新节点的左、右子树，并且将新节点的权值置为左、右子树上根结点的权值之和。

3、从F中删除刚才选出的两棵树，同时将新得到的树加入F中

4、重复步骤2和3，直至F中只剩下一棵树为止

注意：构造时，默认结点小的作为左孩子，结点大的作为右孩子（最核心的一条原则）

特点

• 结点总数为2n-1

• 不存在度为1的结点

• 叶子结点比非叶子结点多1

  由于二叉树有公式n0=n2+1，而哈夫曼树又不存在度为1的结点，因此哈夫曼树中，叶子结点比非叶子结点多1。

• 哈弗曼树不唯一，但WPL必然相同且为最优

哈夫曼编码

• 固定长度编码

  每个字符用相等长度的二进制位表示

• 可变长度编码

  允许对不同字符用不等长的二进制位表示

• 前缀编码

  若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码

森林的遍历

先序遍历

效果等同于依次对二叉树的先序遍历 技巧：就是在原本森林上绕最外边那条线走路

中序遍历

效果等同于依次对各个树进行后根遍历，可以理解位就是后跟遍历，只需要在原来的森林依次对各个树进行剪枝即可得到对应的二叉树的中序序列

树的遍历

先根遍历

若树非空，先访问根结点，再依次对每棵子树进行先根遍历

• 特征

  树的先根遍历与这棵树相应的二叉树的先序序列。它可以在原来的书上绕着最外边行走，得到的效果和二叉树一样

后跟遍历

若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点

• 特征

  树的后根遍历序列与这棵树相应的二叉树的中序序列相同。它就是在原来的树上进行剪枝操作，只是它得到的序列对应二叉树的中序序列

层序遍历（又叫广度优先遍历，即从上到下，从左到右）

1、若树非空，则根结点入队

2、若对列非空，队头元素出队并访问，同时将该元素的孩子依次入队

3、重复2直到队列为空

注意：图也有广度优先遍历（广队、深栈），简记：树广队（即树的层序遍历借助了队列这种数据结构）

• 特征：即从上到下，从左到右进行遍历即可

树和二叉树的转换

本质:用二叉链表存储森林—-左孩子右兄弟 森林中各个树的根节点之间视为兄弟关系

树的存储结构

双亲表示法（顺序存储）

每个结点中保存指向双亲的指针，结点中保存父结点在数组中的下标。对比之前学的静态链表，每个结点存了下一个节点的下标

• 优点

  查指定结点的双亲很方便

• 缺点

  查指定结点的孩子只能从头遍历

孩子表示法（顺序+链式存储）

顺序存储各个节点，每个结点中保存孩子链表头指针

• 优点

  找孩子方便

• 缺点

  找父节点不方便

孩子兄弟表示法（链式存储）

• 方便和树进行转化

  把树的一直向右的孩子结点切断，连接到父节点，左孩子不变

• 森林和二叉树的转换

  把所有右兄弟节点切断，连接到左孩子的右子树上

线索二叉树

作用（为什么要引入线索二叉树）

方便一个指定结点出发，找到其前驱、后继，方便遍历

存储结构

在普通二叉树结点的基础上，增加两个标志位ltag和rtag 1、ltag==1，表示lchild指向前驱，ltag==0，表示lchild指向左孩子 2、rtag==1,表示rchild指向后继，rtag==0时，表示rchild指向右孩子

种类

• 中序线索二叉树

• 先序线索二叉树

• 后序线索二叉树

• 总之：你只要知道了三种遍历方法，便自然知道结点的线索指向哪个结点了

中序线索二叉树：

 后序线索二叉树：

先序线索二叉树：