《数据结构及应用算法教程（修订版） 第6章二叉树和树习题.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 第6章二叉树和树习题.ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 二叉树和树习题,习题6.6:,习题6.8: void Get_PreOrder(BiTree T,int k,TElemType /在右子树中查找 /if /Get_PreOrder,习题6.9: int LeafCount(BiTree T) /求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild /左子树的叶子数加上右子树的叶子数 /LeafCount,习题6.10: /交换所有结点的左右子树 void Change_BiTree (BiTree T) BiTree temp if(T) temp=T-lchild; T-l
2、child=T-rchild; T-rchild=temp /交换左右子树 if(T-lchild) Change_BiTree(T-lchild); if(T-rchild) Change_BiTree (T-rchild); /左右子树再分别交换各自的左右子树/Change_BiTree,习题6.11: /求二叉树中以值为x的结点为根的子树深度int Get_Sub_Depth(BiTree T,int x, int /在左右子树中继续寻找 /Get_Sub_Depth,int Get_Depth(BiTree T) /求子树深度的递归算法 if(!T) return 0; else m=
3、Get_Depth(T-lchild); n=Get_Depth(T-rchild); return (mn?m:n)+1; /Get_Depth,习题6.12: / 删除所有以元素x为根的子树 void Del_Sub_x(BiTree T,int 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
4、-lchild) Del_Sub(T-lchild); if(T-rchild) Del_Sub(T-rchild); free(T); /Del_Sub,习题6.13: / 根据顺序存储结构建立二叉链表 Status CreateBiTree_SqList(BiTree /CreateBitree_SqList,习题6.13: / 根据顺序存储结构建立二叉链表 void CreateBiTree_SqList(BiTree /CreateBiTree_SqList,习题6.19: /求一棵以孩子兄弟链表表示的树的度 int GetDegree_CSTree(CSTree T) /求孩子兄弟链
5、表表示的树T的度 if(!T-firstchild) return 0; /空树 else degree=0; for( p=T-firstchild; p; p=p-nextsibling) degree+; /本结点的度 for( p=T-firstchild; p; p=p-nextsibling) d=GetDegree_CSTree(p); if(ddegree) degree=d; /孩子结点的度的最大值 return degree; /else /GetDegree_CSTree,习题6.20: /求孩子兄弟链表表示的树T的叶子数目int LeafCount_CSTree(CST
6、ree T ) if(!T) return 0; else if(!T-firstchild) return 1; /叶子结点 else count=0; for(p=T-firstchild;p;p=child-nextsibling) count+=LeafCount_CSTree(p); return count; /各子树的叶子数之和 /LeafCount_CSTree,习题6.20: /求孩子兄弟链表表示的树T的叶子数目int LeafCount(CSTree T ) CSTree p=T; int k=0; if(p!=NULL) if(p-firstchild=NULL) k=1
7、+LeafCount(p-firstchild)+LeafCount (p-nextsibling); else k=0+LeafCount(p-firstchild)+LeafCount(p-nextsibling); else k=0; return k; /LeafCount,习题6.23: /按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0 void Print_BiTree(BiTree T,int i) if(T-rchild) Print_BiTree(T-rchild , i+1); for(j=1;jdatalchild) Print_BiTree(T-rchild, i+1 ); /Print_BiTree分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左.,