2021年7基本检索与周游.ppt

2. 二元树周游（遍历）
1）周游次序
在二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历）
★ LRD：后根次序周游（后根遍历）
★ DLR：先根次序周游（先根遍历）
★ RDL：逆中根次序周游
★ RLD：逆后根次序周游
★ DRL：逆先根次序周游
*
7 基本检索与周游
*
2）二元树周游算法
⑴ 中根次序周游
中根次序周游的递归表示
procedure INORDER(T)
//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//
if T≠0 then
call INORDER(LCHILD(T))
call VISIT(T)
call INORDER(RCHILD(T))
endif
end INORDER
*
7 基本检索与周游
*
⑵先根次序周游
先根次序周游的递归表示
procedure PREORDER(T)
//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//
if T≠0 then
call VISIT(T)
call PREORDER(LCHILD(T))
call PREORDER(RCHILD(T))
endif
end PREORDER
*
7 基本检索与周游
*
⑵后根次序周游
后根次序周游的递归表示
procedure POSTORDER(T)
//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//
if T≠0 then
call POSTORDER(LCHILD(T))
call POSTORDER(RCHILD)
call VISIT(T)
endif
end PREORDER
*
7 基本检索与周游
*
A
B
C
D
E
F
G
H
I
左图中：
中根次序周游的输出是：FDHGIBEAC
先根次序周游的输出是：ABDFGHIEC
后根次序周游的输出是：FHIGDEBCA
*
7 基本检索与周游
*
注：
一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。
如已知一棵二元树的中根遍历次序是：DGBEAFHC
先根遍历次序是：ABDGECFH
则这棵二元树唯一确定如下:
A
B
D
E
G
C
F
H
*
7 基本检索与周游
*
当输入的树T有n≥0个结点时，设t(n)和s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个结点所需要的时间和空间是Θ(1)，则t(n)=Θ(n), s(n)=Θ(n)。
证明：
时间：由于已知访问一个结点所需要的时间是Θ(1)，故可用常数c1限界。
设T的左子树中的结点数是n1，则t(n)有：
t(n)=maxn1{t(n1)+t(n-n1-1)+c1} n≥1
其中，t(0)≤c1。
归纳法证明t(n)≤c2n+c1，其中c2是一使得c2≥2c1的常数。
1)当n=0时，成立
2)假定当n=0,1,…,m-1时均成立。则当n=m时有，
设T是一棵有m个结点的树，T左子树结点数为n1,则
t(n)＝maxn1{t(n1)+t(n-n1-1)+c1}
≤maxn1{c2n1+c1+c2(n-n1-1)+c1+c1}
＝maxn1{c2n+3c1-c2}
≤c2n+c1
同理，存在c'2和c'1有t(n)≥c'2n+c'1。所以t(n)=Θ(n)
空间：若T的深度为d，则所需空间为Θ(d), d≤n，所以s(n)=Θ(n)。
*
7 基本检索与周游
*