1．要求二叉树按二叉链表形式存储，(1)写一个建立二叉树的算法；(2)写一个判别给定的二叉树是否是完全二叉树的算法。 参考答案： (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
(2)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．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。 参考答案：
方法一：BiTree Creat(ElemType A[],int i)
//n个结点的完全二叉树存于一维数组A中，本算法据此建立以二叉链表表示的完全二叉树 {BiTree tree;
if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];
if(2*i>n) tree->lchild=null;else tree->lchild=Creat(A,2*i);
if(2*i+1>n) tree->rchild=null;else tree->rchild=Creat(A,2*i+1); }
return (tree); }//Creat 初始调用时i=1。 3．二叉树采用二叉链表存储：(1)编写计算整个二叉树高度的算法；(2)编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 参考答案：
(1)
int Height(BiTree bt)//求二叉树bt的深度 {
int hl,hr;
if (bt==null) return(0); else {
hl=Height(bt->lch); hr=Height(bt->rch); if(hl>hr) return (hl+1); else return(hr+1); } }
(2)求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。
int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else
{ BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大
front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)
{p=Q[front++]; temp++; //同层元素数加1
if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队
if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear;
if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度
temp=0;
}//if }//while
return (maxw); }//结束width
4．已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。 参考答案：
二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。 void Ancestor(ElemType A[],int n,int i,int j)
//二叉树顺序存储在数组A[1..n]中，本算法求下标分别为i和j的结点的最近公共祖先结点的值。 {while(i!=j)
if(i>j) i=i/2; //下标为i的结点的双亲结点的下标 else j=j/2; //下标为j的结点的双亲结点的下标
printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,A[i]);//设元素类型整型。
}// Ancestor
5．设一棵完全二叉树使用顺序存储在数组bt[1..n]中，请写出进行非递归的前序遍历算法。 参考答案：
二叉树的顺序存储是按完全二叉树的顺序存储格式，双亲与子女结点下标间有确定关系。对顺序存储结构的二叉树进行遍历，与二叉链表类似。在顺序存储结构下，判二叉树为空时，用结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”）。本题是完全二叉树。
void PreOrder(ElemType bt,int n)//对以顺序结构存储的完全二叉树bt进行前序遍历 {int top=0,s[]; //top是栈s的栈顶指针，栈容量足够大 while(i<=n||top>0) {while(i<=n)
{ printf(bt[i]); //访问根结点；
if (2*i+1<=n) s[++top]=2*i+1; //右子女的下标位置进栈 i=2*i; } //沿左子女向下 if(top>0) i=s[top--]; } //取出栈顶元素 }//结束PreOrder
6．试给出二叉树的自下而上、自右而左的层次遍历算法。 参考答案：
借助队列和栈，最后弹出栈中元素实现对二叉树按自下至上，自右至左的层次遍历 void InvertLevel(biTree bt) // 对二叉树按自下至上，自右至左的进行层次遍历 {if(bt!=null)
{StackInit(s); //栈初始化，栈中存放二叉树结点的指针
QueueInit(Q); //队列初始化。队列中存放二叉树结点的指针 QueueIn(Q,bt);
while(!QueueEmpty(Q)) //从上而下层次遍历 {p=QueueOut(Q); push(s,p); //出队, 入栈
if(p->lchild) QueueIn(Q,p->lchild); //若左子女不空，则入队列 if(p->rchild) QueueIn(Q,p->rchild);} //若右子女不空,则入队列
while(!StackEmpty(s)) {p=pop(s); printf(p->data);} //自下而上,从右到左的层次遍历 }//if(bt!=null)
} //结束InvertLevel
7．已知一棵二叉树的中序序列和后序序列，写一个建立该二叉树的二叉链表存储结构的算法。 参考答案：
BiTree IntoPost(ElemType in[],post[],int l1,int h1,int l2,int h2)
//in和post是二叉树的中序序列和后序序列,l1,h1,l2,h2分别是两序列第一和最后结点的下标 {BiTree bt=(BiTree)malloc(sizeof(BiNode));//申请结点
bt->data=post[h2];//后序遍历序列最后一个元素是根结点数据
for(i=l1;i<=h1;i++) if(in[i]==post[h2])break;//在中序序列中查找根结点 if(i==l1) bt->lchild=null; //处理左子树
else bt->lchild=IntoPost(in,post,l1,i-1,l2,l2+i-l1-1)； if(i==h1) bt->rchild=null; //处理右子树
else bt->rchild=IntoPost(in,post,i+1,h1,l2+i-l1,h2-1); return(bt); }
8．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析所写算法的时、空复杂度。 参考答案：
叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针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)。
9．一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。 参考答案：
对二叉树的某层上的结点进行运算，采用队列结构按层次遍历最适宜。
int LeafKlevel(BiTree bt, int k) //求二叉树bt 的第k(k>1) 层上叶子结点个数 {if(bt==null || k<1) return(0);
BiTree p=bt,Q[]; //Q是队列，元素是二叉树结点指针,容量足够大 int front=0,rear=1,leaf=0; //front 和rear是队头和队尾指针, leaf是叶子结点数
int last=1,level=1; Q[1]=p; //last是二叉树同层最右结点的指针，level 是二叉树的层数 while(front<=rear) {p=Q[++front];
if(level==k && !p->lchild && !p->rchild) leaf++; //叶子结点 if(p->lchild) Q[++rear]=p->lchild; //左子女入队 if(p->rchild) Q[++rear]=p->rchild; //右子女入队
if(front==last) {level++; //二叉树同层最右结点已处理,层数增1 last=rear; } //last移到指向下层最右一元素 if(level>k) return (leaf); //层数大于k 后退出运行 }//while }//结束LeafKLevel
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第4课 树和二叉树(3)在线全文阅读。
相关推荐：