树和二叉树分析.ppt

先序遍历算法 DLR( tree *root ) { if (root !=NULL) { //非空二叉树 printf(“%d”,root-data); //访问D DLR(root-lchild); //递归遍历左子树 DLR(root-rchild); //递归遍历右子树 } return 0; } 中序遍历算法 LDR(tree *root) { if(root !=NULL) { LDR(root-lchild); printf(“%d”,root-data); LDR(root-rchild); } return 0 ;} 后序遍历算法 LRD (tree *root) { if(root !=NULL) { LRD(root-lchild); LRD(root-rchild); printf(“%d”,root-data); } return 0; } 结点数据类型自定义 typedef struct Node { int data; struct Node *lchild,*rchild； } tree; 三、对遍历的分析： 1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。 从虚线的出发点到终点的路径 上，每个结点经过3次。 A F E D C B G 第1次经过时访问＝先序遍历 第2次经过时访问＝中序遍历 第3次经过时访问＝后序遍历 A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: A D B C L R D L R D L R D A D C L R D 后序遍历序列： D B C A 后序遍历: B A B C D E F G H K 练习： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 4.4 树、森林与二叉树的转换 1.兄弟加线. 树和二叉树之间的对应关系 A B C D E F G 4.4 树、森林与二叉树的转换 2.保留双亲与第一孩子连线,删去与其他孩子的连线. A B C D E F G 树和二叉树之间的对应关系 1.兄弟加线. 3.顺时针转动,使之层次分明. 4.4 树、森林与二叉树的转换 树和二叉树之间的对应关系 2.保留双亲与第一孩子连线,删去与其他孩子的连线. 1.兄弟加线. A B C D E F G 3.顺时针转动,使之层次分明. 4.4 树、森林与二叉树的转换 树和二叉树之间的对应关系 2.保留双亲与第一孩子连线,删去与其他孩子的连线. 1.兄弟加线. G D A B E C F 树转换为二叉树 ⑴加线——树中所有相邻兄弟之间加一条连线。 ⑵去线——对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 ⑶层次调整——以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。 4.4 树、森林与二叉树的转换 a b e i d f h g c 根结点肯定没有右孩子！ 练习：将下列树转换成二叉树 森林转换为二叉树 ⑴ 将森林中的每棵树转换成二叉树； ⑵ 从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。 4.4 树、森林与二叉树的转换 F E D C B A G H I J B A F E D C G H I K K I F E H A B C G D 4.4 树、森林与二叉树的转换 二叉树转换为树或森林 ⑴ 加线——若某结点x是其双亲y的左孩子，则把结点x的右孩子、右孩子的右孩子、……，都与结点y用线连起来； ⑵ 去线——删去原二叉树中所有的双亲结点与右孩子结点的连线； ⑶ 层次调整——整理由⑴、⑵两步所得到的树或森林，使之层次分明。 4.4 树、森林与二叉树