武汉理工大学华夏学院 -信息工程系第五章 树和二叉树树形结构是一种非线性结构，其特点是：树中有且仅有一个无前驱的结点，其余每个结点最多只有一个前驱，但可以有多个后继。
武汉理工大学华夏学院 -信息工程系
5.1 树的概念一,树的定义
1.用形式定义方法定义数据结构 B=(K,R)称为树是指,K为结点的非空有限集合,R是满足下列条件的 K上的一个关系：
（ 1）有且仅有一个结点无前驱，被称为树根；
（ 2）除树根以外的其余结点，都有且仅有一个前驱。
2.用递归方法定义树是结点的非空有限集合 T,其中，有一个无前驱被称为树根的结点，其余结点被分成 m（ m>=0） 个互不相交的子集 T1,,T2,…,Tm,每一个子集又都是一棵树，并称为树根的子树。
武汉理工大学华夏学院 -信息工程系二,树的逻辑结构表示
1,树的逻辑结构一般采用图示法。根在上,子树在下,用小圆圈表示结点,用称为边的直线段表示结点之间的关系。
如图 5－ 1所示,其中结点 a为树根，它有两棵子树 b和 c
且 b和 c又是一棵树。
2,树的逻辑结构的二元组表示按照树的形式定义方法描述为：
tree＝（ D,R）
D=（ a,b,c,d,e,f,g,h,j,k,l）
R=(<a,b>,<a,c>,<b,d>,<b,e>,<b,f>,<c,g>,<c,h>,
<e,j>,<e,k>,<g,l>）
武汉理工大学华夏学院 -信息工程系图 5-1 树的逻辑结构表示
a
b c
d e g
j l
hf
k
树根树叶武汉理工大学华夏学院 -信息工程系
3,树的逻辑结构其它表示法。
（ 1) 文氏图表示法 (2)广义表表示
A(B(E,F(J,K),G),C,D(H,I))
H
I
J K
E G
C
B
A
D
表示根
F
表示结点武汉理工大学华夏学院 -信息工程系
（ 3) 凹入式表示法
A
B
E
F
J
K
G
C
D
H
I
武汉理工大学华夏学院 -信息工程系
1,双亲 与 孩子 设 X与 Y为树中的两个结点，若 X
是 Y的前驱，则称 X是 Y的双亲,Y是 X的孩子。
2,兄弟 与 堂兄弟 树中的两个结点 X 与 Y存在有共同的双亲，称 X与 Y为兄弟，若其双亲为兄弟，
则称为堂兄弟
3,分支结点 和 终端结点 有后继结点的结点称为分支结点；没有后继结点的结点称为终端结点或树叶。
4,结点的度 结点的后继结点的个数,称为该结点的度,显然,度为零的结点一定是树叶。
三,树中常用术语武汉理工大学华夏学院 -信息工程系
5.树的度 树中结点度的最大值,称为树的度。
例如：图 5-1树的度为 3,因为该树中,有度为一的 结点、
也有度为二、度为零与 度为三的结点，其度的最大值为三。若一棵树的度为 n时，则称该树为 n度树。
6,结点的层 又称为结点的层次高度，它是从树根开始定义的：即根结点属于第一层，其余结点的层次高度等于其双亲的层次＋ 1。
7,树的层次高度 树的层次高度等于树中结点的层次的最大值。（也称为树的深度）
8,森林 n（ n>=0 ）棵互不相交的树的集合。 注意：
当 n＝ 0时说明森林中无结点，即森林可以为空。（树不能为空）
9.有序树和无序树：若树中结点从左到右是有序的，则称该树为有序树，反之为无序树。
武汉理工大学华夏学院 -信息工程系
1.双亲数组表示 方法：用一个一维数组存储树中的结点，数组元素是一个结构体，该结构体中包含两个字段：
其一为 data字段，用来存放结点的值；其二为 parent字段,用来存储该结点的双亲结点（即该结点的前驱结点）
在数组中的下标地址。
四,树的存储结构当一棵树的逻辑结构确定以后,就应该考虑如何存放在计算机中，存储一棵树时，不仅要存储树中每个结点的值，而且要存储各结点之间的关系，一般可以用三种方法实现：
武汉理工大学华夏学院 -信息工程系例如,以图 5-1所示的三度树为例，存储该树的双亲数组表示,如图 5-2所示。
1
图 5-2 图 4-1树的双亲数组存储表示
data
2
parent
root 1
3 4 5 6 87 9
a b c d e f hg i
0 1 1 2 2 2 33 7
10 11
j k
5 5
存储特点,可以根据每一个结点本身的内容直接读取其双亲结点的地址，但查找孩子结点较困难。
武汉理工大学华夏学院 -信息工程系
2.孩子链表示式方法,把每一个结点的孩子结点排列起来，
构成一个单链表,称为孩子链表。对于一棵有 n个结点的树来说，就有 n个孩子链表,为便于查找,n个链表的表头指针可用顺序表示。
特点,根据每一个结点组成的链表，可以直接读取该结点的孩子结点地址，但查找双亲结点较困难。
武汉理工大学华夏学院 -信息工程系
31
23
45
67
8
910
11
ab
cd
ef
gh
jk
l
24 5 6 ∧
7 8
9 10
11
∧
∧
∧
∧
root 1
∧
∧
∧∧
∧∧
图 5-3 图 5-1所示树的孩子链表存储表示例,以图 5-1所示的三度树为例，其孩子链存储表示如图 5-3所示。
武汉理工大学华夏学院 -信息工程系
3,左孩子右兄弟链表表示方法：设置一个二叉链表，该链表的每一个结点都包含两个指针，分别指向该结点的第一个孩子和紧靠该结点右边的一个兄弟结点，
所以，结点由三个字段构成。
实例,以图 5-1所示的三度树为例，该存储方法的表示如图 5-4所示。
特点,根据结点本身可以直接读到该结点的第一个孩子结点及其最右边一个兄弟结点的地址，但查找双亲结点地址也较困难。
武汉理工大学华夏学院 -信息工程系结点形式,孩子地址 字段 结点数据 值字段 兄弟地址 字段
root
图 5-4 图 5-1所示树的左孩子右兄弟链表存储表示
d∧ e g h∧
b c ∧
a ∧
j∧ f∧ ∧ d∧
k∧
∧
∧
∧
武汉理工大学华夏学院 -信息工程系一、二叉树的定义和基本术语
1,定义,二叉树是结点的有限集合，它可以为空，也可以是由一个根结点和称为根的左右子树的两棵互不相交的二叉树组成。
2,二叉树的基本形态 二叉树共有五种基本树形，如图 5-５所示 。
5.2 二 叉 树
（ 1）无左右子树的二叉树．
（ 2）只有左子树，无右子树的二叉树．
武汉理工大学华夏学院 -信息工程系图 5-5 二叉树的四种基本形态
（ 3）只有右子树，无左子树的二叉树．
（ 4） 既有左子树，又有右子树的二叉树．
（ 5）无结点的空树。
武汉理工大学华夏学院 -信息工程系二,二叉树的性质性质１,在二叉树的第ｉ层上，最多有２ i-1 个结点。（请思考，为什么？）
性质２,在高度为ｈ（ｈ >0 ）的二叉树中，结点总数最多有 2h -1个结点。
原因,由性质１，把每层结点加起来即可 。
性质３,在非空二叉树中，叶结点的个数 比度为 2的结点个数 多 １ 个 。 为什么？
武汉理工大学华夏学院 -信息工程系证明：
设二叉树中结点的总数为ｎ，度为０，１，２的结点个数分别为ｎ 0，ｎ 1，ｎ 2，
则有ｎ＝ｎ 0 +n1+n2 …………… (1)
另外，又从二叉树的边数来看，可以知道：每一棵树除根结点外的其余结点都有一条边与其双亲结点相连，
则 n 个结点应有 n-1条边，这 n-1条边是由分支结点产生的，共有：度为 1的结点为 n1个，产生的边的条数为 n1
条；度为 2的结点为 n2个，产生的边的条数为 2n2条；
这样，有 n -1=n1+2n2 ………… (2)
由（ 1),(2）两式变换可得 n0=n2 + 1 (证毕）
武汉理工大学华夏学院 -信息工程系
1,满二叉树
(１ )定义,当一棵二叉树的每一层的结点个数都达到该层结点数的最大值，则该树称为满二叉树。
(２ )特点：
,在满二叉树中，位于第 K层上的结点数应为 2K－ 1个。
,在满二叉树中，每一个结点的度不是０就是２，没有度为１的结点，且叶结点都在同一层。（最高层）
三,满二叉树与完全二叉树武汉理工大学华夏学院 -信息工程系图 5－６层次高度为四的满二叉树的示意图
N
A
CB
ED GF
IH KJ ML O
(３ ) 满二叉树的图例 如图 5－ 6所示武汉理工大学华夏学院 -信息工程系
2,完全二叉树
（ １ ） 定义,当一棵二叉树，除最底层以外的每一层的结点个数都达到最大值，而最底层的结点又集中在从最左边开始的若干连续位置上，则该树称为完全二叉树。
（ ２） 特点：
在层数为 H的完全二叉树中，位于第 K（ K<H)层上的结点数应为 2K－ 1个,而第 H层上的结点数不能确定。
在完全二叉树中，度为１的结点只能在最底层，且叶结点也在最底层，而非最底层的结点的度只能为２。
满二叉树一定是完全二叉树。
武汉理工大学华夏学院 -信息工程系
(3) 完全二叉树的图例如图 5－７所示图 5－ 7层次高度为四的完全二叉树的示意图
A
CB
ED GF
IH KJ L
武汉理工大学华夏学院 -信息工程系
1、二叉树的顺序存储表示
（ 1) 完全二叉树的顺序存储存储方法,设完全二叉树中有ｎ个结点，
对这ｎ个结点按层次从上到下、同一层从左往右的原则，用自然数１～ｎ依次编号，作为该结点的号数，并设置一个一维数组作为存储该树的存储区，而结点的号数又是该结点在数组中的下标值，用这种方法存储的完全二叉树，
称为完全二叉树的顺序存储。
例如，图 5－ 6给出的 满 二叉树的顺序存储表示如图 5－ 8所 示。
四,二叉树的存储表示武汉理工大学华夏学院 -信息工程系
N
A
CB
ED GF
IH KJ ML O
图 5－８完全二叉树的顺序存储表示示意图
Tree
１ 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ａ B LKJIHGFEDC M N O
武汉理工大学华夏学院 -信息工程系存储 特点：
在 用顺序存储方法存储的完全二叉树中，
查找其孩子结点及双亲结点都十分方便。这是因为：该完全二叉树的根序号为１，其根的左子树结点的序号就是２；右子树结点的序号为３（若存在的话），显然，设某一个结点的序号为ｉ，则其左孩子结点的序号为
２ｉ（当然２ｉ <=n),而右孩子结点的序号为２ｉ＋１（２ｉ＋１ <=n）； 当ｉ＝１时，
该结点无双亲结点，当ｉ >1时，其双亲结点的序号是ｉ／２取整。
武汉理工大学华夏学院 -信息工程系
（２） 一般二叉树的顺序存储存储方法,用完全二叉树的顺序存储方法也可以存储一般二叉树 。做法是,首先，
在二叉树中补上若干虚拟结点使之成为 一棵完全 二 叉树；然后，按上述方法对结点进行编号，并将它们存入数组 tree[１．,m]
中。其中ｍ等于一般二叉树构成的虚拟完全二叉树中的结点的个数。
武汉理工大学华夏学院 -信息工程系例如,图 5－９给出了一棵一般二叉树的顺序存储结 构。
一般二叉树的逻辑结构
A
H D
G R T
S X Y
A
H D
G R T
S X Y
补齐虚拟结点的完全二叉树的逻辑结构
Tree １ 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ａ H STRGD X Y
图 5－９一般二叉树的顺序存储结构示意图武汉理工大学华夏学院 -信息工程系占用的存储空间利用率较低，虚拟结点在数组中要占用存储单元（不可能访问）；
在确定各个结点之间的关系时，要进行判断。如找图４－９中ｉ＝３的结点的左孩子时，由于其左孩子应放在下标为６的数组元素单元中，但 tree［６］为空，故可以断定结点ｉ无左子树。
存储 特点：
武汉理工大学华夏学院 -信息工程系特点,利用动态变量存储树结构，并且各个结点的孩子可以从结点本身反映出来。
2、二叉树的二叉链表存储表示存储方法,所谓二叉树的二叉链表存储表示是指：对于树中的每一个结点用一个三元组结构表示出来，其中包含有两个指针，分别指向对应结点的左孩子结点的地址与右孩子结点的地址。例如，图 5－１０给出了一棵一般二叉树的二叉链表存储结构。
这是一种常用的存储方法。
武汉理工大学华夏学院 -信息工程系一般二叉树的逻辑结构
A
H
D
G R
T
S
X Y
root
A ∧
H
G∧ R∧
S
X ∧∧ Y ∧
D∧ ∧
T ∧∧
一般二叉树的存储结构示意图图 5－ 10二叉树的二叉链表存储结构示意图武汉理工大学华夏学院 -信息工程系
5.3 遍历树形结构一,遍历的概念
1,定义 遍历树是指将树中的结点都访问一次且仅访问一次的操作过程，成为树的遍历。
2,特点 将一个非线性结构线性化遍历后的结果形成一个线性序列
3,遍历方法 前序遍历 后序遍历
4,前序遍历步骤首先访问根结点；再按从左往右的原则，前序 遍历根的每一棵子树。
武汉理工大学华夏学院 -信息工程系
a
b c
d e g
j l
hf
k
例如 图 5－１ 给出的三度树，按前序遍历后得到的序列为,ａ → ｂ → ｄ → ｅ → ｊ → ｋ → ｆ → ｃ → ｇ → ｌ → ｈ
武汉理工大学华夏学院 -信息工程系
5,后序遍历步骤按从左往右的原则，后序遍历根的每一棵子树；后访问根结点 。
例如 图 5－１ 给出的三度树，按后序遍历后的序列为：
ｄ → ｊ → ｋ → ｅ → ｆ → ｂ → ｌ → ｇ → ｈ → ｃ → ａ
武汉理工大学华夏学院 -信息工程系
1,遍历方法
．前序遍历
．中序遍历
．后序遍历
2,前序遍历步骤首先访问根结点；
再前序遍历根的左子树；
最后前序遍历根的右子树。
二,二叉树的遍历武汉理工大学华夏学院 -信息工程系
A
B C
D H E
F G M I
J K
图 5－ 11 二叉树例如图 5－ 11给出的二叉树
A→B → D → F → G → J → H → C → E
→ M → K→ I
按前序遍历的次序是：
遍历后，形成的前序序列为：
A B D F G J H C E M K I
武汉理工大学华夏学院 -信息工程系
A
B
D
F G
J
H
C
E
M
K
I
前序遍历过程变化图武汉理工大学华夏学院 -信息工程系
3、中序遍历步骤首先中序遍历根的左子树；
再访问根结点；
最后中序遍历根的右子树。
例如 图 5－１１ 给出的二叉树按中序遍历后的次序是：
F → D → G → J → B → H → A → C → M →
K → E→ I
遍历后，形成的中序序列为：
F D G J B H A C M K E I
武汉理工大学华夏学院 -信息工程系
F
D
G
J
B
H
A
C
M
K
E
中序遍历过程变化图
I
武汉理工大学华夏学院 -信息工程系
4、后序遍历步骤首先后序遍历根的左子树；
再后序遍历根的右子树；
最后访问根结点。
例如 图 5－１１ 给出的二叉树按后序遍历的次序为：
F→J → G → D → H → B → K→ M → I → E
→ C → A
遍历后，形成的后序序列为：
F J G D H B K M I E C A
武汉理工大学华夏学院 -信息工程系
F
J
G
D H
B
K
M I
E
C
A
后序遍历过程变化图武汉理工大学华夏学院 -信息工程系
5、二叉树遍历形成的线性序列的特点
＋
前序序列为中序序列为后序序列为根结点 左子树 右子树＋ ＋
右子树右子树左子树左子树根结点根结点＋
＋
＋
＋
因为 二叉树 是一棵特殊的树，它 与一棵二度树的区别是,
二叉树可以为空，二度树不能为空；二叉树的左右两棵子树不能交换，二度树的两棵子树可以交换。
6、将一棵ｎ度树转化为二叉树的方法武汉理工大学华夏学院 -信息工程系由于二叉树只有两个子树，所以在存储二叉树时，存储容易实现； 且实现树形结构的操作算法 二叉树又比较简单,加上一般树很容易转换成二叉树，因此研究二叉树 与一般树的转换问题有着现实的重要意义了。
武汉理工大学华夏学院 -信息工程系
5.4 树和森林与二叉树之间的转换一、树和森林的遍历二、树和森林与二叉树之间的转换
1、一棵ｎ度树转化为二叉树；
2、森林转化为二叉树；
3、二叉树转化为森林；
武汉理工大学华夏学院 -信息工程系
(１）保留双亲结点与最左孩子之间的联系，割断双亲结点与其余孩子之间的联系，建立兄弟结点之间的联系。
(２ ) 将兄弟间的联系（水平线）顺时针方向旋转 45,形成一棵根结点无右子树的二叉树。
一棵ｎ度树转化为二叉树的步骤是：
图 5－１２ 给出了一棵一般树转换成一棵二叉树的转换过程武汉理工大学华夏学院 -信息工程系一棵三度树
a
cb
d f g h
j
e
k l
按左孩子右兄弟相连
a
cb
d f g h
j
e
k l
转换后的二叉树图４－１２树转换成二叉树
a
b
d c
e g
f hl
k
j
武汉理工大学华夏学院 -信息工程系一棵ｎ度树转化成的二叉树的特点是：
１．根结点无右子树
２．某一个结点的左子树是原来ｎ度树中的孩子结点；而右子树为原来ｎ度树中的兄弟结点。
显然，由特点 2很容易理解，为什么根结点一定没有右子树。
武汉理工大学华夏学院 -信息工程系
2、森林转化为二叉树的 方法：
（ 1） 森林为空时转化为空二叉树；
（ 2）森林不空时把森林中的每一棵树转化为二叉树后，再将后一棵二叉树挂在前一棵二叉树的右子树下。
3、二叉树转化为森林 方法：
（ 1） 二叉树为空时转化为空森林；
（ 2）二叉树右子树不空时把 每一棵右子树折下后还原为一般树后；
（ 3）二叉树右子树空时，生成一棵树的森林；
武汉理工大学华夏学院 -信息工程系
5.4 二叉树的遍历算法在讨论二叉树遍历算法前，先采用二叉树的静态二叉链表作为二叉树的存储结构。所谓静态二叉链表是指：用一个一维数组作为二叉树的存储区域，
其数组名为 ｔｒｅｅ,数组的上界定义为整型量ｎ
（表示了树中结点的个数）。每一个数组元素又是一个记录（结构体），它由三个域组成：数据字段
ｄａｔａ ；左孩子指针字段 ｌｌｉｎｋ 和右孩子指针字段 ｒｌｉｎｋ,ｌｌｉｎｋ 与 ｒｌｉｎｋ 的类型为整型，表示结点地址（即数组元素的下标），
ｄａｔａ 字段由结点值确定。
一,二叉树数据类型描述武汉理工大学华夏学院 -信息工程系因此，有数据类型说为：
c语言定义
#define n0 50 //数组最大下标
#define datatype char;
struct node {
datatype data ;
int llink,rlink ; } ;
node tree[n0+1]
int root ; //根结点地址指针武汉理工大学华夏学院 -信息工程系图 5-13 给出了一棵二叉树和它的静态二叉链表的存储结构
A
CB
D
F G
H
I
E
M
KJ
图 5-13 二叉树和它的静态二叉链表存储结构
2
A
8
3
B
7
4
D
5
0
F
0
0
G
6
0
J
0
0
H
0
0
C
11
0
M
0
0
K
0
9
E
12
10
I
0
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
武汉理工大学华夏学院 -信息工程系设ｓ,array[1..n0] of integer; 为一个栈区，
top,integer; 为栈指针，
ｐ,integer; 是一个辅助变量武汉理工大学华夏学院 -信息工程系算法思想,先从根结点开始访问，再看其有否左子树，有则访左；无左或左子树已访问完，则访右子树。
二,二叉树遍历的非递归算法处理方法,设置一个栈，用来对已访问后的结点的右子树进行保存，当根结点访问完后，若其有右子树，则先将右子树的地址送进栈区保存，再取其左子树的地址进行访问，若无左子树或已访问完左子树，
则退栈访问右子树，直至栈空。
1、前序遍历武汉理工大学华夏学院 -信息工程系算法中应考虑的问题与涉及的基本判断
（１） 二叉树空否？表示为 root＝ ０
（２） 结点ｐ有否左子树？
表示为 tree[p].llink=0？
结点ｐ有否右子树？
表示为 tree[p].ｒ link=0？
（３） 栈空否？
表示为 top＝ -1？
该算法用以下算法框图表示为图 5-13所示武汉理工大学华夏学院 -信息工程系输入 root
P＝ root
P＝＝ 0
空树，结束
＋
top＝ -1
访问 p
tree[p].rlink==0
top＝ top+1；
S[top]=tree[p].rlink
＋
P＝ tree[p].llink
P＝＝ 0 －
top＝＝ -1＋
结束 P＝ s[top]； top＝ top－ 1
退栈访右子树有左子树图 5－１３前序遍历二叉树非递归算法流程图武汉理工大学华夏学院 -信息工程系处理方法,利用 栈，先将根结点送入栈保存，
然后沿左链访问左子树，当左子树访问完后，
再退栈访问根结点，最后沿右子树访问，直至栈空。 该算法用以下算法框图表示为图 5-14所示二、中序遍历算法思想,从根结点开始，看其有否左子树，有则 按中序 遍历访 左 子树 ；无左或左子树已访问完后，再 访问根 结 点，最后 按中序 访问右子树。
武汉理工大学华夏学院 -信息工程系图 5－１ 4中序遍历二叉树非递归算法流程图输入 root ; t0p=-1
P＝ root
P＝＝ 0
空树，结束
＋
top=top+1 ; S[top]=p
P==0
＋
top＝＝ -1＋
结束 P＝ s[top]； top＝ top－ 1
访问 p;
p=tree[p].rlink
P=tree[p].llink有左子树，再进栈武汉理工大学华夏学院 -信息工程系处理方法,利用 栈，采用两次进栈、退栈的方法实现后序遍历。即先将根结点送入栈保存，然后沿左链访问左子树，当左子树访问完后，则退栈（第一次）取其结点的右子树地址，并把该结点再次送入栈中保存，然后沿右子树访问，当右子树访问完后，再退栈
（第二次）访问该结点，直至栈空。
3、后序遍历算法思想,从根结点开始，先看其有否左子树，有则 按后序遍历 访左；无左或左子树已访问完后，再 按 后序 访问右子树,最后访问根结点。
武汉理工大学华夏学院 -信息工程系
,两次进栈的处理及判断方法第一次用正值进栈，即 tpo=top+1 ;s[top]=p，
表示此时去处理左子树结点；
第一次退栈 p=s[top],top=top-1
表示此时已处理完左子树，再准备处理右子树，
并取出右子树结点地址 p=tree[p].rlink（ 注意，这里ｐ已是右子树的地址了）
第二次用负地址进栈，即 top=top+1 ; s[top]=-p
第二次退栈出来的值就是一个负值了。
判断是第一次进栈还是第二次进栈，只需将出栈后的值（放在ｐ中）与０进行比较即可。
武汉理工大学华夏学院 -信息工程系
P=root
Top=-1
P==0
树空 Top++;s[tpo]=p
P=tree[p].llink
P==0 有左子树
top==－ 1
p＝ s[tpo]； top－－
P<0
Top++;s[tpo]=-p
p=-p;访问 p
P=tree[p].rlink
右子树进栈结束
＋
＋
＋
＋
图 5－１ 5后序遍历二叉树非递归算法流程图武汉理工大学华夏学院 -信息工程系三,二叉树的遍历的递归算法了解了二叉树遍历的非递归算法的思想以后，二叉树的递归算法就很容易理解了。其过程描述如下：
void preo( int p)
{ if (p>0)
{ printf(“%c”,tree[p].data) ;
preo(tree[p].llink);
preo(tree[p].rlink);
} }
1、前序遍历
c语言 描述为：
武汉理工大学华夏学院 -信息工程系
2、中序遍历
Void innor(int)
{ if(p>0)
{ innor(tree[p].llink);
printf(“%c”,tree[p].data) ;
innor(tree[p].rlink);
}
}
C语言描述为,
武汉理工大学华夏学院 -信息工程系
3、后序遍历
Void post(int)
{ if(p>0)
{post(tree[p].llink);
post(tree[p].rlink;
printf(“%c”,tree[p].data) ;
}
}
C语言描述为：
武汉理工大学华夏学院 -信息工程系四、二叉树遍历的应用举例方法,1、按后序遍历二叉树，形成遍历序列,EDBCA
2,确定各结点的左右子树，若子树为空，则用 #表示，得出一个输入序列,# # # E # D B # # C A
3,输入一个字符，若为 #，则将 NULL送进栈；若为字符，则形成一个结点，将其值送新结点的数据域中，再从栈中取出两个元素分别作为新结点的右子树指针和左子树指针。
然后将新结点的地址送进栈。
1、建立二叉树的存储结构 — 按扩展后序序列建立二叉链表
A
CB
D
E
武汉理工大学华夏学院 -信息工程系
4、输入结束处理：
当最后一个结点输入后，输入结束标志 \n,
则将栈中的值送入 root中，此时栈空，
算法结束武汉理工大学华夏学院 -信息工程系对准备好的序列 # # # E # D B # # C A建立二叉链表实现是：
1、输入 #，进栈； 2、输入 #，进栈； 3、输入 #，进栈；
NULL
0
NULL
NULL
1
NULL
NULL
2
NULL
4、输入 E,形成结点，进栈； 5、输入 #，进栈；
^ E ^ ENULL
1
E
NULL
2
NULL
6、输入 D,形成结点，进栈； 7、输入 B,形成结点，进栈；
^ E ^
D ^ D
NULL
1
^ B
^ E ^
D ^ B
0
武汉理工大学华夏学院 -信息工程系
NULL
B
1
NULL
B
2
NULL
8、输入 #，进栈； 9、输入 #，进栈；
10、输入 C,形成结点，进栈； 11、输入 A,形成结点，进栈；
^ C ^
C
B
1 ^ B
^ E ^
D ^
A
0^ C ^
A
将 A的地址送进栈，输入结束标志,
栈中值即为根结点地址,移出保存在 root中，
root=s[top];top—
栈空，算法结束。
武汉理工大学华夏学院 -信息工程系算法流程图为：top=-1
输入字符 ch
ch==‘#’
是，将 NULL进栈
top++
S[top]=NULL
P=（ NODE） malloc（ SIZEOF（ NODE））
P->data= ch
P->rlink=s[top];top--;
P->llink=s[top];top--;
top++; s[top]=p;
ch==‘\n’
是 root=s[top];top--;
结束武汉理工大学华夏学院 -信息工程系方法,1、按前序遍历二叉树，形成遍历序列,ABDEC
2,确定各结点的左右子树，若子树为空，则用 #表示，得出一个输入序列,A B # D E # # C # #
3,输入一个非 #字符，形成一个结点，再依次建立其左、右子树。
递归算法见教材建立二叉树的存储结构 — 按前序序列建立二叉链表
A
CB
D
E
武汉理工大学华夏学院 -信息工程系
2、求存于二叉树中的算术表达式的值用二叉树表示算术表达式的递归定义如下,
若算术表达式为数或简单变量,则二叉树中只有根结点 ;
若算术表达式 =(第一操作数 )(运算符 ) (第二操作数 ),则左子树表示第一操作数，右子树表示第二操作数，根结点表示运算符 ;
为讨论简单起见，把问题简化为：以单字符表示，且只有双目运算．例如 －（ a+b)/((c+d)*e)+f＋ g
第一操作数,－（ a+b)/((c+d)*e)+f
第二操作数,g
运算符,+
再将 －（ a+b)/((c+d)*e)+f分解为：
第一操作数,－（ a+b)/((c+d)*e)
第二操作数,f
运算符,+
再将 －（ a+b)/((c+d)*e)分解为：
第一操作数,－（ a+b)
第二操作数,((c+d)*e)
运算符,/
依次类推．例如 -(30+50)/((40+80)*3)+90+16的二叉树为：
武汉理工大学华夏学院 -信息工程系
-(30+50)/((40+80)*3)+90+16的二叉树为：
+
16
90-
/
+
30
+
50
*
3+
8040
前序遍历二叉树得到的序列为,+ + - / + 30 50 * + 40 80 3 90 16
中序遍历二叉树得到的序列为,-30 +50 / 40 +80 * 3+ 90 +16
后序遍历二叉树得到的序列为,30 50 + 40 80 +3 * / - 90 + 16 +
前缀表示式中缀表示式后缀表示式武汉理工大学华夏学院 -信息工程系
４,５ 线索与线索二叉树的概念从二叉树的二叉链表存储结构看出，一棵二叉树会有一半以上的指针字段都是空着的，这是树结构中，有叶结点或只有左子树结点无右子树结点或只有右子树无左子树的结点存在，且叶结点的个数一定是多于内结点的个数形成的。同时，在二叉树的遍历算法中，还需要利用栈来进行遍历过程中回溯结点的处理。这样，就想到了一个问题：能否利用空闲的指针字段存放一些有用信息？例如，能否把把遍历形成的线性序列的前驱和后继结点的地址信息存放在空闲指针字段中？如果能行，
又该如何存放？又如何区别是左右子树的信息还是前驱或后继的信息呢？
武汉理工大学华夏学院 -信息工程系一、线索在一棵二叉树的结点的空闲的左孩子指针字段中存放按某种遍历方法形成的序列中该结点的 前驱 结点的地址；在结点的空闲的右孩子指针字段中存放按某种遍历方法形成的序列中该结点的后继结点的地址。这种附加的指针字段值称为线索。
二、线索二叉树带线索的二叉树，称为线索二叉树，又称为穿线二叉树。
武汉理工大学华夏学院 -信息工程系按照遍历二叉树的方法有前序遍历、中序遍历和后序遍历之分，遍历形成的序列有前序遍历序列、中序遍历序列和后序遍历序列，因此线索二叉树也分为：
１．前序线索二叉树,
即线索为前序遍历的前驱和后继结点的地址。
２．中序线索二叉树,
即线索为中序遍历的前驱和后继结点的地址。
３．后序线索二叉树,
即线索为后序遍历的前驱和后继结点的地址。
三、线索二叉树的分类武汉理工大学华夏学院 -信息工程系四,如何区别结点的指针字段中的值
１．若二叉树采用静态二叉链表表示，由于结点的地址是正的整数（数组的下标），所以，当指针字段的值为正时，就表示为实际的左孩子或右孩子的地址；当指针字段的值为负时，就表示的是线索，即为遍历的前驱或后继的地址。
如图 5－１３所示为前序线索二叉树的静态存储结构。
武汉理工大学华夏学院 -信息工程系
A
CB
D
F G
H
I
E
M
KJ
2
A
8
3
B
7
4
D
5
-3
F
-8
-4
G
6
-8
J
-7
-6
H
-8
-7
C
11
-11
M
-12
-12
K
0
9
E
12
10
I
-10
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
下树的前序遍历序列为,ABDFGJHCEMIK
前序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系在实际应用中中序线索二叉树使用较多，图 5-14给出了中序线索二叉树的存储结构。
下面的二叉树中遍历序列为,FDGJBHACMEKI
A
CB
D
F G
H
I
E
M
KJ
2
A
8
3
B
7
4
D
5
0
F
-3
-3
G
6
-5
J
-2
-2
H
-1
-1
C
11
-8
M
-11
-11
K
-12
9
E
12
10
I
0
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
最左点最右点图 5-14 中序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系注意：
在中序线索二叉树的存储中，有且仅有一个左孩子指针字段值为空的结点，称为最左结点；有且仅有一个右孩子指针字段值为空的结点，称为最右结点，最左结点是中序遍历序列的起始结点（当然无前驱），最右结点是中序遍历序列的终端结点（当然无后继）。因此从最左点开始遍历，到最右点结束，通过 二叉树的存储结构 可以直接处理了。
武汉理工大学华夏学院 -信息工程系
2,若二叉树采用动态二叉链表表示，由于结点的地址，用户不知道，则用实箭头线画出实际左右子树连线，用虚箭头线画出线索。
如图４－１５所示。
Ａ
H
G R
DS
X Y
T
一般二叉树的逻辑结构最左结点最右结点武汉理工大学华夏学院 -信息工程系图 5－１５中序线索二叉树的二叉链表存储结构示意图
root
A ∧
H
G∧ R
S
X Y
D
T
中序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系五,线索的用途
１,在中序线索二叉树中打印中序遍历序列给定一棵中序线索二叉树后,可以直接从其存储结构中打印出中序遍历序列（不再使用栈）。
方法,首先，找出最左结点ｐ,并输出 tree[p].data
再通过ｐ的右子树指针字段 tree[p].rlink查ｐ有否右子树，（ tree[p].rlink>0? ） 若 有,则 去找其左子树 ;若 无,则直接输出右子树重复进行，
直至右子树指针字段值为零 时 为止。
算法框图 见 图 5－１６所示。
2.在中序线索二叉树中找前驱结点和后继结点 。
算法框图 见 图 5－１ 7和图 5-18所示武汉理工大学华夏学院 -信息工程系输入 Root
Ｐ =Root
tree[p].llink=0 P=tree[p].llink
继续找最左点否输出 tree[p].dara
tree[p].rlink<0
P=-tree[p].rlink
否
tree[p].rlink=0
算法结束否
P=tree[p].rlink
tree[p].llink<0
否
P=tree[p].llink
图 5-16 中序遍历中序线索二叉树的算法流程图武汉理工大学华夏学院 -信息工程系输出结果输入ｐ
P=tree[p].llink
p=0
Tree[p].rlink>0
+
P=tree[p].rlink
P无 前驱,返回
P>0
P= --p
+
结束图 5－１ 7在中序线索二叉树中找前驱结点
P =0
P
Tree ].rlink>0
武汉理工大学华夏学院 -信息工程系图 5－１ 8在中序线索二叉树中找后继结点输出结果输入ｐ
P=tree[p].rlink
p=0
Tree[p].llink>0
+
P=tree[p].llink
P无后继，返回
P>0
P= --p
+
结束
P==0
>0
Tree[p].lli k>0
武汉理工大学华夏学院 -信息工程系
5.6 哈夫曼树的应用
5.6.1 带权路径长度一、结点的权值设有一棵二叉树，树中的每一个结点伴随有一个整数值，这个整数值表示了结点的某一种含义，如：使用频率、经济效益等，则称这个整数值为结点的权值。
武汉理工大学华夏学院 -信息工程系二、带权路径长度设一棵二叉树中有ｎ个树叶，每个树叶都对应有一个权值，则将树中各个树叶的枝长（该树叶所在层数－
１）与权值的乘积之和称为该二叉树的带权路径长度，用 WPL表示。
记为：
WPL=w1*(d1-1)+w2*(d2-1)+…… +wn*(dn-1)
其中,wk表示第 ｋ 个树叶的权值；
dｋ 表示第 ｋ 个树叶的所在层数。
武汉理工大学华夏学院 -信息工程系图二图 5－１ 9具有不同路径长度的三棵二叉树
20
2 43
5 5
11
20
3
4 11
18
15
2
图一图三
20
9
5
11
32
4
武汉理工大学华夏学院 -信息工程系例如,图 5－１ 9所示的３棵二叉树的 带权路径长度分别为：
(１ ) WPL=11× 1+４＊２ +２＊３ +３＊３＝ 34
(２ ) WPL=2＊ 2+3＊ 2+4＊ 2+11＊２＝ 40
(３ ) WPL=2＊ 1+３＊ 2+４＊ 3+11＊３＝ 53
很显然，树形不同，其路径长度是不同的。
武汉理工大学华夏学院 -信息工程系三、研究的意义一棵二叉树的带权路径长度，反映了对二叉树中各个树叶结点访问的速度，若 WPL
越大，则访问速度慢，因此，要构造 WPL小的二叉树才能提高访问速度。
武汉理工大学华夏学院 -信息工程系
5.６,２ 哈夫曼树（ Huffman树）
一、定义用给定的ｎ个数值作为ｎ个树叶的权值，可以构造出很多不同形状的二叉树，把 WPL最小的二叉树称为哈夫曼树（ Huffman树 )
又称为最优二叉树。
武汉理工大学华夏学院 -信息工程系二、构造方法
１,用ｎ个权值 w1,w2,w３ …,,wｎ 作为树根，形成有ｎ棵树的森林，且每棵树的左右子树均为空。
２,当森林中的二叉树多于一棵时，重复进行排序、组树过程：
排序,按根结点值从小到大的次序进行根结点排序，形成有序森林。
组树,将最左边的第一、第二棵树（根值最小的两棵树）组成一棵新树，使新树的树根值为两棵子树的根值之和，第一棵为新树的左子树，
第二棵为新树的右子树，再放回森林。
３,重复进行,直至森林中只有一棵树为止。
武汉理工大学华夏学院 -信息工程系三、构造举例设有一个权值集合 W= （ 18,,12,８,4,７） 分别为字符集合 F＝（ ａ,ｂ,ｃ,ｄ,ｅ）的权值，构造 Huffman树的过程如图 5－ 20所示。
四、特点
１,树根的值为所有权值之和。
２,各层结点从左到右依次从小到大排列。
３,权值大的结点离树根近，权值小的结点离树根远。
武汉理工大学华夏学院 -信息工程系
(1)构造森林
(2)树根排序
(3)第 1,2棵组树
(４ )再排序
(５ )再组树
18 12 8 4 7
1287 184
12 8 18
74
11
128 18
12 18
74
11
8
19
74
11
接下页武汉理工大学华夏学院 -信息工程系
12
12 18
8
19
74
11
(6)排序
(7)组树排序
(8)组树，形成一棵二叉树图 5－ 20Huffman树的构造
18 8
19
74
11
30
12 188
19
74
11
30
49
武汉理工大学华夏学院 -信息工程系
5.６,３哈夫曼编码哈夫曼树的一个重要应用是在数据通信工作中设计二进制编码。
所谓哈夫曼编码是指：在一棵哈夫曼树中，将左枝用０表示，右枝用１表示，引向叶结点的枝长用０１二进制码表示出来。
即：设 C=｛ ｃ １,ｃ ２,ｃ ３ …… cn}为待编码的字符集合，又设 W=｛ w1,w2,w3,……,wn｝ 为字符的使用频率（权值）的集合，要对 C中的字符进行哈夫曼编码其方法为,
武汉理工大学华夏学院 -信息工程系
１,用 W集合构造哈夫曼树；
２,在每一条从双亲到左孩子的边上用０标注；
在每一条从双亲到右孩子的边上用１标注；
３,顺序连接从根结点到叶结点上的每条边上的数字，就得到该叶结点的哈夫曼编码。
例如：设 C={ａｂｃｐ },W=｛３,６,１ 2,８｝,
得到的哈夫曼编码是：
ａ １１０
ｂ １１１
ｃ ０
ｐ １０
具体步骤见图 5－２１
武汉理工大学华夏学院 -信息工程系
Ｐ １０
３ ６ １２ ８
３ ６
１２ ８９
３ ６
１２
８ ９
１７
３ ６
１２
８ ９
１７
２９
０
０
Ａ １１０
Ｂ １１１
Ｃ ０
图 5－２１构造哈夫曼编码０
1
1
1
武汉理工大学华夏学院 -信息工程系
5.６,４哈夫曼算法一、思想 已知ｎ个叶结点，形成ｎ－１
个内结点，所以构造的二叉树应有 ２ｎ -１
个结点，故应该用有２ｎ－１个单元的数组作为树的存储区。对给定的ｎ个叶结点
（已知），只需构造ｎ－１个内结点即可。
武汉理工大学华夏学院 -信息工程系二、存储结构采用静态存储方式，设置一个有２ｎ－１
个存储单元的数组ｔｒｅｅ，令ｍ＝２ｎ－１
其中 tree[１ ]～ tree[ｎ ]为叶结点 ;tree[m]是根结点；每一个元素定义四个字段,
tree[i].k --------代表第ｉ个元素的字符信息
tree[i].p --------代表第ｉ个元素的频率信息
tree[i].l ---------代表第ｉ个元素的左子树指针信息
tree[i].r --------代表第ｉ个元素的右子树指针信息武汉理工大学华夏学院 -信息工程系
p —— 为被分类（排序）结点序列的最左点的地址指针,（第一次为 1，每次加 2，表示两个频率最小的根结点组成一棵树）。
q —— 为被分类（排序）结点序列的最右点的地址指针,（第一次为 n－ 1，每次加 1，表示增加一个新结点作为内结点）。
Z —— 作标志位，（当 z＝ 0时，表示根结点序列排序好了，可以组成一颗新二叉树，当 z<>0时，
还要继续进行排序）。
i,j,u —— 为循环控制变量。
武汉理工大学华夏学院 -信息工程系三、算法框图图
4
22
所示武汉理工大学华夏学院 -信息工程系赋初值，将ｎ个叶结点的频率与字符读入给ｐ，ｑ赋值：ｐ＝－１：ｑ＝ｎ－１
p＝ ｐ＋２；ｑ＝ｑ＋１
Ｚ＝０
For j=q-1 to p step -1
For u = p to j
交换 tree[u]与 tree[u+1]的信息
Ｚ＝ 1
+
Tree[q+1].f=tree[p].f+tree[p+1].f
Tree[q+1].r=p+1
Tree[q+1].l=p
For i =1 to n
构造完成结束
-
Tree[u+1].f>=tree[u].f Z＝＝ 0
武汉理工大学华夏学院 -信息工程系注意,tree[l+1]与 tree[l]两个结点信息交换的执行过程为：
x=tree[u+1].k ; tree[u+1].k=tree[u].k ; tree[u].k=x
y=tree[u+1].f ; tree[u+1].f=tree[u].f ; tree[u].f=y
l1=tree[u+1].l ; tree[u+1].l=tree[u].l ; tree[u].l=l1
r1=tree[u+1].r ; tree[u+1].r=tree[u].r ; tree[u].r=r
四个数据字段的值都应进行交换。
四、用动态存储结构处理构造哈夫曼树的算法请参考教材。
武汉理工大学华夏学院 -信息工程系
5.６,3 判定树定义以比较运算为主要操作的算法流程绘成一棵树称为算法的判定树。
例如：在八个球中通过两次用天平称重，找出其中一个轻球。
可以用判定树来描述
武汉理工大学华夏学院 -信息工程系
5.1 树的概念一,树的定义
1.用形式定义方法定义数据结构 B=(K,R)称为树是指,K为结点的非空有限集合,R是满足下列条件的 K上的一个关系：
（ 1）有且仅有一个结点无前驱，被称为树根；
（ 2）除树根以外的其余结点，都有且仅有一个前驱。
2.用递归方法定义树是结点的非空有限集合 T,其中，有一个无前驱被称为树根的结点，其余结点被分成 m（ m>=0） 个互不相交的子集 T1,,T2,…,Tm,每一个子集又都是一棵树，并称为树根的子树。
武汉理工大学华夏学院 -信息工程系二,树的逻辑结构表示
1,树的逻辑结构一般采用图示法。根在上,子树在下,用小圆圈表示结点,用称为边的直线段表示结点之间的关系。
如图 5－ 1所示,其中结点 a为树根，它有两棵子树 b和 c
且 b和 c又是一棵树。
2,树的逻辑结构的二元组表示按照树的形式定义方法描述为：
tree＝（ D,R）
D=（ a,b,c,d,e,f,g,h,j,k,l）
R=(<a,b>,<a,c>,<b,d>,<b,e>,<b,f>,<c,g>,<c,h>,
<e,j>,<e,k>,<g,l>）
武汉理工大学华夏学院 -信息工程系图 5-1 树的逻辑结构表示
a
b c
d e g
j l
hf
k
树根树叶武汉理工大学华夏学院 -信息工程系
3,树的逻辑结构其它表示法。
（ 1) 文氏图表示法 (2)广义表表示
A(B(E,F(J,K),G),C,D(H,I))
H
I
J K
E G
C
B
A
D
表示根
F
表示结点武汉理工大学华夏学院 -信息工程系
（ 3) 凹入式表示法
A
B
E
F
J
K
G
C
D
H
I
武汉理工大学华夏学院 -信息工程系
1,双亲 与 孩子 设 X与 Y为树中的两个结点，若 X
是 Y的前驱，则称 X是 Y的双亲,Y是 X的孩子。
2,兄弟 与 堂兄弟 树中的两个结点 X 与 Y存在有共同的双亲，称 X与 Y为兄弟，若其双亲为兄弟，
则称为堂兄弟
3,分支结点 和 终端结点 有后继结点的结点称为分支结点；没有后继结点的结点称为终端结点或树叶。
4,结点的度 结点的后继结点的个数,称为该结点的度,显然,度为零的结点一定是树叶。
三,树中常用术语武汉理工大学华夏学院 -信息工程系
5.树的度 树中结点度的最大值,称为树的度。
例如：图 5-1树的度为 3,因为该树中,有度为一的 结点、
也有度为二、度为零与 度为三的结点，其度的最大值为三。若一棵树的度为 n时，则称该树为 n度树。
6,结点的层 又称为结点的层次高度，它是从树根开始定义的：即根结点属于第一层，其余结点的层次高度等于其双亲的层次＋ 1。
7,树的层次高度 树的层次高度等于树中结点的层次的最大值。（也称为树的深度）
8,森林 n（ n>=0 ）棵互不相交的树的集合。 注意：
当 n＝ 0时说明森林中无结点，即森林可以为空。（树不能为空）
9.有序树和无序树：若树中结点从左到右是有序的，则称该树为有序树，反之为无序树。
武汉理工大学华夏学院 -信息工程系
1.双亲数组表示 方法：用一个一维数组存储树中的结点，数组元素是一个结构体，该结构体中包含两个字段：
其一为 data字段，用来存放结点的值；其二为 parent字段,用来存储该结点的双亲结点（即该结点的前驱结点）
在数组中的下标地址。
四,树的存储结构当一棵树的逻辑结构确定以后,就应该考虑如何存放在计算机中，存储一棵树时，不仅要存储树中每个结点的值，而且要存储各结点之间的关系，一般可以用三种方法实现：
武汉理工大学华夏学院 -信息工程系例如,以图 5-1所示的三度树为例，存储该树的双亲数组表示,如图 5-2所示。
1
图 5-2 图 4-1树的双亲数组存储表示
data
2
parent
root 1
3 4 5 6 87 9
a b c d e f hg i
0 1 1 2 2 2 33 7
10 11
j k
5 5
存储特点,可以根据每一个结点本身的内容直接读取其双亲结点的地址，但查找孩子结点较困难。
武汉理工大学华夏学院 -信息工程系
2.孩子链表示式方法,把每一个结点的孩子结点排列起来，
构成一个单链表,称为孩子链表。对于一棵有 n个结点的树来说，就有 n个孩子链表,为便于查找,n个链表的表头指针可用顺序表示。
特点,根据每一个结点组成的链表，可以直接读取该结点的孩子结点地址，但查找双亲结点较困难。
武汉理工大学华夏学院 -信息工程系
31
23
45
67
8
910
11
ab
cd
ef
gh
jk
l
24 5 6 ∧
7 8
9 10
11
∧
∧
∧
∧
root 1
∧
∧
∧∧
∧∧
图 5-3 图 5-1所示树的孩子链表存储表示例,以图 5-1所示的三度树为例，其孩子链存储表示如图 5-3所示。
武汉理工大学华夏学院 -信息工程系
3,左孩子右兄弟链表表示方法：设置一个二叉链表，该链表的每一个结点都包含两个指针，分别指向该结点的第一个孩子和紧靠该结点右边的一个兄弟结点，
所以，结点由三个字段构成。
实例,以图 5-1所示的三度树为例，该存储方法的表示如图 5-4所示。
特点,根据结点本身可以直接读到该结点的第一个孩子结点及其最右边一个兄弟结点的地址，但查找双亲结点地址也较困难。
武汉理工大学华夏学院 -信息工程系结点形式,孩子地址 字段 结点数据 值字段 兄弟地址 字段
root
图 5-4 图 5-1所示树的左孩子右兄弟链表存储表示
d∧ e g h∧
b c ∧
a ∧
j∧ f∧ ∧ d∧
k∧
∧
∧
∧
武汉理工大学华夏学院 -信息工程系一、二叉树的定义和基本术语
1,定义,二叉树是结点的有限集合，它可以为空，也可以是由一个根结点和称为根的左右子树的两棵互不相交的二叉树组成。
2,二叉树的基本形态 二叉树共有五种基本树形，如图 5-５所示 。
5.2 二 叉 树
（ 1）无左右子树的二叉树．
（ 2）只有左子树，无右子树的二叉树．
武汉理工大学华夏学院 -信息工程系图 5-5 二叉树的四种基本形态
（ 3）只有右子树，无左子树的二叉树．
（ 4） 既有左子树，又有右子树的二叉树．
（ 5）无结点的空树。
武汉理工大学华夏学院 -信息工程系二,二叉树的性质性质１,在二叉树的第ｉ层上，最多有２ i-1 个结点。（请思考，为什么？）
性质２,在高度为ｈ（ｈ >0 ）的二叉树中，结点总数最多有 2h -1个结点。
原因,由性质１，把每层结点加起来即可 。
性质３,在非空二叉树中，叶结点的个数 比度为 2的结点个数 多 １ 个 。 为什么？
武汉理工大学华夏学院 -信息工程系证明：
设二叉树中结点的总数为ｎ，度为０，１，２的结点个数分别为ｎ 0，ｎ 1，ｎ 2，
则有ｎ＝ｎ 0 +n1+n2 …………… (1)
另外，又从二叉树的边数来看，可以知道：每一棵树除根结点外的其余结点都有一条边与其双亲结点相连，
则 n 个结点应有 n-1条边，这 n-1条边是由分支结点产生的，共有：度为 1的结点为 n1个，产生的边的条数为 n1
条；度为 2的结点为 n2个，产生的边的条数为 2n2条；
这样，有 n -1=n1+2n2 ………… (2)
由（ 1),(2）两式变换可得 n0=n2 + 1 (证毕）
武汉理工大学华夏学院 -信息工程系
1,满二叉树
(１ )定义,当一棵二叉树的每一层的结点个数都达到该层结点数的最大值，则该树称为满二叉树。
(２ )特点：
,在满二叉树中，位于第 K层上的结点数应为 2K－ 1个。
,在满二叉树中，每一个结点的度不是０就是２，没有度为１的结点，且叶结点都在同一层。（最高层）
三,满二叉树与完全二叉树武汉理工大学华夏学院 -信息工程系图 5－６层次高度为四的满二叉树的示意图
N
A
CB
ED GF
IH KJ ML O
(３ ) 满二叉树的图例 如图 5－ 6所示武汉理工大学华夏学院 -信息工程系
2,完全二叉树
（ １ ） 定义,当一棵二叉树，除最底层以外的每一层的结点个数都达到最大值，而最底层的结点又集中在从最左边开始的若干连续位置上，则该树称为完全二叉树。
（ ２） 特点：
在层数为 H的完全二叉树中，位于第 K（ K<H)层上的结点数应为 2K－ 1个,而第 H层上的结点数不能确定。
在完全二叉树中，度为１的结点只能在最底层，且叶结点也在最底层，而非最底层的结点的度只能为２。
满二叉树一定是完全二叉树。
武汉理工大学华夏学院 -信息工程系
(3) 完全二叉树的图例如图 5－７所示图 5－ 7层次高度为四的完全二叉树的示意图
A
CB
ED GF
IH KJ L
武汉理工大学华夏学院 -信息工程系
1、二叉树的顺序存储表示
（ 1) 完全二叉树的顺序存储存储方法,设完全二叉树中有ｎ个结点，
对这ｎ个结点按层次从上到下、同一层从左往右的原则，用自然数１～ｎ依次编号，作为该结点的号数，并设置一个一维数组作为存储该树的存储区，而结点的号数又是该结点在数组中的下标值，用这种方法存储的完全二叉树，
称为完全二叉树的顺序存储。
例如，图 5－ 6给出的 满 二叉树的顺序存储表示如图 5－ 8所 示。
四,二叉树的存储表示武汉理工大学华夏学院 -信息工程系
N
A
CB
ED GF
IH KJ ML O
图 5－８完全二叉树的顺序存储表示示意图
Tree
１ 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ａ B LKJIHGFEDC M N O
武汉理工大学华夏学院 -信息工程系存储 特点：
在 用顺序存储方法存储的完全二叉树中，
查找其孩子结点及双亲结点都十分方便。这是因为：该完全二叉树的根序号为１，其根的左子树结点的序号就是２；右子树结点的序号为３（若存在的话），显然，设某一个结点的序号为ｉ，则其左孩子结点的序号为
２ｉ（当然２ｉ <=n),而右孩子结点的序号为２ｉ＋１（２ｉ＋１ <=n）； 当ｉ＝１时，
该结点无双亲结点，当ｉ >1时，其双亲结点的序号是ｉ／２取整。
武汉理工大学华夏学院 -信息工程系
（２） 一般二叉树的顺序存储存储方法,用完全二叉树的顺序存储方法也可以存储一般二叉树 。做法是,首先，
在二叉树中补上若干虚拟结点使之成为 一棵完全 二 叉树；然后，按上述方法对结点进行编号，并将它们存入数组 tree[１．,m]
中。其中ｍ等于一般二叉树构成的虚拟完全二叉树中的结点的个数。
武汉理工大学华夏学院 -信息工程系例如,图 5－９给出了一棵一般二叉树的顺序存储结 构。
一般二叉树的逻辑结构
A
H D
G R T
S X Y
A
H D
G R T
S X Y
补齐虚拟结点的完全二叉树的逻辑结构
Tree １ 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ａ H STRGD X Y
图 5－９一般二叉树的顺序存储结构示意图武汉理工大学华夏学院 -信息工程系占用的存储空间利用率较低，虚拟结点在数组中要占用存储单元（不可能访问）；
在确定各个结点之间的关系时，要进行判断。如找图４－９中ｉ＝３的结点的左孩子时，由于其左孩子应放在下标为６的数组元素单元中，但 tree［６］为空，故可以断定结点ｉ无左子树。
存储 特点：
武汉理工大学华夏学院 -信息工程系特点,利用动态变量存储树结构，并且各个结点的孩子可以从结点本身反映出来。
2、二叉树的二叉链表存储表示存储方法,所谓二叉树的二叉链表存储表示是指：对于树中的每一个结点用一个三元组结构表示出来，其中包含有两个指针，分别指向对应结点的左孩子结点的地址与右孩子结点的地址。例如，图 5－１０给出了一棵一般二叉树的二叉链表存储结构。
这是一种常用的存储方法。
武汉理工大学华夏学院 -信息工程系一般二叉树的逻辑结构
A
H
D
G R
T
S
X Y
root
A ∧
H
G∧ R∧
S
X ∧∧ Y ∧
D∧ ∧
T ∧∧
一般二叉树的存储结构示意图图 5－ 10二叉树的二叉链表存储结构示意图武汉理工大学华夏学院 -信息工程系
5.3 遍历树形结构一,遍历的概念
1,定义 遍历树是指将树中的结点都访问一次且仅访问一次的操作过程，成为树的遍历。
2,特点 将一个非线性结构线性化遍历后的结果形成一个线性序列
3,遍历方法 前序遍历 后序遍历
4,前序遍历步骤首先访问根结点；再按从左往右的原则，前序 遍历根的每一棵子树。
武汉理工大学华夏学院 -信息工程系
a
b c
d e g
j l
hf
k
例如 图 5－１ 给出的三度树，按前序遍历后得到的序列为,ａ → ｂ → ｄ → ｅ → ｊ → ｋ → ｆ → ｃ → ｇ → ｌ → ｈ
武汉理工大学华夏学院 -信息工程系
5,后序遍历步骤按从左往右的原则，后序遍历根的每一棵子树；后访问根结点 。
例如 图 5－１ 给出的三度树，按后序遍历后的序列为：
ｄ → ｊ → ｋ → ｅ → ｆ → ｂ → ｌ → ｇ → ｈ → ｃ → ａ
武汉理工大学华夏学院 -信息工程系
1,遍历方法
．前序遍历
．中序遍历
．后序遍历
2,前序遍历步骤首先访问根结点；
再前序遍历根的左子树；
最后前序遍历根的右子树。
二,二叉树的遍历武汉理工大学华夏学院 -信息工程系
A
B C
D H E
F G M I
J K
图 5－ 11 二叉树例如图 5－ 11给出的二叉树
A→B → D → F → G → J → H → C → E
→ M → K→ I
按前序遍历的次序是：
遍历后，形成的前序序列为：
A B D F G J H C E M K I
武汉理工大学华夏学院 -信息工程系
A
B
D
F G
J
H
C
E
M
K
I
前序遍历过程变化图武汉理工大学华夏学院 -信息工程系
3、中序遍历步骤首先中序遍历根的左子树；
再访问根结点；
最后中序遍历根的右子树。
例如 图 5－１１ 给出的二叉树按中序遍历后的次序是：
F → D → G → J → B → H → A → C → M →
K → E→ I
遍历后，形成的中序序列为：
F D G J B H A C M K E I
武汉理工大学华夏学院 -信息工程系
F
D
G
J
B
H
A
C
M
K
E
中序遍历过程变化图
I
武汉理工大学华夏学院 -信息工程系
4、后序遍历步骤首先后序遍历根的左子树；
再后序遍历根的右子树；
最后访问根结点。
例如 图 5－１１ 给出的二叉树按后序遍历的次序为：
F→J → G → D → H → B → K→ M → I → E
→ C → A
遍历后，形成的后序序列为：
F J G D H B K M I E C A
武汉理工大学华夏学院 -信息工程系
F
J
G
D H
B
K
M I
E
C
A
后序遍历过程变化图武汉理工大学华夏学院 -信息工程系
5、二叉树遍历形成的线性序列的特点
＋
前序序列为中序序列为后序序列为根结点 左子树 右子树＋ ＋
右子树右子树左子树左子树根结点根结点＋
＋
＋
＋
因为 二叉树 是一棵特殊的树，它 与一棵二度树的区别是,
二叉树可以为空，二度树不能为空；二叉树的左右两棵子树不能交换，二度树的两棵子树可以交换。
6、将一棵ｎ度树转化为二叉树的方法武汉理工大学华夏学院 -信息工程系由于二叉树只有两个子树，所以在存储二叉树时，存储容易实现； 且实现树形结构的操作算法 二叉树又比较简单,加上一般树很容易转换成二叉树，因此研究二叉树 与一般树的转换问题有着现实的重要意义了。
武汉理工大学华夏学院 -信息工程系
5.4 树和森林与二叉树之间的转换一、树和森林的遍历二、树和森林与二叉树之间的转换
1、一棵ｎ度树转化为二叉树；
2、森林转化为二叉树；
3、二叉树转化为森林；
武汉理工大学华夏学院 -信息工程系
(１）保留双亲结点与最左孩子之间的联系，割断双亲结点与其余孩子之间的联系，建立兄弟结点之间的联系。
(２ ) 将兄弟间的联系（水平线）顺时针方向旋转 45,形成一棵根结点无右子树的二叉树。
一棵ｎ度树转化为二叉树的步骤是：
图 5－１２ 给出了一棵一般树转换成一棵二叉树的转换过程武汉理工大学华夏学院 -信息工程系一棵三度树
a
cb
d f g h
j
e
k l
按左孩子右兄弟相连
a
cb
d f g h
j
e
k l
转换后的二叉树图４－１２树转换成二叉树
a
b
d c
e g
f hl
k
j
武汉理工大学华夏学院 -信息工程系一棵ｎ度树转化成的二叉树的特点是：
１．根结点无右子树
２．某一个结点的左子树是原来ｎ度树中的孩子结点；而右子树为原来ｎ度树中的兄弟结点。
显然，由特点 2很容易理解，为什么根结点一定没有右子树。
武汉理工大学华夏学院 -信息工程系
2、森林转化为二叉树的 方法：
（ 1） 森林为空时转化为空二叉树；
（ 2）森林不空时把森林中的每一棵树转化为二叉树后，再将后一棵二叉树挂在前一棵二叉树的右子树下。
3、二叉树转化为森林 方法：
（ 1） 二叉树为空时转化为空森林；
（ 2）二叉树右子树不空时把 每一棵右子树折下后还原为一般树后；
（ 3）二叉树右子树空时，生成一棵树的森林；
武汉理工大学华夏学院 -信息工程系
5.4 二叉树的遍历算法在讨论二叉树遍历算法前，先采用二叉树的静态二叉链表作为二叉树的存储结构。所谓静态二叉链表是指：用一个一维数组作为二叉树的存储区域，
其数组名为 ｔｒｅｅ,数组的上界定义为整型量ｎ
（表示了树中结点的个数）。每一个数组元素又是一个记录（结构体），它由三个域组成：数据字段
ｄａｔａ ；左孩子指针字段 ｌｌｉｎｋ 和右孩子指针字段 ｒｌｉｎｋ,ｌｌｉｎｋ 与 ｒｌｉｎｋ 的类型为整型，表示结点地址（即数组元素的下标），
ｄａｔａ 字段由结点值确定。
一,二叉树数据类型描述武汉理工大学华夏学院 -信息工程系因此，有数据类型说为：
c语言定义
#define n0 50 //数组最大下标
#define datatype char;
struct node {
datatype data ;
int llink,rlink ; } ;
node tree[n0+1]
int root ; //根结点地址指针武汉理工大学华夏学院 -信息工程系图 5-13 给出了一棵二叉树和它的静态二叉链表的存储结构
A
CB
D
F G
H
I
E
M
KJ
图 5-13 二叉树和它的静态二叉链表存储结构
2
A
8
3
B
7
4
D
5
0
F
0
0
G
6
0
J
0
0
H
0
0
C
11
0
M
0
0
K
0
9
E
12
10
I
0
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
武汉理工大学华夏学院 -信息工程系设ｓ,array[1..n0] of integer; 为一个栈区，
top,integer; 为栈指针，
ｐ,integer; 是一个辅助变量武汉理工大学华夏学院 -信息工程系算法思想,先从根结点开始访问，再看其有否左子树，有则访左；无左或左子树已访问完，则访右子树。
二,二叉树遍历的非递归算法处理方法,设置一个栈，用来对已访问后的结点的右子树进行保存，当根结点访问完后，若其有右子树，则先将右子树的地址送进栈区保存，再取其左子树的地址进行访问，若无左子树或已访问完左子树，
则退栈访问右子树，直至栈空。
1、前序遍历武汉理工大学华夏学院 -信息工程系算法中应考虑的问题与涉及的基本判断
（１） 二叉树空否？表示为 root＝ ０
（２） 结点ｐ有否左子树？
表示为 tree[p].llink=0？
结点ｐ有否右子树？
表示为 tree[p].ｒ link=0？
（３） 栈空否？
表示为 top＝ -1？
该算法用以下算法框图表示为图 5-13所示武汉理工大学华夏学院 -信息工程系输入 root
P＝ root
P＝＝ 0
空树，结束
＋
top＝ -1
访问 p
tree[p].rlink==0
top＝ top+1；
S[top]=tree[p].rlink
＋
P＝ tree[p].llink
P＝＝ 0 －
top＝＝ -1＋
结束 P＝ s[top]； top＝ top－ 1
退栈访右子树有左子树图 5－１３前序遍历二叉树非递归算法流程图武汉理工大学华夏学院 -信息工程系处理方法,利用 栈，先将根结点送入栈保存，
然后沿左链访问左子树，当左子树访问完后，
再退栈访问根结点，最后沿右子树访问，直至栈空。 该算法用以下算法框图表示为图 5-14所示二、中序遍历算法思想,从根结点开始，看其有否左子树，有则 按中序 遍历访 左 子树 ；无左或左子树已访问完后，再 访问根 结 点，最后 按中序 访问右子树。
武汉理工大学华夏学院 -信息工程系图 5－１ 4中序遍历二叉树非递归算法流程图输入 root ; t0p=-1
P＝ root
P＝＝ 0
空树，结束
＋
top=top+1 ; S[top]=p
P==0
＋
top＝＝ -1＋
结束 P＝ s[top]； top＝ top－ 1
访问 p;
p=tree[p].rlink
P=tree[p].llink有左子树，再进栈武汉理工大学华夏学院 -信息工程系处理方法,利用 栈，采用两次进栈、退栈的方法实现后序遍历。即先将根结点送入栈保存，然后沿左链访问左子树，当左子树访问完后，则退栈（第一次）取其结点的右子树地址，并把该结点再次送入栈中保存，然后沿右子树访问，当右子树访问完后，再退栈
（第二次）访问该结点，直至栈空。
3、后序遍历算法思想,从根结点开始，先看其有否左子树，有则 按后序遍历 访左；无左或左子树已访问完后，再 按 后序 访问右子树,最后访问根结点。
武汉理工大学华夏学院 -信息工程系
,两次进栈的处理及判断方法第一次用正值进栈，即 tpo=top+1 ;s[top]=p，
表示此时去处理左子树结点；
第一次退栈 p=s[top],top=top-1
表示此时已处理完左子树，再准备处理右子树，
并取出右子树结点地址 p=tree[p].rlink（ 注意，这里ｐ已是右子树的地址了）
第二次用负地址进栈，即 top=top+1 ; s[top]=-p
第二次退栈出来的值就是一个负值了。
判断是第一次进栈还是第二次进栈，只需将出栈后的值（放在ｐ中）与０进行比较即可。
武汉理工大学华夏学院 -信息工程系
P=root
Top=-1
P==0
树空 Top++;s[tpo]=p
P=tree[p].llink
P==0 有左子树
top==－ 1
p＝ s[tpo]； top－－
P<0
Top++;s[tpo]=-p
p=-p;访问 p
P=tree[p].rlink
右子树进栈结束
＋
＋
＋
＋
图 5－１ 5后序遍历二叉树非递归算法流程图武汉理工大学华夏学院 -信息工程系三,二叉树的遍历的递归算法了解了二叉树遍历的非递归算法的思想以后，二叉树的递归算法就很容易理解了。其过程描述如下：
void preo( int p)
{ if (p>0)
{ printf(“%c”,tree[p].data) ;
preo(tree[p].llink);
preo(tree[p].rlink);
} }
1、前序遍历
c语言 描述为：
武汉理工大学华夏学院 -信息工程系
2、中序遍历
Void innor(int)
{ if(p>0)
{ innor(tree[p].llink);
printf(“%c”,tree[p].data) ;
innor(tree[p].rlink);
}
}
C语言描述为,
武汉理工大学华夏学院 -信息工程系
3、后序遍历
Void post(int)
{ if(p>0)
{post(tree[p].llink);
post(tree[p].rlink;
printf(“%c”,tree[p].data) ;
}
}
C语言描述为：
武汉理工大学华夏学院 -信息工程系四、二叉树遍历的应用举例方法,1、按后序遍历二叉树，形成遍历序列,EDBCA
2,确定各结点的左右子树，若子树为空，则用 #表示，得出一个输入序列,# # # E # D B # # C A
3,输入一个字符，若为 #，则将 NULL送进栈；若为字符，则形成一个结点，将其值送新结点的数据域中，再从栈中取出两个元素分别作为新结点的右子树指针和左子树指针。
然后将新结点的地址送进栈。
1、建立二叉树的存储结构 — 按扩展后序序列建立二叉链表
A
CB
D
E
武汉理工大学华夏学院 -信息工程系
4、输入结束处理：
当最后一个结点输入后，输入结束标志 \n,
则将栈中的值送入 root中，此时栈空，
算法结束武汉理工大学华夏学院 -信息工程系对准备好的序列 # # # E # D B # # C A建立二叉链表实现是：
1、输入 #，进栈； 2、输入 #，进栈； 3、输入 #，进栈；
NULL
0
NULL
NULL
1
NULL
NULL
2
NULL
4、输入 E,形成结点，进栈； 5、输入 #，进栈；
^ E ^ ENULL
1
E
NULL
2
NULL
6、输入 D,形成结点，进栈； 7、输入 B,形成结点，进栈；
^ E ^
D ^ D
NULL
1
^ B
^ E ^
D ^ B
0
武汉理工大学华夏学院 -信息工程系
NULL
B
1
NULL
B
2
NULL
8、输入 #，进栈； 9、输入 #，进栈；
10、输入 C,形成结点，进栈； 11、输入 A,形成结点，进栈；
^ C ^
C
B
1 ^ B
^ E ^
D ^
A
0^ C ^
A
将 A的地址送进栈，输入结束标志,
栈中值即为根结点地址,移出保存在 root中，
root=s[top];top—
栈空，算法结束。
武汉理工大学华夏学院 -信息工程系算法流程图为：top=-1
输入字符 ch
ch==‘#’
是，将 NULL进栈
top++
S[top]=NULL
P=（ NODE） malloc（ SIZEOF（ NODE））
P->data= ch
P->rlink=s[top];top--;
P->llink=s[top];top--;
top++; s[top]=p;
ch==‘\n’
是 root=s[top];top--;
结束武汉理工大学华夏学院 -信息工程系方法,1、按前序遍历二叉树，形成遍历序列,ABDEC
2,确定各结点的左右子树，若子树为空，则用 #表示，得出一个输入序列,A B # D E # # C # #
3,输入一个非 #字符，形成一个结点，再依次建立其左、右子树。
递归算法见教材建立二叉树的存储结构 — 按前序序列建立二叉链表
A
CB
D
E
武汉理工大学华夏学院 -信息工程系
2、求存于二叉树中的算术表达式的值用二叉树表示算术表达式的递归定义如下,
若算术表达式为数或简单变量,则二叉树中只有根结点 ;
若算术表达式 =(第一操作数 )(运算符 ) (第二操作数 ),则左子树表示第一操作数，右子树表示第二操作数，根结点表示运算符 ;
为讨论简单起见，把问题简化为：以单字符表示，且只有双目运算．例如 －（ a+b)/((c+d)*e)+f＋ g
第一操作数,－（ a+b)/((c+d)*e)+f
第二操作数,g
运算符,+
再将 －（ a+b)/((c+d)*e)+f分解为：
第一操作数,－（ a+b)/((c+d)*e)
第二操作数,f
运算符,+
再将 －（ a+b)/((c+d)*e)分解为：
第一操作数,－（ a+b)
第二操作数,((c+d)*e)
运算符,/
依次类推．例如 -(30+50)/((40+80)*3)+90+16的二叉树为：
武汉理工大学华夏学院 -信息工程系
-(30+50)/((40+80)*3)+90+16的二叉树为：
+
16
90-
/
+
30
+
50
*
3+
8040
前序遍历二叉树得到的序列为,+ + - / + 30 50 * + 40 80 3 90 16
中序遍历二叉树得到的序列为,-30 +50 / 40 +80 * 3+ 90 +16
后序遍历二叉树得到的序列为,30 50 + 40 80 +3 * / - 90 + 16 +
前缀表示式中缀表示式后缀表示式武汉理工大学华夏学院 -信息工程系
４,５ 线索与线索二叉树的概念从二叉树的二叉链表存储结构看出，一棵二叉树会有一半以上的指针字段都是空着的，这是树结构中，有叶结点或只有左子树结点无右子树结点或只有右子树无左子树的结点存在，且叶结点的个数一定是多于内结点的个数形成的。同时，在二叉树的遍历算法中，还需要利用栈来进行遍历过程中回溯结点的处理。这样，就想到了一个问题：能否利用空闲的指针字段存放一些有用信息？例如，能否把把遍历形成的线性序列的前驱和后继结点的地址信息存放在空闲指针字段中？如果能行，
又该如何存放？又如何区别是左右子树的信息还是前驱或后继的信息呢？
武汉理工大学华夏学院 -信息工程系一、线索在一棵二叉树的结点的空闲的左孩子指针字段中存放按某种遍历方法形成的序列中该结点的 前驱 结点的地址；在结点的空闲的右孩子指针字段中存放按某种遍历方法形成的序列中该结点的后继结点的地址。这种附加的指针字段值称为线索。
二、线索二叉树带线索的二叉树，称为线索二叉树，又称为穿线二叉树。
武汉理工大学华夏学院 -信息工程系按照遍历二叉树的方法有前序遍历、中序遍历和后序遍历之分，遍历形成的序列有前序遍历序列、中序遍历序列和后序遍历序列，因此线索二叉树也分为：
１．前序线索二叉树,
即线索为前序遍历的前驱和后继结点的地址。
２．中序线索二叉树,
即线索为中序遍历的前驱和后继结点的地址。
３．后序线索二叉树,
即线索为后序遍历的前驱和后继结点的地址。
三、线索二叉树的分类武汉理工大学华夏学院 -信息工程系四,如何区别结点的指针字段中的值
１．若二叉树采用静态二叉链表表示，由于结点的地址是正的整数（数组的下标），所以，当指针字段的值为正时，就表示为实际的左孩子或右孩子的地址；当指针字段的值为负时，就表示的是线索，即为遍历的前驱或后继的地址。
如图 5－１３所示为前序线索二叉树的静态存储结构。
武汉理工大学华夏学院 -信息工程系
A
CB
D
F G
H
I
E
M
KJ
2
A
8
3
B
7
4
D
5
-3
F
-8
-4
G
6
-8
J
-7
-6
H
-8
-7
C
11
-11
M
-12
-12
K
0
9
E
12
10
I
-10
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
下树的前序遍历序列为,ABDFGJHCEMIK
前序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系在实际应用中中序线索二叉树使用较多，图 5-14给出了中序线索二叉树的存储结构。
下面的二叉树中遍历序列为,FDGJBHACMEKI
A
CB
D
F G
H
I
E
M
KJ
2
A
8
3
B
7
4
D
5
0
F
-3
-3
G
6
-5
J
-2
-2
H
-1
-1
C
11
-8
M
-11
-11
K
-12
9
E
12
10
I
0
llink
data
rlink
root 1
1 2 3 4 5 6 7 8 9 10 11 12
最左点最右点图 5-14 中序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系注意：
在中序线索二叉树的存储中，有且仅有一个左孩子指针字段值为空的结点，称为最左结点；有且仅有一个右孩子指针字段值为空的结点，称为最右结点，最左结点是中序遍历序列的起始结点（当然无前驱），最右结点是中序遍历序列的终端结点（当然无后继）。因此从最左点开始遍历，到最右点结束，通过 二叉树的存储结构 可以直接处理了。
武汉理工大学华夏学院 -信息工程系
2,若二叉树采用动态二叉链表表示，由于结点的地址，用户不知道，则用实箭头线画出实际左右子树连线，用虚箭头线画出线索。
如图４－１５所示。
Ａ
H
G R
DS
X Y
T
一般二叉树的逻辑结构最左结点最右结点武汉理工大学华夏学院 -信息工程系图 5－１５中序线索二叉树的二叉链表存储结构示意图
root
A ∧
H
G∧ R
S
X Y
D
T
中序线索二叉树的存储结构示意图武汉理工大学华夏学院 -信息工程系五,线索的用途
１,在中序线索二叉树中打印中序遍历序列给定一棵中序线索二叉树后,可以直接从其存储结构中打印出中序遍历序列（不再使用栈）。
方法,首先，找出最左结点ｐ,并输出 tree[p].data
再通过ｐ的右子树指针字段 tree[p].rlink查ｐ有否右子树，（ tree[p].rlink>0? ） 若 有,则 去找其左子树 ;若 无,则直接输出右子树重复进行，
直至右子树指针字段值为零 时 为止。
算法框图 见 图 5－１６所示。
2.在中序线索二叉树中找前驱结点和后继结点 。
算法框图 见 图 5－１ 7和图 5-18所示武汉理工大学华夏学院 -信息工程系输入 Root
Ｐ =Root
tree[p].llink=0 P=tree[p].llink
继续找最左点否输出 tree[p].dara
tree[p].rlink<0
P=-tree[p].rlink
否
tree[p].rlink=0
算法结束否
P=tree[p].rlink
tree[p].llink<0
否
P=tree[p].llink
图 5-16 中序遍历中序线索二叉树的算法流程图武汉理工大学华夏学院 -信息工程系输出结果输入ｐ
P=tree[p].llink
p=0
Tree[p].rlink>0
+
P=tree[p].rlink
P无 前驱,返回
P>0
P= --p
+
结束图 5－１ 7在中序线索二叉树中找前驱结点
P =0
P
Tree ].rlink>0
武汉理工大学华夏学院 -信息工程系图 5－１ 8在中序线索二叉树中找后继结点输出结果输入ｐ
P=tree[p].rlink
p=0
Tree[p].llink>0
+
P=tree[p].llink
P无后继，返回
P>0
P= --p
+
结束
P==0
>0
Tree[p].lli k>0
武汉理工大学华夏学院 -信息工程系
5.6 哈夫曼树的应用
5.6.1 带权路径长度一、结点的权值设有一棵二叉树，树中的每一个结点伴随有一个整数值，这个整数值表示了结点的某一种含义，如：使用频率、经济效益等，则称这个整数值为结点的权值。
武汉理工大学华夏学院 -信息工程系二、带权路径长度设一棵二叉树中有ｎ个树叶，每个树叶都对应有一个权值，则将树中各个树叶的枝长（该树叶所在层数－
１）与权值的乘积之和称为该二叉树的带权路径长度，用 WPL表示。
记为：
WPL=w1*(d1-1)+w2*(d2-1)+…… +wn*(dn-1)
其中,wk表示第 ｋ 个树叶的权值；
dｋ 表示第 ｋ 个树叶的所在层数。
武汉理工大学华夏学院 -信息工程系图二图 5－１ 9具有不同路径长度的三棵二叉树
20
2 43
5 5
11
20
3
4 11
18
15
2
图一图三
20
9
5
11
32
4
武汉理工大学华夏学院 -信息工程系例如,图 5－１ 9所示的３棵二叉树的 带权路径长度分别为：
(１ ) WPL=11× 1+４＊２ +２＊３ +３＊３＝ 34
(２ ) WPL=2＊ 2+3＊ 2+4＊ 2+11＊２＝ 40
(３ ) WPL=2＊ 1+３＊ 2+４＊ 3+11＊３＝ 53
很显然，树形不同，其路径长度是不同的。
武汉理工大学华夏学院 -信息工程系三、研究的意义一棵二叉树的带权路径长度，反映了对二叉树中各个树叶结点访问的速度，若 WPL
越大，则访问速度慢，因此，要构造 WPL小的二叉树才能提高访问速度。
武汉理工大学华夏学院 -信息工程系
5.６,２ 哈夫曼树（ Huffman树）
一、定义用给定的ｎ个数值作为ｎ个树叶的权值，可以构造出很多不同形状的二叉树，把 WPL最小的二叉树称为哈夫曼树（ Huffman树 )
又称为最优二叉树。
武汉理工大学华夏学院 -信息工程系二、构造方法
１,用ｎ个权值 w1,w2,w３ …,,wｎ 作为树根，形成有ｎ棵树的森林，且每棵树的左右子树均为空。
２,当森林中的二叉树多于一棵时，重复进行排序、组树过程：
排序,按根结点值从小到大的次序进行根结点排序，形成有序森林。
组树,将最左边的第一、第二棵树（根值最小的两棵树）组成一棵新树，使新树的树根值为两棵子树的根值之和，第一棵为新树的左子树，
第二棵为新树的右子树，再放回森林。
３,重复进行,直至森林中只有一棵树为止。
武汉理工大学华夏学院 -信息工程系三、构造举例设有一个权值集合 W= （ 18,,12,８,4,７） 分别为字符集合 F＝（ ａ,ｂ,ｃ,ｄ,ｅ）的权值，构造 Huffman树的过程如图 5－ 20所示。
四、特点
１,树根的值为所有权值之和。
２,各层结点从左到右依次从小到大排列。
３,权值大的结点离树根近，权值小的结点离树根远。
武汉理工大学华夏学院 -信息工程系
(1)构造森林
(2)树根排序
(3)第 1,2棵组树
(４ )再排序
(５ )再组树
18 12 8 4 7
1287 184
12 8 18
74
11
128 18
12 18
74
11
8
19
74
11
接下页武汉理工大学华夏学院 -信息工程系
12
12 18
8
19
74
11
(6)排序
(7)组树排序
(8)组树，形成一棵二叉树图 5－ 20Huffman树的构造
18 8
19
74
11
30
12 188
19
74
11
30
49
武汉理工大学华夏学院 -信息工程系
5.６,３哈夫曼编码哈夫曼树的一个重要应用是在数据通信工作中设计二进制编码。
所谓哈夫曼编码是指：在一棵哈夫曼树中，将左枝用０表示，右枝用１表示，引向叶结点的枝长用０１二进制码表示出来。
即：设 C=｛ ｃ １,ｃ ２,ｃ ３ …… cn}为待编码的字符集合，又设 W=｛ w1,w2,w3,……,wn｝ 为字符的使用频率（权值）的集合，要对 C中的字符进行哈夫曼编码其方法为,
武汉理工大学华夏学院 -信息工程系
１,用 W集合构造哈夫曼树；
２,在每一条从双亲到左孩子的边上用０标注；
在每一条从双亲到右孩子的边上用１标注；
３,顺序连接从根结点到叶结点上的每条边上的数字，就得到该叶结点的哈夫曼编码。
例如：设 C={ａｂｃｐ },W=｛３,６,１ 2,８｝,
得到的哈夫曼编码是：
ａ １１０
ｂ １１１
ｃ ０
ｐ １０
具体步骤见图 5－２１
武汉理工大学华夏学院 -信息工程系
Ｐ １０
３ ６ １２ ８
３ ６
１２ ８９
３ ６
１２
８ ９
１７
３ ６
１２
８ ９
１７
２９
０
０
Ａ １１０
Ｂ １１１
Ｃ ０
图 5－２１构造哈夫曼编码０
1
1
1
武汉理工大学华夏学院 -信息工程系
5.６,４哈夫曼算法一、思想 已知ｎ个叶结点，形成ｎ－１
个内结点，所以构造的二叉树应有 ２ｎ -１
个结点，故应该用有２ｎ－１个单元的数组作为树的存储区。对给定的ｎ个叶结点
（已知），只需构造ｎ－１个内结点即可。
武汉理工大学华夏学院 -信息工程系二、存储结构采用静态存储方式，设置一个有２ｎ－１
个存储单元的数组ｔｒｅｅ，令ｍ＝２ｎ－１
其中 tree[１ ]～ tree[ｎ ]为叶结点 ;tree[m]是根结点；每一个元素定义四个字段,
tree[i].k --------代表第ｉ个元素的字符信息
tree[i].p --------代表第ｉ个元素的频率信息
tree[i].l ---------代表第ｉ个元素的左子树指针信息
tree[i].r --------代表第ｉ个元素的右子树指针信息武汉理工大学华夏学院 -信息工程系
p —— 为被分类（排序）结点序列的最左点的地址指针,（第一次为 1，每次加 2，表示两个频率最小的根结点组成一棵树）。
q —— 为被分类（排序）结点序列的最右点的地址指针,（第一次为 n－ 1，每次加 1，表示增加一个新结点作为内结点）。
Z —— 作标志位，（当 z＝ 0时，表示根结点序列排序好了，可以组成一颗新二叉树，当 z<>0时，
还要继续进行排序）。
i,j,u —— 为循环控制变量。
武汉理工大学华夏学院 -信息工程系三、算法框图图
4
22
所示武汉理工大学华夏学院 -信息工程系赋初值，将ｎ个叶结点的频率与字符读入给ｐ，ｑ赋值：ｐ＝－１：ｑ＝ｎ－１
p＝ ｐ＋２；ｑ＝ｑ＋１
Ｚ＝０
For j=q-1 to p step -1
For u = p to j
交换 tree[u]与 tree[u+1]的信息
Ｚ＝ 1
+
Tree[q+1].f=tree[p].f+tree[p+1].f
Tree[q+1].r=p+1
Tree[q+1].l=p
For i =1 to n
构造完成结束
-
Tree[u+1].f>=tree[u].f Z＝＝ 0
武汉理工大学华夏学院 -信息工程系注意,tree[l+1]与 tree[l]两个结点信息交换的执行过程为：
x=tree[u+1].k ; tree[u+1].k=tree[u].k ; tree[u].k=x
y=tree[u+1].f ; tree[u+1].f=tree[u].f ; tree[u].f=y
l1=tree[u+1].l ; tree[u+1].l=tree[u].l ; tree[u].l=l1
r1=tree[u+1].r ; tree[u+1].r=tree[u].r ; tree[u].r=r
四个数据字段的值都应进行交换。
四、用动态存储结构处理构造哈夫曼树的算法请参考教材。
武汉理工大学华夏学院 -信息工程系
5.６,3 判定树定义以比较运算为主要操作的算法流程绘成一棵树称为算法的判定树。
例如：在八个球中通过两次用天平称重，找出其中一个轻球。
可以用判定树来描述
