阿猫的博客

阿猫的博客

二叉树笔试题总结

560
2021-10-03

基本性质相关

基本性质

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

  1. 访问根结点;

(3) 中序遍历右子树。

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

若二叉树为空,则空操作;否则

(1) 后序遍历左子树;

(2) 后序遍历右子树;

(3) 访问根结点。

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

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

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

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

  2. 递归递归递归。

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

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

  2. 递归递归递归。