文档介绍：数据结构树
第一页，共99页。
中序遍历:
A的前驱是————，
B的前驱是————;
E的前驱是————；
D的前驱是————；
二叉树
A
B
C
E
F
G
H
D
K
X
M
Y
一个结点N如果有左子树，则该结点的前驱就是其左子树中最右的子孙P。
这个子孙结点的右链接域一定为空。
E
H
G
K
第二页，共99页。
中序遍历:
H的前驱是D，
G的前驱是B;
X的前驱是A
二叉树
A
B
C
E
F
G
H
D
K
X
M
Y
一个结点N如果没有左子树，则该结点的前驱就是其所有祖先中,最接近它的“右倾”祖先P。
这个结点N的左链接域本身就是空 。
第三页，共99页。
思考：二叉链表空间效率这么低，能否利用这些空闲区存放有用的信息或线索？
——我们可以用它来存放当前结点的直接前驱和后继等线索，以加快查找速度。
用二叉链表法存储包含n个结点的二叉树，结点的指针区域中会有n+1个空指针。
这就是线索二叉树（Threaded Binary Tree）
第四页，共99页。
线索二叉树的实现
规 定：
1）若结点有左子树，则Lchild指向其左孩子；
否则，Lchild指向其直接前驱(即线索)；
2）若结点有右子树，则Rchild指向其右孩子；
否则，Rchild指向其直接后继(即线索) 。
如何区别？
约定:
当flag域为0时,表示正常情况;
当flag域为1时,表示线索情况.
前驱(后继)
左(右)孩子
为区别两种不同情况，特增加两个标志域：
各1bit
Lflag
LChild
data
RChild
Rflag
第五页，共99页。
中序线索树
A
0
0
B
0
0
C
1
0
∧
D
1
1
E
1
1
F
1
∧
1
D, B, E, A, C, F
NULL
NULL
第六页，共99页。
二叉树
A
B
E
F
H
K
N
M
D
C
二叉树前序遍历线索树
A
B
M
C
K
D
N
F
H
E
二叉树中序遍历线索树
A
B
M
F
N
H
K
E
C
D
二叉树后序遍历线索树
A
B
M
D
K
H
N
F
C
E
第七页，共99页。
有关线索二叉树的几个术语：
线索链表：
线 索：
线索二叉树：
线 索 化：
用含flag的结点样式所构成的二叉链表
指向结点前驱和后继的指针
加上线索的二叉树
对二叉树以某种次序遍历使其变为线索二叉树的过程
线索化过程就是在遍历过程中修改空指针的过程：
将空的Lchild改为结点的直接前驱；
将空的Rchild改为结点的直接后继。
非空指针呢？仍然指向孩子结点（称为“正常情况”）
第八页，共99页。
例：【考研题】给定如图所示二叉树T，请画出与其对应的中序线索二叉树。
28
25
40
55
60
33
08
54
解:因为中序遍历序列是：55 40 25 60 28 08 33 54对应线索树应当按此规律连线，即在原二叉树中添加虚线。
Null
Null
第九页，共99页。
二叉线索树的结点结构定义
typedef struct
{
EType data;
BinaryTreeNode *LChild;
bool Lflag;
BinaryTreeNode *RChild;
bool Rflag;
} BinaryTreeNode；
第十页，共99页。