树的常见练习题一
- 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
- 2、在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个
- 3、一颗拥有1000个结点的树度为4，则它的最小深度是（ ）
- 4、一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）
- 5、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
- 6、已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）
- 7、已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A.所有的结点均无左孩子
B.所有的结点均无右孩子
C.只有一个叶子结点
D.至多只有一个结点
从二叉树前序和后序遍历结果规则中可以看出，如果树中每个节点只有一个孩子时，遍历结果肯定是反的比如下面这前序和中序序列所构成的树的结构:
12345
54321
故每个节点只有一个孩子，即只有一个叶子节点，所以答案是 C
2、在一颗度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，则叶子结点有（ ）个
A.4
B.5
C.6
D.7
n是总节点数，n3是度为3的节点数，n2是度为2的节点数，n1是度为1的节点数，n0是度为0的节点数，利用节点数和边数的关系来求解此题，见下图解析：
答案是C
3、一颗拥有1000个结点的树度为4，则它的最小深度是（ ）
A.5
B.6
C.7
D.8
假设是满四叉树
所以答案是B
4、一颗完全二叉树有1001个结点，其叶子结点的个数是（ ）
A.251
B.500
C.501
D.不能确定
所以答案是C
5、设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为（ ）个
A.11
B.12
C.13
D.14
利用好结点数量关系的公式
答案是C
6、已知某二叉树的前序遍历序列为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
7、已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A.ABDGHJKCEFILM
B.ABDGJHKCEILMF
C.ABDHKGJCEILMF
D.ABDGJHKCEIMLF
所以选择B
