基本性质相关

基本性质

性质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) 中序遍历左子树；

2. 访问根结点；

(3) 中序遍历右子树。

后序遍历二叉树的操作定义如下：

若二叉树为空，则空操作；否则

(1) 后序遍历左子树；

(2) 后序遍历右子树；

(3) 访问根结点。

常考题：根据遍历序列确定二叉树

由二叉树的先序序列和中序序列，或由其后序序列和中序序列可以唯一确定一棵二叉树。

由先序序列和中序序列确认二叉树

1. 先序序列第一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；

2. 递归递归递归。

由后序序列和中序序列确认二叉树

1. 后序序列的最后一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；

2. 递归递归递归。