一、前中后遍历题型

1.如果一颗二叉树的前序遍历的结果是ABCD，则满足条件的不同的二叉树有（ ）种

A.14

B.15

C.16

D.17

答案是A。

解法i：首先这棵二叉树的高度一定在3~4层之间:

三层：

A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),

A(B,C(D,())), A(B,C((),D))

四层：

如果为四层，就是单边树，每一层只有一个节点，除过根节点，其他节点都有两种选择，在上层节点的左边还是右边，所以2*2*2共8种

总共为14种。

通用解法ii：我们定义f(n)表明结点为n的二叉树的形态数

1. 一个结点只有一种情况，记f(1)=1
2. 两个结点的二叉树，固定一个结点后，剩下左右子树各有一种情况，f(2)=f(1)+f(1)

如果有三个结点，我们如果固定两个结点是不太好的，因为两个结点的二叉树有好多种，不便于推理。

我们固定根节点，那么剩下两个结点我们可以分配给左右子树，分别有三种情况

• 左子树两个右子树零个
• 左右子树分别一个
• 右子树两个左子树一个

那么f(3) = f(2)*f(0)+f(1)*f(1)+f(0)*f(2)

那么f(0)是多少呢，没有结点也是一种情况，所以f(0)=1

那么如果有n个结点，我们可以得到：

f(n) = f(n-1) * f(0)+f(n-2) * f(1)+...+f(0) * f(n-1)

而刚好这个数列正好是卡特兰数，上面式子也就是下面的式子

n个结点组成的二叉树有f(n)种形态

四个结点的二叉树有8!/(4! * 5!)=14种形态

●2和3两道是经典题目建议反复刷，多画图理解

2.已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）

A.4 2 5 7 6 9 1

B.4 2 7 5 6 9 1

C.4 7 6 1 2 9 5

D.4 7 2 9 5 6 1

 答案：C

解析：

通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。

故：根为： 5

5的左子树：4 7   5的右子树： 6 9  1  2

5的左子树的根为: 7  5的右子树的根为：9

7的左子树: 4 7的右：空  9的左子树：6  9的右子树：2

故这棵树的结构为：

3.已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）

A.ABDGHJKCEFILM

B.ABDGJHKCEILMF

C.ABDHKGJCEILMF

D.ABDGJHKCEIMLF

 答案：B

解析：

由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间

故：根为: A

A的左子树：JGDHKB       A的右子树：ELIMCF

A的左子树的根：B        A的右子树的根：C

B的左子树：JGDHK  B的右子树：空  C的左子树：ELIM C的右子树：F

B的左子树的根：D         C的左子树根：E

D的左子树的根：G D的右子树的根：H  E的右子树的根:I

故树的结构为：

故前序遍历：

A B D G J H K C E I L M F

14.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）

A.所有的结点均无左孩子

B.所有的结点均无右孩子

C.只有一个叶子结点

D.至多只有一个结点

答案：C

解析：

前序遍历：根 左 右

后序遍历：左 右 根

从二叉树 前序 和 后序遍历结果规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的

比如下面这前序和中序序列所构成的树的结构:

12345

54321

故每个节点只有一个孩子，即只有一个叶子节点

二、结点的深度问题

1.一颗拥有1000个结点的树度为4，则它的最小深度是（ ）

A. 5

B. 6

C. 7

D. 8

答案：B

解析：

如果这棵树每一层都是满的，则它的深度最小，假设它为一个四叉树，高度为h，则这个数的节点个数为(4^h - 1) / 3，当h = 5, 最大节点数为341， 当h = 6, 最大节点数为1365，所以最小深度应该为6。

 

 图有点简单，见谅了兄弟们。

2.设根结点的深度为1，则一个拥有n个结点的二叉树的深度一定在（   ）区间内

A.[log(n + 1)，n]

B.[logn，n]

C.[log(n + 1)，n - 1]

D.[log(n + 1)，n + 1]

 答案：A

解析：

最大深度： 即每次只有一个节点，次数二叉树的高度为n，为最高的高度

最小深度： 此树为完全二叉树， 如果是完全二叉树

根据二叉树性质，完全二叉树的高低为 h = log(n+1)向上取整

故选择A

3.有n个元素的完全二叉树的深度是（   ）

A.nlogn

B.nlogn+1

C.logn

D.logn+

 三、结点数的计算

1.对任意一颗二叉树，设N0、N1、N2分别是度为0、1、2的结点数，则下列式子中一定正确的是（ ）

A.N0 = N2 + 1

B.N1 = N0 + 1

C.N2 = N0 + 1

D.N2 = N1 + 1

答案：A

解析：

节点总数N： N = N0 + N1 + N2

度和边的关系： N - 1 = 0 * N0 + 1 * N1 + 2 * N2

上面两个式子可以推出： N0 + N1 + N2 - 1 = N1 + 2 * N2

可得： N0 = N2 + 1   //这也是一个二级结论，当只在二叉树中有用

2.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个

A.11

B.12​

C.13

D.14

答案：C

解析：

设Ni表示度为i的节点个数，则节点总数 N = N0 + N1 + N2

节点个数于节点边的关系： N个节点的树有N-1个边

边与度的关系：N - 1 = N1 + 2 * N2

故：N0 + N1 + N2 - 1 = N1 + 2 * N2

因此，得：N0 = N2 + 1   //可以直接记住这个二叉树的二级结论方便计算 

回到原题，N0 = 3，N1 = 8，可得N2 = 2。

因此答案是 3 + 8 + 2 = 13。

3.在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个

A.4

B.5

C.6

D.7

答案：C

解析：

设度为i的节点个数为ni, 该树总共有n个节点,则n=n0+n1+n2+n3. 

有n个节点的树的总边数为n-1条.

根据度的定义,总边数与度之间的关系为：n-1=0*n0+1*n1+2*n2+3*n3.

联立两个方程求解,可以得到n0 = n2 + 2n3 + 1,  n0=6。

在这里二叉树的二级结论n0 =n2+1就不管用了，因为这里有度为3的结点不算是二叉树。

后续会慢慢补充......