数据结构A树2.ppt

文档介绍：

如果按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。
A
B
C
D
G
E
F
先序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则
(1)访问根结点;
(2)先序遍历左子树;
(3)先序遍历右子树。
A B C D F E G
A
B
C
D
G
E
F
先序遍历二叉树的递归算法
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
中序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则
(1)中序遍历左子树;
(2)访问根结点;
(3)中序遍历右子树。
C B D F A G E
A
B
C
D
G
E
F
中序遍历二叉树示例
中序遍历二叉树得:
a+b*(c-d)-e/f
-
+
a
*
e
/
-
f
b
d
c
中序遍历二叉树的递归算法
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
后序遍历二叉树的操作定义为:
若二叉树为空,则空操作;否则
(1)后序遍历左子树;
(2)后序遍历右子树;
(3)访问根结点。
C F D B G E A
A
B
C
D
G
E
F
后序遍历二叉树的递归算法
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 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
中序遍历二叉树的非递归算法示意图
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