王道数据结构 | 第五章 树与二叉树【未完成】

summary 第四章

[该章围绕KMP算法开展，从朴素字符串匹配到KMP算法再到next的优化(nextval)。]
学习KMP算法时，应从分析暴力法的弊端入手，思考如何去优化它。实际上，已匹配的相等序列就是模式串的某个前缀，因此每次回溯就相当于模式串与模式串的某个前缀比较，这种频繁的重复比较是效率低的原因。此时，可从分析模式串本身的结构入手，以便得知当匹配到某个字符不等时，应该向后滑动到什么位置，即已匹配相等的前缀和模式串若首尾重合，则对齐它们，对齐部分显然无须再比较，下一步则使直接从主串的当前位置继续进行比较。
4章如果出应用题，把上一章内容中的暴力匹配、next数组和nextval数组代码背熟，按照那个来就可以。

第五章 树与二叉树

树的概念、
二叉树的定义及其主要特征、顺序存储结构和链式存储结构、遍历、线索二叉树的基本概念和构造
树的存储结构、森林和二叉树的转换、树和森林的遍历
哈夫曼树和哈夫曼树编码、并查集及其应用？
这章不太熟的是代码还有一些数量对应（二叉树高度和结点数量），并查集？

• 概念能在做题时对应起来就可
• 性质是用来计算的，大多

文字内容

问答题中的公式推导是记不住的公式，就不记结果直接记忆过程了

问

1. 度为m、具有n个结点的树的最小高度怎么推？
2. 二叉树与度为2的有序树有什么区别?
3. 非空二叉树上的叶节点树等于度为2的结点数加1怎么推？
4. 哪类二叉树适合顺序存储，为什么？
5. 一般二叉树适合顺序存储吗，为什么？

答

1. 为使树的高度最小，在前$h-1$层中，每层的结点数都要达到最大，前$h-1$层中最多有$(m^{h-1}-1)/(m-1)$个结点，前$h$层最多有$(m^h-1)/(m-1)$个结点。因此$(m^{h-1}-1)/(m-1)<n<=(m^h-1)/(m-1)$，即$h-1<lo{g}_m(n(m-1)+1)<=h$，解得$h_{min}=\lceil lo{g}_m(n(m-1)+1)\rceil$ 。
2. 度为2的树最起码有三个结点,但二叉树可以为空； 度为2的有序树的孩子的左右次序是相对另一个孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序，而二叉树无论其孩子是否为2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言的，而是确定的。
3. 设度为0，1和2的结点个数分别为$n_0,n_1,n_2$，结点总数为$n=n_0+n_1+n_2$。二叉树的分支树，除了根节点外，其余结点都有一个分支进入，设 $B$ 为分治总数，则$n=B+1$，而分治树是由度为1或2的结点射出的，因此$B=n_1+2\ast n_2$，联立两式可以知道$n_0=n_2+1$。
4. 二叉树的顺序存储是指用一组连续的存储单元自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组下表为i-1的分量中。
   根据二叉树的性质，完全二叉树和满二叉树适合顺序存储，树中结点的序号可以唯一地反映结点之间的逻辑关系，既能最大可能节省空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
5. 一般二叉树，为了让数组下标能反映二叉树中结点之间的逻辑关系，只能添加一些并不存在的空结点，让其每个结点与完全二叉树上的结点相对照，再存储到一维数组的相应分量中。然而，最坏情况下，一个高度为h且只有h个结点的单支树却需要占据将近$2^h-1$个存储单元，空间利用效率较低。

挖

概念我感觉只要能在做题的时候想起来对应的条件就好，不用一字不差

1. 树是n(n>=0)个结点的【】。当n=0时，称为【】。
2. 在任意一棵非空树中应满足【】。
3. 树作为一种逻辑结构，同时也是一种分层结构，具有两个特点【】、【】。
4. 在树的定义中又用到了其自身，故树的定义是【】的。
5. 树适用于表示具有【】结构的数据，树中的某个结点最多只与【】有直接关系，根节点没有【】，因此n个结点的树中有【】条边。而树中每个结点与其下一层的零个或多个结点，即【】都有直接关系。

6. 考虑K结点，K的祖先是指【】，双亲是【】，有【】的结点称为兄弟，故K的兄弟有【】，而【】的结点互为堂兄弟，K的堂兄弟有【】；考虑D结点，它的子孙有【】，孩子包括【】。
7. 度是指树中一个结点的【】，树中结点的最大度数称为【】，结点B 的度为【】，图中树的度为【】。
8. 分支结点是指【】的结点，又称为非终端结点；叶节点是指【】的结点，它没有【】
9. 结点的层次是从【】 开始定义的，结点L位于【】，结点的深度就是【】，上图中的树的高度为【】，结点的高度为【】，例如图中B的高度为【】。
10. 有序树中结点的各子树【】都是有次序的，不能【】。
11. 同一双亲的两个孩子之间不存在路径，因为【】。
12. 森林是【】的集合。

