算法描述如下：
int leafnum(Csnode *t,int n) {Gsnode *p;
if(t==NULL) return 0; p=t->fc; if(p==NULL)
n++; while(p) {n=leaf(p,n); p=p->ns; }
return n; }
2.交换左右孩子。算法如下： void exchange(Btnode *t)
{Btnode *p; if(t)
{exchange(t->lchild); exchange(t->rchild); if(t->lchild||t->rchild) {p=t->lchild; t->lchild=t->rchild; t->rchild=p;} } }
3.void printbtree(Btnode *r) {if(r)
{printf(“%c”,r->data); if(r->lchild||r->rchild) printf(“(”); printbtree(r->lchild); if(r->rchild) printf(“,”); printbtree(t->rchild); printf(“)”); } }
56
4. #define MAX 100 int checkt(Btnode *t) {Btnode *s[MAX]; int i,n=0; for(i=0;i
s[n]=s[i]->lchild; }
if(s[i]->rchild) {n=2*i+2;
s[n]=s[i]->rchild; } i++;
} return 1; }
5．(1)前序遍历二叉树的非递归算法的基本思想是：从二叉树的根结点开始，沿左支一直走到没有左孩子的结点为止，在走的过程中访问所遇结点，并把非空右孩子进栈。当找到没有左孩子的结点时，从栈顶退出某结点的右孩子，此时该结点的左子树已遍历结束，然后按上述过程遍历该结点的右子树，如此重复，直到二叉树中所有结点都访问完毕为上。算法如下：
void preorder(Btnode *t) { int I=0; Btnode *p,*s[M]; P=t; Do { while(p)
{printf(“%c\\t”,p->data);
57
if(p->rchild!=NULL) s[i++]=p->rchild; p=p->lchild; } if(i>0) p=s[--i];
}while(i>0||p!=NULL); }
(2)后序遍历二叉树的非递归算法的基本思想：采用一个栈保存返回的结点，先遍历根节点的所有结节点并入栈，出栈一个结点，然后遍历该结点的右结点并入栈，再遍历该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈为空为止。其中的难点是如何判断一个结点t的右结点已访问过，为此用p保存已访问过的结点(初值为NULL)，若t->right=p成立（在后序遍历中，t的右节点一定是在t之前访问），说明t的左右子树均已访问，现在应访问t。算法如下：
void postorder(Btree *t) { Btree *s[maxsize]; Btree *p; int flag,top=-1; Do { while(t) { top++; s[top]=t; t=t->left; } p=NULL; flag=1;
while(top=-1&&flag) { t=s[top]; if(t->right==p)
{ printf(“%d””,t->data); top--; p=t; } else
{ t=t->right; flag=1; }
58
}
}while(top!=-1) }
6.求二叉树中从根结点到p结点之间路径长度的算法描述如下： #define MAX 100
void path(Btnode *t,Btnode *p) { Btnode *s[MAX],*q=t; int b[MAX],top=-1; do {
while(q) {s[++top]=q; b[top]=0; q=q->lchild; }
if(top->-1&&b[top]==1) {q=s[top]; if(q==p)
{printf(“根结点到q结点的路径是：”)； for(I=0;I<=top;I++) printf(“%c”,s[I]->data); return; }
else top--; } if(top>-1)
{ p=s[top]->rchild; b[top]=1; }
}while(top>0); }
7.判断以二叉链表存储的二叉树是否为完全二叉树的算法描述如下：#define MAX 100 void checkt(BTnode *t) { Btnode *s[MAX]; int i,n=0; for(i=0;i 59 if(t==NULL) return 0; s[0]=t; while(i<=n) { if(!s[i]) return 0; if(s[i]->lchild) { n=2*i+1; s[n]=s[i]->lchild; } if(s[i]->rchild) { n=2*i+2; s[n]=s[i]->rchild; } i++; } return 1; } 第六章 一、单项选择题 (1)-(4)AACA (5)-(9)DBCAD (10)-(11)CB (12)图G是一个非连通分量，至少有两个连通分量。含8个顶点的完全无向图共需28条边，另外一个顶点构成一个连通分量，所以至少含9个顶点。 二、判断题 1．正确2．错误3．正确 4．错误5．正确6．错误 7．正确 8．正确 9．正确 10．正确(若n个顶点依次首尾相接构成一个环的有向强连通图，至少含n条边，即邻接矩阵中至少有n个小于u的非零元素)。 11．错误 12．正确 13．错误 14．正确 15．正确 16．错误 17．错误 18．错误 19．正确 三、填空题 (1)n(n-1)／2 (2)n(n-1) (3)n-1 (4)e (5)2e (6)出边 (7)人边 (8)n (9)有向图 (10)O(n) (11)O(n) (12)O(n+e) (13)O(n+e) (14)Kruscal (15)prim 四、算法题 1．将图的深度优先遍历或广度优先遍历算法稍加改造，另设m保存访问的顶点个数，若已访问顶点个数m小于图中顶点个数n，则图G不连通，否则为连通。现将深度优先遍历的非递归算法改造如下： 60 2 2