数据结构（C语言版）严蔚敏 吴伟民 编著 第6章 树和二叉树
数据结构（C语言版）严蔚敏 吴伟民 编著 第6章 树和二叉树
前言
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。树在计算机领域中也得到广泛应用，如在编译程序中，可用树来表示源程序的语法结构。又如在数据库系统中，树形结构也是信息的重要组织形式之一。本章重点讨论二叉树的存储结构及其各种操作，并研究数和森林与二叉树的转换关系。
6.1 树的定义和基本术语
树是n（n≥0）个结点的有限集。在任意一棵非空树中：
（1）有且仅有一个特定的称为根的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。
下面列出树结构中的一些基本术语：
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度。度为0的结点称为叶子或终端结点。度不为0的结点称为非终端结点或分支结点。除根节点之外，分支节点也称为内部结点。树的度是树内各结点的度的最大值。结点的子树的根称为该结点孩子，相应地，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。结点的层次是从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。
如果将树中结点的各子树看成是从左至右是有次序的，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
森林是m（m≥0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，也可以通过森林和树相互递归的定义来描述树。就逻辑而言，任何一棵树是一个二元组Tree(root,F),其中：root是数据元素，称做树的根节点；F是m(m≥0)棵树的森林，F=（T1，T2，…，Tm），其中Ti= (ri,Fi)称做根root的第i棵子树；当m≠0时，在树根和其子树森林之间存在下列关系：
RF={<root,ri>|i=1,2,…,m,m>0}
这个定义将有助于得到森林和树与二叉树之间转换的递归定义。
6.2 二叉树
6.2.1 二叉树的定义
二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树，即二叉树中不存在度大于2的结点，并且，二叉树的子树有左右之分，其次序不能任意颠倒。上述数据结构的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义，它们也可以是空树。由此，二叉树可以有5种基本形态。
6.2.2 二叉树的性质
-
性质1 在二叉树的第i层上至多有2i-1个结点（i≥1）。
-
性质2 深度为k的二叉树至多有2k-1个结点（k≥1）。
-
性质3 对任何一棵二叉树T，如果其终端结点树为n0，度为2的结点树为n2，则n0=n2+1。
完全二叉树和满二叉树是两种特殊形态的二叉树，一棵深度为k且有2k-1个结点的二叉树称为满二叉树。可以对满二叉树的结点进行连续编号，约定编号从根节点起，自上而下，自左向右，由此可引出完全二叉树的定义。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。
完全二叉树将在很多场合下出现，下面介绍完全二叉树的两个重要特性： -
性质4 具有n个结点的完全二叉树的深度为⌊ log2n⌋ + 1。
-
性质5 如果对一棵有n个结点的完全二叉树（其深度为⌊ log2n⌋ + 1）的结点按层序编号（从第1层到第⌊ log2n⌋ + 1层，每层从左到右），则对任一结点i（1≤i≤n），有：
（1）如果i = 1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点⌊ i/2⌋。
（2）如果2i>n，则结点i无左孩子，结点i为叶子结点；否则其左孩子LCHILD(i)是结点2i。
（3）如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。
6.2.3 二叉树的存储结构
1.顺序存储结构
// 二叉树的顺序存储表示
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef TElemType SqBiTree[MAX_TREE_SIZE] // 0号单元存储根节点
SqBiTree bt;
按照顺序存储结构的定义，在此约定，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。由此可见，这种顺序存储结构仅适用于完全二叉树因为最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要2k-1的一维数组。
2.链式存储结构
设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左、右指针域。有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表。链表的头指针指向二叉树的根节点。在含n个结点的二叉链表中有n+1个空链域。在6.3节中我们将看到可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构——线索链域。以下是二叉链表的定义：
// 二叉树的二叉链表存储表示
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode, *BiTree;
6.3 遍历二叉树和线索二叉树
6.3.1 遍历二叉树
回顾二叉树的递归定义可知，二叉树是由3个基本单元组成：根节点、左子树和右子树。因此，若能依次遍历这三部分，便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树，访问根节点和遍历右子树，则可有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右则只有前3种情况，分别称之为先（根）序遍历、中（根）序遍历和后（根）序遍历。基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。
先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
先序遍历二叉树的基本操作的递归算法在二叉链表上的实现：
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElmType e)){
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit
// 最简单的Visit函数是：
// Status PrintElement(TElemType e){ // 输出元素e的值
// print(e); // 实用时，加上格式串
// return OK;
// }
// 调用实例：PreOrderTraverse(T,PrintElement);
if(T) {
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit)) return OK;
return ERROR;
}else return OK;
}// PreOrderTraverse
仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。如从中序遍历递归算法执行过程中递归工作栈的状态可见：
（1）工作记录中包含两项：其一是递归调用的语句编号，其二是指向根节点的指针，则当栈顶记录中指针非空时，应遍历左子树，即指向左子树根的指针进栈。
（2）若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根节点。
（3）若是从右子树返回，则表明当前层的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中指针即可。由此可得两个中序遍历二叉树的非递归算法：
Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){
// 采用二叉树表存储结构，Visit是对数据元素操作的应用函数，中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
InitStack(S); Push(S,T); // 根指针进栈
while(!StackEmpty(S)){
while(GetTop(S,p) && p) Push(S,p->lchild); // 向左走到尽头
Pop(S,p); // 空指针退栈
if(!StackEmpty(S)){ // 访问结点，向右一步
Pop(S,p); if(!Visit(p->data)) return ERROR;
Push(S,p->rchild);
}// if
}// while
return OK;
}// InOrderTraverse
Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){
// 采用二叉树表存储结构，Visit是对数据元素操作的应用函数，中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
InitStack(S); p=T;
while(p || !StackEmpty(S)){
if(p) {Push(S,p); p = p->lchild;} // 根指针进栈，遍历左子树
else{ // 根指针退栈，访问根节点，遍历右子树
Pop(S,p); if(!Visit(p->data)) return ERROR;
p = p->rchild;
}// else
}while
return OK;
}// InOrderTraverse
遍历是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在层次等，反之，也可在遍历过程中生成结点，建立二叉树的存储结构。下列算法是一个按照先序序列建立二叉树的二叉链表的过程：
Status CreateBiTree(BiTree &T){
// 按先序次序输入二叉树中结点的值，一个字符，空格字符表示空树，构造二叉链表表示的二叉树T
scanf(&ch);
if(ch == ' ') T = NULL;
else{
if(!(T = (BiTNode * )malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch; // 生成根节点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
return OK;
}// CreateBiTree
对二叉树进行遍历的搜索路径除了上述按先序、中序或后序外，还可从上到下，从左到右按层次进行。
显然，遍历二叉树的算法中的基本操作是访问结点，则不论按哪一种次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下为n，则空间复杂度也为O(n)。遍历时也可采用二叉树的其他存储结构，如带标志域的三叉链表，此时因存储结构中已存有遍历所需足够信息，则遍历过程中不需另设栈，也可和8.5节将讨论的遍历广义表的算法相类似，采用带标志域的二叉链表作存储结构，并在遍历过程中利用指针域暂存遍历路径，也可省略栈的空间，但这样做将使时间上有很大损失。
6.3.2 线索二叉树
遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的先序序列或中序序列或后序序列。这实质上是对一个非线性结构进行线性化操作。使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是，当以二叉链表作为存储结构时，只能找到结点的左右孩子信息，而不能直接得到结点在任意序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。如何保存这种在遍历过程中得到的信息呢？一个最简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指示结点在依任一次序遍历时得到的前驱和后继信息。显然这样做将使得结构的存储密度大大降低。另一方面，在有n个结点的二叉链表中必定存在n+1个空链域。由此设想能否利用这些空链域来存放结点的前驱和后继的信息。
试做如下规定：若结点有左子树，则其lchild指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域：
lchild LTag data RTag rchild
LTag = 0 lchild域指示结点的左孩子
1 lchild域指示结点的前驱
RTag = 0 rchild域指示结点的右孩子
1 rchild域指示结点的后继
以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找节点后继直至后继为空时而止。
如何在线索树中找结点的后继？以中序线索树来看，树中所有叶子结点的右链是线索，则右链域直接指示了结点的后继。树中所有非终端结点的右链均为指针，则无法由此得到后继的信息。然而，根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。反之，在中序线索树中找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。
在后序线索树中找结点后继较复杂些，可分3种情况：
（1）若结点x是二叉树的根，则其后继为空
（2）若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点
（3）若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。
可见，在后序线索化树上找后继时需知道结点双亲，即需带标志域的三叉链表作存储结构。可见在中序线索二叉树上遍历二叉树，虽时间复杂度亦为O(n)，但常数因子要比上节讨论的算法下，且不需要设栈。因此，若在某程序中所用二叉树需经常遍历或查找结点在遍历所得线性序列中的前驱和后继，则应采用线索链表作存储结构。
// 二叉树的二叉线索存储表示
typedef enum PointerTag{Link, Thread}; // Link == 0：指针，Thread == 1：线索
typedef struct BiThrNode{
TElemType data;
struct BiThrNode *lchild,*rchild; // 左右孩子指针
PointTag LTag,RTag; // 左右标志
}BiThrNode, *BithrTree;
为方便起见，仿照线性表的存储结构，在二叉树的线索链上也添加一个头结点，并令其lchild域的指针指向二叉树的根节点，其rchild域的指针指向中序遍历时访问的最后一个结点；反之令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchil域的指针均指向头结点。这好比为二叉树建立了一个双向线索链表，既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点顺前驱进行遍历。下述算法是以双向线索链表为存储结构时对二叉树进行遍历的算法：
Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)){
// T指向头结点，头结点的左链lchild指向根节点，可参加线索化算法
// 中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit
p = T->lchild; // p指向根节点
while(p!=T){ // 空树或遍历结束时，p == T
while(p->LTag == Link) p = p ->lchild;
if(!Visit(p->data)) return ERROR; // 访问其左子树为空的结点
while(p->RTag == Thread && p->rchild!= T){
p = p->rchild; Visit(p->data); // 访问后继结点
}
p = p->rchild;
}
return OK;
}// InOrderTraverse_Thr
那么如何进行二叉树的线索化呢？由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱，由此可得中序遍历算法建立中序线索化链表的算法如下：
// Status InOrderThreading(BiThrTree &Thrt, BiThrTree T){
// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag = Link; Thrt->RTag = Thread; // 建头结点
Thrt->rchild = Thrt; // 右指针回指
if(!T) Thrt-> lchild = Thrt; // 若二叉树为空，则左指针回指
else{
Thrt ->lchild = T; pre = Thrt;
InThreading(T); // 中序遍历进行中序线索化
pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化
Thrt->rchild = pre;
}
return OK;
}// InOrderThreading
void InThreading(BiThrTree p){
if(p) {
InThreading(p->lchild); // 左子树线索化
if(!p->lchild) {p->LTag = Thread; p->lhild = pre;} // 前驱线索
if(!pre->rchild) {pre->RTag = Thread; pre->rchild = p;} // 后继线索
pre = p; // 保持pre指向p的前驱
InThreading(P->rchild); // 右子树线索化
}
}// InThreading
6.4 树和森林
6.4.1 树的存储结构
- 双亲表示法
假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置，其形式说明如下：
// 树的双亲表存储表示
#define MAX_TREE_SIZE 100
typedef struct PTNode{ // 结点结构
TElemType data;
int parent; // 双亲位置域
}PTNode;
typedef struct{ // 树形结构
PTNode nodes[MAX_TREE_SIZE];
int r, n; // 根的位置和结点数
}PTree;
这种存储结构利用了每个结点（除根以外）只有唯一的双亲的性质。PARENT(T,x)操作可以在常量时间内实现。反复调用PARENT操作，知道遇见无双亲的结点时，便找到了树的根，这就是ROOT(x)操作的执行过程。但是在这种表示法中，求结点的孩子时需要遍历整个结构。
2. 孩子表示法
由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个结点指向一棵子树的根节点，此时链表中的结点可以有如下两种结点格式：
data child1 child2 … childd
data degree child1 child2 … childd-
若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费，不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1个空链域。若采用第二种结点格式，则多重链表中的结点时不同构的，其中d-为结点的度，degree域的值同d-。此时，虽能节约存储空间，但操作不方便。
另一种方法是把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构，这种存储结构可形式地说明如下：
// 树的孩子链表存储表示
typedef struct CTNode { // 孩子结点
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct{
TElemtype data;
ChildPtr firstchild; // 孩子链表头指针
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n,r; // 结点数和根的位置
}CTree;
与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现，却不适用于PARENT(T,x)操作。
3. 孩子兄弟表示法
又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。
// 树的二叉链表（孩子-兄弟）存储表示
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
利用这种存储结构便于实现各种树的操作。
6.4.2 森林与二叉树的转换
由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不用而已。
从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中的第二棵树的根节点看成是第一棵树的根节点的兄弟，则同样可导出森林和二叉树的对应关系。
6.4.3 树和森林的遍历
由树结构的定义可引出两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根节点，然后依次先根遍历根的每个子树；另一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根节点。
由上节森林和二叉树之间转换的规则可知，当森林转化为二叉树时，其第一棵树的子树森林转化为左子树，剩余树的森林转换成右子树，则上述森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。由此可见，当以二叉链表作树的存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现之。
6.6 赫夫曼树及其应用
赫夫曼树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。
6.6.1 最优二叉树（赫夫曼树）
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一个结点的路径之和。完全二叉树就是这种路径长度最短的二叉树。假设有n的权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。
如何构造赫夫曼树，赫夫曼给出了赫夫曼算法：
（1）根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均空。
（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左、右子树上根节点的权值之和。
（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
（4）重复（2）和（3），直到F只含一棵树为止。这棵树便是赫夫曼树。
6.6.2 赫夫曼编码
设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。由于赫夫曼树中没有度为1的结点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需知孩子结点的信息，为此设定下述存储结构：
// 赫夫曼树和赫夫曼编码的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanCode; // 动态分配数组存储赫夫曼树
typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
// 求赫夫曼编码的算法：
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){
// w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
if(n<=1) return;
m = 2*n - 1;
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p = HT +1,i= 1; i<= n; ++i,++p,++w) *p = {*w,0,0,0};
for(; i<=m;++i,++p) *p ={0,0,0,0};
for(i = n+1; i<=m;++i){ // 建赫夫曼树
// 在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(HT,i-1,s1,s2);
HT[s1].parent = i; HT[s2].parent = i
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
// 从叶子到根逆向求每个字符的赫夫曼编码
HC= (HuffmanCode)malloc(n+1) * sizeof(char *); // 分配n个字符编码的头指针向量
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = "\0"; // 编码结束符
for(i = 1; i <=n; ++i){ // 逐个字符求赫夫曼编码
start = n-1;
for(c = i,f = HT[i].parent; f!=0; c=f,f=HT[f].parent ) // 从叶子到根逆向求编码
if(HT[f].lchild == c) cd[--start] = "0";
else cd[--start] = "1";
HC[i] = (char *)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); // 从cd复制编码（串）到HC
}
free(cd); // 释放工作空间
}// HuffmanCoding
向量HT的前n个分量表示叶子结点，最后一个分量表示根节点。各字符的编码长度不等，所以按实际长度动态分配空间。在上述算法中，求每个字符的赫夫曼编码是从叶子到根逆向处理的。也可以从根出发，遍历整棵赫夫曼树，求得各个叶子结点所表示的字符的赫夫曼编码，算法如下所示：
// 无栈非递归遍历赫夫曼树，求赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
p = m; cdlen = 0;
for(i=1; i<=m; ++i) HT[i].weight = 0; // 遍历赫夫曼树时用作结点状态标志
while(p){
if(HT[p].weight == 0){ // 向左
HT[p].weight = 1;
if(HT[p].lchild!=0) {p=HT[p].lchild; cd[cdlen++] = "0" ;}
else if(HT[p].rchild == 0){ // 登记叶子结点的字符的编码
HC[p]= (char *)malloc((cdlen +1)*sizeof(char));
cd[cdlen]= "\0"; strcpy(HC[p],cd); //复制编码（串）
}
}
else if(HT[p].weight == 1){ // 向右
HT[p].weight = 2;
if(HT[p].rchild!=0) {p = HT[p].rchild; cd[cdlen++]="1";}
}
else{ // HT[p].weight == 2,退回
HT[p].weight = 0; p =HT[p].parent; --cdlen; // 退到父结点，编码长度减1
}// else
}// while