树和二叉树课件

第7章树和二叉树7.1树7.2二叉树7.3二叉树的设计和实现7.4线索二叉树7.5哈夫曼树7.6树的存储结构、转换和遍历7.7本章小结数据结构可分为线性结构、

树结构和图结构三大类。

前几章讨论的线性表、

堆栈、

队列、

串和数组都是线性结构。

树结构中每个结点只允许有一个直接前驱结点，

但允许有一个以上直接后继结点。树结构有树和二叉树两种。

二叉树是最多只允许有两个直接后继结点的有序树。

树的操作实现比较复杂，

但树可以转换为二叉树进行处理。

本章主要讨论树和二叉树的基本概念，

二叉树的操作实现以及树和二叉树的转换等，

并以哈夫曼树为例介绍了二叉树的用途。

7.1.1树的定义

树是由n(n≥0)个结点构成的集合。

n＝0的树称为空树；

对n>0的树T有：

(1)有一个特殊的结点称为根结点，

根结点没有前驱结点；7.1树

(2)当n>1时，

除根结点外其他结点被分成m(m>0)个互不相交的集合T1，

T2，…，Tm，其中每一个集合Ti(1≤i≤m)本身又是一棵结构和树类同的子树。

显然树是递归定义的。因此，在树结构(以及二叉树结构)的算法中将会频繁地出现递归。

树结构表示了数据元素之间的层次关系。图7-1是一个树的例子，其中图7-1(a)是一棵只有根结点的树，图7-1(b)是一棵有12个结点的一般的树。

图7-1树的示例

(a)只有根结点的树；(b)一般的树下面介绍树的其他一些常用术语。

结点：由数据元素和构造数据元素之间关系的指针组成。例如，在图7-1(a)中有1个结点，图7-1(b)中有12个结点。

结点的度：结点所拥有的子树的个数称为该结点的度。例如，在图7-1(b)中结点A的度为3，结点B的度为2，结点J的度为0。

叶结点：度为0的结点称为叶结点，叶结点也称作终端结点。例如，在图7-1(b)中结点J，F，K，L，H，I均为叶结点。分支结点：度不为0的结点称为分支结点，分支结点也称作非终端结点。显然，一棵树中除叶结点外的所有结点都是分支结点。

孩子结点：树中一个结点的子树的根结点称作这个结点的孩子结点。例如，在图7-1(b)中结点B，C，D是结点A的孩子结点。孩子结点也称作后继结点。

双亲结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点。例如，在图7-1(b)中结点A是结点B，C，D的双亲结点。双亲结点也称作直接前驱结点。兄弟结点：具有相同的双亲结点的结点称为兄弟结点。例如，在图7-1(b)中结点B，C，D具有相同的双亲结点A，所以称结点B，C，D为兄弟结点。

树的度：树中所有结点的度的最大值称为该树的度。例如，在图7-1(b)树中结点A的度等于3是该树中所有结点的度的最大值，所以该树的度为3。

结点的层次：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为0，这样其他结点的层次就是它的双亲结点的层次加1。树的深度：树中所有结点的层次的最大值称为该树的深度。例如，在图7-1(a)中树的深度等于0，在图7-1(b)中树的深度等于3。

无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树称为无序树。通常树指无序树。

有序树：树中任意一个结点的各孩子结点有严格排列次序的树称为有序树。二叉树是一种有序树，因为二叉树中每个结点的孩子结点都确切地定义为是该结点的左孩子结点或是该结点的右孩子结点。森林：m(m≥0)棵树的集合称为森林。自然界中树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树由根结点和m个子树组成，若把树中的根结点删除，则树就变成了包含m棵树的森林。当然，根据定义，一棵树也可以称作森林。7.1.2树的表示方法

树的表示方法主要有三种，分别用于不同的用途。

1.直观表示法

图7-1就是一棵以直观表示法表示的树。树的直观表示法主要用于直观描述树的逻辑结构。

2.形式化表示法

树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树T为T＝(D，R)，其中D为树T中结点的集合，R为树T中结点之间关系的集合。当树T为空树时D＝∅；当树T不为空树时有D＝{Root}∪DF，其中Root为树T的根结点，DF为树T的根Root的子树集合，DF可由下式表示：

DF＝D1∪D2∪…∪Dm(1≤i，j≤m，Di∩Dj＝)

当树T中结点个数n＝0或n＝1时，R＝；当树T中结点个数n>1时有：

R＝{<Root，ri>，i＝1，2，…，n-1}其中，Root是树T的非终端结点，ri是结点Root的子树Ti的根结点，<Root，ri>表示结点Root和结点ri的父子关系。

3.凹入表示法

树的凹入表示法是一种结点逐层凹入的表示方法。树的凹入表示法还可分为横向凹入表示和竖向凹入表示，图7-1(b)树的横向凹入表示如图7-2所示。树的凹入表示法主要用于树的屏幕显示和打印机输出。

图7-2树的横向凹入表示7.1.3树的抽象数据类型

1.数据集合

树的数据集合即树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。

