第六章 树和二叉树
一、单项选择题
1.A 2.D 3．A 4．C 5．B 6．D 7．E 8. D 9．C 10．B 11. C 12．A 13．D 14．B 15．C 16．B 17. B 18. A 19．C 20．D 21．B 22. D 23．C
二、判断题（在各题后填写“√”或“×”） 1. 完全二叉树一定存在度为1的结点。× 2. 对于有N个结点的二叉树，其高度为log2n。× 3. 二叉树的遍历只是为了在应用中找到一种线性次序。√
4. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。× 5. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。× 6．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列 √ 7．完全二叉树中，若一个结点没有左孩子，则它必是树叶。√ 8. 二叉树只能用二叉链表表示。×
9. 给定一棵树，可以找到唯一的一棵二叉树与之对应。√
10. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。× 11．树形结构中元素之间存在一个对多个的关系。√ 12．将一棵树转成二叉树，根结点没有左子树。× 13．度为二的树就是二叉树。×
14. 二叉树中序线索化后，不存在空指针域。× 15．霍夫曼树的结点个数不能是偶数。√
16．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。√ 三、填空题
1．p->lchild==null && p->rchlid==null 2.(1)2k-1 (2)2k-1
3．64
4. 2n n-1 n+1
5． 先序遍历 后序遍历 中序遍历
6．.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 7．4
8．任何结点至多只有右子女的二叉树。 9．二叉排序树 10．前序 11．69
12． *count++, countleaf(l->rchile,count)
13．(1) p=p->lchild // 沿左子树向下 （2）p=p->rchild 14．(1)0 （2）hl>hr (3)hr=hl 15．(1)p->rchild (2)p->lchild (3)p->lchild
(4)ADDQ(Q,p->lchild) (5)ADDQ(Q,p->rchild) 四、应用题
1．树和二叉树逻辑上都是树形结构，树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。二叉树不是树的特例。
2．【解答】
具有3个结点的树 具有3个结点的二叉树
3．解答：先根序列：A B C D E F G H I J;
中根序列：B C D A F E H J I G;
后根序列：D C B F J I H G E A。
4．(1)k(h为层数)
（2）因为该树每层上均有K个结点，从根开始编号为1，则结点i的从右向左数第２个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2<=n<=ik+1成立，因i是整数，故结点n的双亲i的编号为?n-2)/k?+1。
(3) 结点n(n>1)的前一结点编号为n-1（其最右边子女编号是(n-1)*k+1），故结点 n的第 i个孩子的编号是(n-1)*k+1+i。
(4) 根据以上分析，结点n有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (n-1)%k!=0，其右兄弟编号是n+1。 5. A 6．（l）图略；（2）J B ?前序序列：ＡＢＣＥＤＦＨＧＩD 中序序列： E C B H F D J I G A E G C 后序序列： ＥＣＨＦＪＩＧＤＢＡ （3）图略。 H F I 7．字符A，B，KO C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
J L 1 M 0 五、算法设计题 1．[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍P 0 N 9 1 历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 O BiTree Creat() //建立二叉树的二叉链表形式的存储结构 5 0 1 {ElemType x；BiTree bt; 3 1 scanf(“%d”,&x); //本题假定结点数据域为整型
if(x==0) bt=null;
h-1
h-1
else if(x>0)
{bt=(BiNode *)malloc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat(); }
else error(“输入错误”)； return(bt); }//结束 BiTree
int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回1，否则，返回0
{int tag=0; BiTree p=bt, Q[]; // Q是队列，元素是二叉树结点指针，容量足够大 if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队 while (!QueueEmpty(Q))
{p=QueueOut(Q); //出队 if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0; //前边已有结点为空，本结点不空 else tag=1; //首次出现结点为空 if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队 else if (p->rchild) return 0; else tag=1; } //while
return 1; } //JudgeComplete
[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。
2.[题目分析]后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。 typedef struct
{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问 }stack;
stack s[],s1[];//栈，容量够大
BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT; while(bt!=null ||top>0)
{while(bt!=null && bt!=p && bt!=q) //结点入栈 {s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下
if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。
for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配 {pp=s[i].t;
for (j=top1;j>0;j--)
if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);} ｝
while(top!=0 && s[top].tag==1) top--; //退栈
if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历
}//结束while(bt!=null ||top>0) return(null);//ｑ、p无公共祖先 ｝//结束Ancestor
3．解答：本算法要借用队列来完成，其基本思想是，只要队列不为空，就出队列，然后判断该结点是否有左孩子和右孩子，如有就依次输出左、右孩子的值，然后让左、右孩子进队列。
void layorder (bitreptr T)
{initqueue (q) /*队列初始化*/ if(T!=NULL)
{printf(“%f”, T->data);
enqueue (q, T); /*入队列*/ while (not emptyqueue (q) ) /*若队列非空*/ {outqueue (q, p) ; /*出队*/ if (p->lchild!=NULL)
{printf(“%f”, p->lchild->data);
enqueue (q, p->lchild); /*入队列*/ }
if (p->rchild!=NULL)
{printf(“%”, p->rchild->data);
enqueue (q, p->rchild); /*入队列*/ } } }
}
4．【解答】
Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ {
InitStack(&S); p=root;
while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {
Visit(p->data); push(&S,p); p=p->Lchild;
}
else {
Pop(&S,&p); p=p->RChild; } }
}
5．．void InOrder(BiTree bt)
{BiTree s[],p=bt; //s是元素为二叉树结点指针的栈，容量足够大
int top=0; while(p || top>0)
{while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树
if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树
} }
6．BiTree Copy(BiTree t)//复制二叉树t
{BiTree bt;
if (t==null) bt=null;
else{bt=(BiTree)malloc(sizeof(BiNode)); bt->data=t->data;
bt->lchild=Copy(t->lchild); bt->rchild=Copy(t->rchild); }
return(bt); }//结束Copy
7.[题目分析]叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。
LinkedList head,pre=null; //全局变量
LinkedList InOrder(BiTree bt)
//中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); //中序遍历左子树
if(bt->lchild==null && bt->rchild==null) //叶子结点
if(pre==null) {head=bt; pre=bt;} //处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } //将叶子结点链入链表 InOrder(bt->rchild); //中序遍历左子树 pre->rchild=null; //设置链表尾 }
return(head); } //InOrder
时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)
8.[题目分析] 删除以元素值x为根的子树，只要能删除其左右子树，就可以释放值为x的根结点，因此宜采用后序遍历。删除值为x结点，意味着应将其父结点的左(右)子女指针置空，用层次遍历易于找到某结点的父结点。本题要求删除树中每一个元素值为 x的结点的子树，因此要遍历完整棵二叉树。
void DeleteXTree(BiTree bt) //删除以bt为根的子树
{DeleteXTree(bt->lchild); DeleteXTree(bt->rchild);//删除bt的左子树、右子树 free(bt); }// DeleteXTree //释放被删结点所占的存储空间
void Search(B:Tree bt,ElemType x)
//在二叉树上查找所有以x为元素值的结点，并删除以其为根的子树 {BiTree Q[];//Q是存放二叉树结点指针的队列，容量足够大 if(bt)
{if(bt->data==x) {DeleteXTree(bt); exit(0);}//若根结点的值为x，则删除整棵树 {QueueInit(Q); QueueIn(Q,bt); while(!QueueEmpty(Q))
{p=QueueOut(Q);
if(p->lchild) // 若左子女非空
if(p->lchild->data==x) //左子女结点值为 x,应删除当前结点的左子树 {DeleteXTree(p->lchild); p->lchild=null;} //父结点的左子女置空
else Enqueue (Q,p->lchild);// 左子女入队列 if(p->rchild) // 若右子女非空
if(p->rchild->data==x) //右子女结点值为 x,应删除当前结点的右子树 {DeleteXTree(p->rchild); p->rchild=null;} //父结点的右子女置空
else Enqueue (Q,p->rchild);// 右子女入队列
}//while
}//if(bt) }//search
9．int BTLC(BiTree T,int *c)//对二叉树T的结点计数
{if(T) {*c++;
BTLC(T->lchild,&c); //统计左子树结点 BTLC(T->rchild,&c); //统计右子树结点 } }//结束Count,调用时*c=0 10．
（1）找结点的中序前驱结点
BiTNode *InPre (BiTNode *p)
/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; /*直接利用线索*/ else
{/*在p的左子树中查找“最右下端”结点*/ for ( q=p->LChild; q->Rtag= =0; q=q->RChild); pre = q; }
return (pre); }
（2）找结点的中序后继结点
BiTNode *InSucc (BiTNode *p)
/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/ { if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/ else
{/*在p的右子树中查找“最左下端”结点*/ for ( q=p->RChild; q->Ltag= =0; q=q->LChild); succ= q; }
return (succ); }
(3) 找结点的先序后继结点
BiTNode *PreSucc (BiTNode *p)
/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/ { if (p->Ltag= =0) succ = p->LChild; else succ= p->RChild; return (succ); }
(4) 找结点的后序前驱结点
BiTNode *SuccPre (BiTNode *p)
/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; else pre= p->RChild; return (pre); }
第六章树和二叉树习题数据结构
