5.32
int GList_Equal(GList A,GList B)//判断广义表A和B是否相等,是则返回1,否则返回0 { //广义表相等可分三种情况:
if(!A&&!B) return 1; //空表是相等的
if(!A->tag&&!B->tag&&A->atom==B->atom) return 1;//原子的值相等 if(A->tag&&B->tag)
if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp)) return 1; //表头表尾都相等 return 0; }//GList_Equal 5.33
void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次 {
if(!A) return;
if(!A->tag) printf(\ else {
GList_PrintElem(A->ptr.hp,layer+1);
GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次 }
}//GList_PrintElem 5.34
void GList_Reverse(GList A)//递归逆转广义表A {
if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转 {
D=C->ptr.hp;
A->ptr.tp->ptr.hp=A->ptr.hp;A->ptr.hp=D; //交换表头和表尾 GList_Reverse(A->ptr.hp);
GList_Reverse(A->ptr.tp); //逆转表头和表尾 }
}//GList_Reverse 5.35
Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针 {
scanf(\ if(ch==' ') {
L=NULL;
scanf(\
if(ch!=')') return ERROR; return OK; }
L=(GList)malloc(sizeof(GLNode)); L->tag=1;
if(isalphabet(ch)) //输入是字母 {
p=(GList)malloc(sizeof(GLNode)); //建原子型表头 p->tag=0;p->atom=ch; L->ptr.hp=p; }
else if(ch=='(') Create_GList(L->ptr.hp); //建子表型表头 else return ERROR; scanf (\
if(ch==')') L->ptr.tp=NULL;
else if(ch==',') Create_GList(L->ptr.tp); //建表尾 else return ERROR; return OK; }//Create_GList
分析:本题思路见书后解答. 5.36
void GList_PrintList(GList A)//按标准形式输出广义表 {
if(!A) printf(\空表
else if(!A->tag) printf(\原子 else {
printf(\
GList_PrintList(A->ptr.hp); if(A->ptr.tp) {
printf(\
GList_PrintList(A->ptr.tp);
} //只有当表尾非空时才需要打印逗号 printf(\ }//else
}//GList_PrintList 5.37
void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子 {
if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x); else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x) {
q=A;
A=A->ptr.tp; //删去元素值为x的表头 free(q);
GList_DelElem(A,x); }
if(A->ptr.tp) GList_DelElem(A->ptr.tp,x); }//GList_DelElem 5.39
void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素 {
InitQueue(Q);
for(p=L;p;p=p->ptr.tp) EnQueue(Q,p); while(!QueueEmpty(Q)) {
DeQueue(Q,r);
if(!r->tag) printf(\ else
for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); }//while
}//GList_PrintElem_LOrder
分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.
第六章 树和二叉树
6.33
int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 {
if(u==v) return 1; else {
if(L[v])
if (Is_Descendant(u,L[v])) return 1; if(R[v])
if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 }
return 0;
}//Is_Descendant_C 6.34
int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0 {
for(p=u;p!=v&&p;p=T[p]); if(p==v) return 1; else return 0; }//Is_Descendant_P
6.35
这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 6.36
int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法 {
if(!B1&&!B2) return 1;
else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild)) return 1; else return 0; }//Bitree_Sim 6.37
void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 {
InitStack(S);
Push(S,T); //根指针进栈 while(!StackEmpty(S)) {
while(Gettop(S,p)&&p) {
visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p);
if(!StackEmpty(S)) {
pop(S,p);
push(S,p->rchild); //向右一步 }
}//while
}//PreOrder_Nonrecursive 6.38
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈 {
PMType a;
InitStack(S); //S的元素为PMType类型 Push (S,{T,0}); //根结点入栈 while(!StackEmpty(S)) {
Pop(S,a);
switch(a.mark) {
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树 break; case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树 break; case 2:
visit(a.ptr); //访问结点,返回 }
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作. 6.39
typedef struct {
int data;
EBTNode *lchild; EBTNode *rchild; EBTNode *parent; enum {0,1,2} mark;
} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型
void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈 {
p=T;
while(p)
switch(p->mark) {
case 0:
p->mark=1;
if(p->lchild) p=p->lchild; //访问左子树 break; case 1:
p->mark=2;
if(p->rchild) p=p->rchild; //访问右子树 break; case 2: visit(p);
p->mark=0; //恢复mark值 p=p->parent; //返回双亲结点 }
}//PostOrder_Nonrecursive
分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历. 6.40
typedef struct {
int data;
PBTNode *lchild; PBTNode *rchild; PBTNode *parent;
} PBTNode,PBitree; //有双亲指针域的二叉树结点类型
void Inorder_Nonrecursive(PBitree T)//不设栈非递归遍历有双亲指针的二叉树 {
p=T;
while(p->lchild) p=p->lchild; //向左走到尽头 while(p) {
visit(p);
if(p->rchild) //寻找中序后继:当有右子树时 {
p=p->rchild;
while(p->lchild) p=p->lchild; //后继就是在右子树中向左走到尽头 }
else if(p->parent->lchild==p) p=p->parent; //当自己是双亲的左孩子时后继就是双亲 else {
p=p->parent;
while(p->parent&&p->parent->rchild==p) p=p->parent; p=p->parent;
} //当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先 }//while
}//Inorder_Nonrecursive 6.41
int c,k; //这里把k和计数器c作为全局变量处理 void Get_PreSeq(Bitree T)//求先序序列为k的结点的值 {
if(T) {
c++; //每访问一个子树的根都会使前序序号计数器加1 if(c==k) {
printf(\
exit (1); } else {
Get_PreSeq(T->lchild); //在左子树中查找 Get_PreSeq(T->rchild); //在右子树中查找 } }//if
}//Get_PreSeq
main() {
...
scanf(\
c=0; //在主函数中调用前,要给计数器赋初值0 Get_PreSeq(T,k); ... }//main 6.42
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {
if(!T) return 0; //空树没有叶子
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 6.43
void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 {
T->lchild<->T->rchild; //交换左右子树
if(T->lchild) Bitree_Revolute(T->lchild);
if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 }//Bitree_Revolute 6.44
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {
if(T->data==x) {
printf(\找到了值为x的结点,求其深度 exit 1; } else {
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 }
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法 {
if(!T) return 0; else {
m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }
}//Get_Depth 6.45
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);