面向考试的树、二叉树和森林

树

树的结点数 $n$ 等于所有结点的度数之和加1

以 $n_i$ 表示度为 $i$ 的结点数量， $n$ 为树的结点数。

$n = 1+n_1+2n_2+3n_3+...+n*n_n=n_0+n_1+...+n_0$
度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点 $(i\ge1)$

第1层至多1个结点（即根结点），第2层至多有 $m$ 个结点，第3层至多有 $m^2$ 个结点。

使用数学归纳法可推出第 $i$ 层至多有 $m^{i-1}$ 个结点
高度为 $h$ 的 $m$ 叉树至多有 $(m^h -1)/(m-1)$ 个结点

在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）。

$1+n_1+2n_2+3n_3=1+2+2+6=11$ ， $n_0+n_1+n_2+n_3 = 11$ ，因此 $n_0=6$ .

思考：若此题推广至求 $n_i$ ，当如何？

例如将上题改为：在一棵度为3的树中，度为0的结点数为6个，度为2的结点数为1个，度为1的结点数为2个，则度为3的结点数（）

$1+n_1+2n_2+3n_3=3n_3+5=n$

$n_0+n_1+n_2+n_3 = 9+n_3=n$ ，联立可得 $n_3 = 2$ 。

非空二叉树上的叶结点数等于度为2的结点数加1，即 $n_0=n_2+1$ 。

非空二叉树的第 $k$ 层最多有 $2^{k-1}个结点(k\ge1)$ 。

高度为 $h$ 的二叉树至多有 $2^h-1$ 个结点 $(h\ge1)$ 。

对完全二叉树按从上到下、从左到右的顺序依次编号1,2,…,n，则有以下关系：

若 $i\le \lfloor \frac n 2\rfloor$ ，则结点 $i$ 为分支结点，否则为叶结点，即最后一个分支结点的编号为 $\lfloor \frac n 2 \rfloor$ 。
叶结点只可能在层次最大的两层上出现
若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子（度为1的分支结点只可能是最后一个分支结点，其结点编号为 $\lfloor \frac n2\rfloor$ ）。
按层序编号后，一旦出现某结点（如结点 $i$ ）为叶结点或只有左孩子的情况，则编号大于 $i$ 的结点均为叶结点（与上述1和3相通）
若 $n$ 为奇数，则每个分支结点都有左、右孩子；若 $n$ 为偶数，则编号最大的分支结点（编号为 $\frac n2$ ）只有左孩子，没有右孩子，其余分支结点都有左、右孩子
当 $i \gt 1$ 时，结点 $i$ 的双亲结点的编号为 $\lfloor \frac i2\rfloor$ 。
若结点 $i$ 有左、右孩子，则左孩子编号为 $2i$ ，右孩子编号为 $2i+1$
结点 $i$ 所在层次（深度）为 $\lfloor\log_2i\rfloor+1$

具有 $n$ 个（ $n\gt 0$ ）结点的完全二叉树的高度为 $\lceil \log_2(n+1)\rceil$ 或 $\lfloor \log_2n\rfloor + 1$

先序序列为a,b,c,d的不同二叉树的个数是：

因为先序序列和中序序列可以唯一地确定一棵二叉树，并且题目已经给出先序序列，因此只要知道由该先序序列可以确定多少个中序序列即可。

两个重要的公式：

二叉树会产生两个问题：

而线索化就是利用浪费的空间去解决效率问题。

线索二叉树是一种物理结构。

将某结点的空指针域指向该结点的前驱后继，规则如下：

这种指向前驱和后继的指针称之为线索，将二叉树按某种次序遍历，并按规则添加线索的过程称之为线索化。

添加标志位，以区分子指针指向孩子或前驱/后继结点，规则如下：