1 第一讲 树及二叉树的概念
【内容索引】
一、 引言 ............................................................................................... 2
二、 树的概念 ........................................................................................ 2
1. 树的定义 ........................................................................................ 2
2. 树的基本术语 ................................................................................. 3
三、 二叉树 ............................................................................................ 4
1. 二叉树的定义 ................................................................................. 4
2. 二叉树的性质 ................................................................................. 4
3. 二叉树的存储结构 .......................................................................... 6
4. 二叉树的遍历 ................................................................................. 9
数据结构课后练习题 第6章 树和二叉树
1/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1 第6章 树和二叉树
一、 选择题
1. 有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ D ）
A、向量 B、树 C、图 D、二叉树
2. 树最适合用来表示（ B ）
A、有序数据元素
B、元素之间具有分支层次关系的数据
C、无序数据元素
D、元素之间无联系的数据
3. 树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ）
A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c)
4. 对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（ B ）次序的遍历实现二叉树的结点编号。
A、先序 B、中序 C、后序 D、从根开始按层次遍历
5. 按照二叉树的定义，具有3 个结点的二叉树有（C ）种。
A、3 B、4 C、5 D、6
6. 在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（ ），其叶结点数为（ ）；树的最小高度为（ ），其叶结点数为（ ）；若采用链表存储结构，则有（ ）个空链域。
一、基础知识题
6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。
【解答】 设度为m的树中度为0,1,2,„,m的结点数分别为n0, n1, n2,„, nm，结点总数为n，分枝数为B，则下面二式成立
n= n0+n1+n2+„+nm (1)
n=B+1= n1+2n2 +„+mnm+1 (2)
由(1)和(2)得叶子结点数n0=1+
即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=8
6.2一棵完全二叉树上有1001个结点，求叶子结点的个数。
【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则
n= n0+ n1+ n2
n=2n0+n1-1
1002=2n0+n1
由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.
注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，„„。虽然解法也对，但步骤多且复杂，极易出错。
6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。
【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。
6.4．一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。 【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。
1
习 题 六 树 和 二 叉 树
6.1 单项选择题
1. 如图所示的4棵二叉树，__C__不是完全二叉树。
2. 如图所示的4棵二叉树，____是平衡二叉树。
3. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。
A. t—＞left=NULL B. t—＞ltag=1
C. t—＞ltag=1且t—＞left=NULL D. 以上都不对
4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。
A. 正确 B. 错误
5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。
A. 正确 B. 错误
6. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。
A. 正确 B. 错误 2
7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
A. 2h B. 2h-1 C. 2h+1 D. h+1
8. 如图8.9所示二叉树的中序遍历序列是____。
A. abcdgef B. dfebagc C. dbaefcg D. defbagc
9. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。
A. acbed B. decab C. deabc D. cedba
10．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。
A．a在b的右方 B．a在b的左方
C．a是b的祖先 D．a是b的子孙
11. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为