13. 所有结点的度数加1等于【】。
14. 度为m中的树中第i层上至多有【】个结点。
15. 高度为h的m叉树至多有【】个结点。

16. 二叉树的特点【】，并且其次序【】，所以将其左右子树颠倒，则成为另一棵不同的二叉树。
17. 满二叉树的高度为h则其有【】个结点，可以对满二叉树按次序编号，根节点为1，自上而下，自左至右，对于编号为i的编号，若有双亲，其编号为【】，若有左孩子，其编号为【】，若有右孩子，则其编号为【】。
18. 完全二叉树是指当且仅当其每个结点都与高度为h的满二叉树中【】的结点一一对应的二叉树。
19. 完全二叉树中，若$i<=\lfloor n/2\rfloor$，则结点i为【】，若$i>\lfloor n/2\rfloor$，则为【】，最大分支结点的编号为【】。
20. 完全二叉树中，叶节点只可能在【】层次上出现。
21. 完全二叉树中，树的度为1，则结点数为【】。
22. 完全二叉树中，一旦出现某个结点（编号为i）为叶节点或只有左孩子，则编号大于i的结点【】。
23. 完全二叉树中，结点i所在的层次为【】。
24. 完全二叉树中，具有n个结点，则高度为【】 或 【】。
25. 若n为奇数，则每个分治结点【】；若n为偶数，则编号最大的分支结点（编号为n/2）【】，其余结点【】。
    二叉排序树、平衡二叉树后面复习
26. 树中每个分治结点都有2个孩子，树中的度只有0或2的结点，这样的树为【】。
27. 非空二叉树的第k层最多有【】个结点。
28. 高度为h的二叉树至多有【】个结点。
29. 在含有n个结点的二叉链表中，含有【】个空链域。

空

1. 有限集、空树
2. 有且仅有一个特定的称为根的结点；当n>1时，其余结点可分为m(m>0)个互不相交的有限集$T_1,T_2,\cdot \cdot \cdot ,T_m$，其中每个集合又是一棵树，并成为根的子树。
3. 树的根节点没有前驱，除根节点外的所有结点有且只有一个前驱、树中所有结点都可以有零个或多个后继。
4. 递归
5. 层次、上一层的一个结点即父节点、直接上层节点(父节点)、n-1、子节点
6. 从根A到结点K的唯一路径上的所有其他结点、路径上最接近K的结点E、相同双亲、L、双亲在同一层、M和L、H I J M、H I J
7. 孩子个数、树的度、2、3
8. 度大于0、度为零、孩子结点
9. 根节点、第4层、结点所在的层次、4、该节点为根的子树的高度、2
10. 从左到右、互换
11. 树的分支是有向的，从上至下，从双亲到孩子
12. m(m>=0)棵互不相交的树

13. 结点的个数n
14. $m^{i-1}(i>=1)$
15. $(m^h-1)/(m-1)<=>(1+m^2+m^3+\cdot \cdot \cdot +m^{h-1})$

16. 至多只有两棵子树（度最多为2）、不能颠倒
17. $2^h-1$、$\lfloor i/2\rfloor$、2i、2i+1
18. 编号1~n
19. 分支节点、叶节点、$\lfloor n/2\rfloor$
20. 层次最大的两个
21. 均为叶节点
22. 均有左孩子和右孩子、只有左孩子没有右孩子、左右孩子均有
23. $2^{h-1}<=index<=2^h-1==>h=\lfloor lo{g}_{2}i\rfloor +1$
24. 高度为 $2^{h-1}-1<n<=2^h-1或2^{h-1}<=n<2^h$根据其中闭区间可得$h=\lceil lo{g}_2(n+1)\rceil 或\lfloor lo{g}_2(n)\rfloor +1$【记忆：取对数后如果n大于等于向下取整，否则向上取整】
25. 小于、大于
26. 正则二叉树
27. $2^{k-1}$
28. $1+2+2^2+\cdot \cdot \cdot +2^{(}h-1)=(2^h-1)/(2-1)$
29. n+1

选择（仅错题）

【错误选项】
【思路】
【补充】不一定需要

代码内容

二叉树

链式存储结构

typedef struct BiTNode{ElemType data;struct BiTNode *lchild,*rchild;
}BiTNode , *BiTree;