【★★★★★ 树与二叉树总结笔记 2022 9.5】

1. 树的基本概念

1.1 树的定义：

树是n(n>=0)个结点的有限集合；当n等于0时，称为空树；任意的一棵非空树应该满足：
1. 有且仅有一个特定的称为根的结点。(只有一个根)
2. 当n>1时，其余的结点可分为m(m>0)个互不相交的有限集T1、T2、...Tm，期中每个集合本身又是一棵树，并且称为根的子树。(树是一种递归的数据结构，是一种逻辑结构，同时也是一种分层结构)
树具有以下两个特点：
- 树的根没有前驱，除根结点外，所有结点有且只有一个前驱，
- 树中所有结点可以有0个或多个后继。(每层结点最多只和上层父节点有直接关系，根结点没有上层结点，因此树中有n-1条边) 
1
2
3
4
5
6

1.2 基本术语：

如图：
祖先： 以k结点为例；根节点A到K的唯一路径的任意结点，称为k的 “祖先”
双亲： 路径上最接近k结点的E称为k的 “双亲结点”
孩子： k为E的 “孩子结点”
兄弟： k和L有相同的双亲，故L是k的 “兄弟结点”
堂兄弟： 双亲结点在同一层的结点互为堂兄弟 图中G E F H I J 均为堂兄弟
结点的度： 树中一个结点的孩子个数称为 ”结点的度“
树的度” 树中max{结点的度}  上图中结点D的度为3，则”树的度“为3
分支结点： 结点度大于0的结点，又称为非终端结点
叶子结点： 结点的度为0称为叶子结点，又称为终端结点
结点的层次： 结点的层次从树根开始定义，根结点为第一层，它的子结点为第二册，以此类推
结点的深度： 从根结点开始 ”自顶向下“逐层累加
结点的高度： 从叶子结点开始 ”自底向上“逐层累加
树的高度(深度)： 树中结点的最大层数   图中树的高度为4
有序树和无序树： 树中各个子树从左到右是有次序的，不能呼唤称为有序树，反之称为无序树。图上为有序树，若将子结点互换位置，就变成了一棵不同的树
路径和路径长度： 路径长度是路径上所经过的边的个数；  路径：两个结点之间存在一条路径。
森林：森林是m(m>0)棵互不相交的树的集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.3 树的性质

1. 树中的结点数等于所有结点的度数之和+1  (结点数=所有结点度数和+1)
2. 度为m的树中第i层上至多有 m的(i-1)次方 个结点  (i>=1)
3. 高度为h的m叉树至多有(m的h次方-1)/(m-1)个结点
4. 具有n个结点的m叉树最小高度为 向上取整:(logm[n(m-1)+1])  
1
2
3
4

.

做题总结：
5. n个结点 度为m的树， 树的高度最多为 n-m+1
6. 度为m 高度为h的树  结点至少为h-1+m      (有h-1个度为1，最后一层度为m可以画出来)
7. 公式运用 假设度为4的树  n=1+n1+2n2+3n3+4n4=n0+n1+n2+n3+n4
1
2
3
4

2. 二叉树的概念

2.1 二叉树的定义

二叉树是另一种树形结构，特点是每个结点至多只有两颗树，树的度为2.二叉树子数分左右之分，次序不能任意颠倒
二叉树是n(n>=0)个结点的有限集合
1. n=0 为空二叉树
2. 由一个根节点和两个互不相交的被称为根的左子树和右子树组成。  左子树和右子树又分别是一颗二叉树
   二叉树是有序树，左右子数不能颠倒，即使树中只有一颗子树也要分右子树还是左子树
   二叉树有5种基本形态：
-  空二叉树    2.只有根节点  3. 只有左子树   4.只有右子树    5.左右子树都有
二叉树和度为2的有序树的区别
- 度为2的树至少有3个结点，但二叉树可以为空
- 度为2的有序树的孩子左右次序是相对于另一孩子而言的，若某一个结点只有一个孩子不用区分左右，但是二叉树不论孩子数是不是2，都需要区分左右子树； 二叉树结点次序不是相对于另一结点的而是确定的   
1
2
3
4
5
6
7
8
9
10

满二叉树

一棵高度为h，且有2^h-1个结点的二叉树称为满二叉树。树中每层含有最多的结点，满二叉树的叶子结点在最后一层，除叶子结点为其余每个结点均为2；
对满二叉树按层数编号，根为1，自上而下，自左向右，每个结点对应一个编号，若有双亲 双亲为： 2i（向下取整） 若有左孩子：为2i 若有右孩子：为2i+1

完全二叉树

高度为h，有n个结点的二叉树，当且仅当每个结点都与高度h的满二叉树中结点的编号 一 一对应，则称为完全二叉树
有以下性质：

