二叉树遍历(递归—非递归转换).ppt

——遍历二叉树
制作人:计科系孙玉霞
数据结构
1/13/2018
1
数据结构——二叉树的遍历
遍历二叉树
二叉树的先序遍历
二叉树的中序遍历
二叉树的后序遍历
遍历二叉树
本次课主要内容
2
遍历二叉树
方法
先序遍历:先访问根结点,然后分别先序遍历左子树、右子树
中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树
后序遍历:先后序遍历左、右子树,然后访问根结点
按层次遍历:从上到下、从左到右访问各结点
D
L
R
LDR、LRD、DLR
RDL、RLD、DRL
返回目录
3
A
D
B
C
D L R
A
D L R
D L R
>
B
>
>
D
>
>
C
D L R
先序遍历序列:A B D C
二叉树的先序遍历
4
算法实现:
进入
非递归算法
递归算法
先序遍历
过程演示
5
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%d\t",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
主程序
Pre( T )
返回
返回
pre(T R);
返回
返回
pre(T R);
A
C
B
D
T
B
printf(B);
pre(T L);
B
T
A
printf(A);
pre(T L);
A
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
T
T
T
T
Back
6
非递归算法
A
B
C
D
E
F
G
p
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
访问:C
(4)
7
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
访问:C B E
p
(8)
8
A
B
C
D
E
F
G
i
P->A
P->D
P->G
访问:C B E
P=NULL
(9)
A
B
C
D
E
F
G
i
P->A
访问:C B E G D
p
(11)
A
B
C
D
E
F
G
i
P->A
P->F
访问:C B E G D
p
(12)
A
B
C
D
E
F
G
i
P->A
P->D
访问:C B E G
p
(10)
9
A
B
C
D
E
F
G
i
P->A
访问:C B E G D F
p=NULL
(13)
A
B
C
D
E
F
G
i
访问:C B E G D F A
p
(14)
A
B
C
D
E
F
G
i
访问:C B E G D F A
p=NULL
(15)
返回目录
10