第六章树和二叉树 6.33 int Is descendant c(intu,intv∥/在孩子存储结构上判断u是否ⅴ的子孙,是则返回 1,否则返回0 if(u=v)return 1 if(LLvD if (Is Descendant(u, LIvD)return 1 if(RIvD) if( (s Descendant(u,RⅣv]) return1;∥这是个递归算法 return 0 i//s Descendant C 6.34 int Is descendant P(int u,intv∥在双亲存储结构上判断u是否v的子孙是则返回 1,否则返回0 for(p=u pl=v&&p p=TpD; if(p=v)return 1 else return 0 i//s Descendant P 6.35 这一题根本不需要写什么算法见书后注释:两个整数的值是相等的 6 int Bitree sin( Bitree B1, Bitree B2y判断两棵树是否相似的递归算法 if(!b l&&! B2)return 1; else if(B l&&B2&& Bitree Sim(B1->lchild, B2->lchild )&& Bitree Sim(B1->rchild, B2->rc hild )) else return 0
第六章 树和二叉树 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->rc hild)) return 1; else return 0; }//Bitree_Sim
6.37 void PreOrder Nonrecursive( Bitree T∥先序遍历二叉树的非递归算法 Init Stack(S) Push(S,T,∥根指针进栈 while(!Stack Empty(s)) while(g it(p->data) push(s, p->lchild ) }/向左走到尽头 if(Stack Empty(s)) pop(s,P push(Sp-> achild),∥向右一步 i//while i//PreOrder Nonrecursive typedef struct i BTNode* pt enum 10, 1, 2) mark } PMType;有mark域的结点指针类型 void Postorder_ Stack( BiTree T)后续遍历二叉树的非递归算法,用栈 PMType a, Init stack(S),∥S的元素为 PMType类型 Push(S,{T,0},/根结点入栈 while(!Stack Empty(s)) Pop(s switch (a mark) Push(S,{aptr,1}),∥修改mark域 if(a ptr-> Child)Push(S,{aptr-> lchild0}),∥访问左子树 case Push(S,aptr2}),∥修改mark域
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,{aptr> schild,0});∥访问右子树 break visit(aptr),∥访问结点返回 i/while 3//PostOrder Stack 分析为了区分两次过栈的不同处理方式在堆栈中增加一个mark域mark=0表示 刚刚访问此结点mark=1表示左子树处理结束返回mark=2表示右子树处理结束 返回每次根据栈顶元素的mark域值决定做何种动作 6.39 typedef struct i int data EBTNode *lchild EBTNode *rchild EBTNode parent; enum 10, 1, 2) mark; } BINOde,EBre,∥有mark域和双亲指针域的二叉树结点类型 void Postorder nonrecursive( EBitree T后序遍历二叉树的非递归算法不用栈 hile(p) switch(p->mark) 0: p->mark-I ip-> lchild)p=p-> lchild,∥访问左子树 break p->mark=2 ifp> schild)p=p>chid;访问右子树 break case visit(p); p→>mark=0;∥恢复mak值 p=p-> parent;/返回双亲结点 i//PostOrder Nonrecursive 分析本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的而不 是暂存在堆栈中所以访问完毕后要将mark域恢复为0,以备下一次遍历 6.40
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 i int data PBTNode *lchild PBTNode *rchild PBTNode*parent PBTNode, PBitree;双亲指针域的二叉树结点类型 void Inorder nonrecursive( PBitree t∥不设栈非递归遍历有双亲指针的二叉树 while(p-> lchild)p=p->lhid,/向左走到尽头 while(p) p): fp->rchd)∥寻找中序后继:当有右子树时 p=p->rchild while(p> Child)p=p-> lchild;∥后继就是在右子树中向左走到尽头 else if(p-> parent> Child=p)p=p→> parent;∥当自己是双亲的左孩子时后继就 是双亲 p=p->parent hile(p->parent&&p->parent->rchild==p)p=p->parent }∥当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树 中的祖先 i//while i//norder Nonrecursive 6.41 int ck;∥这里把k和计数器c作为全局变量处理 void get PreSec( Bitree t求先序序列为k的结点的值 IfT) c++;∥每访问一个子树的根都会使前序序号计数器加1 printf("Value is %d n"T->data); exit(1);
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("Value is %d\n",T->data); exit (1); }
else Get PreSeq(T~ achild),∥在左子树中查找 Get PreSen(T> rchild),∥在右子树中查找 i//if i//Get Pre maino scanf("%d",&k C=0;∥主函数中调用前要给计数器赋初值0 Get PreSeq(t, k) 6.42 int LeafCount BiTree(Bitree T)求二叉树中叶子结点的数目 if(!T)return0,∥空树没有叶子 else if(T> Child e&&!T-> rchild) retur1;/叶子结点 else return Leaf Count(T-> lchild)+ Leaf Count(T> rchild)∥左子树的叶子数加上 右子树的叶子数 i //LeafCount BiTree 6.43 void Bitree Revolute( Bitree T交换所有结点的左右子树 T-> lchildT> Achild;∥交换左右子树 if(T->lchild)Bitree Revolute(T->lchild); i(T> achild) Bitree Revolute(I> rchild),∥左右子树再分别交换各自的左右子树 3//Bitree Revolute 6.44 int Get Sub Depth( Bitree T, int x)/求二叉树中以值为x的结点为根的子树深度 if(T->data==x) printf("%odn" Get Depth(D)∥找到了值为x的结点求其深度 exit 1
else { Get_PreSeq(T->lchild); //在左子树中查找 Get_PreSeq(T->rchild); //在右子树中查找 } }//if }//Get_PreSeq main() { ... scanf("%d",&k); 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->lchildT->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("%d\n",Get_Depth(T)); //找到了值为 x 的结点,求其深度 exit 1; }
if(T->Child)Get Sub Depth(T->lchild, x) if(T-> achild) Get Sub Depth(T-> Achild,x),∥在左右子树中继续寻找 i//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 1//Get Depth 645 void del sub x( Bitree T, int x)删除所有以元素ⅹ为根的子树 if(T->data=x) Del sub(D),/删除该子树 if(T->lchild)Del Sub x(T->lchild, x); f(-> achild) Del sub x(T-> rchild,x,∥在左右子树中继续查找 i//else i//Del Sub X void Del sub( Bitree T删除子树T if(T->lchild) Del Sub(T->lchild ) if(T->rchild)Del Sub(T->rchild ); freeT) i//Del Sub void Bitree Copy Nonrecursive( Bitree T, Bitree&U∥非递归复制二叉树 Init Stack(S 1), Init Stack (S2) push(S1,D,∥根指针进栈 U=(BTNode*)malloc(sizeof(BTNode)) U->data=T->data
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); if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找 }//else }//Del_Sub_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 6.46 void Bitree_Copy_Nonrecursive(Bitree T,Bitree &U)//非递归复制二叉树 { InitStack(S1);InitStack(S2); push(S1,T); //根指针进栈 U=(BTNode*)malloc(sizeof(BTNode)); U->data=T->data;
q=U: push(S2, 0); while(!Stack Empty(s) while(Gettop(Sl, p)&&p) q->lchild=(BTNode*)malloc(sizeof(BTNode)); q->lchild; ->data=p->data; bush(sl, p->lchild) bush(s2, 9) }/向左走到尽头 pop(Sl, P); pop(S2, 9); if(!Stack Empty(S1) pop(Sl, p): pop(S2, 9); ->rchild=(BTNode*)malloc(sizeof(B TNode)); q=q->rchild; q->data=p->data; push(S1,p> rchild),∥向右一步 push(S2, q) i //while 3//BiTree Copy_ Nonrecursive 分析本题的算法系从6.37改写而来 6.47 void LayerOrder(Bitree T)层序遍历二又树 InitQueue(Q),∥建立工作队列 EnQueue(Q, T) while(!QueueEmpty(Q)) DeQueue(Q,p); isit(p); if(p->lchild) En Queue(Q p->lchild) (p->rchild) EnQueue(Q, p->rchild ) g//LayerOrder int found=FAlSE Btee* Find Near Ancient( Bitree T, Bitree p, Bitree q)∥求二叉树T中结点p和q的 最近共同祖先
q=U;push(S2,U); while(!StackEmpty(S)) { while(Gettop(S1,p)&&p) { q->lchild=(BTNode*)malloc(sizeof(BTNode)); q=q->lchild;q->data=p->data; push(S1,p->lchild); push(S2,q); } //向左走到尽头 pop(S1,p); pop(S2,q); if(!StackEmpty(S1)) { pop(S1,p);pop(S2,q); q->rchild=(BTNode*)malloc(sizeof(BTNode)); q=q->rchild;q->data=p->data; push(S1,p->rchild); //向右一步 push(S2,q); } }//while }//BiTree_Copy_Nonrecursive 分析:本题的算法系从 6.37 改写而来. 6.47 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder 6.48 int found=FALSE; Bitree* Find_Near_Ancient(Bitree T,Bitree p,Bitree q)//求二叉树 T 中结点 p 和 q 的 最近共同祖先
Bitree pathp[100 pathan1001∥设立两个辅助数组暂存从根到pq的路径 Findpath(t,p, pathp, 0); found=FALSE Findpathe( T, q, patho,0),/求从根到pq的路径放在 pathp和 patho中 for(i=0 pathp[==path[&& pathp[计++);〃查找两条路径上最后一个相同结点 return pathp[-1 i//Find Near Ancient void Find path( Bitree, Bitree p, Bitree path[] int i)y/求从T到p路径的递归算法 if(T=p) found=TRUE return,/找到 path[}T,∥当前结点存入路径 ifT-> lchild) Findpath(I-> lchild, p, path,计+1);∥在左子树中继续寻找 if(T-> achild&&! found) Findpath(T→ rchild, p, path计+1)∥在右子树中继续寻找 if(!found)path[]=NULL;∥回溯 i//Findpath 6.49 int IsFull Bitree(Bitree T)判断二叉树是否完全二叉树,是则返回1,否则返回0 InitQueue(Q) f EnQueue(Q,T,∥建立工作队列 while(!QueueEmpty(Q)) DeQueue(Q p); if(p)flag=l else if(flag)return 0: else EnQueue(Q, p->lchild) EnQueue(Qp-> rchild),∥不管孩子是否为空都入队列 i/while i//sFull Bitree 分析该问题可以通过层序遍历的方法来解决与647相比作了一个修改不管当 前结点是否有左右孩子都入队列这样当树为完全二叉树时遍历时得到是一个 连续的不包含空指针的序列反之,则序列中会含有空指针
{ Bitree pathp[ 100 ],pathq[ 100 ] //设立两个辅助数组暂存从根到 p,q 的路径 Findpath(T,p,pathp,0); found=FALSE; Findpath(T,q,pathq,0); //求从根到 p,q 的路径放在 pathp 和 pathq 中 for(i=0;pathp[i]==pathq[i]&&pathp[i];i++); //查找两条路径上最后一个相同结点 return pathp[--i]; }//Find_Near_Ancient void Findpath(Bitree T,Bitree p,Bitree path[ ],int i)//求从 T 到 p 路径的递归算法 { if(T==p) { found=TRUE; return; //找到 } path[i]=T; //当前结点存入路径 if(T->lchild) Findpath(T->lchild,p,path,i+1); //在左子树中继续寻找 if(T->rchild&&!found) Findpath(T->rchild,p,path,i+1); //在右子树中继续寻找 if(!found) path[i]=NULL; //回溯 }//Findpath 6.49 int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回 1,否则返回 0 { InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree 分析:该问题可以通过层序遍历的方法来解决.与 6.47 相比,作了一个修改,不管当 前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个 连续的不包含空指针的序列.反之,则序列中会含有空指针
6.50 Status CreateB itree Triplet(Bitree&ny输入三元组建立二叉树 if(getchar(=A)return ERROR T(BTNode*)malloc(sizeof(B TNode) p=T p->data=getchar(; getchar,∥滤去多余字符 Init Queue(Q) EnQueue(Q,T) while((parent=getchar()l=A'&&(child=getchar)&&(side=getchar)) while(queueHead(Q)=parent &&! QueueEmpty(Q) DeQueue(Q, e); Queue empty(Q) return error,∥未按层序输入 p=QueueHead (Q); q=(BTNode")malloc(sizeof(BTNode)); if(side=L')p-lchild=q: else if(side=R)p->rchild=q else return ERROR;/格式不正确 q->data=child EnQueue(Q, q); return OK i//CreateBitree Triplet 6.51 Status Print Expression( Bitree∥按标准形式输出以二叉树存储的表达式 ifT>data是字母) printf("%c", T->data) else if(T->data是操作符) if(-> Lchild!-> rchild) return Error,格式错误 if(T> Lchild->data是操作符&&T> lchild->data优先级低于T>data) printf(() if(! Print Expression(T->lchild)) return ERROR; print. f(")y") }/注意在什么情况下要加括号 else if(! Print Expression(T->lchild))return ERROR; if( T->rchild->data是操作符&&T-> rchild->data优先级低于T->data) ("(" if(! Print Expression(T->rchild)) return ERROR printf()");
6.50 Status CreateBitree_Triplet(Bitree &T)//输入三元组建立二叉树 { if(getchar()!='^') return ERROR; T=(BTNode*)malloc(sizeof(BTNode)); p=T;p->data=getchar(); getchar(); //滤去多余字符 InitQueue(Q); EnQueue(Q,T); while((parent=getchar())!='^'&&(child=getchar())&&(side=getchar())) { while(QueueHead(Q)!=parent&&!QueueEmpty(Q)) DeQueue(Q,e); if(QueueEmpty(Q)) return ERROR; //未按层序输入 p=QueueHead(Q); q=(BTNode*)malloc(sizeof(BTNode)); if(side=='L') p->lchild=q; else if(side=='R') p->rchild=q; else return ERROR; //格式不正确 q->data=child; EnQueue(Q,q); } return OK; }//CreateBitree_Triplet 6.51 Status Print_Expression(Bitree T)//按标准形式输出以二叉树存储的表达式 { if(T->data 是字母) printf("%c",T->data); else if(T->data 是操作符) { if(!T->lchild||!T->rchild) return ERROR; //格式错误 if(T->lchild->data 是操作符&&T->lchild->data 优先级低于 T->data) { printf("("); if(!Print_Expression(T->lchild)) return ERROR; printf(")"); } //注意在什么情况下要加括号 else if(!Print_Expression(T->lchild)) return ERROR; if(T->rchild->data 是操作符&&T->rchild->data 优先级低于 T->data) { printf("("); if(!Print_Expression(T->rchild)) return ERROR; printf(")");
else if(! Print Expression(T->rchild)) return ERROR else return error;/排法字符 eturn OK &//Pr rint Expression 6.52 ypedef struct( BTNode node int layer } BTNRecord,/包含结点所在层次的记录类型 int FanMao( Bitree T)求一棵二叉树的"繁茂度 int count;/ count数组存放每一层的结点数 Init Queue(Q;/Q的元素为 BTNRecord类型 EnQueue(Q,T,0)); while(!QueueEmpty(Q)) De Queue(Q, r) t[r layer]+ if(r node->lchild) EnQueue(Q, r.node->Child, r layer+1); (r node->rchild) EnQueue(Q,r. node->rchild, r layer+1) }/利用层序遍历来统计各层的结点数 h= r layer,∥最后一个队列元素所在层就是树的高度 for(maxn=count[0] Fl; count]; 1++) if(count[}maxn)maxn= count[,∥求层最大结点数 maxn i//FanMao 分析如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上 会复杂一些你能写出来吗? int max Status Printpath Maxdepths 1( Bitree T)/求深度等于树高度减一的最靠左的结点 Bitree path; maxh= Get Depth(D),∥ Get Depth函数见644 if(maxh<2) return error;∥无符合条件结点 Find h(T,1)
} else if(!Print_Expression(T->rchild)) return ERROR; } else return ERROR; //非法字符 return OK; }//Print_Expression 6.52 typedef struct{ BTNode node; int layer; } BTNRecord; //包含结点所在层次的记录类型 int FanMao(Bitree T)//求一棵二叉树的"繁茂度" { int countd; //count 数组存放每一层的结点数 InitQueue(Q); //Q 的元素为 BTNRecord 类型 EnQueue(Q,{T,0}); while(!QueueEmpty(Q)) { DeQueue(Q,r); count[r.layer]++; if(r.node->lchild) EnQueue(Q,{r.node->lchild,r.layer+1}); if(r.node->rchild) EnQueue(Q,{r.node->rchild,r.layer+1}); } //利用层序遍历来统计各层的结点数 h=r.layer; //最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++) if(count[i]>maxn) maxn=count[i]; //求层最大结点数 return h*maxn; }//FanMao 分析:如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上 会复杂一些,你能写出来吗? 6.53 int maxh; Status Printpath_MaxdepthS1(Bitree T)//求深度等于树高度减一的最靠左的结点 { Bitree pathd; maxh=Get_Depth(T); //Get_Depth 函数见 6.44 if(maxh<2) return ERROR; //无符合条件结点 Find_h(T,1);