2.操作集合

(1)创建树Create(T)：创建树T。

(2)撤消树Destroy(T)：释放树T的所有动态存储空间。

(3)双亲结点Parent(T，curr)：若树T存在，则返回树T中当前结点curr的双亲结点指针，否则返回空指针。

(4)左孩子结点LeftChild(T，curr)：若树T存在且当前指针curr存在，则返回当前结点curr的最左孩子结点(或称作第一个孩子结点)指针，否则返回空指针。

(5)右兄弟结点RightSibling(T，curr)：若树T存在且当前指针curr存在，则返回当前结点curr的右兄弟结点指针，否则返回空指针。

(6)遍历树Traverse(T，Visit())：若树T存在，则按某种遍历方法访问树T的每个结点，且每个结点只访问一次，访问结点时调用函数Visit()。树的遍历方法主要有先根遍历方法、后根遍历方法和层序遍历方法三种。上述操作集合中给出的只是树的一些基本操作，实际使用中，树的操作集合中通常还包括其他一些操作。

由于树的操作实现比较复杂，树可以转换为二叉树，而二叉树的操作实现相对简单，因此实际使用中经常是把树问题转换为二叉树问题处理。

本节只介绍了树的基本概念，在随后的几节中我们将详细讨论二叉树的操作实现等问题，最后一节将介绍几种树的存储结构以及树和二叉树的相互转换方法。

7.2.1二叉树的定义

二叉树是n(n≥0)个有限结点构成的集合。n＝0的树称为空二叉树；n>0的二叉树由一个根结点和两个互不相交的、分别称作左子树和右子树的子二叉树构成。

显然，二叉树是一种有序树。二叉树中某个结点即使只有一个子树也要区分是左子树还是右子树。因此，图7-3(a)和图7-3(b)所示是两棵不同的二叉树。7.2二叉树

图7-3两棵不同的二叉树

(a)二叉树1；(b)二叉树2二叉树中所有结点的形态共有5种：空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。

满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶结点都在同一层上，这样的二叉树称作满二叉树。

图7-4(a)所示的二叉树是一棵满二叉树。

完全二叉树：如果一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同，这样的二叉树称作完全二叉树。

图7-4(b)所示的二叉树是一棵完全二叉树，比较图7-4(b)和图74(a)可知，图7-4(b)所示二叉树的10个结点与图7-4(a)所示满二叉树的前10个结点的结构相同，因此图7-4(b)所示的二叉树是完全二叉树。显然，满二叉树一定是完全二叉树。

图7-4满二叉树和完全二叉树

(a)满二叉树；(b)完全二叉树7.2.2二叉树抽象数据类型

1.数据集合

二叉树的数据集合即二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。

2.操作集合

(1)初始化Initiate(T)：初始化二叉树T。

(2)左插入结点InsertLeftNode(curr，x)：若当前结点curr非空，在curr的左子树插入元素值为x的新结点，原curr所指结点的左子树成为新插入结点的左子树，若插入成功返回新插入结点的指针，否则返回空指针。

(3)右插入结点InsertRightNode(curr，x)：若当前结点curr非空，在curr的右子树插入元素值为x的新结点，原curr所指结点的右子树成为新插入结点的右子树，若插入成功返回新插入结点的指针，否则返回空指针。

(4)左删除子树DeleteLeftTree(curr)：若当前结点curr非空，删除curr所指结点的左子树，若删除成功返回删除结点的双亲结点指针，否则返回空指针。

(5)右删除子树DeleteRightTree(curr)：若当前结点curr非空，删除curr所指结点的右子树，若删除成功返回删除结点的双亲结点指针，否则返回空指针。

(6)遍历二叉树Traverse(T，Visit())：若二叉树T存在则按某种次序访问二叉树T的每个结点，且每个结点只访问一次，访问结点时调用函数Visit()。二叉树的遍历次序主要有先序遍历次序、中序遍历次序、后序遍历次序和层序遍历次序四种。

(7)撤消二叉树Destroy(T)：释放二叉树T的所有动态存储空间。

实际上，撤消二叉树操作是遍历二叉树操作的一个具体应用。

上面给出的操作集合只是其主要部分，实际使用的二叉树操作集合中还包括如左删除结点、右删除结点等操作，为简洁起见，这里未做介绍。7.2.3二叉树的性质

性质1若规定根结点的层次为0，则一棵非空二叉树的第i层上最多有2i(i≥0)个结点。

证明采用归纳法来证明。当层次n＝0时，二叉树在根结点只有一个结点，20＝1，结论成立；当层次n＝t时结论成立，即第t层上最多有2t个结点；当层次n＝t＋1时，根据二叉树的定义，第t层上的每个结点最多有2个子结点，所以第t＋1层上最多有2t*2＝2t＋1个结点。证毕。

性质2若规定空树的深度为-1，则深度为k的二叉树的最大结点数是2k＋1-1(k≥-1)个。

