Chapter 5. 树与二叉树

概念

• 堆也是一种完全二叉树。

• 线索二叉树是一种物理结构，直接涉及链表的表示。

• 空树和只有根结点的二叉树的前序、中序、后序遍历序列相同。前序和后序遍历相同的也仅有这二者。

• 可以唯一确定二叉树的遍历序列：

  • 先序遍历和中序遍历
  • 中序遍历和后序遍历
  • 层次遍历和中序遍历

• 无法唯一确定二叉树的遍历序列：

  • 先序遍历和后序遍历
  • 层次遍历和先序遍历

• 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为X的左子树中最右结点。

  是最右结点而不是最右叶结点，如以下情况：

         A
        / \
       B   X      //此时X的前驱应为B而不是C
      /
     C
  

考点

• 设二叉树有 2n 个 结点， 且 m \lt n ，则不可能存在 2m 个度为 1 的结点。

  设度为 2 的结点个数为 x ，则有 2m \times 1 + x \times 2 = 2n - 1 ，等式左侧一定为偶数，右侧一定为奇数，故该等式不可能成立。

• 若度为 m 的哈夫曼树中，叶结点的个数为 n ，则非叶结点的个数为 \lceil \frac {n-1} {m-1} \rceil 。

  度为 m 的哈夫曼树中所有结点的度只有 0 和 m 两种，联立方程 N = N_0+N_m 与 mN_m=N-1 可得 (m-1)N_m=N_0-1 ，得解。

• 若一棵树用孩子兄弟链表示，则空的左指针域的个数等于该树叶子结点的个数。

• 设完全二叉树的结点总数为 n ，则叶子结点的个数为 \lceil \frac n 2 \rceil

• 设一颗完全二叉树的第 n 层有 m 个叶结点，则：

  • 该完全二叉树的结点个数最多时，该树共有 n+1 层，第 n 层的前 2^{n-1}-m 个结点均有两个子结点。
  • 该完全二叉树的结点个数最少时，该树仅有 n 层。

• 若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用后序遍历方法最合适。

  自底向上交换左右子树，最后交换根结点的左右子树，刚好对应后序遍历的过程。

• n 个结点的线索二叉树上含有的线索数为 n+1 。

  勿将线索二叉树与二叉链表弄混。
  除根结点外，每个结点都被一个指针指向： 2n-(n-1) 。

• 一棵树使用孩子链表表示法时，若树度为 k ，则空指针域的个数为 kn-(n-1) 。

• 设 F 是一个森林， B 是由 F 变换得到的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有 n+1 个。

  每个非终端结点的最后一个孩子都没有右兄弟 + F 中最后一棵树的根结点无右孩子。

• 将森林 F 转换为对应的二叉树 T ， 则F 中叶结点的个数等于 T 中左孩子指针为空的结点个数。

  叶结点就是无左孩子。

• 如果一个哈夫曼树高度不超过 5 ，已知其中两个字符的编码为 0 和 10 ，则该哈夫曼树最多还可有 4 个编码结点。

  全部编码在第 5 层以获得最多结点：0 \ \ \ 10 \ \ \ 1100 \ \ \ 1101 \ \ \ 1110 \ \ \ 1111