1 第六章 树和二叉树
一．选择题
1. 以下说法错误的是 。
A.树形结构的特点是一个结点可以有多个直接前趋
B.线性结构中的一个结点至多只有一个直接后继
C.树形结构可以表达(组织)更复杂的数据
D.树(及一切树形结构)是一种"分支层次"结构
2. 如图6-2所示的 4 棵二叉树中， 不是完全二叉树。
图6-2 4 棵二叉树
3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是 。
A. t->left == NULL B. t->ltag==1
C. t->ltag==1 且 t->left==NULL D .以上都不对
4. 以下说法错误的是 。
A.二叉树可以是空集
B.二叉树的任一结点最多有两棵子树
C.二叉树不是一种树
D.二叉树中任一结点的两棵子树有次序之分
5. 以下说法错误的是 。
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
B.在三叉链表上，二叉树的求双亲运算很容易实现
C.在二叉链表上，求根，求左、右孩子等很容易实现
D.在二叉链表上，求双亲运算的时间性能很好
6. 如图6-3所示的 4 棵二叉树， 是平衡二叉树。 2
图6-3 4 棵二叉树
7. 如图6-4所示二叉树的中序遍历序列是 。
A. abcdgef B. dfebagc C. dbaefcg
D. defbagc
图6-4 1 棵二叉树
8. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是 。
A. acbed B. decab C. deabc D. cedba
..WORD完美格式..
..专业知识编辑整理..
第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）
习 题
一、选择题
1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。
A.向量 B.树 C图 D.二叉树
2．树最合适用来表示( )。
A.有序数据元素 B元素之间具有分支层次关系的数据
C无序数据元素 D.元素之间无联系的数据
3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。
A. la (2b (3d,3e),2c) B. a(b(D,e),c)
C. a(b(d,e),c) D. a(b,d(e),c)
4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。
A. 2h_l B.h C．2h-1 D. 2h
5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。
A. 2i B. 2i-l C. 2i+l D. 2i+2
6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为 ( )。
A.3 B.4 C.5 D.6
7.深度为5的二叉树至多有( )个结点。
A. 31 B. 32 C. 16 D. 10
一、基础知识题
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。
严蔚敏《数据结构(c语言版)习题集》标准答案树和二叉树文库
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
3 第六章 树和二叉树
6.33
int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
if(u==v) return 1;
else
{
if(L[v])
if (Is_Descendant(u,L[v])) return 1;
if(R[v])
if (Is_Descendant(u,R[v])) return 1; //这是个递归算法
}
return 0;
}//Is_Descendant_C
6.34
int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0
{
for(p=u;p!=v&&p;p=T[p]);
if(p==v) return 1;
else return 0;
}//Is_Descendant_P
6.35
这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.
6.36
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法
{
if(!B1&&!B2) return 1;
else
if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild))