证明当深度为k＝-1时是空二叉树，空二叉树应当一个结点也没有，有2-1＋1-1＝20-1＝0，结论成立；当深度为k≥0时是非空二叉树，具有层次i＝0，1，2，…，k，由性质1知，第i层上最多有2i(i≥0)个结点，所以整个二叉树中所具有的最大结点数为

∑ki＝02i＝2k＋1-1

性质3具有n个结点的完全二叉树的深度k为不超过lb(n＋1)-1的最大整数。证明由性质2和完全二叉树的定义可知，对于有n个结点的深度为k的完全二叉树有

2k-1<n≤2k＋1-1

移项有

2k<n＋1≤2k＋1

对不等式求对数，有

k<lb(n＋1)≤k＋1因为lb(n＋1)介于k和k＋1之间且不等于k，而二叉树的深度又只能是整数，必有lb(n＋1)等于k＋1，所以n个结点的完全二叉树的深度k为不超过lb(n＋1)-1的最大整数。性质4对于具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从0开始顺序编号，则对于序号为i的结点，有：

(1)如果i>0，则序号为i的结点的双亲结点的序号为(i-1)/2(“/”表示整除)；如果i＝0，则序号为i的结点为根结点，无双亲结点。

(2)如果2i＋1<n，则序号为i的结点的左孩子结点的序号为2i＋1；如果2i＋1≥n，则序号为i的结点无左孩子。

(3)如果2i＋2<n，则序号为i的结点的右孩子结点的序号为2i＋2；如果2i＋2≥n，则序号为i的结点无右孩子。

性质4的证明比较复杂，故省略。我们用实际例子检验性质4的正确性。对于图7-4(b)所示的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从0开始顺序编号，则结点和结点序号的对应关系如下：

ABCDEFGHIJ

0123456789

该完全二叉树共有10个结点，所以n＝10。对于结点B，相应的序号为1，则结点B的双亲结点A的序号为(i-1)/2＝(1-1)/2＝0，结点B的左孩子结点D的序号为2i＋1＝2×1＋1＝3，结点B的右孩子结点E的序号为2i＋2＝2×1＋2＝4。对于结点E，相应的序号为4，则结点E的双亲结点B的序号为(i-1)/2＝(4-1)/2＝1，结点E的左孩子结点J的序号为2i＋1＝2×4＋1＝9，因有2i＋2＝2×4＋2＝10＝n，所以结点E无右孩子结点。性质4告诉我们，如果我们把完全二叉树按照从上至下和从左至右的顺序对所有结点顺序编号，则可以用一维数组存储完全二叉树。此时完全二叉树中任意结点的双亲结点序号、左孩子结点序号和右孩子结点序号均可以根据该结点的序号计算得出。

7.3.1二叉树的存储结构

二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。7.3二叉树的设计和实现

1.二叉树的顺序存储结构

由性质4可知，对于完全二叉树中任意结点i的双亲结点序号、左孩子结点序号和右孩子结点序号都可由公式计算得到。因此完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到，这就是二叉树的顺序存储结构。图74(a)所示的二叉树在数组中的存储结构为：

图7-4(b)所示的二叉树在数组中的存储形式为：

但是，对于一般的非完全二叉树，如果仍按从上至下和从左至右的次序存储在一维数组中，则数组下标之间的关系不能反映二叉树中结点之间的逻辑关系。此时我们可首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。图7-5(a)是一棵非完全二叉树，图7-5(b)是图7-5(a)的完全二叉树形态，图7-5(c)是图7-5(b)在数组中的存储形式。

图7-5非完全二叉树的顺序存储结构

(a)一般二叉树；(b)完全二叉树形态；(c)在数组中的存储形式显然，对于完全二叉树，用顺序存储结构存储时既能节省存储空间，又能使二叉树的操作实现简单。但对于非完全二叉树，如果它接近于完全二叉树，即需要增加的空结点数目不多时，可采用顺序存储结构存储，但如果需要增加的空结点数太多时就不宜采用顺序存储结构存储。最坏的情况是右单支树，若右单支树采用顺序存储结构方法存储，则一棵深度为k的右单支树只有k个结点，却需分配2k-1个存储单元。另外，使用中还需要识别数据域为空的情况，图7-5(c)中用符号“∧”表示数据域为空。

2.二叉树的链式存储结构

二叉树的链式存储结构是用指针建立二叉树中结点之间的关系的。二叉树最常用的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：

和单链表有不带头结点和带头结点两种类似，二叉链存储结构的二叉树也有不带头结点和带头结点两种。对于图7-3(b)所示的二叉树，不带头结点的二叉链存储结构的二叉树如图7-6(a)所示；带头结点的二叉链存储结构的二叉树如图7-6(b)所示。

图7-6二叉链存储结构的二叉树

(a)不带头结点的二叉树；(b)带头结点的二叉树二叉树的二叉链存储结构是一种常用的二叉树存储结构。二叉链存储结构的优点是结构简单，可以方便地构造任意需要的二叉树，可以方便地实现二叉树的大多数操作。二叉链存储结构的缺点是查找当前结点的双亲结点操作实现起来比较麻烦。