1. 若i<=n/2(向下取整) 则结点i为 分支结点，否则为叶子结点
2. 叶子结点只可能出现在层数最大的两层。对于层数最大的叶子结点，都依次排列在该层的最左侧，即：完全二叉树不会有最后一层有单独的叶子结点为右孩子的情况
3. 若度为1的结点则只可能有一个，且该节点只能有左孩子而无右孩子(★★★非常重要)
4. 按层序编号后，一旦出现某个结点为叶子结点或只有右孩子(假设该结点为i)，则编号大与i的结点均为叶子结点
5. 若n为奇数，则每个分支结点都有左右孩子；若n为偶数，则编号最大的分支结点（编号为n/2），只有左孩子，没有右孩子，其余分支结点左右孩子都有

扩充二叉树

不存在度为1的结点的二叉树称为扩充二叉树，又称为2-树；

二叉排序树

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

平衡二叉树

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

2.2 二叉树的性质

1. 非空二叉树的叶子结点等于度为2的结点+1；n₀=n₂+1
2. 非空二叉树第k层最多有2^k-1个结点
3. 高度为h的二叉树最多有2^h-1个结点
4. 对完全二叉树从上到下从左到右编号1.2…n，i>=1时，结点i的双亲为向下取整i/2，当i为偶数是其双亲为i/2，它是左孩子；i为奇数时，双亲编号为(i-1)/2，它是双亲的右孩子； 结点所在的层次深度为[log2i +]1; 2i<=n时，结点i的左孩子为2i，否则无左孩子；2i+1<=n时，结点i的右孩子编号为2i+1，否则无右孩子；
5. 具有n个结点的完全二叉树高度为 log2(n+1)或者[log2n]+1

2.3 二叉树的存储结构：

顺序存储结构：

1. 二叉树顺序存储指的是：用一组地址连续的存储单元依次自上而下自左至右存储完全二叉树上的结点元素； 完全二叉树和满二叉树采用顺序存储比较合适；(树中的结点序号可以唯一反映结点之间的逻辑结构，好处：节省存储空间，利用下标值确定结点在二叉树中的位置，以及结点之间的关系)
2. 对一般的二叉树，为了让数组下标能反映二叉树中结点的关系，只能添加一些空结点，让与之完全二叉树结点相对应，再存储到一维数组中。 最坏的情况下，一个高度h且只有h个结点的单支树却需要2^h-1存储单元。期中0表示不存在的空结点。
   
   链式存储结构：包括3个域，1个数据域data，两个指针域，左指针lchild，右指针rchild； 含有n个结点的二叉链表中，有n+1个空链域；（线索二叉树就是利用这些空链域的链表结构）
   
   如下：

typedef struct BTBode{
     int data;
     struct BTNode *lchild,*rchild;
}BTNode;
1
2
3
4

做题总结：对于n个结点的二叉树的高度 为(向下取整 [log2n]) +1 ~n，对于完全二叉树是(向下取整 [log2n]) +1；

3. 二叉树的遍历和线索二叉树

二叉树的递归遍历与非递归遍历
层次遍历用队列；
线索二叉树利用n+1个空指针进行快速的查找结点的前驱和后继的速度；
规定若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继结点；还需要增加两个标志域识别指向左右孩子的是前驱还是后继

ltag =0 lchild指向结点的左孩子 rtag=0 rchild指向结点的右孩子
=1 lchild指向结点的前驱 =1 rchild指向结点的后继
结点结构如下：

typedef struct ThreadNode{
      int data;
      struct ThreadNode *lchild,*rchild;
      int ltag,rtag;
}ThreadNode;
1
2
3
4
5

利用线索二叉树可以做的操作：

做题总结：

1. 二叉树的两个结点m和n，m是n的祖先，利用后序遍历可以找到从m到n的路径；
2. 对二叉树结点从1开始编号，要求结点编号大于左右孩子，同一结点的左右孩子中，左孩子小于右孩子，可采用后序遍历
3. 前序为 ABC后序为CBA的二叉树共有：根据卡特兰数Cⁿ_2n/（n+1）=5种，满足要求的只有4种
4. 线索二叉树是一种物理结构
5. 在线索二叉树种不是每个结点都能通过线索找到它的前驱和后继的；（在先序线索二叉树种找到一个结点的先序后继很简单，但是查找先序前驱必须知道该结点的双亲结点； 同样在后序线索二叉树中，找结点的后序前驱也很简单，但是找后序后继也必须知道该结点的双亲结点）
6. 结论：在中序线索二叉树中，若某结点有右孩子，其后继结点是它的右子树的最左下结点；（因为左根右，p这个结点有右孩子，那么它作为根结点的后继的话一定是右子树中第一个被遍历的，所以是右子树的最左下结点）
7. 在中序线索二叉树中，若结点有左孩子，其前驱是它左子树最右下结点（因为左根右，p这个结点有左孩子，那么它作为根节点的前驱的话，一定是左子树中最后一个被访问的，这样根的前驱结点的后继才能是这个根节点p）
8. 线索二叉树中一个有左孩子的结点，X不为根，X的前驱是X的左子树的最右结点（不一定是最右叶子结点）
9. 后序线索二叉树的遍历需要栈的支持（要知道其双亲需要借助栈）
10. 某二叉树前序和后序序列恰好相反，二叉树一定是 高度等于其结点数（说白了这棵树是只有根节点的树）

