ds6.3陆小马功钟浩.ppt

5. 非递归遍历二叉树 Push ( S, p ); p = p-lchild; } else { Pop ( S, p ); p = p-rchild; } } } 5. 非递归遍历二叉树 或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit ) { InitStack ( S ); Push ( S, bt ); while ( ! StackEmpty(S) ) { Pop ( S, p ); if ( p ) { visit ( p ); Push ( S, p-rchild ); // 先进栈，后访问，所以 Push ( S, p-lchild ); // 这里先让右子树进栈 } } } 树和二叉树 6.3 遍历二叉树及其应用 6.3 遍历二叉树及其应用 1. 遍历二叉树的方法 2. 先序、中序和后序遍历二叉树 3. 按层遍历二叉树 4. 遍历二叉树的应用 5. 非递归遍历二叉树 1. 遍历二叉树的方法 （1）何谓“遍历二叉树”？ 按一定的顺序逐个访问二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。 “遍历”是各种算法的基础。 （2）如何遍历二叉树？ 二叉树是一种非线性结构，而遍历的结果是一个线性的序列。 考虑二叉树的结构… D L R 1. 遍历二叉树的方法 根据二叉树的结构，分为三部分： L 左子树 D 根结点 R 右子树 （3）遍历二叉树的方法 先序遍历 DLR 中序遍历 LDR 后序遍历 LRD 由于其中的左右子树也是二叉树，属于递归结构，所以常常借助递归算法实现。 D L R 2. 先序、中序和后序遍历二叉树 （1）先序遍历二叉树 若二叉树为空，则空操作； 否则， 访问根结点； 先序遍历左子树； 先序遍历右子树。 例： ABCDEFGH D L R D L R B A C D E F G H B A C D E F G H （1）先序遍历二叉树 算法 //先序遍历二叉树T，对每个结点数据调用visit进行访问 void PreOrder ( BinTree T, Func visit ) { if ( T ) { visit( T-data ); //访问根结点 PreOrder( T-lchild, visit ); //先序遍历左子树 PreOrder( T-rchild, visit ); //先序遍历右子树 } } 2. 先序、中序和后序遍历二叉树 （2）中序遍历二叉树 若二叉树为空，则空操作； 否则， 中序遍历左子树； 访问根结点； 中序遍历右子树。 例： BDCEAGHF D L R D L R B A C D E F G H B A C D E F G H （2）中序遍历二叉树 算法 //中序遍历二叉树T，对每个结点数据调用visit进行访问 void InOrder ( BinTree T, Func visit ) { if ( T ) { InOrder( T-lchild, visit); //中序遍历左子树 visit( T-data ); //访问根结点 InOrder( T-rchild, visit); //中序遍历右子树 } } 2. 先序、中序和后序遍历二叉树 （3）后序遍历二叉树 若二叉树为空，则空操作； 否则， 后序遍历左子树； 后序遍历右子树。 访问根结点； 例： DECBHGFA D L R D L R B A C D E F G H B A C D E F G H （3）后序遍历二叉树 算法 //后序遍历二叉树T，对每个结点数据调用visit进行访问 void PostOrder ( BinTree T, Func visit ) { if ( T ) { PostOrder ( T-lchild, visit ); //后序遍历左子树 PostOrder ( T-rchild, visit ); //后序遍历右子树 visit( T-data ); //访问根结点 } } 3. 按层遍历二叉树 （1）按层次遍历 从第一层开始，同一层从左到右。 例： ABFCGDEH 一般借助队列进行遍历。 B A C D E F G H B A C D E F G H 3. 按层遍历二叉树 （2） 按层次遍历二叉树算法 void LevelOrder ( BinTree bt )