第六章树和二叉树 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-> lchild<→>T> 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->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("%d\n",Get_Depth(T)); //找到了值为 x 的结点,求其深度 exit 1; }