第5章-树(1)（常规课）

A有3个兄弟，说明B有4个孩子（A和3个兄弟），即B的度为4。

满二叉树的结点数为2^h-1。

一般树和二叉树的遍历顺序不一定一致。

二叉树的深度与结构有关，只有结点数无法确定深度。

树转二叉树时，根结点的右指针为空。

二叉树中至少有一个结点的度为2（除特殊情况外）。

森林的定义
森林是若干棵互不相交的树的集合。
转换步骤
（1）在森林中，每棵树的每个结点，只保留它的第一个孩子（如果有），把这个孩子作为该结点的左孩子。
（2）每个结点的“右兄弟”作为该结点的右孩子。
（3）森林中第一棵树的根作为二叉树的根，后面每棵树的根作为前一棵树根的右孩子。
具体操作
对于森林中的每个结点，
—— 只保留它的第一个孩子，作为左孩子。
—— 其余的兄弟，依次作为前一个兄弟的右孩子。
森林中多棵树的根节点，依次用右孩子指针连接起来。

n个结点的二叉树有n-1条边，因此有n+1个空指针域。

3个结点的不同二叉树种数为5（卡特兰数）。

树的定义中，除根结点外每个结点只有一个双亲，可以有任意多个孩子。

二叉树的高度最小为log2(1025)向上取整=11，最大为1025（单链）。

后序和中序遍历可以唯一确定一棵二叉树。

完全二叉树不一定有度为1的结点。

二叉树可以用顺序存储、链式存储等多种方式表示，不仅限于二叉链表。

树形结构的特点是每个结点只有一个直接前趋（双亲），A说法错误。

二叉排序树（Binary Sort Tree），又称二叉查找树或二叉搜索树，是一种特殊的二叉树结构，其定义基于递归性质：

• ‌左子树‌：若不空，则所有节点值均小于根节点值
• ‌右子树‌：若不空，则所有节点值均大于根节点值
• 
  

二叉排序树最小值结点一定在最左侧，其左指针为空。

二叉排序树（BST）中序遍历的结果就是从小到大的有序序列。

哈夫曼树的权值较大的结点

完全二叉树叶子结点数为(n+1)/2向下取整，(1001+1)/2=501，选E。

完全二叉树最少结点数为2^(h-1)。

哈夫曼树的结点总数为2n-1。

根据前序和中序遍历可唯一确定后序遍历，结果为CBEFDA。

可以用栈等非递归方法实现前序遍历。

树形结构的特点是一个结点可以有多个孩子（一个对多个）。

设度为0的结点数为x，二叉树结点数=度为2+度为1+度为0=10+5+x，二叉树的结点数=度为1的结点数+2*度为2的结点数+1，解得x=11。

一、什么是线索二叉树的“线索”？
        线索：指的是在二叉树的链式存储结构中，原本为NULL（空）的左、右指针，被用来指向该结点在某种遍历（如中序、先序、后序）下的前驱或后继结点的指针。
        这样做的目的是为了方便遍历时能直接找到前驱或后继，提高遍历效率。
二、二叉树的指针域与空指针
        n个结点的二叉树，每个结点有2个指针域（左、右），总共2n个指针域。
        在一棵普通二叉树中，非空指针域的数量等于树的边数，即n-1（因为n个结点连成一棵树有n-1条边）。
        空指针域的数量 = 2n - (n-1) = n+1。
三、线索数的推导
        线索二叉树就是把这些空指针域全部用来存放线索（即前驱或后继的指针）。
        所以，线索的数量 = 空指针域的数量 = n+1。
        公式总结：
        总指针域数：2n
        非空指针域（实际指向孩子）：n-1
        空指针域（可用作线索）：2n - (n-1) = n+1

       在二叉树中，每个结点有2个指针（左、右），n个结点共有2n个指针。其中，非空指针的数量等于树的边数，即n-1（每个结点除根外均有一个父结点，形成n-1条边）。剩余的指针数为2n - (n-1) = n+1，全被用作线索。因此，线索个数为n+1。线索二叉树的线索数为n+1。

前缀编码（Prefix Code）是一种编码方式，满足如下条件：
    > 任意一个码字都不是其他码字的前缀。
    前缀：如果有两个码字A和B，A是B的前缀，意思是B以A开头。例如A=“10”，B=“101”，则A是B的前缀。
    前缀码的好处：解码时不会产生歧义，可以做到“即时译码”，即从左到右扫描编码串，遇到一个合法码字就能立即确定它，不需要回溯。
二、常见的前缀编码
    哈夫曼编码就是一种常用的前缀编码。
    例如：{0, 10, 110, 1111}
    0不是10、110、1111的前缀
    10不是110、1111的前缀
    110不是1111的前缀
    所以这是前缀码
B选项中有前缀关系（10是101的前缀），不是前缀编码。