4. 树、森林

树的存储方式有很多种，既可以采用顺序结构，也可以采用链式结构；

4.1双亲表示法

采用一组连续空间存储每个结点，同时在每个结点增设一个伪指针，指示其双亲结点在数组中的位置，根结点下标为0，伪指针域为-1
这种结构就是利用了每个结点(除根结点以外)只有双亲的性质，可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构；

4.2 孩子表示法

将每个结点的孩子结点都用单链表链接形成一个线性结构，此时n个结点就有n个链表，叶子结点的孩子链表为空表
这种存储方式寻找自诩的操作非常直接，而寻找双亲需要遍历n个结点中孩子链表指针域所指向的n个孩子链表；

4.3 孩子兄弟表示法

孩子兄弟表示法又称为二叉树表示法，孩子兄弟表示法每个结点包括三部分内容：结点值，指向结点第一个孩子结点的指针，以及指向结点下一个兄弟结点的指针；
这种表示法：最大优点是可以方便地实现树转换为二叉树的皂搓，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。

4.4 树、森林、二叉树的转换

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

4.4.1 树转二叉树的规则(左孩子右兄弟)

4.4.2 森林转二叉树

先将森林中的每棵树转换成为二叉树，把森林中第二棵树根视为第一棵树根的右兄弟，第三棵为第二棵根的右兄弟，以此类推；图例：

这里其实只要记住 “左孩子右兄弟“ 这个口诀就行；

4.4.3 树和森林的遍历与二叉树遍历的对应关系

做题总结：

1. 二叉链表存储森林时，根结点的右指针所指的是森林中第二棵树的根节点； 若森林只一棵树 右指针为空； 总之 右指针可以为空也可以不为空；
2. 森林转换成二叉树 使用孩子兄弟表示法，根结点及其左子树为森林中的第一棵树； 剩余的为右子树；
3. 森林转为二叉树，如果森林中有n个非终端结点，则二叉树中有n+1个右指针为空的结点；(说白了就是 有n棵树你转化为之后肯定有n棵独立的右指针为空的树，把除第一棵以外的树连接到第一棵树根的右孩子依次类推第二棵第三棵，这些除了第一棵以外的树连接成的右子数也一定会有一棵右指针为空的结点 故：n+1)

5. 树与二叉树的应用

5.1 哈夫曼树和哈夫曼编码

哈夫曼树的定义：树中的结点被赋一个表示某种意义的数值，称为结点的权。 从树的根到任意结点的路径长度与该结点的权值的乘积称为该该结点的带权路径长度。
树中所有叶子结点的带权路径长度之和称为该树的带权路径长度:
WPL= w_il_i(i从1到n的和)
在含有n个带权叶子结点的二叉树中，期中带权路径长度WPL最小的二叉树称为哈夫曼树，也称为最优二叉树

5.2 哈夫曼的构造

1. 将n个结点分别作为n棵只含有一个结点的二叉树，构成森林F
2. 构造一个新的结点，从F中选取结点权值最小的两个作为新结点的左、右子树，并且将左右子树的权值的和给新结点
3. 从F中删除这两棵树，将新得到的树加入到F
4. 重复步骤2，3，直到F中只有一棵树位置
   哈夫曼树的特点：

• 每个初始结点都为叶子结点，且权值越小结点到根结点的路径长度越大。
• 构造过程中共新建了n-1个结点，均为双分支结点，因此哈夫曼树中的结点总数为2n-1
• 哈夫曼树每次构造结点都选择两棵树作为新的结点的孩子，所以哈夫曼树中不存在度为1的结点。
  构造过程如下：
  

5.3 哈夫曼编码：

每个字符用相等的二进制位表示，称这种编码方式为固定长度编码；若允许对不同字符使用不等长的二进制位表示，则这种编码方式称为 可变长度编码
若没有一个编码是另一个编码的前缀，称这样的编码为 前缀编码。

将每个出现的字符当作一个独立的结点，其权值为它出现的频度或次数，构造出对应的哈夫曼树，所有的字符结点都在叶结点中，用0，1表示其左右孩子，0表示左孩子，1表示右孩子； 矩形数值表示字符及出现的次数

这个哈夫曼树的WPL=145+3(13+12+16)+4*(5+9)=224
此时得到的最终编码二进制编码长度为224位； 若采用3位固定长度编码，则得到的二进制长度为300位。因此哈夫曼编码共压缩了 25%的数据 224/300=0.746，利用哈夫曼树可以设计出总长度最短的二进制前缀编码；

题目总结：

1. 哈夫曼树的总结点为 2n-1； 非叶子结点总数为 n-1 可用公式n₀=n₂+1
2. 不存在度为1的结点；