链式存储结构二叉树的另一种形式是三叉链。三叉链是在二叉链存储结构的基础上再增加一个双亲结点指针域parent。三叉链除具有二叉链的优点外，对于查找当前结点的双亲结点操作实现起来也很容易。相对于二叉链存储结构，三叉链存储结构的缺点是每个结点占用的内存单元更多一些。

3.二叉树的仿真指针

在使用数组存储数据元素时，我们可在存储数据元素的数组中增加一个或几个数组下标域，这些数组下标域的值表示了该数组中某个数据元素的下标。由于在数组中增加的数组下标域仿真了链式存储结构中的指针域，所以这种存储结构也称作仿真指针。

图7-7二叉树的仿真二叉链存储结构二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。二叉树的仿真指针存储结构有仿真二叉链存储结构和仿真三叉链存储结构。图7-7所示是图7-6(a)所示的二叉树的仿真二叉链存储结构，其中leftChild域和rightChild域中的数值为左孩子结点和右孩子结点在数组中的下标序号。

要注意图7-7的二叉树的仿真二叉链存储结构和图7-5(c)的二叉树的顺序存储结构的不同。7.3.2二叉链存储结构下二叉树的操作实现

在二叉链存储结构下，二叉树的结点定义以及如图7-6(b)所示的带头结点二叉树的初始化操作、左结点插入操作、右结点插入操作、左子树删除操作、右子树删除操作实现算法设计如下：

typedefstructNode

{

DataTypedata;/*数据域*/

structNode*leftChild;/*左子树指针*/

structNode*rightChild;/*右子树指针*/

}BiTreeNode;/*结点的结构体定义*/

/*初始化创建二叉树的头结点*/

voidInitiate(BiTreeNode**root)

{

*root＝(BiTreeNode*)malloc(sizeof(BiTreeNode));

(*root)->leftChild

＝NULL;

(*root)->rightChild

＝NULL;

}

/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/

/*原curr所指结点的左子树成为新插入结点的左子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode*InsertLeftNode(BiTreeNode*curr，DataTypex)

{

BiTreeNode*s，*t;

if(curr

＝＝NULL)returnNULL;

t＝curr->leftChild;/*保存原curr所指结点的左子树指针*/

s＝(BiTreeNode*)malloc(sizeof(BiTreeNode));

s->data＝x;

s->leftChild

＝t;/*新插入结点的左子树为原curr的左子树*/

s->rightChild

＝NULL;

curr->leftChild

＝s;/*新结点成为curr的左子树*/

returncurr->leftChild;/*返回新插入结点的指针*/

}

/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/

/*原curr所指结点的右子树成为新插入结点的右子树*/

/*若插入成功返回新插入结点的指针，否则返回空指针*/

BiTreeNode*InsertRightNode(BiTreeNode*curr，DataTypex)

{

BiTreeNode*s，*t;

if(curr

＝＝NULL)returnNULL;

t＝curr->rightChild;/*保存原curr所指结点的右子树指针*/

s＝(BiTreeNode*)malloc(sizeof(BiTreeNode));

s->data＝x;

s->rightChild

＝t;/*新插入结点的右子树为原curr的右子树*/

s->leftChild

＝NULL;

curr->rightChild

＝s;/*新结点成为curr的右子树*/

returncurr->rightChild;/*返回新插入结点的指针*/

}

/*若curr非空，删除curr所指结点的左子树*/

/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/

BiTreeNode*DeleteLeftTree(BiTreeNode*curr)

{

if(curr

＝＝NULL||curr->leftChild

＝＝NULL)returnNULL;

Destroy(curr->leftChild);

curr->leftChild

＝NULL;

returncurr;

}

/*若curr非空，删除curr所指结点的右子树*/

/*若删除成功返回删除结点的双亲结点指针，否则返回空指针*/

BiTreeNode*DeleteRightTree(BiTreeNode*curr)

{

if(curr

＝＝NULL||curr->rightChild

＝＝NULL)returnNULL;

Destroy(curr->rightChild);

curr->rightChild

＝NULL;

returncurr;

}编写一个建立如图7-6(b)所示的带头结点的二叉链存储结构二叉树的程序。

设计程序设计如下：voidmain(void)

{

BiTreeNode*root，*p，*pp;

Initiate(&root);

p＝InsertLeftNode(root，′A′);

p＝InsertLeftNode(p，′B′);

p＝InsertLeftNode(p，′D′);

p＝InsertRightNode(p，′G′);

p＝InsertRightNode(root->leftChild，′C′);

pp＝p;

InsertLeftNode(p，′E′);

InsertRightNode(pp，′F′);

}7.3.3二叉树的遍历及其实现

1.二叉树的遍历

由二叉树的定义知，一棵二叉树由三部分组成：根结点、左子树和右子树。若规定D，L，R分别代表“访问根结点”、“遍历根结点的左子树”和“遍历根结点的右子树”，则共有六种组合：LDR，DLR，LRD，RDL，DRL，RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以我们只讨论六种组合的前三种：DLR，LDR，LRD。