完全二叉树中，若某结点没有左孩子，则它一定没有右孩子，因此它是叶子结点。

根据后序和中序遍历可以唯一确定前序遍历，具体重建过程可得前序为cedba。

在二叉树中，每个结点有2个指针（左、右），n个结点共有2n个指针。其中，非空指针的数量等于树的边数，即n-1（每个结点除根外均有一个父结点，形成n-1条边）。剩余的指针数为2n - (n-1) = n+1，全被用作线索。因此，线索个数为n+1。

完全二叉树中，编号为i的结点的双亲编号为i/2（向下取整）。49/2=24.5，取整为24。

二叉树第I层最多有2^(I-1)个结点。

完全二叉树的叶结点没有左、右子结点。

度为二的树不一定是二叉树，二叉树要求每个结点最多有两个孩子，且有左右之分。

树转二叉树时，根结点的左子树为空。

线索二叉树的主要目的是加快查找前驱或后继。

前序遍历是先访问结点再访问子女。

无论哪种遍历方式，叶子结点的出现顺序是一样的。

一、什么是二叉树的线索化？
线索二叉树：是对普通二叉树的空指针加以利用，把它们用来存放结点在某种遍历下的前驱或后继结点的指针，这样的指针称为“线索”。
先序线索化：是指在先序遍历的基础上，把所有空的左、右指针分别指向该结点在先序遍历下的前驱和后继。
二、题目条件分析
“左右子树均不空的二叉树”
说明每个结点都有左、右孩子，没有叶子结点（度为0的结点），每个结点的左、右指针都指向实际的孩子结点。
三、空链域的来源
普通二叉树中，空链域（即空指针）一般出现在叶子结点的左、右指针上。
但本题说“左右子树均不空”，所以每个结点的左、右指针都不为空，即没有空链域。
四、线索化后空链域的变化
线索化的本质是：
如果某个结点的左指针为空，则用它指向该结点在遍历序列中的前驱；
如果右指针为空，则用它指向后继。
但本题的树本身没有空指针，所以线索化时也没有需要填充的空链域。
五、特殊情况：头结点的前驱
先序线索化时，根结点的前驱是空的，因为根结点在先序遍历中是第一个访问的结点，没有前驱。
这时，根结点的“前驱线索”指针仍然为空。
六、结论
只有根结点的前驱线索为空，其余结点的左右指针都不为空。
所以，空的链域个数为1。
先序线索化后，只有根结点的前驱为空，空链域为1。

线索化的概念：
在普通二叉树的链式存储结构中，每个结点有两个指针域（左、右），但实际上只有n-1条边（n为结点数），因此有很多指针域是空的。线索化就是利用这些原本为NULL的指针域，存放指向该结点在某种遍历（如中序、前序、后序）下的前驱或后继结点的指针，这样可以方便遍历时直接找到前驱或后继，提高遍历效率。

中序线索化的具体做法：
对于某个结点，如果它的左指针为空，则将其左指针指向中序遍历时的前驱结点；
如果它的右指针为空，则将其右指针指向中序遍历时的后继结点；
通常还会用一个标志位（如ltag、rtag）来区分该指针是线索还是孩子。

举例说明：
比如有一棵二叉树：
 A
/ \
B C
中序遍历顺序是B A C。
B的左指针为空，可以用来指向B的前驱（无），B的右指针为空，可以用来指向B的后继A。
A的左指针指向B（孩子），右指针指向C（孩子）。
C的左指针为空，可以用来指向C的前驱A，右指针为空，可以用来指向C的后继（无）。

题目解析：
“二叉树中序线索化后，不存在空指针域。”这句话是错误的。虽然线索化后大部分原本为NULL的指针被用作线索，但仍然可能存在空指针域，比如整棵树的第一个结点的前驱和最后一个结点的后继，依然没有实际结点可指向，通常仍为NULL。因此，线索化后并不是所有空指针域都被填充，仍然可能存在空指针域。

结论：
中序线索化后，仍然可能存在空指针域，所以题目说“线索化后不存在空指针域”是错误的。

满二叉树的叶子结点都在最后一层。

通常是按层次遍历顺序存储。

二叉树的高度与结构有关，不一定为log2n。

树结构适合表达分支层次关系的数据。

霍夫曼树的结点个数可以是偶数或奇数，具体霍夫曼树的结点总数公式为：
  总结点数 = 2n - 1
其中，n 是叶子结点的个数（即原始权值的个数）。
如果 n 是奇数，2n-1 是奇数。
如果 n 是偶数，2n-1 是奇数。取决于权值个数。

树与二叉树之间有唯一的对应转换方法（孩子-兄弟表示法）。

遍历的本质是将树结构线性化。

哈夫曼树的叶子结点数为(n+1)/2，1999=2*1000-1，所以有1000个字符。

顺序存储时，右孩子下标为2i+1。