数据结构第六章第三节.ppt

《数据结构第六章第三节.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章第三节.ppt（179页珍藏版）》请在三一办公上搜索。

1、6.4 树和森林,6.4.1 树的存储结构6.4.2 森林与二叉树的转换6.4.3 树和森林的遍历,6.4.1 树的存储结构,双亲表示法 孩子表示法 孩子兄弟表示法,双亲表示法,数组下标,找双亲易，找孩子难,双亲表示法,#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data;int parent;/双亲位置域PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;/结点数PTree;,孩子表示法,data,child1,child2,childd,data,child1,ch

2、ild2,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 struct TElemType data;ChildPtr firstchild;/孩子链表

3、头指针CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置CTree;,孩子兄弟表示法,typedef struct CSNode TElemType data;struct CSNode*firstchild;/指向结点的第1个孩子 struct CSNode*nextsibling;/指向第1个孩子的右兄第CSNode,*CSTree;,孩子兄弟表示法,易于实现各种操作,6.4.2 森林与二叉树的转换,typedef struct CSNode TElemType data;struct CSNode*firstch

4、ild,*nextsibling;CSNode,*CSTree;,typedef struct BiNode TElemType 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森林中第一棵树的根结点；,2森林中第

5、一棵树的子树森林；,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 C D A F E H J I G,树的遍

6、历和二叉树遍历的对应关系？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,树的遍历及应用,孩子兄弟表示 树的遍历算法 求树的深度 求树的叶子结点数 建立树的孩子兄弟链表存储结构 孩子链表结构 孩子链表结构的遍历 根据孩子链表建立孩子兄弟结构,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为空树，则直接返回 Visit(T-data)；/访问根结

