二叉树笔试题总结

基本性质相关

基本性质

性质 1 在二叉树的第 层上至多有 个结点。

性质 2 深度为 的二叉树至多有 个结点。

性质 3 对任何一棵二叉树 ，如果其终端结点数为 ，度为 2 的结点数为 ，则 。

性质 4 具有 个结点的完全二叉树的深度为

常考题

完全二叉树的叶子结点数

一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是？

利用性质 3，可以知道

对于该题，因为结点数为奇数，因此 ，所以有 。因此，。

二叉树的高/深度

一个具有 1025 个结点的二叉树的高 为？

利用性质 4，可以知道若该二叉树最小深度（尽量为“满”的二叉树）为 ，同时也可以每个结点都只有一个孩子，因此也可以为 1025，结果为 11~1025 之间。

树的叶子结点数

在一棵度为 4 的树 T 中，如有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1 的结点，则树 T 的叶结点个数是？

因此该题

遍历相关

遍历

二叉树的遍历有先序遍历、中序遍历、后序遍历三种。二叉树是递归定义的，因此二叉树的遍历也是递归的。这里的先、中、后是指根的先中后，即先遍历根、中间遍历根、最后遍历根的意思！

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

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

(1) 访问根结点；

(2) 先序遍历左子树；

(3) 先序遍历右子树。

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

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

(1) 中序遍历左子树；

1. 访问根结点；

(3) 中序遍历右子树。

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

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

(1) 后序遍历左子树；

(2) 后序遍历右子树；

(3) 访问根结点。

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

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

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

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

2. 递归递归递归。

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

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

2. 递归递归递归。