二叉树笔试题总结
基本性质相关
基本性质
性质1 在二叉树的第$i $层上至多有$2^ $个结点。
性质2 深度为$k $的二叉树至多有$2^k-1 $个结点。
性质3 对任何一棵二叉树$T$，如果其终端结点数为$n_0 $，度为2的结点数为$n_2 $，则$n_0 = n_2 + 1$。
性质4 具有$n$个结点的完全二叉树的深度为$\lfloor log_2n \rfloor + 1$
常考题
完全二叉树的叶子结点数
一棵完全二叉树上有1001个结点，其中叶子结点的个数是？
利用性质3，可以知道
$$
\begin\left{
n_1 & = 1 (结点数为偶数), 0(结点数为奇数）
\endn & = n_0 + n_1 + n_2 \n_0 & = n_2 + 1 \
\right.
$$
对于该题，因为结点数为奇数，因此$n_1 = 0$，所以有$n = 2n_2 + 1$。因此，$n_0 = \frac{(n-0-1)}{2} + 1 = 501$。
二叉树的高/深度
一个具有1025个结点的二叉树的高$h$为？
利用性质4，可以知道若该二叉树最小深度（尽量为“满”的二叉树）为$\lfloor log_2 1025 \rfloor + 1 = 11$，同时也可以每个结点都只有一个孩子，因此也可以为1025，结果为11~1025之间。
树的叶子结点数
在一棵度为4的树T中，如有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是？
$n_0 = 1 \times n_1 + 2 \times n_2 + ... - (n_1 + n_2 + ...)$
因此该题$n_0 = 1\times10 + 2 \times 1 + 3 \times 10 + 4 \times 20 - (20+10+1+10) = 82$
遍历相关
遍历
二叉树的遍历有先序遍历、中序遍历、后序遍历三种。二叉树是递归定义的，因此二叉树的遍历也是递归的。这里的先、中、后是指根的先中后，即先遍历根、中间遍历根、最后遍历根的意思！
先序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则
(1) 访问根结点；
(2) 先序遍历左子树；
(3) 先序遍历右子树。
中序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则
(1) 中序遍历左子树；
- 访问根结点；
(3) 中序遍历右子树。
后序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则
(1) 后序遍历左子树；
(2) 后序遍历右子树；
(3) 访问根结点。
常考题：根据遍历序列确定二叉树
由二叉树的先序序列和中序序列，或由其后序序列和中序序列可以唯一确定一棵二叉树。
由先序序列和中序序列确认二叉树
-
先序序列第一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；
-
递归递归递归。
由后序序列和中序序列确认二叉树
-
后序序列的最后一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；
-
递归递归递归。