7、点 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 PreOrderTraverseTree1(CSTree

8、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(CSTree T,Status(*Visit)(TElem

9、Type 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)(TElemType e)if(!T)return OK;/若T为空树，则直接返回

10、 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=NULLHeight(T)=max(Height(T-firstchild)+1,Height(T-nextsibling)其它,求树的深度,int Height_Tree(CSTree T)int h1,h2;if(!T)return 0;/若T

11、为空树 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=NULLLeafCount(T)=1 T-firstlchild=NULL LeafCount(T)=LeafCount(T-firstlchild)+LeafCount(T-nextsibling)其它,求树的叶子结点个数,Int LeafCount_Tree(

12、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),主调用,建立树的孩子兄弟链表存储结构,根据先根遍历的扩展序列建立 根据两种遍历序列建立（先根和后根）根据广义表表达式建立,R,

13、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,

14、F,R,A,D,B,E,F,C,S=(R(A(D,E),B,C(F),广义表表达式,(R(A(D,E),B,C(F),R,A,D,B,E,F,C,Status CreateCSTree(CSTree,R,A,D,B,E,F,C,S=(R(A(D,E),B,C(F),Status CreateCSTree(CSTree,1,S(1)=(R(A(D,E),B,C(F),root(1)=?hsub(1)=?tsub(1)=?,Status CreateCSTree(CSTree,1,S(1)=(R(A(D,E),B,C(F),root(1)=?hsub(1)=?tsub(1)=?,Status Cr

15、eateCSTree(CSTree,1,S(1)=(R(A(D,E),B,C(F),root(1)=?hsub(1)=?tsub(1)=?,Status CreateCSTree(CSTree,S(1)=(R(A(D,E),B,C(F),1,root(1)=Rhsub(1)=(A(D,E),B,C(F)tsub(1)=(),Status CreateCSTree(CSTree,S(1)=(R(A(D,E),B,C(F),1,root(1)=Rhsub(1)=(A(D,E),B,C(F)tsub(1)=(),Status CreateCSTree(CSTree,S(1)=(R(A(D,E),B,

16、C(F),1,root(1)=Rhsub(1)=(A(D,E),B,C(F)tsub(1)=(),R,T(1),Status CreateCSTree(CSTree,S(1)=(R(A(D,E),B,C(F),1,root(1)=Rhsub(1)=(A(D,E),B,C(F)tsub(1)=(),R,T(1),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=?hsub(2)=?tsub(2)=?,R,T(1),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=?hs

17、ub(2)=?tsub(2)=?,R,T(1),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=?hsub(2)=?tsub(2)=?,R,T(1),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=Ahsub(2)=(D,E)tsub(2)=(B,C(F),R,T(1),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=Ahsub(2)=(D,E)tsub(2)=(B,C(F),R,T(1),Stat

18、us CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=Ahsub(2)=(D,E)tsub(2)=(B,C(F),R,T(1),A,T(2),Status CreateCSTree(CSTree,S(2)=(A(D,E),B,C(F),2,root(2)=Ahsub(2)=(D,E)tsub(2)=(B,C(F),R,T(1),A,T(2),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=?hsub(3)=?tsub(3)=?,R,T(1),A,T(2),Status CreateCSTree(

19、CSTree,S(3)=(D,E),3,root(3)=?hsub(3)=?tsub(3)=?,R,T(1),A,T(2),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=?hsub(3)=?tsub(3)=?,R,T(1),A,T(2),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=Dhsub(3)=()tsub(3)=(E),R,T(1),A,T(2),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=Dhsub(3)=()tsub(3)=(E),

20、R,T(1),A,T(2),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=Dhsub(3)=()tsub(3)=(E),R,T(1),A,T(2),D,T(3),Status CreateCSTree(CSTree,S(3)=(D,E),3,root(3)=Dhsub(3)=()tsub(3)=(E),R,T(1),A,T(2),D,T(3),Status CreateCSTree(CSTree,S(4)=(),4,root(4)=?hsub(4)=?tsub(4)=?,R,T(1),A,T(2),D,T(3),Status CreateCST

21、ree(CSTree,S(4)=(),4,root(4)=?hsub(4)=?tsub(4)=?,R,T(1),A,T(2),D,T(3),Status CreateCSTree(CSTree,S(4)=(),4,root(4)=?hsub(4)=?tsub(4)=?,R,T(1),A,T(2),D,T(3),T(4)=NULL,Status CreateCSTree(CSTree,3,R,T(1),A,T(2),D,T(3),S(3)=(D,E),root(3)=Dhsub(3)=()tsub(3)=(E),Status CreateCSTree(CSTree,4,R,T(1),A,T(2)

22、,D,T(3),S(4)=(E),root(4)=?hsub(4)=?tsub(4)=?,Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=?hsub(4)=?tsub(4)=?,Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=?hsub(4)=?tsub(4)=?,Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=Ehsub(4)=()tsu

23、b(4)=(),Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=Ehsub(4)=()tsub(4)=(),Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=Ehsub(4)=()tsub(4)=(),E,T(4),Status CreateCSTree(CSTree,4,R,T(1),A,T(2),D,T(3),S(4)=(E),root(4)=Ehsub(4)=()tsub(4)=(),E,T(4),0,1,2,3,4,5

24、,6,7,1,2,3,4,5,6,7,树的孩子表示法,A,B,C,F,H,D,E,G,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,树的孩子表示法,typedef struct CTNode/孩子结点 int child;struct CTNode*next;*ChildPtr;Typedef struct TElemType data;ChildPtr firstchild;/孩子链表头指针CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置PTree;,0,1,2,3,4,5,6,7,1,2,3,4,5

25、,6,7,void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,树的先根遍历,A,B,F,H,D,E,G,C,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的

26、孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,1,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,

27、Visit);p=p-next;,1,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,1,0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTre

28、e_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,1,p(1),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.node

29、sv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,1,p(1),1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,1,p(1),1,2,

30、3,4,5,6,7,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int

31、v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.no

32、desv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p

33、(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1

34、),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子

35、链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-c

36、hild;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v

37、0(2),p(2),v0(3),p(3)=NULL,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3)=NULL,0,1,2,3,4,5,6,7,A,B,F,H

38、,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3)=NULL,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Sta

39、tus(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nod

40、esv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;

41、,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,2,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,

42、v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/

43、树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;whi

44、le(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3

45、,4,5,6,7,v0(2),p(2),v0(3),p(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),0,1,2,3,4,5,6,7,A,B,F,H

46、,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,3,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*

47、Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,4,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p

48、=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,4,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),v0(4),0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_D

49、FS(T,w,Visit);p=p-next;,4,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),v0(4),p(4)=NULL,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,4,p(1),1,2,3,4

50、,5,6,7,v0(2),p(2),v0(3),p(3),v0(4),p(4)=NULL,0,1,2,3,4,5,6,7,A,B,F,H,D,E,G,C,v0(1),void CTTree_DFS(CTree T,int v0,Status(*Visit)(TElemType e)/树的孩子链表的先根遍历 Visit(T.nodesv0.data)p=T.nodesv0.firstchild;while(p)w=p-child;CTTree_DFS(T,w,Visit);p=p-next;,4,p(1),1,2,3,4,5,6,7,v0(2),p(2),v0(3),p(3),v0(4),p(4