《数据结构第六章 第三节》由会员分享，可在线阅读，更多相关《数据结构第六章 第三节（179页珍藏版）》请在金锄头文库上搜索。
1、6.4 树和森林,6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历,6.4.1 树的存储结构,双亲表示法孩子表示法孩子兄弟表示法,双亲表示法,数组下标,找双亲易，找孩子难,双亲表示法,#define MAX_TREE_SIZE 100 typedef struct PTNodeTElemType data;int parent; /双亲位置域 PTNode;typedef structPTNode nodesMAX_TREE_SIZE;int n; /结点数 PTree;,孩子表示法,data,child1,child2,childd,data,child1
2、,child2,childd,degree,n个结点度为k的树中有 个空链域,n(k-1)+1,nk-(n-1)=,节省空间，但操作不便,孩子表示法,孩子链表,找孩子易 找双亲难,孩子表示法,A,B,C,D,R,E,F,G,H,K,0,1,2,3,4,5,6,7,8,9,4,4,4,0,-1,0,2,6,6,6,孩子链表,双亲位置,找孩子易 找双亲也易,孩子表示法,typedef struct CTNode/孩子结点int child;struct CTNode *next; *ChildPtr;Typedef structTElemType data;ChildPtr firstchild;
3、 /孩子链表头指针 CTBox;typedef structCTBox nodesMAX_TREE_SIZE;int n, r; /结点数和根的位置 CTree;,孩子兄弟表示法,typedef struct CSNodeTElemType data;struct CSNode *firstchild; /指向结点的第1个孩子struct CSNode *nextsibling; /指向第1个孩子的右兄第 CSNode, *CSTree;,孩子兄弟表示法,易于实现各种操作,6.4.2 森林与二叉树的转换,typedef struct CSNodeTElemType data;struct CS
4、Node *firstchild,*nextsibling; CSNode,*CSTree;,typedef struct BiNodeTElemType data;struct BiNode *lchild,*rchild; BiNode,*BiTree;,树的孩子兄弟表示,二叉树的二叉链表示,树,二叉树,对应,森林转换成二叉树,二叉树转换成森林,6.4.3 树和森林的遍历,树的遍历森林的遍历,树的遍历,先根（次序）遍历树 （1）访问树的根结点 （2）依次先根遍历树的每棵子树,A B C D E,后根（次序）遍历树 （1）依次后根遍历树的每棵子树 （2）访问树的根结点,B D C E A,1
5、森林中第一棵树的根结点；,2森林中第一棵树的子树森林；,3森林中其它树构成的森林。,森林由三部分构成：,森林的遍历,A,B,C,D,E,F,G,H,I,J,森林的遍历,先序遍历森林若森林为非空，则按下述规则遍历之 （1）访问森林中第一棵树的根结点 （2）先序遍历森林中第一棵树的子树森林； （3）先序遍历除去第一棵树之后剩余的树构成的森林,森林的遍历,中序遍历森林若森林为非空，则按下述规则遍历之 （1）中序遍历森林中第一棵树的子树森林； （2）访问森林中第一棵树的根结点 （3）中序遍历除去第一棵树之后剩余的树 构成的森林,森林的遍历,先序序列,A B C D E F G H I J,中序序列,B
6、 C D A F E H J I G,树的遍历和二叉树遍历的对应关系 ？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,树的遍历及应用,孩子兄弟表示 树的遍历算法求树的深度求树的叶子结点数建立树的孩子兄弟链表存储结构孩子链表结构孩子链表结构的遍历根据孩子链表建立孩子兄弟结构,R,A,D,B,E,F,H,K,C,G,树的先根（次序）遍历,R,A,D,B,E,F,H,K,C,G,Status PreOrderTraverseTree(CSTree T, Status(*Visit)(TElemType e)if(!T) return OK; /若T为空树，则直接返回
7、Visit(T-data)；/访问根结点PreOrderTraverseTree(T-firstchild,Visit)；PreOrderTraverseTree(T-nextsibling,Visit) ; return OK; /PreOrderTraverse,树的先根（次序）遍历,R,A,D,B,E,F,H,K,C,G,p=T-firstchild,p=p-nextsibling,for(p=T-firstchild; p ; p=p-nextsibling)visit(p-firstchild);,树的先根（次序）遍历,R,A,D,B,E,F,H,K,C,G,Status PreOr
8、derTraverseTree1(CSTree T, Status(*Visit)(TElemType e)if(!T) return OK; /若T为空树，则直接返回Visit(T-data)；/访问根结点for(p=T-firstchild; p; p=p-nextsibling)PreOrderTraverseTree1(p-firstchild,Visit)；return OK; /PreOrderTraverseTree1,R,A,D,B,E,F,H,K,C,G,树的后根（次序）遍历,R,A,D,B,E,F,H,K,C,G,Status PostOrderTraverseTree(C
9、STree T, Status(*Visit)(TElemType e)if(!T) return OK; /若T为空树，则直接返回PostOrderTraverseTree(T-firstchild,Visit)；PostOrderTraverseTree(T-nextsibling,Visit) ; Visit(T-data)；/访问根结点return OK; /PostOrderTraverseTree,树的后根（次序）遍历,R,A,D,B,E,F,H,K,C,G,Status PostOrderTraverseTree1(CSTree T, Status(*Visit)(TElemTy
10、pe e)if(!T) return OK; /若T为空树，则直接返回for(p=T-firstchild; p; p=p-nextsibling)PostOrderTraverseTree1(p-firstchild,Visit)；Visit(T-data)；/访问根结点return OK; /PostOrderTraverseTree1,R,A,D,B,E,F,H,K,C,G,求树的深度,Height(T)=0 T=NULL Height(T)=max(Height(T-firstchild)+1, Height(T-nextsibling) 其它,求树的深度,int Height_Tre
11、e(CSTree T)int h1, h2;if(!T) return 0; /若T为空树h1=Height_BiTree(T-firstchild)； /求左子树的高度h2=Height_BiTree(T-nextsibling)；/求右子树的高度return (max(h1+1), h2); /Height_BiTree,R,A,D,B,E,F,H,K,C,G,求树的叶子结点个数,LeafCount(T)=0 T=NULL LeafCount(T)=1 T-firstlchild=NULL LeafCount(T)=LeafCount(T-firstlchild) + LeafCount(
12、T-nextsibling) 其它,求树的叶子结点个数,Int LeafCount_Tree(CSTree T)int num1, num2;if(!T) return 0; /若T为空树if(T-firstchild=NULL) return 1; /T为叶子结点num1=LeafCount_BiTree(T-firstchild)； /求左子树的叶子数num2=LeafCount_BiTree(T-nextsibling)； /求右子树的叶子数return (num1 + num2); /LeafCount_Tree,count=LeafCount_Tree(root),主调用,建立树的孩
13、子兄弟链表存储结构,根据先根遍历的扩展序列建立根据两种遍历序列建立（先根和后根）根据广义表表达式建立,R,B,A,C,D,E,F,R,A,D,B,E,F,C,孩子兄弟链表的建立（1）,R A D E B C F ,先序遍历的扩展序列,R,B,A,C,D,E,F,R,A,D,B,E,F,C,Status CreateBiTree(CSTree /CreateBiTree,孩子兄弟链表的建立（1）,R A D E B C F ,假设一棵树的先根序列为RADEBCF ，后根序序列为. DEABFCR, 请画出该树,R A D E B C F,D E A B F C R,先根序列,后根序列,孩子兄弟链表的建立（2）,Status CreatCSTree(CSTree ,孩子兄弟链表的建立（3）,R,B,A,C,D,E,F,R,A,D,B,E,F,C,S=(R(A(D, E), B, C(F),广义表表达式,(R(A(D, E), B, C(F),
