数据结构之二叉树的收尾（性质）
1）对任何⼀棵二叉树, 如果度为 0 其叶结点个数为 n0 , 度为 2 的分支结点个数为 n2 ,
则有n0=n2 + 1
1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
解：
n0=n2 + 1
故答案为200.
解： 因为n0+n1+n2=2n，n0=n2 + 1
得到2n0+n1-1=2n
因为该二叉树为完全二叉树
所以我们要讨论一下：分为如下两种情况：
n1=0:
n1=1:
所以当n1=0时，2n0+n1-1=2n可化简为n0=n+1/2
当n1=1时，2n0+n1-1=2n可化简为n0=n
故选a
提示： 用n<=2^h-1求解，设h=9和h=10求解
答案：B
提示：用 n0+n1+n2=767，n0=n2 + 1，讨论n1=0 and 1
答案：B
链式二叉树遍历选择题
1.
某完全二叉树按层次输出（同一层从左到右）的序列为
ABCDEFGH
。该完全二叉树的前序序列为（ ）
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
答案：画出二叉树的结构图，由前序遍历--根左右，此题选A
2.
二叉树的先序遍历和中序遍历如下：先序遍历：
EFHIGJK;
中序遍历：
HFIEJKG.
则二叉树根结点为（）
A 、E
B 、F
C、 G
D 、H
答案：由前序遍历知，此题答案为A
3.
设一棵二叉树的中序遍历序列：
badce
，后序遍历序列：
bdeca
，则⼆叉树前序遍历序列为
____
。
A adbce
B decab
C debac
D abcde
答案：由中序遍历和后序遍历画出二叉树，在根据前序遍历选择D
4.
某二叉树的后序遍历序列与中序遍历序列相同，均为
ABCDEF
，则按层次输出（同一层从左到右的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF
答案：选A