根据遍历算法对访问根结点处理的位置我们称这三种遍历算法分别为前序遍历(DLR)、中序遍历(LDR)和后序遍历(LRD)。显然，二叉树的遍历过程是递归的。

1)前序遍历(DLR)算法

若二叉树为空则算法结束；否则：

(1)访问根结点；

(2)前序遍历根结点的左子树；

(3)前序遍历根结点的右子树。

对于图7-3(b)所示的二叉树，前序遍历访问结点的次序为：

ABDGCEF

2)中序遍历(LDR)算法

若二叉树为空则算法结束；否则：

(1)中序遍历根结点的左子树；

(2)访问根结点；

(3)中序遍历根结点的右子树。

对于图7-3(b)所示的二叉树，中序遍历访问结点的次序为：

DGBAECF

3)后序遍历(LRD)算法

若二叉树为空则算法结束；否则：

(1)后序遍历根结点的左子树；

(2)后序遍历根结点的右子树；

(3)访问根结点。

对于图7-3(b)所示的二叉树，后序遍历访问结点的次序为：

GDBEFCA

除前序、中序和后序遍历算法外，二叉树还有层序遍历。二叉树的层序遍历要求按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。二叉树的层序遍历算法为：

(1)初始化设置一个队列，并把根结点指针入队列。

(2)当队列非空时，循环执行步骤①~③。

①出队列取得一个结点指针，访问该结点。

②若该结点的左子树非空，则将该结点的左子树指针入队列。

③若该结点的右子树非空，则将该结点的右子树指针入队列。

4)结束

对于图7-3(b)所示的二叉树，层序遍历访问结点的次序为：

ABCDEFG

由于二叉树是非线性结构，每个结点会有零个、一个或两个孩子结点，所以一个二叉树的遍历序列不能决定一棵二叉树，例如图7-3(a)和图7-3(b)所示的二叉树的前序遍历序列是相同的，但它们是两棵不同的二叉树。但某些不同的遍历序列可以惟一确定一棵二叉树。可以证明，给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树。二叉树虽然不能像单链表那样每个结点都有一个惟一的前驱结点和惟一的后继结点，但当一棵二叉树用一种特定的遍历方法来遍历时，其遍历序列一定是惟一的。因此，当规定了二叉树的遍历方法时，二叉树也像单链表一样，除根结点和最后一个结点外每个结点都有一个惟一的前驱结点和惟一的后继结点。

2.二叉链存储结构的二叉树遍历操作实现voidPreOrder(BiTreeNode*t，voidvisit(DataTypeitem))

/*使用visit()函数前序遍历二叉树t*/

{

if(t!＝NULL)

{

visit(t->data);

PreOrder(t->leftChild，visit);

PreOrder(t->rightChild，visit);

}

}

voidInOrder(BiTreeNode*t，voidvisit(DataTypeitem))

/*使用visit()函数中序遍历二叉树t*/

{

if(t!＝NULL)

{

InOrder(t->leftChild，visit);

visit(t->data);

InOrder(t->rightChild，visit);

}

}

voidPostOrder(BiTreeNode*t，voidvisit(DataTypeitem))

/*使用visit()函数后序遍历二叉树t*/

{

if(t!＝NULL)

{

PostOrder(t->leftChild，visit);

PostOrder(t->rightChild，visit);

visit(t->data);

}

}3.二叉链存储结构的二叉树撤消操作实现

二叉树的撤消操作实际上是二叉树某种遍历操作的一个具体应用。由于二叉树中每个结点允许有左孩子结点和右孩子结点，所以在释放某个结点的存储空间前必须先释放该结点左孩子结点的存储空间和右孩子结点的存储空间，因此，二叉树撤消操作必须是后序遍历的具体应用。撤消操作算法实现如下：voidDestroy(BiTreeNode**root)

{

if((*root)!＝NULL&&(*root)->leftChild!＝NULL)

Destroy(&(*root)->leftChild);

if((*root)!＝NULL&&(*root)->rightChild!＝NULL)

Destroy(&(*root)->rightChild);

free(*root);

}4.应用举例

编写一个建立如图7-6(b)所示的带头结点的二叉链存储结构二叉树的程序，并分别按照前序遍历二叉树次序、中序遍历二叉树次序和后序遍历二叉树次序输出显示二叉树各结点的信息。

设计输出显示函数设计：按照某种遍历方法输出显示二叉树各结点的信息，其实就是把上述各遍历二叉树函数中的visit()函数设计成输出显示结点信息的函数。visit()函数设计如下：

voidvisit(DataTypeitem)

{

printf("%c"，item);

}程序设计：设二叉树的结点定义以及带头结点二叉树的初始化操作、左结点插入操作、右结点插入操作、左子树删除操作、右子树删除操作的实现函数存放在文件BiTree.h中，设二叉树遍历操作和撤消操作的实现函数存放在文件BiTreeTraverse.h中。程序设计如下：

＃include<stdlib.h>

＃include<stdio.h>

typedefcharDataType;＃include"BiTree.h"

