数据结构-树和森林的表示和遍历.ppt

树的遍历-后根(次序)遍历 后根(次序)遍历:若树不空，则先依次后根遍历各棵子树，然后访问根结点。 A B C D E F G H I J K A B C D E F G H I J K A E F B C I J K H G D 后根(次序)遍历序列为： 树的遍历-按层次遍历 按层次遍历:若树不空，则自上而下自左至右访问树中每个结点。 A B C D E F G H I J K A B C D E F G H I J K A B C D E F G 按层次遍历序列为： H I J K 树的遍历 树的二叉树表示: B C D E F G A B C E D G F A 树先根遍历 ABEFCDG 因此，树的先根遍历结果与其对应二叉树表示的先序遍历结果相同 树的遍历 树的二叉树表示: B C D E F G A B C E D G F A 树后根遍历 EFBCGDA 因此，树的后根遍历结果与其对应二叉树表示的中序遍历结果相同 森林的遍历 C B E F D G H I J K B C D E F G H I J K 1.森林中第一棵树的根点； 2.森林中第一棵树的子森林； 3.森林中其它树构成的森林。 森林可以分解成三部分： 森林的遍历-先序遍历 若森林不空，则 1）访问森林中第一棵树的根结点; 即：依次从左至右对森林中的每一棵树进行先根遍历。 2）先序遍历森林中第一棵树的子树森林; 3）先序遍历森林中(除第一棵树之外)其余树构成的森林。 A B D C E G F H I J K A B C D E F G H I J K 先根遍历序列为： A B C D E F G H I K J 森林的遍历-先序遍历 A B D C E G F H I J K 森林对应的二叉树： A B D C E G F H I J K 森林的遍历-中序遍历 森林不空，则 中序遍历森林中第一棵树的子树森林; 即：依次从左至右对森林中的每一棵树进行后根遍历。 访问森林中第一棵树的根结点; 中序遍历森林中(除第一棵树之外)其余树构成的森林。 中序遍历序列为： A B C E D G F K I J H 森林的遍历-中序遍历 A B D C E G F H I J K A B C D E F G H I J K A B D C E G F H I J K A B D C E G F H I J K * 树和森林的表示方法和遍历 树和森林的遍历 树的表示方法 小结和作业 森林和二叉树的对应关系 一、双亲表示法 二、孩子链表表示法 三、带双亲的孩子链表表示法 树的存储结构 四、树的孩子兄弟表示法 双亲表示法 用一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。 双亲表示法 A B C D E F G root=0 n=7 0 A 1 B 2 C 3 D 4 E 5 F 6 G data -1 0 0 0 2 2 5 parent 双亲表示法 data parent #define MAX_TREE_SIZE 100 结点结构: C语言的类型描述: typedef struct PTNode { TElemType data; int parent; // 双亲位置域 } PTNode; 双亲表示法 typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree; 树结构: 孩子链表表示法 1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域. 1.多重链表：每个结点有多个指针域，分别指向其子树的根 data child1 child2 ………. childD 孩子链表表示法 2）结点不同构：结点指针个数不等，为该结点的度d data child1 child2 ………. childD 2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表 孩子链表表示法 A B C D E F G root=0 n=7 data 0 A 1 B 2 C 3 D 4 E 5 F 6 G 1 2 3 firstchild 4 5 6 孩子链表表示法 typedef struct CTNode { int child; struct CTNode *nextchild; } *