浙江大学：《数据结构与算法》第六章（6-3） 遍历二叉树和线索二叉树

63遍历二叉树和线索二叉树 63.1遍历二叉树 如果按某条搜索路径巡 访树中每个结点,使得 每个结点均被访问一次, 而且仅被访问一次

6.3遍历二叉树和线索二叉树 6.3.1遍历二叉树 如果按某条搜索路径巡 访树中每个结点，使得 每个结点均被访问一次， 而且仅被访问一次。 A B C D G E F

先序遍历二叉树的操作定义为: 若二叉树为空,则空操作; 否贝 A (1)访问根结点; (2)先序遍历左子树; B E (3)先序遍历右子树 DG ABCDFEG F

先序遍历二叉树的操作定义为： 若二叉树为空，则空操作； 否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 A B C D F E G A B C D G E F

先序遍历二叉树的递归算法 Status PreOrder Traverse(BiTree T, Status(* Visit)(TElem Type e)i if(T)i if (Visit(T->data)) if (PreOrder Traverse(T->lchild, Visit)) if(PreOrder Traverse(T->rchild, Visit) return OK return error. felse return OK 3//PreOrder Traverse

先序遍历二叉树的递归算法 Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (Visit(T->data)) if (PreOrderTraverse(T->lchild,Visit)) if (PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; }else return OK; }//PreOrderTraverse

中序遍历二叉树的操作定义为: 若二叉树为空,则空操作; 否贝 A (1)中序遍历左子树; B E (2)访问根结点; (3)中序遍历右子树 DG CBDFAG E F

中序遍历二叉树的操作定义为： 若二叉树为空，则空操作； 否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 C B D F A G E A B C D G E F

中序遍历二叉树示例 中序遍历二叉树得 a+b米(C-d)-e/f

中序遍历二叉树示例 中序遍历二叉树得: a+b*(c-d)-e/f - + a * e / - f b c d

中序遍历二叉树的递归算法 Status In Order Traverse(BiTree T, Status( Visit) (TElem Type e) if(T)i if(InOrder Traverse(T->lchild, Visit)) if (Visit(T->data)) if(InOrder Traverse(T->rchild, Visit)) return OK return ErroR Else return OK /nOrder Traverse

中序遍历二叉树的递归算法 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(T->lchild,Visit)) if (Visit(T->data)) if (InOrderTraverse(T->rchild,Visit)) return OK; return ERROR; }else return OK; }//InOrderTraverse

后序遍历二叉树的操作定义为: 若二叉树为空,则空操作; 否贝 A (1)后序遍历左子树; (2)后序遍历右子树; B E (3)访问根结点。 DG CFDBGEA F

后序遍历二叉树的操作定义为： 若二叉树为空，则空操作； 否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 C F D B G E A A B C D G E F

后序遍历二叉树的递归算法 Status PostOrder Traverse(BiTree T, Status(= Visit )(TElem Type e))i if(T)i if (PostOrder Traverse(T->lchild, Visit) if(PostOrder Traverse(T->rchild, Visit) if( Visit(T->data)) return OK; return ErRoR Else return OK 3//PostOrder Traverse

后序遍历二叉树的递归算法 Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (PostOrderTraverse(T->lchild,Visit)) if (PostOrderTraverse(T->rchild,Visit)) if (Visit(T->data)) return OK; return ERROR; }else return OK; }//PostOrderTraverse

中序遍历二叉树的非递归算法 Status InOrder Traverse(BiTree T, status(* Visit TElem Type e)i InitStack(S); Push(S,T) while(!Stack Empty(s)i while( GetTop(s,p)&& p)Push(s, p->lchild) Pop(s, p) if ( StackEmpty(s)& Pop(S, p); if(! Visite(p->data)) return ERROR Push(s, p->rchild) 1) return OK )//nOrder Traverse

中序遍历二叉树的非递归算法 Status InOrderTraverse(BiTree T, Status(* Visit) (TElemType e)){ InitStack(S); Push(S,T); while(!StackEmpty(S)){ while(GetTop(S,p) && p)Push(S,p->lchild); Pop(S, p); if (!StackEmpty(S)){ Pop(S,p); if (!Visite(p->data)) return ERROR; Push(S,p->rchild); } } return OK; }//InOrderTraverse

中序遍历二叉树的非递归算法 示意图 A Pop Get Top<--NULL B E p p C—B—A—S DG A F CBDFA CBDFAGE

中序遍历二叉树的非递归算法 示意图 C B D F A G E A B C D G E F A B C NULL S GetTop<-- p A S Pop p C B D F A