全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。 【算法源代码】
BiTree Creat() { /*建立二叉树的二叉链表形式的存储结构*/ ElemType x; BiTree bt;
scanf(\ if(x==0) bt=NULL; else if(x>0) {bt=(BiTNode *)malloc(sizeof(BiTNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat(); } return(bt); }/*结束 creat*/
int JudgeComplete(BiTree bt){
/*判断二叉树是否是完全二叉树，如是，返回1，否则，返回0*/ int tag=0;
BiTree p=bt, Q[50]; /* 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*/
5．有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。
【算法源代码】
typedef int ElemType;
BiTree Creat(ElemType A[],int i){ 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*/
6．编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。 【算法源代码】
int c,k; /*这里把k和计数器c作为全局变量处理 */
void Get_PreSeq(BiTree T) /*求先序序列为k的结点的值 */ { if(T)
{ c++; /*每访问一个子树的根都会使前序序号计数器加1 */
if(c==k) { printf(\ return; } else
{ Get_PreSeq(T->lchild); /*在左子树中查找 */ Get_PreSeq(T->rchild); /*在右子树中查找 */ } }/*if */
}/*Get_PreSeq */
7．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注
37
：已知树中结点数） 【算法分析】
由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树的深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。 【算法源代码】 int Depth(PTree t){
int maxdepth=0; int i,f,temp; for(i=1;i<=t.n;i++){ temp=0; f=i;
while(f>0) {temp++; f=t.nodes[f].parent; } /* 深度加1，并取新的双亲*/ if(temp>maxdepth) maxdepth=temp; } /*最大深度更新*/ }
return(maxdepth);/*返回树的深度*/ } /*结束Depth*/
8．二叉树采用二叉链表存储
（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。
（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。 【算法分析】
二叉树是递归定义的，其运算最好采取递归方式。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。 【算法源代码】
int Height(BiTree bt) /*求二叉树bt的深度*/ {int hl,hr;
if (bt==NULL) return(0); else {
hl=Height(bt->lchild); hr=Height(bt->rchild); if(hl>hr) return (hl+1); else return(hr+1);} }
int Width(BiTree bt)/*求二叉树bt的最大宽度*/ {if (bt==NULL) return (0); /*空二叉树宽度为0*/ else
{BiTree p,Q[50];/*Q是队列，元素为二叉树结点指针，容量足够大*/ int front=1,rear=1,last=1;
int 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; /*last指向下层最右元素, 更新当前最大宽度*/ if(temp>maxw) maxw=temp; temp=0;}/*if*/ }/*while*/
return (maxw); }
}/*结束width*/
9．设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。 【算法源代码】
void exchange(BiTree bt)/*将二叉树bt所有结点的左右子树交换 { BiTree p; if(bt){
p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; /*左右子女交换 exchange(bt->lchild); /*交换左子树上所有结点的左右子树 exchange(bt->rchild); /*交换右子树上所有结点的左右子树 } }
【算法讨论】
38
将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历不适合本题。
10．已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储。 （1）编写用先根遍历二叉树中每个结点的递归算法；
（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。 【算法分析】
K
高度为K的二叉树，按顺序方式存储，要占用2-1个存储单元，与实际结点个数n关系不大，对不是完全二叉树的二叉树，要增加“虚结点”，使其在形态上成为完全二叉树。注意：二叉树中最大序号的叶子结点，是在顺序存储方式下编号最大的结点。 【算法源代码】
K
int m=2-1; /*全局变量*/
void PreOrder(ElemType bt[], int i ) {if (i<=m) /*设虚结点以0表示*/ {printf(\ /*访问根结点*/
if(2*i<=m && bt[2*i]!=0) PreOrder(bt,2*i); /*先序遍历左子树*/ if(2*i+1<=m && bt[2*i+1]!=0) PreOrder(bt,2*i+1);/*先序遍历右子树*/ }
}/*结束PreOrder*/
void Ancesstor(ElemType bt[]){ /*打印最大序号叶子结点的全部祖先*/ c=m;
while(bt[c]==0) c--; /*找最大序号叶子结点，该结点存储时在最后*/ f=c/2; /*c的双亲结点f*/ while(f!=0){
/*从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点*/ printf(\ f=f/2;
}/*逆序输出，最老的祖先最后输出*/ }/*结束*/
11．编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。 【算法源代码】
void Del_Sub(BiTree T)/*删除子树T */ { if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }/*Del_Sub */
void Del_Sub_x(BiTree T,int x)/*删除所有以元素x为根的子树*/ { if(T->data==x) Del_Sub(T); /*删除该子树 */ else
{if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x); /*在左右子树中继续查找 */ }/*else */ }/*Del_Sub_x */
12．设计一个算法，在中序全线索二叉树中，查找给定结点* p在中序序列中的后继（二叉树的根结点指针并未给出），并中序遍历该线索二叉树。 【算法源代码】
BiThrTree insucc(BiThrTree p)/*找p结点的后继*/ { if(p->rtag==1) /*后继线索*/ return p->rchild;
else /*右子树的最左下结点*/ { p=p->rchild; while(p->ltag==0) p=p->lchild; return p; } }
void inorder_thr(BiThrTree T) { BiThrTree p=T; if(p)
{ while(p->ltag==0) p=p->lchild;/*找中序遍历的第1个结点*/ do{ printf(\
39
p=insucc(p);/*找当前结点的后继结点*/ }while(p); } }
7.5 算法设计题
1．设计一个算法，删除无向图的邻接矩阵中给定顶点。 【算法分析】
要在邻接矩阵中删除某顶点i主要操作有以下三步：（1）图的边数要减去与顶点i相关联的边的数目；（2）在邻接矩阵中删除第i行与i列,即把第i+１行到第n行依次前移，第i+１列到第n列依次前移。（3）图中顶点的个数-1。
【算法源代码】
void Delvi(MGraph *G,int i)/*在图 G中删除顶点I*/ {int num,j,k;
if(i<1||i>G->vexnum)
{printf(\ exit(0);} else {num=0;
for(j=1;j<=G->vexnum;j++)
{if(G->arcs[i][j]) num++; if(G->arcs[j][i]) num++; } G->arcnum-=num;
for(j=i+1;j<=G->vexnum;j++) for(k=1;k<=G->vexnum;k++)
G->arcs[j-1][k]=G->arcs[j][k]; for(j=i+1;j<=G->vexnum;j++) for(k=1;k<=G->vexnum-1;k++) G->arcs[k][j-1]=G->arcs[k][j]; G->vexnum--; } }
2．设计一个算法，求出分别用邻接矩阵和邻接表表示的有向图中顶点的最大出度值。 【算法分析】
用邻接矩阵表示的有向图中顶点的最大出度是该顶点所在行上非零元的个数。邻接表表示的有向图中顶点的最大出度值是该顶点所连接的单链表中结点的个数。 【算法源代码1】
void Max_du(MGraph *G) {int num,i,j; int max=0;
for(i=1;i<=G->vexnum;i++) {num=0;
for(j=1;j<=G->vexnum;j++) if(G->arcs[i][j]) num++; if(max printf(\ } 【算法源代码2】用邻接表表示 void Max_du(ALGraph *G) {ArcPtr p; int num,i,j; int max=0; for(i=1;i<=G->vexnum;i++) {num=0; p=G->ag[i].firstarc; while(p) {p=p->nextarc; num++; } if (max printf(\ } 3．已知某有向图用邻接表表示，设计一个算法，求出给定两顶点间的简单路径。 【算法分析】 因为在遍历的过程中每个顶点仅被访问一次，所以从顶点u到顶点v遍历的过程中走过的路径就是一条简单路径。我们只需在遍历算法中稍作修改，就可实现该算法。为了记录路径中访问过的顶点，只需设一数组存储走过的顶点即可。 【算法源代码】 40