二叉树的遍历.

Presentation on theme: "二叉树的遍历."— Presentation transcript:

1 二叉树的遍历

2 二叉树遍历 (Binary Tree Traversal)
所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 设访问根结点记作 V 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 VLR 镜像 VRL 中序 LVR 镜像 RVL 后序 LRV 镜像 RLV

3 中序遍历 (Inorder Traversal)
中序遍历二叉树算法的框架是： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (V)； 中序遍历右子树 (R)。 遍历结果 a + b * c - d - e / f 表达式语法树

4 二叉树递归的中序遍历算法 template <class Type> void BinaryTree <Type>::InOrder ( ) { InOrder ( root ); } template <class Type> void BinaryTree <Type>:: InOrder ( BinTreeNode <Type> *current ) { if ( current != NULL ) { InOrder ( current→leftChild ); cout << current→data; InOrder ( current→rightChild );

5 中序遍历二叉树的递归过程图解

6 前序遍历 (Preorder Traversal)
前序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 访问根结点 (V)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 - + a * b - c d / e f

7 二叉树递归的前序遍历算法 template <class Type> void BinaryTree <Type>::PreOrder ( ) { PreOrder ( root ); } template <class Type> void BinaryTree<Type>:: PreOrder ( BinTreeNode <Type> *current ) { if ( current != NULL ) { cout << current→data; PreOrder ( current→leftChild ); PreOrder ( current→rightChild );

8 后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (V)。 遍历结果 a b c d - * + e f / -

9 二叉树递归的后序遍历算法 template <class Type> void BinaryTree <Type>::PostOrder ( ) { PostOrder ( root ); } template <class Type> void BinaryTree<Type>:: PostOrder ( BinTreeNode <Type> *current ) { if ( current != NULL ) { PostOrder ( current→leftChild ); PostOrder ( current→rightChild ); cout << current→data;

10 应用二叉树遍历的事例 利用二叉树后序遍历计算二叉树结点个数及二叉树的高度 template <class Type> int BinaryTree<Type> :: Size ( const BinTreeNode <Type> *t ) const { if ( t == NULL ) return 0; else return 1 + Size ( t→leftChild ) + Size ( t→rightChild ); }

11 template <class Type>
int BinaryTree<Type> :: Depth ( const BinTreeNode <Type> *t ) const { if ( t == NULL ) return -1; else return 1 + Max ( Depth ( t→leftChild ), Depth ( t→rightChild ) ); }

12 二叉树结点定义 传统方法：利用栈的非递归遍历算法 typedef struct BitreeNode {
TreeDataType data; struct BitreeNode * leftChild, * rightChild; } BitreeNode, * Bitree;

13 传统方法：利用栈的前序遍历非递归算法 void PreOrderTraverse ( Bitree T ) {
StackType S; BitreeNode * p; S.makeEmpty( ); S.Push(null); p = T; //初始化 while ( p ) { printf ( p→data ); if ( p→rightChild ) S.Push ( p→rightChild ); //预留右子树指针在栈中 if ( p→leftChild ) p = p→leftChild;//进左子树 else { p = S.getTop( ); S.Pop( ); } //进右子树 }

14 传统方法：利用栈的中序遍历非递归算法 void InOrderTraverse ( Bitree T ) {
StackType S; BitreeNode * p; S.makeEmpty( ); p = T; //初始化 do{ while ( p ) { S.Push(p); p = p→leftChild; } if ( !S.IsEmpty( ) ) { //栈非空 p = S.getTop( ); S.Pop( ); //退栈 printf ( p→data); //访问根结点 p = p→rightChild; //向右链走 } } while ( p || !S.IsEmpty( ) );

15 传统方法：利用栈的后序遍历非递归算法 后序遍历时使用的栈的结点定义 typedef struct StackNode {
enum tag{ L, R }; BitreeNode * ptr; } StackNode; void PostOrderTraverse ( Bitree T ) { //后序遍历根为 T 的二叉树, 存储结构为二叉链//表, S 是存储所经过二叉树结点的工作栈。其//中, tag 是结点标记。当 tag＝L 时, 表示刚才 //是在左子树中, 从左子树退出时, 还要去遍历 ptr tag (LR)

16 //右子树。当 tag ＝R 时, 表示刚才是在右子树//中, 在从右子树中退出时, 去访问位于栈顶的
//结点。 StackType S; BitreeNode * p; StackNode w; S.makeEmpty( ); p = T; //初始化 do { while ( p ) { w.ptr = p; w.tag = L; S.Push(w); p = p→leftChild; } //遍历左子树并把经过结点加左标记进栈 int continue = 1; //继续循环标记

17 while ( continue && !S.IsEmpty( ) ) {
w = S.getTop( ); S.Pop( ); p = w.ptr; switch (w.tag) { //判断栈顶的tag标记 case L : w.tag = R; S.Push(w); continue = 0; //修改栈顶tag p = p→rightChild; break; case R : printf (p→data); break; } } while ( p || !S.IsEmpty( ) );

18 二叉树遍历的游标类 (Tree Iterator)
二叉树的游标抽象基类 template <class Type> class TreeIterator { public: TreeIterator ( const BinaryTree <Type> & BT ) : T (BT), current (NULL) { } virtual ~TreeIterator ( ) { } virtual void First ( ) = 0; virtual void operator ++ ( ) = 0; int operator +( ) const {return current != NULL; } const Type & operator ( ) ( ) const;

19 protected: const BinaryTree <Type> & T; const BinTreeNode <Type> * current; private: TreeIterator ( const TreeIterator & ) { } TreeIterator & operator = ( const TreeIterator & ) const ; };

20 template <class Type>
const Type &TreeIterator<Type> :: operator ( ) const { if ( current == NULL ) { cout << "非法访问" << endl; exit (1); } return current→GetData ( ); }

21 后序游标类 为记忆走过的结点，设置一个工作栈： S.PopTim = 0, 1或2，表示第几次退栈，用以 判断下一步向哪一个方向走。
后序遍历时，每遇到一个结点，先把它推入 栈中，让 S.PopTim = 0。 在遍历其左子树前，改结点的 S.PopTim = 1， 将其左子女推入栈中。 在遍历完左子树后，还不能访问该结点，要 结点地址 *Node 退栈次数 S.PopTim

22 继续遍历右子树，此时改结点的S.PopTim = 2，并把其右子女推入栈中。在遍历完右子树后，结点才退栈访问。

23 后序遍历游标类的定义 template <class Type> struct stkNode {
//后序遍历使用的递归工作栈 结点定义 const BinTreeNode <Type> *Node; //结点指针 int PopTim; //退栈次数 stkNode ( const BinTreeNode <Type> *N = NULL ) : Node (N), PopTim (0) { } } template <class Type> class PostOrder : public TreeIterator <Type> { public: PostOrder ( const BinaryTree <Type> & BT );

24 后序游标类成员函数的实现 ~PostOrder ( ) { } void First ( ); //定位到后序次序下第一个结点
void operator ++ ( ); //定位到后序次序下的下一个结点 protected: Stack < StkNode<Type> > st; //工作栈 } 后序游标类成员函数的实现

25 template <class Type>PostOrder <Type> ::
PostOrder ( const BinaryTree <Type> &BT ) : TreeIterator <Type> (BT) { st.Push ( StkNode<Type>( T.GetRoot( ) ) ); } template <class Type> void PostOrder <Type> :: First ( ) { st.MakeEmpty ( ); if ( T.GetRoot ( ) != NULL ) st.Push ( StkNode <Type>( T.GetRoot ( ) ) ); operator ++ ( );

26 template <class Type> void PostOrder <Type> ::
operator ++ ( ) { if ( st.IsEmpty ( ) ) { if ( current == NULL ) { cout << "已经遍历结束" << endl; exit (1); } current = NULL; return; //遍历完成 StkNode <Type> Cnode; for ( ; ; ) { //循环,找后序下的下一个结点 Cnode = st.Pop ( ); if ( ++Cnode.PopTim == 3 ) //从右子树退出 { current = Cnode.Node; return; }

27 st.Push ( Cnode ); //否则加一进栈
if ( Cnode.PopTim == 1 ) { //左子女进栈 if ( Cnode.Node→GetLeft ( ) != NULL ) st.Push ( StkNode <Type> ( Cnode.Node→GetLeft ( ) ) ); } else { // =2,右子女进栈 if ( Cnode.Node→GetRight ( ) != NULL ) st.Push ( StkNode <Type> ( Cnode.Node→GetRight ( ) ) );

28 中序游标类 中序遍历与后序遍历走过的路线一样，只是在从左子树退出后立即访问根结点，再遍历右子树。中序遍历也要使用一个递归工作栈 st。 中序游标类的定义 template <class Type> class InOrder : public PostOrder <Type> { public: InOrder ( BinaryTree <Type> & BT ) : PostOrder <Type> ( BT ) { }

29 中序游标类operator ++( )操作的实现
void First ( ); void operator ++ ( ); }; 中序游标类operator ++( )操作的实现 template <class Type> void InOrder <Type>:: operator ++ ( ) { if ( st.IsEmpty ( ) ) { if ( current == NULL ) { cout << "已经遍历完成" << endl; exit (1); } current = NULL; return; } StkNode <Type> Cnode;

30 for ( ; ; ) { //循环,找中序下的下一个结点
Cnode = st.Pop ( ); //退栈 if ( ++Cnode.PopTim == 2 ) { //从左子树退出，成为当前结点 current = Cnode.Node; if ( Cnode.Node→GetRight ( ) != NULL ) st.Push ( StkNode <Type> ( Cnode.Node→GetRight ( ) ) ); return; } st.Push ( Cnode ); //否则加一进栈

31 层次序游标类 if ( Cnode.Node→GetLeft ( ) != NULL )
st.Push ( StkNode <Type> ( //左子女进栈 Cnode.Node→GetLeft ( ) ) ); } 层次序游标类 从根开始逐层访 问，用 FIFO 队列 实现。 遍历顺序

32 层次序游标类的定义 template <class Type> class LevelOrder :
public TreeIterator <Type> { public: LevelOrder ( const BinaryTree <Type> & BT ); ~LevelOrder ( ) { } void First ( ); void operator ++ ( ); protected: Queue < const BinTreeNode <Type> * > qu; };

33 层次序游标类的operator ++ ( )操作
template <class Type> LevelOrder <Type>:: LevelOrder ( const BinaryTree <Type> & BT ) : TreeIterator <Type> ( BT ) { qu.EnQueue ( T.GetRoot ( ) ); } template <class Type> viod LevelOrder<Type> :: First ( ) { //初始化：只有根结点在队列中 qu.MakeEmpty ( ); if ( T.GetRoot ( ) ) qu.EnQueue ( T.GetRoot ( ) ); operator ++ ( ); }

34 template <class Type>
void LevelOrder<Type> :: operator ++ ( ) { if ( qu.IsEmpty ( ) ) { if ( current == NULL ) { cout << "已经遍历完成" << endl; exit (1);} current = NULL; return; } current = qu.DeQueue ( ); //退队 if ( current→GetLeft ( ) != NULL ) //左子女 qu.EnQueue ( current→GetLeft ( ) ); //进队列 if ( current→GetRight ( ) != NULL ) //右子女 qu.EnQueue ( current→GetRight ( ) ); //进队列