第 5章 树和二叉树本章中主要介绍下列内容：
树的逻辑定义和存储结构
二叉树的逻辑定义、存储结构
二叉树的基本操作算法
树和二叉树的转换
哈夫曼树及其应用退出
5.1 树
5.2 二叉树
5.3 哈夫曼树及其应用
5.1 树
5.1.1 树的定义和基本运算
1,定义树是一种常用的非线性结构。我们可以这样定义：
树 是 n（ n≥0）个结点的有限集合。若 n=0，则称为 空树 ；否则，有且仅有一个特定的结点被称为 根,当 n>1
时，其余结点被分成 m（ m>0）个互不相交的子集 T1，
T2,...,Tm，每个子集又是一棵树。由此可以看出，
树的定义是递归。
图 5-1
K L M
E F G H I J
B C D
AA?
(a) (b) (c)
结点 数据元素的内容及其指向其子树根的分支统称为结点。
结点的度 结点的分支数。
终端结点（叶子） 度为 0的结点。
非终端结点 度不为 0的结点。
结点的层次 树中根结点的层次为 1，根结点子树的根为第 2层，以此类推。
树的度 树中所有结点度的最大值。
树的深度 树中所有结点层次的最大值。
有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
森林 是 m（ m≥ 0）棵互不相交的树的集合。
在树结构中，结点之间的关系又可以用家族关系描述，定义如下：
孩子、双亲 结点子树的根称为这个结点的孩子，
而这个结点又被称为孩子的双亲。
子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙。
祖先 从根结点到该结点路径上的所有结点。
兄弟 同一个双亲的孩子之间互为兄弟。
堂兄弟 双亲在同一层的结点互为堂兄弟。
2,树的基本运算常用操作：
（ 1） 构造一个树 CreateTree (T)
（ 2） 清空以 T为根的树 ClearTree(T)
（ 3） 判断树是否为空 TreeEmpty(T)
（ 4） 获取给定结点的第 i个孩子 Child(T,node,i)
（ 5） 获取给定结点的双亲 Parent(T,node)
（ 6） 遍历树 Traverse(T)
对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，
一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依
5.1.2 树的存储结构
1,双亲表示法树的双亲表示法主要描述的是结点的双亲关系。
图 5-3
下标 i nf o p a re n
t
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 1
6 G 3
7 H 6
8 I 6
9 J 6
H I J
E F G
B C D
A
A
B DC
E F G
H I J
类型定义：
#define MAX_TREE_NODE_SIZE 100
typedef struct {
TEntryType info;
int parent;
} ParentNode;
typedef struct {
ParentNode item[MAX_TREE_NODE_SIZE];
int n; //树中当前的结点数目
}ParentTree;
这种存储方法的特点是寻找结点的双亲很容易，
但寻找结点的孩子比较困难。
算法实现举例：
int Parent(ParentTree T,int node)
{ if (node<0||node>=T.n) return -2;
else return T.item[node].parent;
}
2,孩子表示法孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：
图 5-4
root 0 A 2 1 4 ^
1 C ^
2 B 3 5 ^
3 E ^
4 D 6 ^
5 F ^
6 G 7 8 9 ^
7 H ^
8 I ^
9 J ^
在 C语言中，这种存储形式定义如下：
#define MAX_TREE_NODE_SIZE 10
typedef struct ChildNode{
int child; //该孩子结点在一维数组中的下标值
struct ChileNode *next; //指向下一个孩子结点
}CNode;
typedef struct{
TEntryType info; //结点信息
CNode *firstchild; //指向第一个孩子结点的指针
}TNode;
typedef struct {
TNode item[MAX_TREE_NODE_SIZE];
int n,root;
//n为树中当前结点的数目,root为根结点在一维数组中的位置
}ChildTree;
这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，
可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域 parent，用来指示结点的双亲在一维数组中的位置。
获取给定结点第 i个孩子的操作算法实现：
int Child(ChildTree T,int node,int i)
{
if (node<0||node>=T.n) return -2；
p=T.item[node].firstchild; j=1;
while (p&&j!=i) { p=p->next; j++;}
if (!p) return -2;
else return p->child;
}
3,孩子兄弟表示法孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：
f i r s t c h i l d i t e m n e x t s i b l i
ng
其中,firstchild为指向该结点第一个孩子的指针，
nextsibling为指向该结点的下一个兄弟,item是数据元素内容。举例：
图 5-5
^ H ^ I ^ J ^
^ E ^ F ^ G ^
B ^ C D ^
A ^
T
在 C语言中，这种存储形式定义如下：
typedef struct CSNode{
EntryType item;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
void AllChild(CSTree T,CSTree p)
//输出树中 p指针所指结点的所有孩子信息
{
q=p->fisrtchild;
while (q) {
printf(“%c”,q ->item); q=q->nextsibling;
}
}
5.2 二叉树
5.2.1 二叉树的定义和基本运算
1,定义定义,二叉树 是另一种树形结构。它与树形结构的区别是：
（ 1）每个结点最多有两棵子树；
（ 2）子树有左右之分。
二叉树也可以用递归的形式定义。即：二叉树是
n（ n≥ 0）个结点的有限集合。当 n=0时，称为空二叉树；当 n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，
另一个作为右子集，每个子集又是一个二叉树。
图 5-6
G H
D E F
B C
A
二叉树的 5种形态：
图 5-7
(a) (b) (c) (d) (e)
2,二叉树的基本运算
（ 1） 构造一棵二叉树 CreateBTree ( BT)
（ 2）清空以 BT为根的二叉树 ClearBTree(BT)
（ 3）判断二叉树是否为空 BTreeEmpty(BT)
（ 4）获取给定结点的左孩子和右孩子
LeftChild(BT,node),RightChild(BT,node)
（ 5）获取给定结点的双亲 Parent(BT,node)
（ 6）遍历二叉树 Traverse(BT)
2．二叉树的性质二叉树具有下列 5个重要的性质。
【 性质 1】 在二叉树的第 i层上最多有 2i-1个结点
（ i≥ 1）。
叉树的第 1层只有一个根结点，所以,i=1时,2i-
1=21-1=20=1成立。
假设对所有的 j,1≤j<i成立，即第 j层上最多有 2j-1
个结点成立。若 j=i-1，则第 j层上最多有 2j-1=2i-2个结点。
由于在二叉树中，每个结点的度最大为 2，所以可以推导出第 i层最多的结点个数就是第 i-1层最多结点个数的
2倍，即 2i-2*2=2i-1。
【 性质 2】 深度为 K的二叉树最多有 2K-1个结点
（ K≥ 1）。
由性质 1可以得出,1至 K层各层最多的结点个数分别为,20,21,22,23,...,2K-1。这是一个以 2为比值的等比数列，前 n项之和的计算公式为：
q
qaa
S
n
n
1
*1
其中 a1为第一项,an为第 n项,q为比值。可以得到，该数列前 K项之和为：
12
21
2*
1
2
0
2
K
K
【 性质 3】 对于任意一棵二叉树 BT，如果度为 0的结点个数为 n0，度为 2的结点个数为 n2，则 n0=n2+1。
证明：假设度为 1的结点个数为 n1，结点总数为 n，
B为二叉树中的分支数。
因为在二叉树中，所有结点的度均小于或等于 2，
所以结点总数为：
n=n0+n1+n2 （ 1）
再查看一下分支数。在二叉树中，除根结点之外，
每个结点都有一个从上向下的分支指向，所以，总的结点个数 n与分支数 B之间的关系为,n=B+1。
又因为在二叉树中，度为 1的结点产生 1个分支，
度为 2的结点产生 2个分支，所以分支数 B可以表示为：
B=n1+2n2。
将此式代入上式，得：
n=n1+2n2+1 （ 2）
用（ 1）式减去（ 2）式，并经过调整后得到：
n0=n2+1。
满二叉树：
如果一个深度为 K的二叉树拥有 2K-1个结点，则将它称为 满二叉树 。
图 5-8
8 9 10 11 12 13 14 15
4 5 6 7
2 3
1
完全二叉树：有一棵深度为 h，具有 n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为 1~n的结点位置一一对应，则称这棵二叉树为 完全二叉树 。
【 性质 4】 具有 n个结点的完全二叉树的深度为
log2n?+1。其中,?log2n?的结果是不大于 log2n的最大整数。
证明：假设具有 n个结点的完全二叉树的深度为 K，
则根据性质 2可以得出：
2K-1-1<n≤2K-1
将不等式两端加 1得到：
2K-1≤n<2K
将不等式中的三项同取以 2为底的对数，并经过化简后得到：
K-1≤log2n<K
由此可以得到,?log2n?=K-1。整理后得到,K=
log2n?+1。
【 性质 5】 对于有 n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点 i （ 1≤i≤n），都有：
（ 1）如果 i=1，则结点 i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为?i/2?。
（ 2）如果 2i>n，则结点 i没有左孩子；否则其左孩子结点的编号为 2i。
（ 3）如果 2i+1>n，则结点 i没有右孩子；否则其右孩子结点的编号为 2i+1。
下面我们利用数学归纳法证明这个性质。
我们首先证明（ 2）和（ 3）。
当 i=1时，若 n≥ 3，则根的左、右孩子的编号分别是 2,3；若 n<3，则根没有右孩子；若 n<2，则根将没有左、右孩子；以上对于（ 2）和（ 3）均成立。
假设：对于所有的 1≤j≤i 结论成立。即：结点 j的左孩子编号为 2j；右孩子编号为 2j+1。
图 5-10
2i +2
2i 2i+1 2i+2 2i+3 i+1 2i 2i+1
i i i+1
由完全二叉树的结构可以看出：结点 i+1或者与结点 i同层且紧邻 i结点的右侧，或者 i位于某层的最右端，
i+1位于下一层的最左端。
可以看出,i+1的左、右孩子紧邻在结点 i的孩子后面，由于结点 i 的左、右孩子编号分别为 2i和 2i+1，所以，结点 i+1的左、右孩子编号分别为 2i+2和 2i+3，经提取公因式可以得到,2(i+1)和 2(i+1)+1，即结点 i+1的左孩子编号为 2(i+1)；右孩子编号为 2(i+1)+1。
又因为二叉树由 n个结点组成，所以，当
2(i+1)+1>n，且 2(i+1)=n时，结点 i+1只有左孩子，而没有右孩子；当 2(i+1)>n，结点 i+1既没有左孩子也没有右孩子。
以上证明得到（ 2）和（ 3）成立。
下面利用上面的结论证明（ 1）。
对于任意一个结点 i，若 2i≤n，则左孩子的编号为
2i，反过来结点 2i的双亲就是 i，而?2i/2?=i；若 2i+1≤n，
则右孩子的编号为 2i+1，反过来结点 2i+1的双亲就是 i，
而?(2i+1)/2? =i，由此可以得出（ 1）成立。
5.2.3 二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。
1,顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：
用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。
图 5-11
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
8
4 5 6 7
2 3
1
（ 1）构造一棵完全二叉树
void CreateBTree(QBTree *BT,EntryType item[ ],int n)
{
if (n>=MAX_TREE_NODE_SIZE)
n=MAX_TREE_NODE_SIZE-1;
for (i=1; i<=n;i++)
BT->item[i]=item[i];
BT->n=n;
}
（ 2）获取给定结点的左孩子
int LeftCHild(QBTree BT,int node)
{
if (2*node>BT.n) return 0;
else return 2*node;
}
RightChild(BT,node)与这个操作类似，读者可试着自行完成。
（ 3）获取给定结点的双亲
int Parent(QBTree BT,int node)
{
if (1<=node&&node<=BT.n) return i/2;
else return -1;
}
3,2 链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，
需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。
常见的二叉树结点结构如下所示：
L c h i l d i t e m R c h i l d
图 5-12
其中,Lchild和 Rchild是分别指向该结点左孩子和右孩子的指针,item是数据元素的内容。在 C语言中的类型定义为：
typedef struct BTNode{
EntryType item;
struct BTNode *Lchild,*Rchlid;
}BTNode,*BTree;
下面是一棵二叉树及相应的链式存储结构。
图 5-13
G H
D E F
B C
A
^ G ^ ^ H ^
^ D ^ E ^ F ^
B ^ C
A
BT
这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。
L c h i l d i t e m R c h i l
d
P a r e n t
图 5-14
有关二叉树在链式存储结构下的操作算法将在随后介绍。
5.2.4 遍历二叉树二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。
下面我们将分别进行讨论。
1,按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面 6种可能：
TLR（根左右）,TRL（根右左）
LTR（左根右）,RTL（右根左）
LRT（左右根）,RLT（右左根）
其中,TRL,RTL和 RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序 TLR、
LTR和 LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。
（ 1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；
先序遍历左子树；
先序遍历右子树。
（ 2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；
访问根结点；
中序遍历右子树。
（ 3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；
后序遍历右子树；
访问根结点。
下面是一棵二叉树及其经过三种遍历得到的相应序列。
G H
D E F
B C
A 先序序列,ABDGCEFH
中序序列,DGBAECHF
后序序列,GDBEHFCA
图 5-15
下面我们再给出两种遍历二叉树的方法：
（ 1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。
D G B A E C H F
G H
D E F
B C
A
图 5-16
（ 2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。
G H
D E F
B C
A
图 5-17
由此可以看出：（ 1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；
（ 2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。
（ 1）先序遍历递归算法
void PreOrder(BTree BT)
{
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild); }
}
（ 2）中序遍历递归算法
void InOrder(BTree BT)
{
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}
（ 3）后序遍历递归算法
void PostOrder(BTree BT)
{
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
}
2,按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
G H
D E F
B C
A
图 5-19
按层次遍历该二叉树的序列为：
ABCDEFGH
二叉树用顺序存储结构表示时，按层遍历的算法实现
A 1
B 3 4 C
D 5 6 E F 7 8 G
0 1 2 3 4 5 6 7
A B C D E F G
(a)
A 1
B 2 3 C
D 4 E 6 7 F (b)
0 1 2 3 4 5 6 7
A B C # D E F
图 5-20
void LevelOreder(QBTree BT)
{
for (i=1;i<=BT.n;i++)
if (BT.item[i]!=?#?)Visite(BT.item[i]);
}
二叉树用链式存储结构表示时,按层遍历的算法实现访问过程描述如下：
访问根结点,并将该结点记录下来；
若记录的所有结点都已处理完毕,则结束遍历操作；否则重复下列操作 。
取出记录中第一个还没有访问孩子的结点,若它有左孩子,则访问左孩子,并将记录下来；若它有右孩子,则访问右孩子,并记录下来 。
在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：
（ 1）访问根结点，并将根结点入队；
（ 2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
void LevelOrder(BTree *BT)
{
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p);
//访问根结点，并将根结点入队
while (!QueueEmpty(Q)) {
//当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p-
>Lchild); //处理左孩子
if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p-
>Rchild); //处理右孩子
}
}
5.2.5 典型二叉树的操作算法
1,输入一个二叉树的先序序列，构造这棵二叉树为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，‘ #?。在算法中，需要对每个输入的字符进行判断，如果对应的字符是‘ #?，
则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，
二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。
【 算法 5-12】
BTree Pre_Create_BT( )
{
getch(ch);
if (ch==?#?) return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTNode));
//构造新结点
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //构造左子树
BT->rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
}
2,计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，
如果是叶子结点将累加器加 1即可。下面这个算法是利用中序遍历实现的。
【 算法 5-13】
void Leaf(BTree BT,int *count)
{
if (BT) {
Leaf(BT->child,&count);
//计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL)
(*count)++;
Leaf(BT->rchild,&count);
//计算右子树的叶子结点个数
}
}
5,3 交换二叉树的左右子树许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。
void change_left_right(BTree BT)
{
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchild<->BT->rchild;
}
}
5,4 求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加 1。
int hight(BTree BT)
{//h1和 h2分别是以 BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
}
5.2.6 树、森林与二叉树的转换
1,树、森林转换成二叉树将一棵树转换成二叉树的方法：
将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。
特点：一棵树转换成二叉树后，根结点没有右孩子。
将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。
2,二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。
比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，
直到为空，途经的结点个数就是这个结点的孩子数目。
5.3 哈夫曼树及其应用
1．哈夫曼树的定义图 5-26
G H
D E F
B C
A
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的 路径 。
在路径上的分支数目被称为 路径长度 。用公式可表示为：
n
k
kk lwW P L
1
带权的路径长度最小的二叉树称为 哈夫曼二叉树或 最优二叉树 。
54
8
图 5-27 叶子结点带权值的二叉树下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有 6个权值分别为 {3,6,9,10,7，
11}，以这 6个权值作为叶子结点的权值可以构造出下面三棵二叉树。
3 6 7 9
10 11
(a)
图 5-28
11 10
9
7
6
3
11 10
3
6
7
9
(b) (c)
这三棵二叉树的带权路径长度分别为：
WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117
WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177
WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158
构造哈夫曼树的过程：
（ 1）将给定的 n个权值 {w1,w2,...,wn}作为 n个根结点的权值构造一个具有 n棵二叉树的森林 {T1,T2,...,Tn}，
其中每棵二叉树只有一个根结点；
（ 2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；
（ 3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；
（ 4）重复上面（ 2）和（ 3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。
假设有一组权值 {5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
第一步：以这 8个权值作为根结点的权值构造具有
8棵树的森林
5 29 7 8 14 23 3 11
第二步：从中选择两个根的权值最小的树 3,5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去
3 5
29 7 8 14 23 11 8
第三步：重复第二步过程，直到森林中只有一棵树为止选择 7,8
29 14 23 11
7 8
15
3 5
8
29 14 23
7 8
15
8
3 5
19
11
选择 8,11
选择 14,15
选择 19,23
3 5
29
15
7 8
29
14
8
42
23 19
11
选择 29,29
7 8
15
58
29 29
14
3 5
8
42
23 19
11
选择 42,58
100
7 8
15
58
29 29
14
3 5
8
42
23 19
11
这就是以上述 8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：
WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271
5.3.2 判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：
if (socre<60) printf(“bad”);
else if (socre<70) printf(“pass”);
else if (score<80) printf(“general”);
else if (score<90) printf(“good”);
esle printf(“very good”);
在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
下面我们就利用哈夫曼树寻找一棵最佳判定树，
即总的比较次数最少的判定树。
分数 0 ~ 5 9 6 0 ~ 6 9 7 0 ~ 7 9 8 0 ~ 8 9 9 0 ~ 1 0 0
比例 0,0 5 0,1 5 0,4 0 0,3 0 0,1 0
v e ry g o o d
b a d
p a s s
g e n e ra l
g o o d
< 8 0
< 9 0
< 7 0
< 6 0
图 5-29
very good
bad
pass
general
good
<80
<90
<70
<60
首先，将各分数段的比例数值作为权值构造一棵哈夫曼树。
very goodbad
pass
general
good 60≤...≤69
...<59
80≤...≤89
70≤...≤79
图 5-30
图 5-31
<70 <90
<80
general good very good
bad pass
<60
5.3.3 前缀编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（ 1）
发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（ 2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
1,等长编码这种编码方式的特点是每个字符的编码长度相同
（编码长度就是每个编码所含的二进制位数）。假设字符集只含有 4个字符 A,B,C,D，用二进制两位表示的编码分别为 00,01,10,11。若现在有一段电文为,ABACCDA，则应发送二进制序列：
00010010101100，总长度为 14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
2,不等长编码在传送电文时，为了使其二进制位数尽可能地少，
可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为 A,B，
C,D四个字符分别分配 0,00,1,01，并可将上述电文用二进制序列,000011010发送，其长度只有 9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面 4个 0是 4个 A，
1个 B,2个 A，还是 2个 B，即译码不唯一，因此这种编码方法不可使用。
（ 1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（ 2）从根结点开始，为到每个叶子结点路径上的左分支赋予 0，右分支赋予 1，并从根到叶子方向形成该叶子结点的编码。
假设有一个电文字符集中有 8个字符，每个字符的使用频率分别为 {0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，
现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（ 1）为方便计算，将所有字符的频度乘以 100，使其转换成整型数值集合，得到 {5,29,7,8,14,23,3,11}；
（ 2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图 5-27所示；
（ 3）由此哈夫曼树生成哈夫曼编码，如图 5-28所示。
最后得出每个字符的编码为：
字符 字符的使用频率 编码
① 0,05 01 1 1
② 0,29 10
③ 0,07 1 1 10
④ 0,08 1111
⑤ 0,14 1 10
⑥ 0,23 00
⑦ 0,03 01 10
⑧ 0,1 1 010
以上的①? ⑧分别代表 8 个字符。
比如,发送一段编码,0000011011010010，
接收方可以准确地通过译码得到,⑥⑥⑦⑤②⑧ 。
树的逻辑定义和存储结构
二叉树的逻辑定义、存储结构
二叉树的基本操作算法
树和二叉树的转换
哈夫曼树及其应用退出
5.1 树
5.2 二叉树
5.3 哈夫曼树及其应用
5.1 树
5.1.1 树的定义和基本运算
1,定义树是一种常用的非线性结构。我们可以这样定义：
树 是 n（ n≥0）个结点的有限集合。若 n=0，则称为 空树 ；否则，有且仅有一个特定的结点被称为 根,当 n>1
时，其余结点被分成 m（ m>0）个互不相交的子集 T1，
T2,...,Tm，每个子集又是一棵树。由此可以看出，
树的定义是递归。
图 5-1
K L M
E F G H I J
B C D
AA?
(a) (b) (c)
结点 数据元素的内容及其指向其子树根的分支统称为结点。
结点的度 结点的分支数。
终端结点（叶子） 度为 0的结点。
非终端结点 度不为 0的结点。
结点的层次 树中根结点的层次为 1，根结点子树的根为第 2层，以此类推。
树的度 树中所有结点度的最大值。
树的深度 树中所有结点层次的最大值。
有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。
森林 是 m（ m≥ 0）棵互不相交的树的集合。
在树结构中，结点之间的关系又可以用家族关系描述，定义如下：
孩子、双亲 结点子树的根称为这个结点的孩子，
而这个结点又被称为孩子的双亲。
子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙。
祖先 从根结点到该结点路径上的所有结点。
兄弟 同一个双亲的孩子之间互为兄弟。
堂兄弟 双亲在同一层的结点互为堂兄弟。
2,树的基本运算常用操作：
（ 1） 构造一个树 CreateTree (T)
（ 2） 清空以 T为根的树 ClearTree(T)
（ 3） 判断树是否为空 TreeEmpty(T)
（ 4） 获取给定结点的第 i个孩子 Child(T,node,i)
（ 5） 获取给定结点的双亲 Parent(T,node)
（ 6） 遍历树 Traverse(T)
对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，
一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依
5.1.2 树的存储结构
1,双亲表示法树的双亲表示法主要描述的是结点的双亲关系。
图 5-3
下标 i nf o p a re n
t
0 A -1
1 B 0
2 C 0
3 D 0
4 E 1
5 F 1
6 G 3
7 H 6
8 I 6
9 J 6
H I J
E F G
B C D
A
A
B DC
E F G
H I J
类型定义：
#define MAX_TREE_NODE_SIZE 100
typedef struct {
TEntryType info;
int parent;
} ParentNode;
typedef struct {
ParentNode item[MAX_TREE_NODE_SIZE];
int n; //树中当前的结点数目
}ParentTree;
这种存储方法的特点是寻找结点的双亲很容易，
但寻找结点的孩子比较困难。
算法实现举例：
int Parent(ParentTree T,int node)
{ if (node<0||node>=T.n) return -2;
else return T.item[node].parent;
}
2,孩子表示法孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：
图 5-4
root 0 A 2 1 4 ^
1 C ^
2 B 3 5 ^
3 E ^
4 D 6 ^
5 F ^
6 G 7 8 9 ^
7 H ^
8 I ^
9 J ^
在 C语言中，这种存储形式定义如下：
#define MAX_TREE_NODE_SIZE 10
typedef struct ChildNode{
int child; //该孩子结点在一维数组中的下标值
struct ChileNode *next; //指向下一个孩子结点
}CNode;
typedef struct{
TEntryType info; //结点信息
CNode *firstchild; //指向第一个孩子结点的指针
}TNode;
typedef struct {
TNode item[MAX_TREE_NODE_SIZE];
int n,root;
//n为树中当前结点的数目,root为根结点在一维数组中的位置
}ChildTree;
这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，
可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域 parent，用来指示结点的双亲在一维数组中的位置。
获取给定结点第 i个孩子的操作算法实现：
int Child(ChildTree T,int node,int i)
{
if (node<0||node>=T.n) return -2；
p=T.item[node].firstchild; j=1;
while (p&&j!=i) { p=p->next; j++;}
if (!p) return -2;
else return p->child;
}
3,孩子兄弟表示法孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：
f i r s t c h i l d i t e m n e x t s i b l i
ng
其中,firstchild为指向该结点第一个孩子的指针，
nextsibling为指向该结点的下一个兄弟,item是数据元素内容。举例：
图 5-5
^ H ^ I ^ J ^
^ E ^ F ^ G ^
B ^ C D ^
A ^
T
在 C语言中，这种存储形式定义如下：
typedef struct CSNode{
EntryType item;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
void AllChild(CSTree T,CSTree p)
//输出树中 p指针所指结点的所有孩子信息
{
q=p->fisrtchild;
while (q) {
printf(“%c”,q ->item); q=q->nextsibling;
}
}
5.2 二叉树
5.2.1 二叉树的定义和基本运算
1,定义定义,二叉树 是另一种树形结构。它与树形结构的区别是：
（ 1）每个结点最多有两棵子树；
（ 2）子树有左右之分。
二叉树也可以用递归的形式定义。即：二叉树是
n（ n≥ 0）个结点的有限集合。当 n=0时，称为空二叉树；当 n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，
另一个作为右子集，每个子集又是一个二叉树。
图 5-6
G H
D E F
B C
A
二叉树的 5种形态：
图 5-7
(a) (b) (c) (d) (e)
2,二叉树的基本运算
（ 1） 构造一棵二叉树 CreateBTree ( BT)
（ 2）清空以 BT为根的二叉树 ClearBTree(BT)
（ 3）判断二叉树是否为空 BTreeEmpty(BT)
（ 4）获取给定结点的左孩子和右孩子
LeftChild(BT,node),RightChild(BT,node)
（ 5）获取给定结点的双亲 Parent(BT,node)
（ 6）遍历二叉树 Traverse(BT)
2．二叉树的性质二叉树具有下列 5个重要的性质。
【 性质 1】 在二叉树的第 i层上最多有 2i-1个结点
（ i≥ 1）。
叉树的第 1层只有一个根结点，所以,i=1时,2i-
1=21-1=20=1成立。
假设对所有的 j,1≤j<i成立，即第 j层上最多有 2j-1
个结点成立。若 j=i-1，则第 j层上最多有 2j-1=2i-2个结点。
由于在二叉树中，每个结点的度最大为 2，所以可以推导出第 i层最多的结点个数就是第 i-1层最多结点个数的
2倍，即 2i-2*2=2i-1。
【 性质 2】 深度为 K的二叉树最多有 2K-1个结点
（ K≥ 1）。
由性质 1可以得出,1至 K层各层最多的结点个数分别为,20,21,22,23,...,2K-1。这是一个以 2为比值的等比数列，前 n项之和的计算公式为：
q
qaa
S
n
n
1
*1
其中 a1为第一项,an为第 n项,q为比值。可以得到，该数列前 K项之和为：
12
21
2*
1
2
0
2
K
K
【 性质 3】 对于任意一棵二叉树 BT，如果度为 0的结点个数为 n0，度为 2的结点个数为 n2，则 n0=n2+1。
证明：假设度为 1的结点个数为 n1，结点总数为 n，
B为二叉树中的分支数。
因为在二叉树中，所有结点的度均小于或等于 2，
所以结点总数为：
n=n0+n1+n2 （ 1）
再查看一下分支数。在二叉树中，除根结点之外，
每个结点都有一个从上向下的分支指向，所以，总的结点个数 n与分支数 B之间的关系为,n=B+1。
又因为在二叉树中，度为 1的结点产生 1个分支，
度为 2的结点产生 2个分支，所以分支数 B可以表示为：
B=n1+2n2。
将此式代入上式，得：
n=n1+2n2+1 （ 2）
用（ 1）式减去（ 2）式，并经过调整后得到：
n0=n2+1。
满二叉树：
如果一个深度为 K的二叉树拥有 2K-1个结点，则将它称为 满二叉树 。
图 5-8
8 9 10 11 12 13 14 15
4 5 6 7
2 3
1
完全二叉树：有一棵深度为 h，具有 n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为 1~n的结点位置一一对应，则称这棵二叉树为 完全二叉树 。
【 性质 4】 具有 n个结点的完全二叉树的深度为
log2n?+1。其中,?log2n?的结果是不大于 log2n的最大整数。
证明：假设具有 n个结点的完全二叉树的深度为 K，
则根据性质 2可以得出：
2K-1-1<n≤2K-1
将不等式两端加 1得到：
2K-1≤n<2K
将不等式中的三项同取以 2为底的对数，并经过化简后得到：
K-1≤log2n<K
由此可以得到,?log2n?=K-1。整理后得到,K=
log2n?+1。
【 性质 5】 对于有 n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点 i （ 1≤i≤n），都有：
（ 1）如果 i=1，则结点 i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为?i/2?。
（ 2）如果 2i>n，则结点 i没有左孩子；否则其左孩子结点的编号为 2i。
（ 3）如果 2i+1>n，则结点 i没有右孩子；否则其右孩子结点的编号为 2i+1。
下面我们利用数学归纳法证明这个性质。
我们首先证明（ 2）和（ 3）。
当 i=1时，若 n≥ 3，则根的左、右孩子的编号分别是 2,3；若 n<3，则根没有右孩子；若 n<2，则根将没有左、右孩子；以上对于（ 2）和（ 3）均成立。
假设：对于所有的 1≤j≤i 结论成立。即：结点 j的左孩子编号为 2j；右孩子编号为 2j+1。
图 5-10
2i +2
2i 2i+1 2i+2 2i+3 i+1 2i 2i+1
i i i+1
由完全二叉树的结构可以看出：结点 i+1或者与结点 i同层且紧邻 i结点的右侧，或者 i位于某层的最右端，
i+1位于下一层的最左端。
可以看出,i+1的左、右孩子紧邻在结点 i的孩子后面，由于结点 i 的左、右孩子编号分别为 2i和 2i+1，所以，结点 i+1的左、右孩子编号分别为 2i+2和 2i+3，经提取公因式可以得到,2(i+1)和 2(i+1)+1，即结点 i+1的左孩子编号为 2(i+1)；右孩子编号为 2(i+1)+1。
又因为二叉树由 n个结点组成，所以，当
2(i+1)+1>n，且 2(i+1)=n时，结点 i+1只有左孩子，而没有右孩子；当 2(i+1)>n，结点 i+1既没有左孩子也没有右孩子。
以上证明得到（ 2）和（ 3）成立。
下面利用上面的结论证明（ 1）。
对于任意一个结点 i，若 2i≤n，则左孩子的编号为
2i，反过来结点 2i的双亲就是 i，而?2i/2?=i；若 2i+1≤n，
则右孩子的编号为 2i+1，反过来结点 2i+1的双亲就是 i，
而?(2i+1)/2? =i，由此可以得出（ 1）成立。
5.2.3 二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。
1,顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：
用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。
图 5-11
0 1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
8
4 5 6 7
2 3
1
（ 1）构造一棵完全二叉树
void CreateBTree(QBTree *BT,EntryType item[ ],int n)
{
if (n>=MAX_TREE_NODE_SIZE)
n=MAX_TREE_NODE_SIZE-1;
for (i=1; i<=n;i++)
BT->item[i]=item[i];
BT->n=n;
}
（ 2）获取给定结点的左孩子
int LeftCHild(QBTree BT,int node)
{
if (2*node>BT.n) return 0;
else return 2*node;
}
RightChild(BT,node)与这个操作类似，读者可试着自行完成。
（ 3）获取给定结点的双亲
int Parent(QBTree BT,int node)
{
if (1<=node&&node<=BT.n) return i/2;
else return -1;
}
3,2 链式存储结构在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，
需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。
常见的二叉树结点结构如下所示：
L c h i l d i t e m R c h i l d
图 5-12
其中,Lchild和 Rchild是分别指向该结点左孩子和右孩子的指针,item是数据元素的内容。在 C语言中的类型定义为：
typedef struct BTNode{
EntryType item;
struct BTNode *Lchild,*Rchlid;
}BTNode,*BTree;
下面是一棵二叉树及相应的链式存储结构。
图 5-13
G H
D E F
B C
A
^ G ^ ^ H ^
^ D ^ E ^ F ^
B ^ C
A
BT
这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。
L c h i l d i t e m R c h i l
d
P a r e n t
图 5-14
有关二叉树在链式存储结构下的操作算法将在随后介绍。
5.2.4 遍历二叉树二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。
下面我们将分别进行讨论。
1,按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面 6种可能：
TLR（根左右）,TRL（根右左）
LTR（左根右）,RTL（右根左）
LRT（左右根）,RLT（右左根）
其中,TRL,RTL和 RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序 TLR、
LTR和 LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。
（ 1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；
先序遍历左子树；
先序遍历右子树。
（ 2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；
访问根结点；
中序遍历右子树。
（ 3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；
后序遍历右子树；
访问根结点。
下面是一棵二叉树及其经过三种遍历得到的相应序列。
G H
D E F
B C
A 先序序列,ABDGCEFH
中序序列,DGBAECHF
后序序列,GDBEHFCA
图 5-15
下面我们再给出两种遍历二叉树的方法：
（ 1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。
D G B A E C H F
G H
D E F
B C
A
图 5-16
（ 2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。
G H
D E F
B C
A
图 5-17
由此可以看出：（ 1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；
（ 2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。
（ 1）先序遍历递归算法
void PreOrder(BTree BT)
{
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild); }
}
（ 2）中序遍历递归算法
void InOrder(BTree BT)
{
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}
（ 3）后序遍历递归算法
void PostOrder(BTree BT)
{
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
}
2,按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
G H
D E F
B C
A
图 5-19
按层次遍历该二叉树的序列为：
ABCDEFGH
二叉树用顺序存储结构表示时，按层遍历的算法实现
A 1
B 3 4 C
D 5 6 E F 7 8 G
0 1 2 3 4 5 6 7
A B C D E F G
(a)
A 1
B 2 3 C
D 4 E 6 7 F (b)
0 1 2 3 4 5 6 7
A B C # D E F
图 5-20
void LevelOreder(QBTree BT)
{
for (i=1;i<=BT.n;i++)
if (BT.item[i]!=?#?)Visite(BT.item[i]);
}
二叉树用链式存储结构表示时,按层遍历的算法实现访问过程描述如下：
访问根结点,并将该结点记录下来；
若记录的所有结点都已处理完毕,则结束遍历操作；否则重复下列操作 。
取出记录中第一个还没有访问孩子的结点,若它有左孩子,则访问左孩子,并将记录下来；若它有右孩子,则访问右孩子,并记录下来 。
在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：
（ 1）访问根结点，并将根结点入队；
（ 2）当队列不空时，重复下列操作：
从队列退出一个结点；
若其有左孩子，则访问左孩子，并将其左孩子入队；
若其有右孩子，则访问右孩子，并将其右孩子入队；
void LevelOrder(BTree *BT)
{
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p);
//访问根结点，并将根结点入队
while (!QueueEmpty(Q)) {
//当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p-
>Lchild); //处理左孩子
if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p-
>Rchild); //处理右孩子
}
}
5.2.5 典型二叉树的操作算法
1,输入一个二叉树的先序序列，构造这棵二叉树为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，‘ #?。在算法中，需要对每个输入的字符进行判断，如果对应的字符是‘ #?，
则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，
二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。
【 算法 5-12】
BTree Pre_Create_BT( )
{
getch(ch);
if (ch==?#?) return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTNode));
//构造新结点
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //构造左子树
BT->rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
}
2,计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，
如果是叶子结点将累加器加 1即可。下面这个算法是利用中序遍历实现的。
【 算法 5-13】
void Leaf(BTree BT,int *count)
{
if (BT) {
Leaf(BT->child,&count);
//计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL)
(*count)++;
Leaf(BT->rchild,&count);
//计算右子树的叶子结点个数
}
}
5,3 交换二叉树的左右子树许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。
void change_left_right(BTree BT)
{
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchild<->BT->rchild;
}
}
5,4 求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加 1。
int hight(BTree BT)
{//h1和 h2分别是以 BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
}
5.2.6 树、森林与二叉树的转换
1,树、森林转换成二叉树将一棵树转换成二叉树的方法：
将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。
特点：一棵树转换成二叉树后，根结点没有右孩子。
将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。
2,二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。
比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，
直到为空，途经的结点个数就是这个结点的孩子数目。
5.3 哈夫曼树及其应用
1．哈夫曼树的定义图 5-26
G H
D E F
B C
A
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的 路径 。
在路径上的分支数目被称为 路径长度 。用公式可表示为：
n
k
kk lwW P L
1
带权的路径长度最小的二叉树称为 哈夫曼二叉树或 最优二叉树 。
54
8
图 5-27 叶子结点带权值的二叉树下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有 6个权值分别为 {3,6,9,10,7，
11}，以这 6个权值作为叶子结点的权值可以构造出下面三棵二叉树。
3 6 7 9
10 11
(a)
图 5-28
11 10
9
7
6
3
11 10
3
6
7
9
(b) (c)
这三棵二叉树的带权路径长度分别为：
WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117
WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177
WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158
构造哈夫曼树的过程：
（ 1）将给定的 n个权值 {w1,w2,...,wn}作为 n个根结点的权值构造一个具有 n棵二叉树的森林 {T1,T2,...,Tn}，
其中每棵二叉树只有一个根结点；
（ 2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；
（ 3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；
（ 4）重复上面（ 2）和（ 3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。
假设有一组权值 {5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
第一步：以这 8个权值作为根结点的权值构造具有
8棵树的森林
5 29 7 8 14 23 3 11
第二步：从中选择两个根的权值最小的树 3,5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去
3 5
29 7 8 14 23 11 8
第三步：重复第二步过程，直到森林中只有一棵树为止选择 7,8
29 14 23 11
7 8
15
3 5
8
29 14 23
7 8
15
8
3 5
19
11
选择 8,11
选择 14,15
选择 19,23
3 5
29
15
7 8
29
14
8
42
23 19
11
选择 29,29
7 8
15
58
29 29
14
3 5
8
42
23 19
11
选择 42,58
100
7 8
15
58
29 29
14
3 5
8
42
23 19
11
这就是以上述 8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：
WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271
5.3.2 判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：
if (socre<60) printf(“bad”);
else if (socre<70) printf(“pass”);
else if (score<80) printf(“general”);
else if (score<90) printf(“good”);
esle printf(“very good”);
在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
下面我们就利用哈夫曼树寻找一棵最佳判定树，
即总的比较次数最少的判定树。
分数 0 ~ 5 9 6 0 ~ 6 9 7 0 ~ 7 9 8 0 ~ 8 9 9 0 ~ 1 0 0
比例 0,0 5 0,1 5 0,4 0 0,3 0 0,1 0
v e ry g o o d
b a d
p a s s
g e n e ra l
g o o d
< 8 0
< 9 0
< 7 0
< 6 0
图 5-29
very good
bad
pass
general
good
<80
<90
<70
<60
首先，将各分数段的比例数值作为权值构造一棵哈夫曼树。
very goodbad
pass
general
good 60≤...≤69
...<59
80≤...≤89
70≤...≤79
图 5-30
图 5-31
<70 <90
<80
general good very good
bad pass
<60
5.3.3 前缀编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（ 1）
发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（ 2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
1,等长编码这种编码方式的特点是每个字符的编码长度相同
（编码长度就是每个编码所含的二进制位数）。假设字符集只含有 4个字符 A,B,C,D，用二进制两位表示的编码分别为 00,01,10,11。若现在有一段电文为,ABACCDA，则应发送二进制序列：
00010010101100，总长度为 14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。
2,不等长编码在传送电文时，为了使其二进制位数尽可能地少，
可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为 A,B，
C,D四个字符分别分配 0,00,1,01，并可将上述电文用二进制序列,000011010发送，其长度只有 9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面 4个 0是 4个 A，
1个 B,2个 A，还是 2个 B，即译码不唯一，因此这种编码方法不可使用。
（ 1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（ 2）从根结点开始，为到每个叶子结点路径上的左分支赋予 0，右分支赋予 1，并从根到叶子方向形成该叶子结点的编码。
假设有一个电文字符集中有 8个字符，每个字符的使用频率分别为 {0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，
现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（ 1）为方便计算，将所有字符的频度乘以 100，使其转换成整型数值集合，得到 {5,29,7,8,14,23,3,11}；
（ 2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图 5-27所示；
（ 3）由此哈夫曼树生成哈夫曼编码，如图 5-28所示。
最后得出每个字符的编码为：
字符 字符的使用频率 编码
① 0,05 01 1 1
② 0,29 10
③ 0,07 1 1 10
④ 0,08 1111
⑤ 0,14 1 10
⑥ 0,23 00
⑦ 0,03 01 10
⑧ 0,1 1 010
以上的①? ⑧分别代表 8 个字符。
比如,发送一段编码,0000011011010010，
接收方可以准确地通过译码得到,⑥⑥⑦⑤②⑧ 。
