数据结构之二叉树的收尾（性质）
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