＃include"BiTreeTraverse.h"

voidvisit(DataTypeitem)

{

printf("%c"，item);

}

voidmain(void)

{

BiTreeNode*root，*p，*pp;

Initiate(&root);

p＝InsertLeftNode(root，′A′);

p＝InsertLeftNode(p，′B′);

p＝InsertLeftNode(p，′D′);

p＝InsertRightNode(p，′G′);

p＝InsertRightNode(root->leftChild，′C′);

pp＝p;

InsertLeftNode(p，′E′);

InsertRightNode(pp，′F′);

printf("前序遍历：");

PreOrder(root->leftChild，visit);

printf("＼n中序遍历：");

InOrder(root->leftChild，visit);

printf("＼n后序遍历：");

PostOrder(root->leftChild，visit);

Destroy(&root);

}

程序运行输出结果如下：

前序遍历：ABDGCEF

中序遍历：DGBAECF

后序遍历：GDBEFCA

二叉树遍历算法提供了二叉树的一次性遍历，但二叉树遍历算法无法实现用户程序像分步遍历单链表那样分步遍历二叉树。线索二叉树就是专为实现分步遍历二叉树而设计的。线索二叉树可以实现像双向链表那样，既可以从前向后分步遍历二叉树，又可以从后向前分步遍历二叉树。7.4线索二叉树二叉树是非线性结构，但从前面的讨论可知，当以某种规则遍历二叉树时将把二叉树中的结点按该规则排列成一个线性结构。然而，我们每次按某种规则遍历二叉树时都没有把遍历时得到的结点的后继结点信息和前驱结点信息保存下来，因此，我们不能像操作双向链表那样操作二叉树。保存这种按某种规则遍历二叉树时得到的结点的后继结点信息和前驱结点信息的最常用的方法是建立线索二叉树。对于二叉链存储结构的二叉树分析可知，在有n个结点的二叉树中必定存在n＋1个空链域。我们希望能利用这些空链建立起相应结点的前驱结点信息和后继结点信息。

我们做如下规定：当某结点的左指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的前驱结点；当某结点的右指针为空时，令该指针指向按某种方法遍历二叉树时得到的该结点的后继结点。

仅仅这样做会使我们不能区分左指针指向的结点到底是左孩子结点还是前驱结点，右指针指向的结点到底是右孩子结点还是后继结点。因此我们再在结点中增加两个线索标志位来区分这两种情况。线索标志位定义如下：leftThread＝0leftChild指向结点的左孩子结点1leftChild指向结点的前驱结点rightThread＝0rightChild指向结点的右孩子结点1rightChild指向结点的后继结点这样，每个结点的存储结构就如下所示：

leftThreadleftChilddatarightChildrightThread

我们把结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法(如前序、中序或后序方法)遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。

为使算法设计方便，一般在设计线索二叉树时都包含有头结点。头结点的data域为空，leftChild指针指向二叉树的根结点，leftThread为0，rightChild指向按某种方式遍历二叉树时的最后一个结点，rightThread为1。

对于图7-8(a)所示的二叉树，图7-8(b)是相应的中序线索二叉树，图7-8(c)是相应的前序线索二叉树，图7-8(d)是相应的后序线索二叉树。图中实线表示二叉树原来指针所指的结点，虚线表示线索二叉树所添加的线索。注意，中序、前序和后序线索二叉树中所有实线均相同，所有结点的线索标志位取值也完全相同，只是当线索标志位取1时不同的线索二叉树虚线将不同。

如何把一棵二叉树变为一棵线索二叉树呢？方法是在遍历二叉树的过程中给每个结点添加线索。

例如，要建立一棵中序线索二叉树，方法就是在中序遍历二叉树的过程中给每个结点添加线索(或称中序线索)；要建立一棵前序线索二叉树，方法就是在前序遍历二叉树的过程中给每个结点添加线索(或称前序线索)。

一旦建立了某种方式的线索二叉树后，用户程序就可以像操作双向链表一样操作该线索二叉树。例如，一旦建立了中序线索二叉树后，用户程序可以设计一个正向循环结构遍历该二叉树的所有结点，

循环初始定位在中序线索二叉树的第一个结点位置，每次循环使指针指向当前结点的中序遍历的后继结点位置，当指针指向中序线索二叉树的最后一个结点位置后循环过程结束；或者用户程序可以设计一个反向循环结构遍历该二叉树的所有结点，循环初始定位在中序线索二叉树的最后一个结点位置，每次循环使指针指向当前结点的中序遍历的前驱结点位置，当指针指向中序线索二叉树的第一个结点位置前循环过程结束。

图7-8线索二叉树(a)二叉树；(b)中序线索二叉树；

(c)前序线索二叉树；(d)后序线索二叉树

7.5.1哈夫曼树的基本概念

在一棵二叉树中，我们定义从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径；从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度；从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。7.5哈夫曼树如果二叉树中的叶结点都带有权值，我们可以把这个定义加以推广。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为该二叉树的带权路径长度(WPL)，即

