《算法与数据结构考研试题精析》笔记(6) - 树与二叉树
综合TIPS
注意题目的出题对象是谁。是二叉树？还是树？还是完全二叉树？亦或是满二叉树？
不同对象的性质不同，所以要注意。比如说，普通的二叉树层序遍历放到一个数组中，元素之间的索引关系就不可以像完全二叉树中一样有规律。
【错误选项】树的前序遍历序列和中序遍历序列可以推出树的后序遍历序列。
此处描述对象为树，而不是二叉树，故而错误
【例题】n(n>1)个结点的各棵树中，其深度最小的那棵树的深度为(2)，它共有(n-1)个叶子结点和(1)个非叶结点；其中深度最大的那棵树深度为(n)，共有(1)个叶结点和(n-1)个非叶结点。
这里的对象是树而不是二叉树。
【例题】已知完全二叉树的第7层有10个叶子结点，则整个二叉树的结点数最多是(235)。
此题的结点数有两种算法。算法一：
2 ^ 8 - 1 - 2 * 10 = 235；算法二：(2 ^ 7 - 1) + 2 * (2 ^ (7 - 1) - 10) = 235
如果题目没有特别要求，在自己绘制哈夫曼树的时候，每个结点的子结点们按照从左到右从小到大的顺序。(通用习俗？)
注意关键信息。左子树中最右结点？左子树最右叶结点？看清选项！
SKILLS
在选择正确序列的时候，我们可以利用排除法，每一次多得到一些信息就可以排除一些选项，以至于一般来说不需要将整个二叉树构造出来就可选出正确选项，节省了时间。
树
高度、深度与层数：结点的层次从根开始定义，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度(Depth)或高度。
如果没有说明，树根的高度从1开始(树根的高度为1)。
树的存储形式(树在计算机内的表示方法)：双亲表示法、孩子链表表示法、孩子兄弟表示法
注意，顺序存储表示法并不是树的存储形式，应该是二叉树的一种存储形式。
二叉树
- 二叉树不是树的特例。
- 二叉树中不存在度大于2的结点。
- 一棵二叉树的度可以小于2。
前h层的结点总量为
第h层的结点数量为
在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是：设编号为i和j的结点在顺序存储中的下标为s和t，则i与j在同一层的条件为.
任何一棵二叉树的叶子结点在其先序、中序、后序遍历序列中的相对位置肯定不发生变化。
若用一维数组表示一个深度为h的二叉树，则数组的长度至少为.
数组的长度与二叉树的结点个数无关，最短数组长度等于深度为h的满二叉树的结点个数。
若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用何种遍历方法最合适？前序遍历和后序遍历。
唯一确定一棵二叉树的遍历组合：
- 前序遍历和中序遍历
- 中序遍历和后序遍历
- 中序遍历和层次遍历
设m、n为一棵二叉树上的两个结点，在中序遍历，n在m前的条件是(n在m的左方)。
在“n为m的祖先，m在n的右子树分支”的时候也有中序遍历序列中n在m的左方，此时图像上来看，也还是有n在m的左上方，所以总结起来，就是n在m的左方。
结点数相同，二叉树高度最大的情况：每一层都只有一个结点(结点数即为层数)。另一个说法，只有一个叶结点的二叉树。
结点数相同，且只有度数为0和2的结点时，二叉树高度最大的情况：第一层只有根结点，其余层每层的结点数均为2。
结点数相同，二叉树高度最小的情况：完全树。
深度为k具有n个结点的完全二叉树，其编号最小的叶结点序号为。
为何编号最小的叶结点序号与n无关？个人认为上面的答案是错误的。 我自己的答案如下：
高度为K的完全二叉树至少有2^(K-2)个叶子结点。
注意省题，是“叶子结点”的个数。 如何算出？高度为
K且叶结点数最少时，第K层仅有一个叶结点，故而其叶结点个数等于第K-1层的结点个数2^{(K-1)-1} = 2^{K-2}。
若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么结点i没有右孩子的条件为(2*i+1>n)
没有右兄弟的条件又应该是？ 在没有右兄弟时，此时结点i为根结点或者为某一结点的右孩子或者为某一结点的左孩子但是
i==n. 故而条件为i % 2 || (!(i % 2) && i==n)
设一棵完全二叉树叶子结点树为k，最后一层结点数大于2，则该二叉树的高度为。
如果没有最后一层(第h层)，那么前h-1层的叶子个数(就是第h-1层的叶子数)为
2^{(h-1)-1} = 2^{h-2}。 而最后一层结点数大于2，故而log_{2}{k}向上取整必然为h-1（向下取正为h-2）。故而h=。
各种二叉树
【正则二叉树】如果每个分支点的出度恰好等于m，则称该树为m叉正则树。m=2时，该树称为二叉正则树。若其所有树叶层次相同，称为二叉完全正则树。
当结点数量一定时，具有最小深度的二叉树是完全二叉树。
为什么不是满二叉树呢？因为结点数量一定时，不一定可以构成一个满二叉树。
- 平衡二叉树结点的平衡因子(BF)取值只可能为0，1，-1。
- 完全二叉树结点的平衡因子(BF)取值只可能为0，1，-1。
为什么完全二叉树的BF不是0或者1，为什么可以取到-1? 平衡因子更多的是一个绝对值。清华教材上所述为“如果设
BF=左子树高度-右子树高度，则…”。而平衡二叉树的定义是任意结点的左右子树高度差小于等于1。所以可以看出，完全二叉树的BF值是可以取到-1的，即使在完全二叉树中任意结点的左子树高度都大于等于右子树的高度。
线索化二叉树
一棵左子树为空的二叉树在先序线索化后，其中空的链域个数是2。
一棵左右子树均不为空的二叉树在先序线索化后，其中空的链域个数是1。
后序线索树的遍历仍需要栈的支持。
二叉树在线索化后，仍不能有效解决的问题是后序线索二叉树中求后序后继。
任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。
在中序线索二叉树中，每一非空的线索均指向其祖先结点。
祖先结点为后继时右线索指向其祖先结点，祖先结点为前继时左线索指向其祖先结点。
【例题】设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y，y的右子树高度是31，x是y的左孩子。则确定x的后继最多需经过31个中间结点。
为什么最多经过31个中间结点？ 因为x的后继可能在y的右子树的最底下一层，故最多需要经过31个中间结点。（x的后继：y的右子树的左子树的最左下结点，此结点可能为叶结点也可能不是叶结点，但是在经过中间结点最多的情况下，x的后继必为叶结点）
各种遍历
前序遍历和后序遍历结果相同的二叉树为：空树或只有根结点的二叉树
前序遍历和中序遍历结果相同的二叉树为：空树或所有非叶结点只有右子树的二叉树(却左子树的单支二叉树)
中序遍历和后序遍历结果相同的二叉树为：空树或所有非叶结点只有左子树的二叉树(却右子树的单支二叉树)
一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足其中只有一个叶子结点。
某二叉树的前序序列和中序序列正好相反，则该二叉树一定具有如下特征：二叉树为空或者只有一个结点；若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子；若二叉树不为空，则任一结点没有右孩子。
二叉树以后序遍历与前序遍历序列反映同样的信息(他们反映的信息不独立)。
二叉树的对称序列即为中序遍历序列。
树与二叉树的比较
二叉树每个结点位置或者说次序都是固定的，可以是空，但是不可以说它没有位置；而树的结点位置是相对于别的结点来说的，没有别的结点时，它就无所谓左右了，因此二者是不同的。(二叉树特点是每个结点最多只能有两棵子树，且有左右之分)。
因此，空的二叉树就不是树。
树和二叉树的主要差别：
- 树的结点个数至少为1，而二叉树的结点个数可以为0；
- 树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
- 树的结点无左、右之分，而二叉树的结点有左、右之分。
树与二叉树的转换
树中非叶结点个数 + 1 = 对应二叉树中无右孩子的结点
树在转换为二叉树时，非终端结点(非叶结点)的子女中的最右子女结点的右指针为空(即最右子女无右孩子)。另外，森林中各棵树互为兄弟，转换为二叉树时，最右一棵树根结点的右指针为空。故而
树中非叶结点个数 + 1 = 对应二叉树中无右孩子的结点。
类似道理：树用孩子兄弟表示法，每个结点有两个指针域，分别指向“第一个孩子”和“下一个兄弟”。若指向“下一个兄弟”的指针有n个为空，在该树有n-1个非终端结点。
前序遍历森林正好等同于按前序遍历对应的二叉树，后序遍历森林正好等同于按中序遍历对应的二叉树。
树的各种度的结点数量之间的关系
度为i的结点个数为n_i。（n_0为叶结点的数量）
对于完全二叉树而言，度为1的结点数量n_1为0或1。故而，对于完全二叉树而言，只要知道完全二叉树的结点总个数，就可以知道n_1为0或者1(n_0 + n_1必为奇数)，进而知道叶结点和度为2的结点的数量(n_0 = 1 + n_2)。
【例题】用六叉链表表示30个结点的六叉树，则树中共有151个指针。
如何计算？此处的指针还要加上空指针(此处的空指针就相当于叶结点)。 类比，设30个度为6的结点，然后算有多少个叶结点。1+30*(6-1)=151.
带权路径长度
对于k叉树，设m为叶子数，若(m - 1) % (k - 1) != 0，要增加虚结点。虚结点，权值为0，通常处于最下层，且增加个数小于k-1。
国内多数教科书对“带权路径长度”的定义是所有叶子结点的带权路径长度之和，而“外部”结点指不存在的结点。
哈夫曼树
带权路径长WPL最小的二叉树称作最优二叉树或Huffman树。
所以，Huffman树 = 最优二叉树。 Huffman树一定是一棵二叉树。
哈夫曼编码
【例题】一棵Huffman树共有215个结点，对其进行Huffman编码，共能得到(108)个不同的码字。
其实，得到码字的数量其实就是Huffman树中叶结点的数量。而Huffman结点中只有度为0和度为2的点，所以，
(215 + 1) / 2 = 108。
【例题】设Huffman编码的长度不超过4，若已对两个字符编码为1和01，则还可以对(4)个字符编码。
前两位必须为00，后面两位的情况为2*2=4种。现举例如下，0000，0001.0010，0011。
Huffman编码中，任何两个字符的编码都不会相同，即使两字符出现的频率一样也是如此。
树的计数
给定一个序列(先序、中序或者后序)，求不同的二叉树的个数。公式为
为何种序列无关，只要把结点的树状结构列出来，然后按照某种规律往里面填元素就可以了。
由3个结点可以构成多少个不同的有向树？ 答案：2. 而不是5