二叉树笔试题总结
基本性质相关
基本性质
性质 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) 中序遍历左子树；
- 访问根结点；
(3) 中序遍历右子树。
后序遍历二叉树的操作定义如下：
若二叉树为空，则空操作；否则
(1) 后序遍历左子树；
(2) 后序遍历右子树；
(3) 访问根结点。
常考题：根据遍历序列确定二叉树
由二叉树的先序序列和中序序列，或由其后序序列和中序序列可以唯一确定一棵二叉树。
由先序序列和中序序列确认二叉树
先序序列第一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；
递归递归递归。
由后序序列和中序序列确认二叉树
后序序列的最后一个结点一定是二叉树的根结点，在中序序列中找到根结点，其左边为左子树子孙，右边为右子树子孙；
递归递归递归。