该算法找到p和q的最近共同祖先结点r。
3．有一二叉链表，试编写按层次顺序遍历二叉树的算法。
4．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
5．对于二叉树的链接实现,完成非递归的中序遍历过程。
6．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。。
7．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
8．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
9．设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。
10．分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
第六章 树和二叉树
一、单项选择题 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。
h-1
4．(1)k(h为层数)
h-1
（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
B D
E G C
H
F I KO J L M
P N
O 6．（l）图略；
（2） 前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ （3）图略。
7．字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
1 0
9 0 1
5 0 1
3 1
五、算法设计题
1．[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。
BiTree Creat() //建立二叉树的二叉链表形式的存储结构 {ElemType x；BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型 if(x==0) bt=null; 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;
第六章树和二叉树习题 - 数据结构汇总
