树

基本概念：

树：是n个（n≥0）个节点的有限集合，n=0时，称为空树

非空树：有且仅有一个根节点

• 特性

  • 没有后继的节点称为：叶子结点

  • 有后继的节点称为：分支节点

  • 除根节点以外，任何一个节点都有且仅有一个前驱

  • 每个节点可以有0个或多个后继

image.png

空树：节点数为0的数

基本术语：

节点之间的关系

• 在非空树中

  1. 有且仅有一个特定的称为根的节点

  2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集合，其中每个结合本身有事一棵树，并且称为根节点的子树

节点、树的属性描述

• 属性：

  1. 节点的层次（深度）：从上往下

  2. 节点的高度：从下往上

  3. 树的高度：总共的层数

  4. 节点的度：有几个孩子

  5. 树的度：各节点度的最大值

有序树、无序树

• 有序树

  逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

• 无序树

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

森林

m（m>0）棵互不相交的数的集合

m=0:空森林

树的性质

1. 节点数=总度数+1

2. 度为m的数、m叉树的区别

   |度为m的数|m叉树|
   |-|-|
   |任意节点的度≤m|任意节点的度≤m|
   |至少有一个节点度=m|允许所有节点的度都<m|
   |一定是非空树，至少有m+1个节点|可以是空树|

3. 度为m的数第i层至多有m^(i-1)个节点

4. 高度为h的m叉树至多有(m^h-1)/(m-1)个节点

5. 高度为h的m叉树至少有h个节点

   高度为h、度为m的数至少有h+m-1个节点

   

   image.png


二叉树

基本概念

二叉树是（n>0）个节点的有限集合

1. 或者为空二叉树，即n = 0。

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

• 注意：

  每个节点至多只有两颗子树

  左右子树不能颠倒

• 二叉树的五种状态

  

  image.png

满二叉树

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

  

  image.png

• 特点

  ①只有最后一层有叶子结点

  ②不存在度为1的结点
  ③按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;结点i的父节点为

  $\lfloor (i/2)\rfloor$

完全二叉树

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

  

  image.png

• 特点

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

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

  3. 按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1;结点i的父节点为

$\lfloor (i/2)\rfloor$

image.png

二叉排序树

image.png

平衡二叉树

• 概念

  树上任一节点的左子树和柚子树的深度之差不超过1

  

  image.png

二叉树常考的性质

1. 设非空二叉树中度为0、1和2的节点个数分别为n0、n1和n2，则n0=n2+1（叶子结点比二叉分支多一个）

   

   n0=n2+1.jpg

2. 二叉树第i层至多有2^(i-1)个节点

   m叉树第i层至多有m^(i-1)个节点

3. 高度为h的m叉树至多有(m^h-1)/(m-1)个节点

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

4. 见图

   

   image.png

   

   image.png

5. 见图

   

   image.png

二叉树的存储结构

顺序存储

二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来

image.png

链式存储

image.png

二叉树的遍历

二叉树的先中后序遍历

image.png

先序遍历

image.png

中序遍历

image.png

后续遍历

image.png

二叉树的层序遍历

一层一层的遍历

image.png

由遍历序列构造二叉树

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

• 由遍历序列构造二叉树

  前序+中序

  后序+中序

  层序+中序

只存在以上的三种情况!!!

其他的情况问什么不行：

image.png

左：                                                   右：

    前序遍历：AB                              前序遍历：AB

    中序遍历：BA                              中序遍历：AB

    后序遍历：BA                              后序遍历：BA

无法确定！

线索二叉树

线索二叉树的作用

找节点的前驱和后继、遍历比较容易

线索二叉树的存储结构

struct ThreadNode{
  int data;
  struct ThreadNode *lchild,*rchild;
  int ltag,rtag;
};

tag==0：表示指针指向孩子

tag==1：表示指针是线索

三种线索二叉树

树的逻辑结构：递归定义的逻辑结构

树的存储结构的表示

• 双亲表示法

  

  image.png

• 孩子表示法

  

  image.png

• 孩子兄弟表示法

  

  image.png

森林与二叉树的转换

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

• 森林转换成二叉树

  

  image.png

• 二叉树转化成森林

  

  image.png

树和森林的遍历

• 树的遍历

  • 1.先根遍历

    

    image.png

  1. 后根遍历

     

     image.png

  2. 层序遍历

• 森林的遍历

  1. 先序遍历

     若森林为非空，则按如下规则进行遍历:访问森林中第一棵树的根结点。
     先序遍历第一棵树中根结点的子树森林。
     先序遍历除去第一棵树之后剩余的树构成的森林。

     

     image.png

  2. 中序遍历

     若森林为非空，则按如下规则进行遍历:
     中序遍历森林中第一棵树的根结点的子树森林。访问第一棵树的根结点。
     中序遍历除去第一棵树之后剩余的树构成的森林。

     

     image.png

哈夫曼树

带权路径长度

1. 节点的权：有某种现实含义的数值（如：表示节点的重要性）

2. 节点的带权路径长度：从数的根到该节点的路径长度（经过的边数）与该节点上权值的乘积

3. 树的带权路径长度：树中所有的叶节点的带权路径长度之和（WPL）

   $WPL=\sum _{i=1}^n{w}_i{l}_i$

   例：

   

   image.png

哈夫曼树的定义

在含有n个带权也节点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称之为最优二叉树

哈夫曼树的构造

给定n个权值分别为W1, W2..., Wn,的结点，构造哈夫曼树的算法描述如下:

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

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

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

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

注意：

1. 每个初始节点最终都成为叶节点，且权值越小的节点到根节点的路径长度越大

2. 哈夫曼树的节点总数为2n-1

3. 哈夫曼树中不存在度唯一的节点

4. 哈夫曼树并不唯一，单WPL必然相同且为最优

哈夫曼树的编码

• 国定长度编码：每个字符用相等长度的二进制位表示

• 可变长度编码：允许对不同的字符用不等长的二进制位表示

• 前缀编码：没有一个编码是另一个编码的前缀

  

  image.png