,数据结构,
第六章 (中 )
数据结构
tjm
6.3.2 线索二叉树
在二叉树的先序、中序或后序遍历序列中两个相邻
的结点互称为前驱与后继。
指向前驱或后继结点的指针称为线索。
加上线索的二叉链表表示的二叉树叫线索二叉树。
对二叉树按某种遍历次序使其变为线索二叉树的过
程叫线索化。
实现：在有 n个结点的二叉链表中必定有 n+1个空链
域。在线索二叉树的结点中增加两个标志域：
LTag,若 LTag=0,lchild域指向左孩子；
若 LTag=1,lchild域指向其前驱。
RTag,若 RTag=0,rchild域指向右孩子；
若 RTag=1,rchild域指向其后继。
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
先序序列,ABCDE
先序线索二叉树
0 0
0 01 1
1 1 ^1 1
lchild LTag data RTag rchild
线索链表的类型定义参见 P133
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
后序序列,CBEDA
后序线索二叉树
0 0
0 01 1
1 11 1^
数据结构
tjm
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
A
B
C
D
E
头结点,LTag=0,lchild指向
根结点。 RTag=1,rchild指
向遍历序列中最后一个结点 。
遍历序列中第一个结点的
lchild域和最后一个结点的
rchild域都指向头结点。
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
数据结构
tjm
A
B
C
D
E
thrt
0 1
pre
p
P->A
A
B D
C E
T
^^
^ ^ ^ ^
0 0
0 00 0
0 00 0
按中序线索化二叉树
算法参见 P134算法
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
p
P->A
P->B
0 0
0 00 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
P=NULL
P->A
P->B
0 0
0 00 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
0 0
0 00 0
0 00 0
1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
P->C
0 0
0 01 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P=NULL
P->A
P->C
0 0
0 01 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
0 0
0 01 0
0 00 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^
thrt
0 1
pre
P=NULL
P->A
0 0
0 01 0
0 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^
thrt
0 1
pre
P
0 0
0 01 0
0 01 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
P->E
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P=NULL
pre
P->D
P->E
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
0 0
0 01 0
1 01 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^
thrt
0 1
P=NULL
pre
P->D
0 0
0 01 0
1 01 1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^
thrt
0 1
P
pre
0 0
0 01 0
1 01 1 1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
thrt
0 1
P=NULL
pre
0 0
0 01 0
1 11 1
1
数据结构
tjm
A
B
C
D
E
A
B D
C E
thrt
0 1
1
1 1 1 1
1
0 0
0 0
数据结构
tjm
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
遍历中序线索二叉树
算法参见 P134
第六章 (中 )
数据结构
tjm
6.3.2 线索二叉树
在二叉树的先序、中序或后序遍历序列中两个相邻
的结点互称为前驱与后继。
指向前驱或后继结点的指针称为线索。
加上线索的二叉链表表示的二叉树叫线索二叉树。
对二叉树按某种遍历次序使其变为线索二叉树的过
程叫线索化。
实现：在有 n个结点的二叉链表中必定有 n+1个空链
域。在线索二叉树的结点中增加两个标志域：
LTag,若 LTag=0,lchild域指向左孩子；
若 LTag=1,lchild域指向其前驱。
RTag,若 RTag=0,rchild域指向右孩子；
若 RTag=1,rchild域指向其后继。
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
先序序列,ABCDE
先序线索二叉树
0 0
0 01 1
1 1 ^1 1
lchild LTag data RTag rchild
线索链表的类型定义参见 P133
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
后序序列,CBEDA
后序线索二叉树
0 0
0 01 1
1 11 1^
数据结构
tjm
A
B D
C E
T
中序序列,BCAED
中序线索二叉树
0 0
0 01 1
1 1
^
1 1
^
A
B
C
D
E
头结点,LTag=0,lchild指向
根结点。 RTag=1,rchild指
向遍历序列中最后一个结点 。
遍历序列中第一个结点的
lchild域和最后一个结点的
rchild域都指向头结点。
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
数据结构
tjm
A
B
C
D
E
thrt
0 1
pre
p
P->A
A
B D
C E
T
^^
^ ^ ^ ^
0 0
0 00 0
0 00 0
按中序线索化二叉树
算法参见 P134算法
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
p
P->A
P->B
0 0
0 00 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
P=NULL
P->A
P->B
0 0
0 00 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
0 0
0 00 0
0 00 0
1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
P->C
0 0
0 01 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P=NULL
P->A
P->C
0 0
0 01 0
0 00 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^ ^
thrt
0 1
pre
P
P->A
0 0
0 01 0
0 00 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^
thrt
0 1
pre
P=NULL
P->A
0 0
0 01 0
0 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^ ^
thrt
0 1
pre
P
0 0
0 01 0
0 01 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
P->E
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P=NULL
pre
P->D
P->E
0 0
0 01 0
1 01 0
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^ ^
thrt
0 1
P
pre
P->D
0 0
0 01 0
1 01 01
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^
thrt
0 1
P=NULL
pre
P->D
0 0
0 01 0
1 01 1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
^
thrt
0 1
P
pre
0 0
0 01 0
1 01 1 1
数据结构
tjm
A
B
C
D
E
A
B D
C E
T
^
thrt
0 1
P=NULL
pre
0 0
0 01 0
1 11 1
1
数据结构
tjm
A
B
C
D
E
A
B D
C E
thrt
0 1
1
1 1 1 1
1
0 0
0 0
数据结构
tjm
A
B
C
D
E
0 A 0
1 B 0 0 D 1
1 C 1 1 E 1
T
中序序列,BCAED
带头结点的中序线索二叉树
0 1
遍历中序线索二叉树
算法参见 P134
