树和二叉树的遍历.pptVIP

二叉树的周游 按照一定的顺序对二叉树的每一个结点都访问一次（仅访问一次），得到一个由该二叉树的所有结点组成的序列，这一过程称为二叉树的周游. 二叉树的周游 先序周游 中序周游 后序周游 按层次周游 先序周游 先访问根结点,然后分别先序周游左子树、右子树 中序周游 先中序周游左子树，然后访问根结点，最后中序周游右子树 后序周游 先后序周游左、右子树，然后访问根结点 按层次周游 从上到下、从左到右访问各结点 递归算法 * 5.3 二叉树的周游 常用二叉树的周游方法 根 左 子 树 右 子 树 D L R LDR、LRD、DLR RDL、RLD、DRL 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 - e f c d 先序周游： 中序周游： 后序周游： 层次周游： - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f 前序周游 中序周游 后序周游 void preorder(BiTree bt) { if(bt!=NULL) { printf(%d\t,bt-data); preorder(bt-lchild); preorder(bt-rchild); } } 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 A C B D T B printf(B); pre(T L); B T A printf(A); pre(T L); A pre(T R); T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 非递归算法(中序周游) p A B C D E F G i P-A (1) A B C D E F G p i P-A P-B (2) A B C D E F G p i P-A P-B P-C (3) p=NULL A B C D E F G i P-A P-B (4) P-C p=NULL A B C D E F G i P-A P-B 访问：C (5) p A B C D E F G i P-A P-B 访问：C (5) p A B C D E F G i P-A 访问：C B (5) A B C D E F G i P-A P-D 访问：C B p (6) A B C D E F G i P-A P-D P-E 访问：C B p (7) A B C D E F G i P-A P-D P-E 访问：C B P=NULL (7) A B C D E F G i P-A P-D 访问：C B E p (8) P-G A B C D E F G i P-A P-D 访问：C B E p (8) P=NULL A B C D E F G i P-A P-D P-G 访问：C B E (9) A B C D E F G i P-A P-D 访问：C B E G p (10) A B C D E F G i P-A P-D 访问：C B E G P=NULL (10) A B C D E F G i P-A 访问：C B E G D p (11)