《江南大学程序设计课件第六章 树和二叉树》由会员分享，可在线阅读，更多相关《江南大学程序设计课件第六章 树和二叉树（21页珍藏版）》请在金锄头文库上搜索。
1、第六章 树和二叉树6.33int Is_Descendant_C(int u,int v)/在孩子存储结构上判断 u 是否v 的子孙,是则返回1,否则返回 0if(u=v) return 1; elseif(Lv)if (Is_Descendant(u,Lv) return 1; if(Rv)if (Is_Descendant(u,Rv) return 1; /这是个递归算法return 0;/Is_Descendant_C 6.34int Is_Descendant_P(int u,int v)/在双亲存储结构上判断 u 是否 v 的子孙,是则返回1,否则返回 0for(p=u;p!=v&p
2、;p=Tp); if(p=v) return 1;else return 0;/Is_Descendant_P 6.35这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.6.36int Bitree_Sim(Bitree B1,Bitree B2)/判断两棵树是否相似的递归算法if(!B1&!B2) return 1; elseif(B1&B2&Bitree_Sim(B1-lchild,B2-lchild)&Bitree_Sim(B1-rchild,B2-rc hild)return 1;else return 0;/Bitree_Sim6.37void PreOrder_Nonr
3、ecursive(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.38typedef struct BTNode* ptr; enum 0,1,2 mark; PMType; /有 mark 域的结点指
4、针类型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
5、.ptr-rchild,0); /访问右子树break;case 2:visit(a.ptr); /访问结点,返回/while/PostOrder_Stack分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个 mark 域,mark=0 表示刚刚访问此结点,mark=1 表示左子树处理结束返回,mark=2 表示右子树处理结束返回.每次根据栈顶元素的 mark 域值决定做何种动作.6.39typedef struct int data; EBTNode *lchild; EBTNode *rchild;EBTNode *parent; enum 0,1,2 mark; EBTNode,EB
6、itree; /有 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分析:本
7、题思路与上一题完全相同,只不过结点的 mark 值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将 mark 域恢复为 0,以备下一次遍历.6.40typedef 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-
8、rchild) /寻找中序后继:当有右子树时p=p-rchild;while(p-lchild) p=p-lchild; /后继就是在右子树中向左走到尽头else if(p-parent-lchild=p) p=p-parent; /当自己是双亲的左孩子时后继就是双亲elsep=p-parent;while(p-parent&p-parent-rchild=p) p=p-parent; p=p-parent; /当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先/while/Inorder_Nonrecursive 6.41int c,k; /这里把 k 和计数器 c 作为
9、全局变量处理void Get_PreSeq(Bitree T)/求先序序列为 k 的结点的值if(T)c+; /每访问一个子树的根都会使前序序号计数器加 1 if(c=k)printf(Value is %dn,T-data); exit (1);elseGet_PreSeq(T-lchild); /在左子树中查找Get_PreSeq(T-rchild); /在右子树中查找/if/Get_PreSeqmain().scanf(%d,&k);c=0; /在主函数中调用前,要给计数器赋初值 0 Get_PreSeq(T,k);./main 6.42int LeafCount_BiTree(Bitr
10、ee 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.43void Bitree_Revolute(Bitree T)/交换所有结点的左右子树T-lchildT-rchild; /交换左右子树if(T-lchild) Bitree_Revolute(T-lchild);if(T-rchild) Bi
11、tree_Revolute(T-rchild); /左右子树再分别交换各自的左右子树/Bitree_Revolute 6.44int Get_Sub_Depth(Bitree T,int x)/求二叉树中以值为 x 的结点为根的子树深度if(T-data=x)printf(%dn,Get_Depth(T); /找到了值为 x 的结点,求其深度exit 1;elseif(T-lchild) Get_Sub_Depth(T-lchild,x);if(T-rchild) Get_Sub_Depth(T-rchild,x); /在左右子树中继续寻找/Get_Sub_Depthint Get_Depth
12、(Bitree T)/求子树深度的递归算法if(!T) return 0; elsem=Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1;/Get_Depth 6.45void Del_Sub_x(Bitree T,int x)/删除所有以元素 x 为根的子树if(T-data=x) Del_Sub(T); /删除该子树elseif(T-lchild) Del_Sub_x(T-lchild,x);if(T-rchild) Del_Sub_x(T-rchild,x); /在左右子树中继续查找/else/Del_Sub_xv
13、oid Del_Sub(Bitree T)/删除子树 Tif(T-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T);/Del_Sub 6.46void 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,U); while(!StackEmpty(
14、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.47v
