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

6 4树和森林 6 4 1树的存储结构6 4 2森林与二叉树的转换6 4 3树和森林的遍历 6 4 1树的存储结构 双亲表示法孩子表示法孩子兄弟表示法 双亲表示法 数组下标 找双亲易 找孩子难 双亲表示法 defineMAX TREE SIZE100typedefstructPTNode TElemTypedata intparent 双亲位置域 PTNode typedefstruct PTNodenodes MAX TREE SIZE intn 结点数 PTree 孩子表示法 data child1 child2 childd data child1 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 孩子链表 双亲位置 找孩子易找双亲也易 孩子表示法 typedefstructCTNode 孩子结点intchild structCTNode next ChildPtr Typedefstruct TElemTypedata ChildPtrfirstchild 孩子链表头指针 CTBox typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根的位置 CTree 孩子兄弟表示法 typedefstructCSNode TElemTypedata structCSNode firstchild 指向结点的第1个孩子structCSNode nextsibling 指向第1个孩子的右兄第 CSNode CSTree 孩子兄弟表示法 易于实现各种操作 6 4 2森林与二叉树的转换 typedefstructCSNode TElemTypedata structCSNode firstchild nextsibling CSNode CSTree typedefstructBiNode TElemTypedata structBiNode lchild rchild BiNode BiTree 树的孩子兄弟表示 二叉树的二叉链表示 树 二叉树 对应 森林转换成二叉树 二叉树转换成森林 6 4 3树和森林的遍历 树的遍历森林的遍历 树的遍历 先根 次序 遍历树 1 访问树的根结点 2 依次先根遍历树的每棵子树 ABCDE 后根 次序 遍历树 1 依次后根遍历树的每棵子树 2 访问树的根结点 BDCEA 1 森林中第一棵树的根结点 2 森林中第一棵树的子树森林 3 森林中其它树构成的森林 森林由三部分构成 森林的遍历 A B C D E F G H I J 森林的遍历 先序遍历森林若森林为非空 则按下述规则遍历之 1 访问森林中第一棵树的根结点 2 先序遍历森林中第一棵树的子树森林 3 先序遍历除去第一棵树之后剩余的树构成的森林 森林的遍历 中序遍历森林若森林为非空 则按下述规则遍历之 1 中序遍历森林中第一棵树的子树森林 2 访问森林中第一棵树的根结点 3 中序遍历除去第一棵树之后剩余的树构成的森林 森林的遍历 先序序列 ABCDEFGHIJ 中序序列 BCDAFEHJIG 树的遍历和二叉树遍历的对应关系 先根遍历 后根遍历 树 二叉树 森林 先序遍历 先序遍历 中序遍历 中序遍历 树的遍历及应用 孩子兄弟表示树的遍历算法求树的深度求树的叶子结点数建立树的孩子兄弟链表存储结构孩子链表结构孩子链表结构的遍历根据孩子链表建立孩子兄弟结构 R A D B E F H K C G 树的先根 次序 遍历 R A D B E F H K C G StatusPreOrderTraverseTree CSTreeT Status Visit TElemTypee if T returnOK 若T为空树 则直接返回Visit T data 访问根结点PreOrderTraverseTree T firstchild Visit PreOrderTraverseTree T nextsibling Visit returnOK 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 StatusPreOrderTraverseTree1 CSTreeT Status Visit TElemTypee if T returnOK 若T为空树 则直接返回Visit T data 访问根结点for p T firstchild p p p nextsibling PreOrderTraverseTree1 p firstchild Visit returnOK PreOrderTraverseTree1 R A D B E F H K C G 树的后根 次序 遍历 R A D B E F H K C G StatusPostOrderTraverseTree CSTreeT Status Visit TElemTypee if T returnOK 若T为空树 则直接返回PostOrderTraverseTree T firstchild Visit PostOrderTraverseTree T nextsibling Visit Visit T data 访问根结点returnOK PostOrderTraverseTree 树的后根 次序 遍历 R A D B E F H K C G StatusPostOrderTraverseTree1 CSTreeT Status Visit TElemTypee if T returnOK 若T为空树 则直接返回for p T firstchild p p p nextsibling PostOrderTraverseTree1 p firstchild Visit Visit T data 访问根结点returnOK PostOrderTraverseTree1 R A D B E F H K C G 求树的深度 Height T 0T NULLHeight T max Height T firstchild 1 Height T nextsibling 其它 求树的深度 intHeight Tree CSTreeT inth1 h2 if T return0 若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 0T NULLLeafCount T 1T firstlchild NULLLeafCount T LeafCount T firstlchild LeafCount T nextsibling 其它 求树的叶子结点个数 IntLeafCount Tree CSTreeT intnum1 num2 if T return0 若T为空树if T firstchild NULL return1 T为叶子结点num1 LeafCount BiTree T firstchild 求左子树的叶子数num2 LeafCount BiTree T nextsibling 求右子树的叶子数return num1 num2 LeafCount Tree count LeafCount Tree root 主调用 建立树的孩子兄弟链表存储结构 根据先根遍历的扩展序列建立根据两种遍历序列建立 先根和后根 根据广义表表达式建立 R B A C D E F R A D B E F C 孩子兄弟链表的建立 1 RAD E B CF 先序遍历的扩展序列 R B A C D E F R A D B E F C StatusCreateBiTree CSTree CreateBiTree 孩子兄弟链表的建立 1 RAD E B CF 假设一棵树的先根序列为RADEBCF 后根序序列为 DEABFCR 请画出该树 RADEBCF DEABFCR 先根序列 后根序列 孩子兄弟链表的建立 2 StatusCreatCSTree 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 R A D B E F C StatusCreateCSTree CSTree R A D B E F C S R A D E B C F StatusCreateCSTree CSTree 1 S 1 R A D E B C F root 1 hsub 1 tsub 1 StatusCreateCSTree CSTree 1 S 1 R A D E B C F root 1 hsub 1 tsub 1 StatusCreateCSTree CSTree 1 S 1 R A D E B C F root 1 hsub 1 tsub 1 StatusCreateCSTree CSTree S 1 R A D E B C F 1 root 1 Rhsub 1 A D E B C F tsub 1 StatusCreateCSTree CSTree S 1 R A D E B C F 1 root 1 Rhsub 1 A D E B C F tsub 1 StatusCreateCSTree 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 StatusCreateCSTree 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 StatusCreateCSTree CSTree S 2 A D E B C F 2 root 2 hsub 2 tsub 2 R T 1 StatusCreateCSTree CSTree S 2 A D E B C F 2 root 2 hsub 2 tsub 2 R T 1 StatusCreateCSTree CSTree S 2 A D E B C F 2 root 2 hsub 2 tsub 2 R T 1 StatusCreateCSTree CSTree S 2 A D E B C F 2 root 2 Ahsub 2 D E tsub 2 B C F R T 1 StatusCreateCSTree CSTree S 2 A D E B C F 2 root 2 Ahsub 2 D E tsub 2 B C F R T 1 StatusCreateCSTree 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 StatusCreateCSTree 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 StatusCreateCSTree CSTree S 3 D E 3 root 3 hsub 3 tsub 3 R T 1 A T 2 StatusCreateCSTree CSTree S 3 D E 3 root 3 hsub 3 tsub 3 R T 1 A T 2 StatusCreateCSTree CSTree S 3 D E 3 root 3 hsub 3 tsub 3 R T 1 A T 2 StatusCreateCSTree CSTree S 3 D E 3 root 3 Dhsub 3 tsub 3 E R T 1 A T 2 StatusCreateCSTree CSTree S 3 D E 3 root 3 Dhsub 3 tsub 3 E R T 1 A T 2 StatusCreateCSTree CSTree S 3 D E 3 root 3 Dhsub 3 tsub 3 E R T 1 A T 2 D T 3 StatusCreateCSTree CSTree S 3 D E 3 root 3 Dhsub 3 tsub 3 E R T 1 A T 2 D T 3 StatusCreateCSTree CSTree S 4 4 root 4 hsub 4 tsub 4 R T 1 A T 2 D T 3 StatusCreateCSTree CSTree S 4 4 root 4 hsub 4 tsub 4 R T 1 A T 2 D T 3 StatusCreateCSTree CSTree S 4 4 root 4 hsub 4 tsub 4 R T 1 A T 2 D T 3 T 4 NULL StatusCreateCSTree CSTree 3 R T 1 A T 2 D T 3 S 3 D E root 3 Dhsub 3 tsub 3 E StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 hsub 4 tsub 4 StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 hsub 4 tsub 4 StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 hsub 4 tsub 4 StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 Ehsub 4 tsub 4 StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 Ehsub 4 tsub 4 StatusCreateCSTree CSTree 4 R T 1 A T 2 D T 3 S 4 E root 4 Ehsub 4 tsub 4 E T 4 StatusCreateCSTree 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 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 树的孩子表示法 typedefstructCTNode 孩子结点intchild structCTNode next ChildPtr Typedefstruct TElemTypedata ChildPtrfirstchild 孩子链表头指针 CTBox typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根的位置 PTree 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 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 NULL 0 1 2 3 4 5 6 7 A B F H D E G C v0 1 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的先根遍历Visit T nodes v0 data p T nodes v0 firstchild while p w p child CTTree DFS T w Visit p p next 1 p 1 1 2 3 4 5 6 7 voidCTTree DFS CTreeT intv0 Status Visit TElemTypee 树的孩子链表的后根遍历p T nodes v0 firstchild while p w p child CTTree DFS T w Visit p p next Visit T nodes v0 data 树的后根遍历 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 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 A B D C E H F G 从孩子链表结构建立孩子兄弟结构 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 A B F H D E G C A B D C E H F G r q r nextsibling q 从孩子链表结构建立孩子兄弟结构 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree A B D C E H F G 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 p 1 first 1 1 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 p 1 first 1 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 p 1 first 1 1 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 1 v0 1 A T1 1 p 1 first 1 1 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 2 3 4 5 6 7 v0 2 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 2 3 4 5 6 7 v0 2 B T1 2 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 2 3 4 5 6 7 v0 2 B T1 2 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 1 2 3 4 5 6 7 v0 2 B T1 2 p 2 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 1 2 3 4 5 6 7 v0 2 B T1 2 p 2 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 1 2 v0 2 B T1 2 p 2 3 4 5 6 7 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 2 v0 1 A T1 1 p 1 first 2 1 1 2 v0 2 B T1 2 p 2 3 4 5 6 7 q 1 0 1 2 3 4 5 6 7 StatusCreateCSTree CTreeT intv0 CSTree 3 v0 1 A T1 1 p 1 first 3 1 2 v0 2 B T1 2 p 2 3 4 5 6 7 q 1 0 1