其中，wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。对图7-9(a)所示的二叉树，其带权路径长度为

WPL＝1×2＋3×2＋5×2＋7×2＝32

图7-9具有相同叶结点和不同带权路径长度的二叉树给定一组具有确定权值的叶结点，可以构造出多个具有不同带权路径长度的二叉树。例如，给定4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的4棵二叉树，如图7-9所示。图7-9(a)~(d)所示的4棵二叉树的带权路径长度分别为：

WPL1＝1×2＋3×2＋5×2＋7×2＝32

WPL2＝1×2＋3×3＋5×3＋7×1＝33

WPL3＝7×3＋5×3＋3×2＋1×1＝43

WPL4＝1×3＋3×3＋5×2＋7×1＝29由此可见，对于一组具有确定权值的叶结点可以构造出多个具有不同带权路径长度的二叉树，我们把其中具有最小带权路径长度的二叉树称作哈夫曼树(或称最优二叉树)。可以证明，图7-9(d)所示的二叉树是一棵哈夫曼树。

根据哈夫曼树的定义，一棵二叉树要使其带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼提出的哈夫曼树构造算法为：

(1)由给定的n个权值{w1，w2，…，wn}构造n棵只有根结点的二叉树，从而得到一个二叉树森林F＝{T1，T2，…，Tn}。

(2)在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。

(3)在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。

(4)重复步骤(2)和(3)，当二叉树森林F中只剩下一棵二叉树时，这棵二叉树就是所构造的哈夫曼树。

对于一组给定的叶结点，设它们的权值集合为{7，5，3，1}，按哈夫曼树构造算法对此集合构造哈夫曼树的过程如图7-10(a)、(b)、(c)、(d)所示。

图7-10哈夫曼树的构造过程哈夫曼树可用于解决最优化问题。例如，由哈夫曼树构造的哈夫曼编码可用于构造代码总长度最短的电文编码方案。7.5.2哈夫曼编码问题

在数据通讯中，经常需要将传送的文字转换为二进制字符0和1组成的二进制串，我们称这个过程为编码。例如，假设要传送的电文为ABACCDA，电文中只有A，B，C，D四种字符，若这四个字符采用表7-1(a)所示的编码方案，则电文的代码为00010010101100(空格是为方便阅读所加)，代码总长度为14。若这四个字符采用表7-1(b)所示的编码方案，则电文的代码为0110010101110，代码总长度为13。表7-1字符集的不同编码方案哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为{d1，d2，…，dn}，各个字符在电文中出现的次数集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，以w1，w2，…，wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称为哈夫曼编码。

图7-11哈夫曼编码对于图7-10所构造出的哈夫曼树，假设权值1对应字符A，权值3对应字符B，权值5对应字符C，权值7对应字符D，则字符集{A，B，C，D}的哈夫曼编码如图7-11所示。因此，权值为7的字符D的编码为0，权值为1的字符A的编码为100，权值为3的字符B的编码为101，权值为5的字符C的编码为11。

在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的惟一性。例如，若字符A的编码为01，字符B的编码为010，那么字符A的编码就成了字符B编码的前缀，这时对于代码串01010，在译码时就无法判定是将前两位码01译成字符A还是将前三位码010译成字符B。在哈夫曼树中，由于每个字符结点都是叶结点，而叶结点是不可能在根结点到其他叶结点的路径上的，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀。*7.5.3哈夫曼编码问题设计和实现

1.哈夫曼编码问题数据结构设计

对于哈夫曼编码问题，在构造哈夫曼树时要求能方便地实现从双亲结点到左右孩子结点的操作，在进行哈夫曼编码时又要求能方便地实现从孩子结点到双亲结点的操作。因此我们设计哈夫曼树的结点存储结构为双亲孩子存储结构。

如7.3.1节所述，二叉树结点的双亲孩子存储结构既可以用常规指针实现，也可以用仿真指针实现，这里我们采用仿真指针实现。另外，每个结点还要有权值域。为了判断一个结点是否已加入到哈夫曼树中，每个结点还要有一个标志域flag，flag＝0时表示该结点尚未加入到哈夫曼树中，flag＝1时表示该结点已加入到哈夫曼树中。这样，每个结点的数据结构设计为：

由图7-11所示的哈夫曼编码可见，从哈夫曼树求叶结点的哈夫曼编码实际上是从叶结点到根结点路径分支的逐个遍历，每经过一个分支就得到一位哈夫曼编码值。因此我们需要一个数组bit［MaxBit］保存每个叶结点到根结点路径所对应的哈夫曼编码，由于是不等长编码，我们还需要一个数据域start表示每个哈夫曼编码在数组中的起始位置。这样每个叶结点的哈夫曼编码是从数组bit的起始位置start开始到数组结束位置中存放的0和1序列。存放哈夫曼编码的数组元素结构为：

所设计出的哈夫曼编码问题的C语言形式的结点结构体定义和算法一起在下面给出。

2.哈夫曼编码问题算法设计和实现

