1
上节回顾
7.3 二叉树的设计和实现
7.3.1 二叉树的存储结构
7.3.2 二叉链存储结构的二叉树操作实现
2
7.4 二叉树遍历
7.4.1 二叉树遍历
1,遍历定义 ——
2,遍历用途 ——
3,遍历方法 ——
指按照某种顺序访问二叉树中的每个结点，
使每个结点被访问一次且仅被访问一次。
（或指按某条搜索路线遍访每个结点且不
重复）。
它是树结构插入、删除、修改、查找和排
序运算的前提，是二叉树一切运算的基础
和核心。
对每个结点的查看通常都是, 先左后
右, 。
3
4,遍历规则 ———
二叉树由根、左子树、右子树构成，定义为 D,L,R
以根结点为参照系
注：, 先、中、后, 的意思是指访问的结点 D是先于子树出
现还是后于子树出现。
?D,L,R的组合定义了六种可能的遍历方案：
LDR,LRD,DLR,DRL,RDL,RLD
?若限定 先 左 后 右,则有三种实现方案：
DLR LDR LRD
先 序遍历 中 序遍历 后 序遍历
4
5、二叉树遍历的基本方法
有三种,先 序遍历 (DLR),中 序遍历 (LDR),后 序遍历 (LRD)
通常可以把二叉树遍历操作设计成递归算法。
（一） 先序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
（ 1）访问根结点；
（ 2）先序遍历根结点的左子树；
（ 3）先序遍历根结点的右子树。
（二） 中序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
(1）中序遍历根结点的左子树；
（ 2）访问根结点；
5
（ 3）中序遍历根结点的右子树。
（三） 后序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
（ 1）后序遍历根结点的左子树；
（ 2）后序遍历根结点的右子树；
（ 3）访问根结点。
（四） 二叉树 的层序遍历算法：
(1)初始化设置一个队列；
(2)把根结点指针入队列；
(3)当队列非空时，循环执行步骤 (3.a)到步骤 (3.c):
6
(3.a)出队列取得一个结点指针，访问该结点；
(3.b)若该结点的左子树非空，则将该结点的左子树指针入
队列；
(3.c)若该结点的右子树非空，则将该结点的右子树指针入
队列；
（ 4）结束。
注意,一个 二叉树的遍历序列 不能决定一棵 二叉树，但 先
序（或后序）和中序遍历序列的组合 可以 惟一确定 一棵二叉
树。而先序和后序遍历则不能。
7
例 1,先序遍历的结果是：
中序遍历的结果是：
后序遍历的结果是：
A
B C
D E
D B E A C
D E B C A
口诀：
DLR— 先序遍历，即 先根 再左再右
LDR— 中序遍历，即 先左 再根 再右
LRD— 后序遍历，即 先左再右 再根
A B D E C
8
+
*
A
*
/
E
D
C
B
先序遍历结果
+ * * / A B C D E
— 前缀表示法
中序遍历结果
A / B * C * D + E
— 中缀表示法
后序遍历结果
A B / C * D * E +
— 后缀表示法
层次遍历结果
+ * E * D / C A B
例 2,用二叉树表示算术表达式
9
例 3,已知一棵二叉树的中序序列和 后序序列 分别是
BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。
分析：
① 由后序遍历特征, 根结点必在后序序列尾部 （ 即 A） ；
② 由中序遍历特征, 根结点必在其中间, 而且其左部必
全部是左子树的子孙 （ 即 BDCE）, 其右部必全部是右
子树的子孙 （ 即 FHG） ；
③ 继而, 根据后序中的 DECB子树可确定 B为 A的左孩子,
根据 HGF子串可确定 F为 A的右孩子；以此类推 。
10
已知中序遍历,B D C E A F H G
已知后序遍历,D E C B H G F A
（ B D C E） （ F H G）（ D C E）
B F
G
H
C
D E
A
11
7.4.2 二叉链存储结构下二叉树遍历的实现
结点数据类型自定义
typedef struct Node{
DataType data;
struct Node *leftchild；
struct Node *righthild；
}BiTreeNnode;
BiTreeNnode *root;
先序遍历函数
void InOrder(BiTreeNode *t,void
visit(DataType item))
//使用 visit(item)函数中序遍历二叉树 t
{ if(t != NULL)
{ InOrder(t->leftChild,visit);
visit(t->data);
InOrder(t->rightChild,visit);
}
}
思考,请同学们写出中序和后序 遍历算法思想和函数。
12
例 4,编写递归算法，打印二叉树中所有叶子结点的值。
思路,若左右指针均空，必为叶子。可选用任何一种遍历
算法查找叶子，将其统计并打印出来。
void DLR(BiTreeNode *root,void visit(DataType item))
//采用先序遍历的递归算法
{ if ( root!=NULL ) //非空二叉树条件, 等效于 if(root)
{if(!root->leftChild&&!root->rightChild) //是叶子结点则统计并打印
{visit(root->data);}
DLR(root->leftChild,visit); //递归遍历左子树, 直到叶子处；
DLR(root->rigthChild,visit); //递归遍历右子树, 直到叶子处；
}
}
13
7.5 线索二叉树
所以,空指针数目＝ 2n－ (n-1)=n+1个 。
证明,用二叉链表存储包含 n个结点的二叉树, 结点必有 2n
个链域 。
除根结点外, 二叉树中每一个结点 有且仅有一个双亲,
意即每个结点地址占用了双亲的一个直接后继, n个结点地址
共占用了 n-1个双亲的指针域 。 也就是说, 只会有 n－ 1个结
点的链域存放指针 。
Threaded Binary Tree
讨论,用二叉链表法（ leftchild,rightchild）存储包含 n个结
点 的二叉树，结点的指针区域中会有多少个 空 指针？
有 n+1个！
14
思考,二叉链表空间效率这么低，能否利用这些空
闲区存放有用的信息或线索？
—— 我们可以用它来存放当前结点的 直接前驱和后
继 等线索，以加快查找速度。
结论,用二叉链表法存储包含 n个结点的二叉树，结
点的指针区域中会有 n+1个空指针。
这就是 线索二叉树 （ Threaded Binary Tree）
15
二叉树中容易找到结点的 左右孩子 信息，但该结点的
直接前驱和直接后继只能在某种遍历过程中 动态 获得。
先依 遍历规则 把每个结点对应的 前驱 和 后继线索 预存
起来，这叫做,线索化,。
意义,从 任一结点 出发都能快速找到其前驱和后继，
且 不必借助堆栈。
对二叉树进行某种遍历之后，将得到一个线性有序的序列。
例如对某二叉树的 中序遍历 结果是 B D C E A F H G，意味着 已
将该树转为线性排列，显然其中结点 具有唯一前驱和唯一后继。
在此前提下，那 n+1个空链域才能装入（也装得下）“线索”。
讨论 2.如何获得这种, 直接前驱, 或, 直接后继,？有何
意义？
讨论 1,二叉树是 1:2的非线性结构，如何定义其直接后继？
16
① 每个结点增加两个域,fwd和 bwd；
存放前驱指针
存放后继指针
如何预存这类信息？有两种解决方法：
② 与原有的左右孩子指针域“复用”，充分利用那 n+1个空链域。
规 定：
1）若结点有左子树，则 lchild指向其左孩子；
否则,lchild指向其直接前驱 (即线索 )；
2）若结点有右子树，则 rchild指向其右孩子；
否则,rchild指向其直接后继 (即线索 ) 。
datalchild rchildfwd bwd
datalchild rchild
缺点：空间效率太低！
问题：计算机如
何判断是孩子指
针还是线索指针？
如何区别？
17
lchild LTag data RTag rchild
约定, 当 Tag域为 0时,表示 正常 情况 ;
当 Tag域为 1时,表示 线索 情况, 前驱 (后继 )
左 (右 )孩子
为区别两种不同情况，特增加两个标志域：
问,增加了前驱和后继等线索有什么好处？
—— 能方便找出当前结点的前驱和后继，不用
堆栈（递归）也能遍历整个树。
各 1bit
18
1,有关线索二叉树的几个术语
线索链表：
线 索：
线索二叉树：
线 索 化：
用 含 Tag的结点样式所构成的二叉链表。
指向结点前驱和后继的指针。
在二叉树的结点上加上线索的二叉树。
对二叉树以 某种次序遍历 使其变为线索
二叉树的过程。
线索化过程就是在遍历过程中修改空指针的过程：
将空的 lchild改为结点的直接前驱；
将空的 rchild改为结点的直接后继。
非空指针呢？仍然指向孩子结点（称为, 正常情况, ）
19
data A G E I D J H C F B
Ltag 0 0 1 1 1 1 0 1 0 1
Rtag 0 0 0 1 0 1 0 1 1 1
A
G
E
I
D
J
H
C F
B
例 5,带了 两个标志 的某 先序 遍历结果如下表所
示，请画出对应的二叉树。
Tag=1表示 线索,
Ltag=1表示前驱
Rtag=1表示后继
20
A
B C
GE
I
D
H
F
root
悬空？
NIL
悬空？
NIL
解,对该二叉树 中序 遍历的结果为, H,D,I,B,E,A,F,C,G
所以添加线索应当按如下路径进行：
为避免悬空
态，应增设
一个头结点
例 6,画出以下二叉树对应的 中序 线索二叉树。
2,线索二叉树的生成 —— 线索化 线索化过程就是在遍历过程中修改空指针的过程
21
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
注：此图中序遍历结果为, H,D,I,B,E,A,F,C,G
0root 0
对应的中序线索二叉树存储结构如图所示：
22
例 7,给定如图所示二叉树 T，请画出与其对应的
中序线索二叉树。
28
25
40
55
60
33
08 54
解,因为中序遍历序列是,55 40 25 60 28 08 33 54
对应线索树应当按此规律连线，即 在原二叉树中添加虚线。
NIL NIL
23
小结
7.4 二叉树遍历
7.4.1 二叉树遍历
7.4.2 二叉链存储结构下二叉树遍历的实现
7.5 线索二叉树
1.有关线索二叉树的几个术语
2,线索二叉树的生成 —— 线索化
24
下结内容
7.6 哈夫曼树
7.7 树与二叉树的转换
上节回顾
7.3 二叉树的设计和实现
7.3.1 二叉树的存储结构
7.3.2 二叉链存储结构的二叉树操作实现
2
7.4 二叉树遍历
7.4.1 二叉树遍历
1,遍历定义 ——
2,遍历用途 ——
3,遍历方法 ——
指按照某种顺序访问二叉树中的每个结点，
使每个结点被访问一次且仅被访问一次。
（或指按某条搜索路线遍访每个结点且不
重复）。
它是树结构插入、删除、修改、查找和排
序运算的前提，是二叉树一切运算的基础
和核心。
对每个结点的查看通常都是, 先左后
右, 。
3
4,遍历规则 ———
二叉树由根、左子树、右子树构成，定义为 D,L,R
以根结点为参照系
注：, 先、中、后, 的意思是指访问的结点 D是先于子树出
现还是后于子树出现。
?D,L,R的组合定义了六种可能的遍历方案：
LDR,LRD,DLR,DRL,RDL,RLD
?若限定 先 左 后 右,则有三种实现方案：
DLR LDR LRD
先 序遍历 中 序遍历 后 序遍历
4
5、二叉树遍历的基本方法
有三种,先 序遍历 (DLR),中 序遍历 (LDR),后 序遍历 (LRD)
通常可以把二叉树遍历操作设计成递归算法。
（一） 先序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
（ 1）访问根结点；
（ 2）先序遍历根结点的左子树；
（ 3）先序遍历根结点的右子树。
（二） 中序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
(1）中序遍历根结点的左子树；
（ 2）访问根结点；
5
（ 3）中序遍历根结点的右子树。
（三） 后序遍历二叉树 的递归算法为：
若二叉树为空，则算法结束；否则：
（ 1）后序遍历根结点的左子树；
（ 2）后序遍历根结点的右子树；
（ 3）访问根结点。
（四） 二叉树 的层序遍历算法：
(1)初始化设置一个队列；
(2)把根结点指针入队列；
(3)当队列非空时，循环执行步骤 (3.a)到步骤 (3.c):
6
(3.a)出队列取得一个结点指针，访问该结点；
(3.b)若该结点的左子树非空，则将该结点的左子树指针入
队列；
(3.c)若该结点的右子树非空，则将该结点的右子树指针入
队列；
（ 4）结束。
注意,一个 二叉树的遍历序列 不能决定一棵 二叉树，但 先
序（或后序）和中序遍历序列的组合 可以 惟一确定 一棵二叉
树。而先序和后序遍历则不能。
7
例 1,先序遍历的结果是：
中序遍历的结果是：
后序遍历的结果是：
A
B C
D E
D B E A C
D E B C A
口诀：
DLR— 先序遍历，即 先根 再左再右
LDR— 中序遍历，即 先左 再根 再右
LRD— 后序遍历，即 先左再右 再根
A B D E C
8
+
*
A
*
/
E
D
C
B
先序遍历结果
+ * * / A B C D E
— 前缀表示法
中序遍历结果
A / B * C * D + E
— 中缀表示法
后序遍历结果
A B / C * D * E +
— 后缀表示法
层次遍历结果
+ * E * D / C A B
例 2,用二叉树表示算术表达式
9
例 3,已知一棵二叉树的中序序列和 后序序列 分别是
BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。
分析：
① 由后序遍历特征, 根结点必在后序序列尾部 （ 即 A） ；
② 由中序遍历特征, 根结点必在其中间, 而且其左部必
全部是左子树的子孙 （ 即 BDCE）, 其右部必全部是右
子树的子孙 （ 即 FHG） ；
③ 继而, 根据后序中的 DECB子树可确定 B为 A的左孩子,
根据 HGF子串可确定 F为 A的右孩子；以此类推 。
10
已知中序遍历,B D C E A F H G
已知后序遍历,D E C B H G F A
（ B D C E） （ F H G）（ D C E）
B F
G
H
C
D E
A
11
7.4.2 二叉链存储结构下二叉树遍历的实现
结点数据类型自定义
typedef struct Node{
DataType data;
struct Node *leftchild；
struct Node *righthild；
}BiTreeNnode;
BiTreeNnode *root;
先序遍历函数
void InOrder(BiTreeNode *t,void
visit(DataType item))
//使用 visit(item)函数中序遍历二叉树 t
{ if(t != NULL)
{ InOrder(t->leftChild,visit);
visit(t->data);
InOrder(t->rightChild,visit);
}
}
思考,请同学们写出中序和后序 遍历算法思想和函数。
12
例 4,编写递归算法，打印二叉树中所有叶子结点的值。
思路,若左右指针均空，必为叶子。可选用任何一种遍历
算法查找叶子，将其统计并打印出来。
void DLR(BiTreeNode *root,void visit(DataType item))
//采用先序遍历的递归算法
{ if ( root!=NULL ) //非空二叉树条件, 等效于 if(root)
{if(!root->leftChild&&!root->rightChild) //是叶子结点则统计并打印
{visit(root->data);}
DLR(root->leftChild,visit); //递归遍历左子树, 直到叶子处；
DLR(root->rigthChild,visit); //递归遍历右子树, 直到叶子处；
}
}
13
7.5 线索二叉树
所以,空指针数目＝ 2n－ (n-1)=n+1个 。
证明,用二叉链表存储包含 n个结点的二叉树, 结点必有 2n
个链域 。
除根结点外, 二叉树中每一个结点 有且仅有一个双亲,
意即每个结点地址占用了双亲的一个直接后继, n个结点地址
共占用了 n-1个双亲的指针域 。 也就是说, 只会有 n－ 1个结
点的链域存放指针 。
Threaded Binary Tree
讨论,用二叉链表法（ leftchild,rightchild）存储包含 n个结
点 的二叉树，结点的指针区域中会有多少个 空 指针？
有 n+1个！
14
思考,二叉链表空间效率这么低，能否利用这些空
闲区存放有用的信息或线索？
—— 我们可以用它来存放当前结点的 直接前驱和后
继 等线索，以加快查找速度。
结论,用二叉链表法存储包含 n个结点的二叉树，结
点的指针区域中会有 n+1个空指针。
这就是 线索二叉树 （ Threaded Binary Tree）
15
二叉树中容易找到结点的 左右孩子 信息，但该结点的
直接前驱和直接后继只能在某种遍历过程中 动态 获得。
先依 遍历规则 把每个结点对应的 前驱 和 后继线索 预存
起来，这叫做,线索化,。
意义,从 任一结点 出发都能快速找到其前驱和后继，
且 不必借助堆栈。
对二叉树进行某种遍历之后，将得到一个线性有序的序列。
例如对某二叉树的 中序遍历 结果是 B D C E A F H G，意味着 已
将该树转为线性排列，显然其中结点 具有唯一前驱和唯一后继。
在此前提下，那 n+1个空链域才能装入（也装得下）“线索”。
讨论 2.如何获得这种, 直接前驱, 或, 直接后继,？有何
意义？
讨论 1,二叉树是 1:2的非线性结构，如何定义其直接后继？
16
① 每个结点增加两个域,fwd和 bwd；
存放前驱指针
存放后继指针
如何预存这类信息？有两种解决方法：
② 与原有的左右孩子指针域“复用”，充分利用那 n+1个空链域。
规 定：
1）若结点有左子树，则 lchild指向其左孩子；
否则,lchild指向其直接前驱 (即线索 )；
2）若结点有右子树，则 rchild指向其右孩子；
否则,rchild指向其直接后继 (即线索 ) 。
datalchild rchildfwd bwd
datalchild rchild
缺点：空间效率太低！
问题：计算机如
何判断是孩子指
针还是线索指针？
如何区别？
17
lchild LTag data RTag rchild
约定, 当 Tag域为 0时,表示 正常 情况 ;
当 Tag域为 1时,表示 线索 情况, 前驱 (后继 )
左 (右 )孩子
为区别两种不同情况，特增加两个标志域：
问,增加了前驱和后继等线索有什么好处？
—— 能方便找出当前结点的前驱和后继，不用
堆栈（递归）也能遍历整个树。
各 1bit
18
1,有关线索二叉树的几个术语
线索链表：
线 索：
线索二叉树：
线 索 化：
用 含 Tag的结点样式所构成的二叉链表。
指向结点前驱和后继的指针。
在二叉树的结点上加上线索的二叉树。
对二叉树以 某种次序遍历 使其变为线索
二叉树的过程。
线索化过程就是在遍历过程中修改空指针的过程：
将空的 lchild改为结点的直接前驱；
将空的 rchild改为结点的直接后继。
非空指针呢？仍然指向孩子结点（称为, 正常情况, ）
19
data A G E I D J H C F B
Ltag 0 0 1 1 1 1 0 1 0 1
Rtag 0 0 0 1 0 1 0 1 1 1
A
G
E
I
D
J
H
C F
B
例 5,带了 两个标志 的某 先序 遍历结果如下表所
示，请画出对应的二叉树。
Tag=1表示 线索,
Ltag=1表示前驱
Rtag=1表示后继
20
A
B C
GE
I
D
H
F
root
悬空？
NIL
悬空？
NIL
解,对该二叉树 中序 遍历的结果为, H,D,I,B,E,A,F,C,G
所以添加线索应当按如下路径进行：
为避免悬空
态，应增设
一个头结点
例 6,画出以下二叉树对应的 中序 线索二叉树。
2,线索二叉树的生成 —— 线索化 线索化过程就是在遍历过程中修改空指针的过程
21
0 0A
0 0C0 0B
1 1E 1 1F 1 1G0 0D
1 1I1 1H
注：此图中序遍历结果为, H,D,I,B,E,A,F,C,G
0root 0
对应的中序线索二叉树存储结构如图所示：
22
例 7,给定如图所示二叉树 T，请画出与其对应的
中序线索二叉树。
28
25
40
55
60
33
08 54
解,因为中序遍历序列是,55 40 25 60 28 08 33 54
对应线索树应当按此规律连线，即 在原二叉树中添加虚线。
NIL NIL
23
小结
7.4 二叉树遍历
7.4.1 二叉树遍历
7.4.2 二叉链存储结构下二叉树遍历的实现
7.5 线索二叉树
1.有关线索二叉树的几个术语
2,线索二叉树的生成 —— 线索化
24
下结内容
7.6 哈夫曼树
7.7 树与二叉树的转换