基于上述结点的双亲孩子仿真指针存储结构的哈夫曼树构造算法和相应的哈夫曼编码算法如下：typedefstruct

{

intweight;/*权值*/

intflag;/*标记*/

intparent;/*双亲结点下标*/

intleftChild;/*左孩子下标*/

intrightChild;/*右孩子下标*/

}HaffNode;/*哈夫曼树的结点结构*/

typedefstruct

{

intbit［MaxN］;/*数组*/

intstart;/*编码的起始下标*/

intweight;/*字符的权值*/

}Code;/*哈夫曼编码的结构*/

voidHaffman(intweight［］，intn，HaffNodehaffTree［］)

/*建立叶结点个数为n、权值数组为weight的哈夫曼树haffTree*/

{

inti，j，m1，m2，x1，x2;

/*哈夫曼树haffTree初始化。n个叶结点的二叉树共有2n-1个结点*/

for(i

＝0;i<2*n-1;i＋＋)

{

if(i<n)haffTree［i］.weight＝weight［i］;

elsehaffTree［i］.weight＝0;

haffTree［i］.parent＝0;

haffTree［i］.flag＝0;

haffTree［i］.leftChild

＝-1;

haffTree［i］.rightChild

＝-1;

}

/*构造哈夫曼树haffTree的n-1个非叶结点*/

for(i

＝0;i<n-1;i＋＋)

{

m1＝m2＝MaxValue;

x1＝x2＝0;

for(j

＝0;j<n＋i;j＋＋)

{

if(haffTree［j］.weight<m1&&haffTree［j］.flag＝＝0)

{

m2＝m1;

x2＝x1;

m1＝haffTree［j］.weight;

x1＝j;

}

elseif(haffTree［j］.weight<m2&&haffTree［j］.flag＝＝0)

{

m2＝haffTree［j］.weight;

x2＝j;

}

}

/*将找出的两棵权值最小的子树合并为一棵子树*/

haffTree［x1］.parent＝n＋i;

haffTree［x2］.parent＝n＋i;

haffTree［x1］.flag＝1;

haffTree［x2］.flag＝1;

haffTree［n＋i］.weight＝haffTree［x1］.weight＋haffTree［x2］.weight;

haffTree［n＋i］.leftChild

＝x1;

haffTree［n＋i］.rightChild

＝x2;

}

}

voidHaffmanCode(HaffNodehaffTree［］，intn，CodehaffCode［］)

/*由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode*/

{

Code*cd

＝(Code*)malloc(sizeof(Code));

inti，j，child，parent;

/*求n个叶结点的哈夫曼编码*/

for(i

＝0;i<n;i＋＋)

{

cd->start＝n-1;/*不等长编码的最后一位为n-1*/

cd->weight＝haffTree［i］.weight;/*取得编码对应的权值*/

child＝i;

parent＝haffTree［child］.parent;

/*由叶结点向上直到根结点*/

while(parent!＝0)

{

if(haffTree［parent］.leftChild

＝＝child)

cd->bit［cd->start］＝0;/*左孩子分支编码0*/

else

cd->bit［cd->start］＝1;/*右孩子分支编码1*/

cd->start--;

child＝parent;

parent＝haffTree［child］.parent;

}

for(j

＝cd->start＋1;j<n;j＋＋)

haffCode［i］.bit［j］＝cd->bit［j］;/*保存每个叶结点的编码*/

haffCode［i］.start＝cd->start;/*保存不等长编码的起始位*/

haffCode［i］.weight＝cd->weight;/*保存相应字符的权值*/

}

}3.测试主函数设计

设有字符集{A，B，C，D}，各字符在电文中出现的次数集为{1，3，5，7}，设计各字符的哈夫曼编码。

设计设上述哈夫曼编码问题的结点结构体定义和函数存放在文件Haffman.h中，测试主函数设计如下：＃include<stdio.h>

＃include<stdlib.h>

＃defineMaxValue10000/*设定的权值最大值*/

＃defineMaxBit4/*设定的最大编码位数*/＃defineMaxN10/*设定的最大结点个数*/

＃include"Haffman.h"/*包含文件Haffman.h*/

voidmain(void)

{

inti，j，n＝4;

intweight［］＝{1，3，5，7};

HaffNode*myHaffTree

＝(HaffNode*)malloc(sizeof(HaffNode)*(2*n＋1));

Code*myHaffCode

＝(Code*)malloc(sizeof(Code)*n);

if(n>MaxN)

{

printf("给出的n越界，修改MaxN!＼n");

exit(1);

}

Haffman(weight，n，myHaffTree);

HaffmanCode(myHaffTree，n，myHaffCode);

/*输出每个叶结点的哈夫曼编码*/

for(i

＝0;i<n;i＋＋)

{

printf("Weight

＝%dCode＝"，myHaffCode［i］.weight);

for(j

＝myHaffCode［i］.start＋1;j<n;j＋＋)

printf("%d"，myHaffCode［i］.bit［j］);

printf("＼n");

}

}程序运行输出结果如下：

Weight＝1Code＝100

Weight＝3Code＝