实用数据结构基础 第6章 树

第 6 章 树 知 识 点 难 点 树的基本概念与术语 二叉树及二叉树的存储结构 二叉树的遍历及线索二叉树 一般树和二叉树的转换 第 6 章 树 知 识 点 树的基本概念与术语 二叉树及二叉树的存储结构 二叉树的遍历及线索二叉树 一般树和二叉树的转换 哈夫曼树及哈夫曼编码 难 点 二叉树遍历算法的设计 利用二叉树遍历算法，解决简单应用问题 哈夫曼树的算法

要 求 熟练掌握以下内容: 了解以下内容： 树的基本概念和术语 二叉树定义和存储结构 二叉树遍历的概念和二叉树遍历的算法 哈夫曼树的建立 树和二叉树之间的相互转换方法 线索二叉树的概念 哈夫曼编码

第 6 章 目 录 6-1 树的定义和术语 6-2 二叉树 6-3 遍历二叉树和线索二叉树 6-4 二叉树的转换 6-5 二叉树树的应用 6-1 树的定义和术语 6-2 二叉树 6-3 遍历二叉树和线索二叉树 6-4 二叉树的转换 6-5 二叉树树的应用 6-6 哈夫曼树及其应用 小 结 实验6 树子系统 习题6

6-1 树的定义和术语 6-1 树的定义 1．树的定义 树（Tree）是n（n≥0）个有限数据元素的集合。在任意一棵非空树T中： （1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点； （2）当n>1时，除根结点之外的其余结点被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤ i ≤m）本身又是一棵树，并且称为根的子树。 树的定义采用了递归定义的方法，即在树的定义中又用到树的概念，这正好反映了树的固有特性。

2．树的其它表示法 1 2 3 4 A B C H D E F G I J 图 6-1 树结构示意图 1 2 3 4 A B C H G F E D J I 图 6-1 树结构示意图 2．树的其它表示法 图6-1是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的描述非常直观、清晰。是使用最多的一种描述方法。除此以外，还有以下几种描述树的方法：

（1）嵌套集合法 嵌套集合法，也称为文氏图法（Venn Diagram），它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。图6-2 (a)就是一棵树的嵌套集合表示。 A B C E I J D F G H 图6-2 （a）嵌套集合表示

( 2 ) 圆括号表示法 圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包含关系显示出来。下式即是图6-1所示树的圆括号表示法： ( A ( B ( D, E ( I, J ), F ), C ( G, H ) ) ) ( 3 ) 凹入法 凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系，图6-1所示树的凹入法表示如图6-2 (b)。 树的凹入表示法主要用于树的屏幕显示和打印输出。

A B C E D J F G H I 图6-2（b）凹入表示法

6-1-2 基本术语 （1）结点——树的结点包含一个数据及若干指向其子树的分支。 （2）结点的度——结点所拥有的子树数称为该结点的度（Degree）。 （3）树的度——树中各结点度的最大值称为该树的度。 （4）叶子（终端结点）——度为零的结点称为叶子结点。 （5）分枝结点——度不为零的结点称为分支结点。 （6）兄弟结点——同一父亲结点下的子结点称为兄弟结点。

（7）层数——树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。 （8）树的深度——树中结点的最大层数称为树的深度（或高度）。 （9）森林——零棵或有限棵互不相交的树的集合称为森林。 在数据结构中，树和森林并不象自然界里有一个明显的量的差别。任何一棵树，只要删去根结点就成了森林，见图6-3。

（10）有序树和无序树——树中结点的各子树从左到右是有次序的（即不能互换位置），称这样的树为有序树；否则称为无序树。 A B C H G F E D J I K (a) 树 (b) 移去根结点后成为森林 图6-3 （10）有序树和无序树——树中结点的各子树从左到右是有次序的（即不能互换位置），称这样的树为有序树；否则称为无序树。

6-2 二叉树 6-2-1 二叉树的定义 1．定义 二叉树是有n（n>=0）个结点的有限集合。 （1）该集合或者为空（n=0）； 6-2 二叉树 6-2-1 二叉树的定义 1．定义 二叉树是有n（n>=0）个结点的有限集合。 （1）该集合或者为空（n=0）； （2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树； （3）左子树和右子树同样又都是二叉树。 通俗地讲：在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。

2．二叉树的形态 根据定义，二叉树可以有五种基本形态，如图6-4所示。 Ф Rchild Lchild (a) (b) (c) (d) (e) 图6-4 二叉树的基本形态 其中：（a）空二叉树； （b）仅有根结点的二叉树； （c）右子树为空的二叉树； （d）左子树为空的二叉树； （e）左、右子树均非空的二叉树。

3．二叉树的基本操作： （1） CreateBT（）： 创建一棵二叉树。 （2）ShowTree(BT *T)：按凹入法显示二叉树。 （3）Preorder(BT *T)：按先序（根、左、右）遍历二叉树上所有结点。 （4）Inorder(BT *T)： 按中序（左、根、右）遍历二叉树上所有结点。 （5）Postorder(BT *T)：按后序（左、右、根）遍历二叉树上所有结点。 （6）Levelorder(BT *T)：按层次遍历二叉树上所有结点。 （7）Leafnum(BT *T)： 求二叉树叶结点总数。 （8）TreeDepth(BT *T)： 求二叉树的深度。

6-2-2 二叉树的性质 性质1 一棵非空二叉树的第i层上最多有2 i–1个结点（i ≥1）。 性质2 深度为h的二叉树中，最多具有2 h －1个结点（h ≥1）。 证明：根据性质1，当深度为h的二叉树每一层都达到最多结点数时，它的和（n）最大，即： ∴ 命题正确。

（1）满二叉树 一棵深度为h，且有2 h‐1个结点的二叉树称为满二叉树。图6-5所示是一棵深度为4的满二叉树，其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续的编号，约定编号从根结点起，从上往下，自左向右（如图6-5），由此可以引出完全二叉树的定义。 1 2 3 8 7 6 5 4 10 9 11 12 13 14 15 图6-5 满二叉树

（2）完全二叉树 深度为h，有n个结点的二叉树，当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。如图6-6（a）所示为一棵完全二叉树。 A B C H G F E D J I 图6-6（a）一棵完全二叉树

完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。 如图6-6（b）所示则不是完全二叉树。 A B C D E F G H 图6-6（b） 一棵非完全二叉树 完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。

性质3 对于一棵有n个结点的完全二叉树，若按满二叉树的同样方法对结点进行编号，（见图6-5）则对于任意序号为i的结点，有： （1）若i>1，则序号为i的结点的父结点的序号为i/2； 若i＝1，则序号为i的结点是根结点。 （2）若2i≤n，则序号为i的结点的左孩子结点的序号为2i； 若2i>n，则序号为i的结点无左孩子。 （3）若2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1； 若2i＋1>n，则序号为i的结点无右孩子。 证明略。

性质4 具有n（n>0）个结点的完全二叉树（包括满二叉树）的深度（h）为： 证明：由性质2和完全二叉树定义可知，当完全二叉树的深度为h、结点个数为n时 有： 2 h－1–1<n≤2 h-1 即： 2 h－1≤n<2 h 对不等式取对数有： h–1≤log2n< h 由于h是整数，所以有h＝ 。

性质5 对于一棵非空的二叉树，设n0、n1、n2分别表示度为0、1、2的结点个数， 则有: n0＝n2＋1。 证明： （1）设n为二叉树的结点总数，则有： n＝n0＋n1＋n2 （6-1） （2）由二叉树的定义可知，除根结点外，二叉树其余结点都有唯一父结点， 那么父结点的总数（F）为： F＝n–1 （6-2） （3）根据假设，各结点的子结点总数（C）为： C＝n1＋2n2 （6-3） （4）因为父子关系是相互对应的，即F=C，也即： n–1＝n1+2n2 （6-4） 综合（6-1）、（6-2）、（6-3）式可以得到： n0＋n1＋n2 ＝n1＋2n2 ＋1 n0＝n2＋1 ∴ 命题正确。

6-2-3 二叉树的存储 1．顺序存储结构 二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般可以采用一维数组或二维数组的方法进行存储。 （1）一维数组存储法 二叉树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同。其编号过程为：首先把根结点的编号定为1，然后按照层次从上至下、从左到右的顺序，对每一个结点编号。当双亲结点为i时,其左孩子的编号为2i，其右孩子的编号为2i+1。在图6-7(a)中,各结点右边的数字就是该结点的编号。

A B C H E D J I 1 6 5 10 2 3 12 13 图6-7 (a) 一般二叉树 如果按从上至下、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增加一些并不存在的空结点，使之成为一棵完全二叉树的形式才能用一维数组进行存储。图7-6（a），经过改造以后成为图6-7（b）所示的完全二叉树。

A B C E D F G H 其顺序存储状态示意图如图7-6（c）。 图6-7 (b) 改造为完全二叉树

显然，这种存储结构会造成空间的大量浪费，如图6-8(a)所示，一棵4个结点的二叉树，却要扩充为(b)的完全二叉树，分配14个存储单元如(c)。可以证明，深度为h的（右向）单支二叉树，虽然只有h个结点，却需分配2h -1个存储单元。 A A B C D B C D 图6-8(a) 原二叉树 图6-8(b) 改造后的完全二叉树

图6-8(c) 改造后的完全二叉树在一维数组中的存储 对于完全二叉树和满二叉树。这种顺序存储结构既能够最大限度地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，因为完全二叉树上编号为i的结点元素存储在一维数组中下标为i–1的分量中，如图6-8 (c)。

（2）二维数组存储法 设二叉树的结点数为n，可以将二维数组的容量定义为[n][3]，即n行3列。仍以图6-7 (a) 的二叉树为例，并按二维数组存储的下标重新对结点编号如图6-9(a)，设data为结点数据，leftno为结点左子树号，rightno为结点右子树号，则其存储表示如图6-9(b)所示： 图6-9 二叉树二维数组存储示意图

顺序存储小结： 2．链式存储结构 （1）当二叉树为满二叉树或完全二叉树时，采用一维数组可以节省存储空间； （2）当二叉树层数高而结点较少时，采用二维数组比较好，只要n行3列存储空间； （3）顺序存储的优点是找父结点的位置方便； （4）顺序存储缺点是进行插入或删除操作要进行大量的数据移动，且存储空间的扩充不方便。  2．链式存储结构 二叉树的链式存储结构是用链表来表示二叉树，即用链指针来指示结点的逻辑关系。通常有下面两种形式。

lchild data rchild （1）二叉链表存储 二叉链表结点由一个数据域和两个指针域组成，其结构如下： 当左子树或右子树不存在时，相应指针域值为空，用符号∧表示。 设一棵二叉树如图6-10所示，其二叉链表的存储表示如图6-11所示。

图 6-10 二叉树 图6-11 二叉树的链式存储示意图 容易证明，在含有n个结点的二叉链表中有n+1个空指针域。利用这些空指针域存储其它有用信息，从而可以得到另外一种存储结构——线索化链表，关于这一概念将在6-3-3节介绍。

（2）三叉链表存储 lchild data rchild parent 下面给出二叉树的二叉链表描述： typedef struct BT // 定义二叉树结构体 { datatype data; // 定义数据域 BT *lchild; // 定义结点的左指针 BT *rchild; // 定义结点右指针 } BT; // 将BT定义为指向二叉树结点结构体的指针类型 （2）三叉链表存储 三叉链表结点由一个数据域和三个指针域组成，其结构如下： lchild data rchild parent

其中：data为数据域，存放结点的数据信息； lchild为左指针域，存放该结点左子树的存储地址； rchild为右指针域，存放该结点右子树的存储地址。 parent为父指针域，存放结点的父结点存储地址。 这种存储结构既便于查找左、右子树的结点，又便于查找父结点；但付出的代价是，增加了存储空间的开销。 图6-12给出了二叉树的三叉链表存储示意图。

6-3 遍历二叉树和线索二叉树 6-3-1 遍历二叉树 二叉树的遍历是指按某种顺序访问二叉树中的所有结点，使得每个结点都被访问，且仅被访问一次。通过一次遍历，使二叉树中结点的非线性序列转变为线性序列。也就是说，使得遍历的结点序列之间有一个一对一的关系。 由二叉树的递归定义可知，一棵二叉树由根结点（D）、根结点的左子树（L）和根结点的右子树（R）三部分组成。因此，只要依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根结点、遍历根结点的左子树、遍历根结点的右子树，则二叉树的遍历方式有六种不同的组合：DLR、LDR、LRD、DRL、RDL和RLD。 一般限定先左后右的次序，那么只有三种遍历： DLR（根左右）、LDR（左根右）、LRD（左右根）。

1．先序遍历（DLR）的递归过程 若二叉树为空，遍历结束。否则， （1）访问根结点； （2）先序遍历根结点的左子树； （3）先序遍历根结点的右子树。 void Preorder(BT *T) // 先序遍历二叉树BT { if (T= =NULL) return; // 递归调用的结束条件 { printf(T->data); // 输出结点的数据域 Preorder(T->lchild); // 先序递归遍历左子树 Preorder(T->rchild); // 先序递归遍历右子树 } 图6-10的二叉树，按先序遍历所得到的结点序列为： 　A B D G C E F H

2．中序遍历（LDR）的递归过程 若二叉树为空，遍历结束。否则， （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。 void Inorder(BT *T) // 中序遍历二叉树BT { if (T= =NULL) return; 　 // 递归调用的结束条件 { Inorder(T->lchild); 　 // 中序递归遍历左子树 printf(T->data); 　 // 输出结点的数据域 Inorder(T->rchild); // 中序递归遍历右子树 } 图6-10的二叉树，按中序遍历所得到的结点序列为： D G B A E C H F

3．后序遍历（LRD）的递归过程 若二叉树为空，遍历结束。否则， （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树。 （3）访问根结点； void Postorder(BT *T) // 后序遍历二叉树BT { if (T= =NULL) return; // 递归调用的结束条件 { Postorder(T->lchild); // 后序递归遍历左子树 Postorder(T->rchild); // 后序递归遍历右子树 printf(T->data); // 输出结点的数据域 } 图6-10的二叉树，按后序遍历所得到的结点序列为： G D B E H F C A

4．层次遍历 按照自上而下（从根结点开始），从左到右（同一层）的顺序逐层访问二叉树上的所有结点，这样的遍历称为按层次遍历。 按层次进行遍历时，当一层结点访问完后，接着访问下一层的结点，先遇到的结点先访问，这与队列的操作原则是一致的。因此，在进行层次遍历时，可设置一个数组来模拟队列，用于保存被访问结点的子结点的地址。遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作： （1）访问该元素所指结点； （2）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针依次入队。 此过程不断进行，直到队空为止。在下面的层次遍历算法中，以二叉链表方式存储，一维数组q[MAXLEN]用以实现队列，lchild和rchild分别是被访问结点的左、右指针。

void Levelorder(BT *T) // 按层次遍历二叉树BT { int i,j; BT *q[MAXLEN],*p; // 设置一个数组来模拟队列 p=T; if (p!=NULL) // 若二叉树非空，则根结点地址入队 { i=1;q[i]=p;j=2; } while (i!=j) { p=q[i];printf(p->data); // 访问队首结点的数据域 if( p->lchild!=NULL) // 将队首结点的左孩子结点入队列 {q[j]=p->lchild; j++;} if(p->rchild!=NULL) // 将队首结点的右孩子结点入队列 { q[j]=p->rchild；j++；} i++ ； }   图6-10的二叉树，按层次遍历所得到的结果序列为： A B C D E F G H

【例6-1】 二叉树，如图6-14所示，求它的先序遍历、中序遍历、后序遍历和层次遍历。 A B C I K F E D H G 先序遍历的序列： A B D G E H C F I K 中序遍历的序列： D G B H E A F K I C 后序遍历的序列： G D H E B K I F C A 层次遍历的序列： A B C D E F G H I K 图6-13 二叉树

- * 【例6-2】设表达式A–B*（C+D）+E/（F+G）的二叉树表示如图6-14所示。试写出它的先序遍历、中序遍历和后序遍历。 A / 先序遍历的结果（即前缀表达）： + – A * B + C D / E + F G 中序遍历的结果： A – B * C + D + E / F + G 后序遍历（即后缀表达式）： A B C D + * – E F G + / + 图6-14 表达式二叉树

6-3-2 恢复二叉树 在统一绘图软件或其它绘图软件中存在着这样的问题：如何存储一个用树表示的图形数据结构？在研制统一绘图软件系统时是用这样的办法来处理的： （1）对于用链表结构表示的图形数据结构，我们把每一个结点去掉指针项，只按结点的中序序列存储，并给出这棵树的前序（或后序）“序表”。 （2）图形结构调入内存时，由中序的结点表及“序表”，形成的前序和中序数组（或后序和中序数组），恢复图形数据结构。 二叉树的先序遍历是先访问根结点，然后再遍历根结点的左子树，最后遍历根结点的右子树。即在先序序列中，第一个结点必定是二叉树的根结点。

中序遍历则是先遍历左子树，然后访问根结点，最后再遍历右子树。这样，根结点在中序序列中必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，而后一个子序列是根结点的右子树的中序序列。 根据这两个子序列，先由先序序列确定第一个结点为根结点；知道根结点后，按中序序列可以划分左、右子树。 在先序序列中，左子树序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。这样，就确定了二叉树的三个结点。 同时，左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列，如此递归下去，当取尽先序序列中的结点时，便可以恢复一棵二叉树。

1. 由前序和中序恢复二叉树 （1）根据前序序列确定树的根（第一个结点），根据中序序列确定左子树和右子树； （2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到父（father）结点上去； （3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。 【例6-3】由下列前序序列和中序序列恢复二叉树。 前序序列：A C B R S E D F M L K 中序序列：R B S C E A F D L K M 首先，由先序序列可知，结点A是二叉树的根结点；其次，根据中序序列，在A之前的所有结点都是根结点左子树的结点，在A之后的所有结点都是根结点右子树的结点：

前序序列： A C B R S E D F M L K 根 左子树 子树 中序序列： R B S C E A F D L K M 根 左子树 子树 中序序列： R B S C E A F D L K M 左子树 根 右子树 继续对左、右子树进行分解： 左子树： 右子树： 前序前序：C B R S E D F M L K 根 左子树 右子树 根 左子树 右子树 中序前序：R B S C E F D L K M 左子树 根 右子树 左子树 根 右子树

再按同样的方法继续分解下去，最后得到如图6-16所示的整棵二叉树。 A C D R M F E B L S K 图6-15 上述过程是一个递归过程，其递归算法的思想是：先根据先序序列的第一个元素建立根结点；然后在中序序列中找到该元素，确定根结点的左、右子树的中序序列；再在先序序列中确定左、右子树的先序 序列；最后由左子树的先序序列与中序序列建立左子树，由右子树的先序序列与中序序列建立右子树。

2．由中序和后序恢复二叉树 由二叉树的后序序列和中序序列也可唯一地确定一棵二叉树。其方法为： （1）根据后序序列找出根结点（最后一个），根据中序序列确定左、右子树； （2）分别找出左子树和右子树的根结点，并把左、右子树的根结点联到父（father）结点上去； （3）再对左子树和右子树按此法找根结点和左、右子树，直到子树只剩下1个结点或2个结点或空为止。 【 例6-4 】由下列中序序列和后序序列恢复二叉树。 中序序列：C B E D A G H F J I 后序序列：C E D B H G J I F A

首先，由后序序列可知，结点A是二叉树的根结点；其次，根据中序序列，在A之前的所有结点都是根结点左子树的结点，在A之后的所有结点都是根结点右子树的结点： 后序序列：C E D B H G J I F A 左子树 右子树 根 中序序列：C B E D A G H F J I 左子树 根 右子树 继续分解： 左子树： 右子树： 后序序列：C E D B H G J I F 根 根 中序序列： C B E D G H F J I 左子树 根 右子树 左子树 根 右子树

思 考 A B F E I G D C J H 再按同样的方法继续分解下去，最后得到如图6-17的整棵二叉树。 图6-16 再按同样的方法继续分解下去，最后得到如图6-17的整棵二叉树。 思 考 根据二叉树的前序序列和后序序列能唯一恢复一棵二叉树吗？

6-3-3 线索二叉树 1．什么是线索二叉树 遍历二叉树是按一定的规则将二叉树中所有结点排列为一个有序序列，这实质上是对一个非线性的数据结构进行线性化的操作。经过遍历的结点序列，除第一个结点和最后一个结点以外，其余每个结点都有且仅有一个直接前驱结点和一个直接后继结点。 当以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而不能直接得到结点任意一个序列中的直接前趋结点和直接后继结点是什么，这种信息只有在对二叉树遍历的动态过程中才能得到得到。若增加前趋和后继指针将使存储密度进一步降低。 在用二叉链表存储的二叉树中，单个结点的二叉树有两个空指针域，如图6-17(a) 所示，两个结点的二叉树有三个空指针域，如图6-17(b) 所示。

A ∧ ∧ A ∧ B 图6-17(a) 单结点的二叉链表图 6-17(b) 两个结点的二叉链表 不难证明：n 个结点的二叉树有n+1个空指针域。也就是说一个具有n个结点的二叉树，若采用二叉链表存储结构，在其总共2n个指针域中只有n­1个指针域是用来存储结点子树的地址，而另外n+1个指针域存放的都是空指针域。可以充分利用二叉链表存储结构中的那些空指针域，来保存结点在某种遍历序列中的直接前趋和直接后继的地址信息。 指向直接前趋结点或指向直接后继结点的指针称为线索（Thread），带有线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

2．线索二叉树的方法 由于二叉树结点的序列可由不同的遍历方法得到，因此，线索二叉树也有先序线索二叉树、中序线索二叉树和后序线索二叉树三种。在三种线索二叉树中一般以中序线索化用得最多，所以下面以图6-10（P111）所示的二叉树为例，说明中序线索二叉树的方法： （1）先写出原二叉树的中序遍历序列： D G B A E C H F （2）若结点的左子树为空，则此线索指针将指向前一个遍历次序的结点； （3）若结点的右子树为空，则此线索指针将指向下一个遍历次序的结点。

图6-10二叉树的中序遍历序列： D G B A E C H F。 其中序线索二叉树的结果如图6-18所示。其中实线表示指针，虚线表示线索。 图6-18 中序线索二叉树 另外，为了便于操作，在存储线索二叉树时需要增设一头结点，其结构与其它线索二叉树的结点结构一样。

3．线索二叉树的优点 （1）利用线索二叉树进行中序遍历时，不必采用堆栈处理，速度较一般二叉树的遍历速度快，且节约存储空间。 （2）任意一个结点都能直接找到它的前一个或后一个遍历顺序的结点。  4．线索二叉树的缺点 （1）结点的插入和删除麻烦，且速度也较慢。 （2）线索子树不能共用。

6-4 二叉树的转换 6-4-1 一般树转换为二叉树 如果对树或森林采用链表存储并设定一定的规则，就可用二叉树结构表示树和森林。这样，对树的操作实现就可以借助二叉树存储，利用二叉树上的操作来实现。 1．一般树和二叉树的二叉链表存储结构比较 一般树是无序树，树中结点的各孩子的次序是无关紧要的；二叉树中结点的左、右孩子结点是有区别的。为避免发生混淆，我们约定树中每一个结点的孩子结点按从左到右的次序排列。如图6-19所示为一棵一般树。

A B C K J F E D M L G H I 图6-19 一般树 根结点A有B、C、D三个孩子，可以认为结点B为A的长子，结点C为B的次弟，结点D为C的次弟。

图6-20为一般树和二叉树的二叉链表存储结构示意图 长子地址 结点信息 次弟地址 左子树地址 结点信息 右子树地址 (a) 一般树双链表存储结构 (b) 二叉树双链表存储结构 图6-20 2．将一棵树转换为二叉树的方法： 只要把一般树的长子作为其父结点的左子树；把一般树的次弟作为其兄结点的右子树，即可以把一棵一般树转换为一棵二叉树。

整个转换可以分为三步： （1）连线——链接树中所有相邻的亲兄弟之间连线。 （2）删线——保留父结点与长子的连线，打断父结点与非长子结点之间的连线。 （3）旋转——以根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次分明。 可以证明，树作这样的转换所构成的二叉树是唯一的。图6-21 (a)、(b)、(C)给出了图6-19所示的一般树转换为二叉树的转换过程。

A B C K J F E D M L G H I 图6-21(a) 链接相邻亲兄弟结点

A B C K J F E D M L G H I 图 6-21 (b) 删去与非长子结点的链接

图6-21(c) 将兄弟结点顺时针旋转后得到的二叉树 A B C K J F E D M L G H I 1 2 3 4 5 6 7 图6-21(c) 将兄弟结点顺时针旋转后得到的二叉树

结 论： （1）在转换产生的二叉树中，左分支上的各结点在原来的树中是父子关系；而右分支上的各结点在原来的树中是兄弟关系。 结 论： （1）在转换产生的二叉树中，左分支上的各结点在原来的树中是父子关系；而右分支上的各结点在原来的树中是兄弟关系。 （2）由于树的根结点无兄弟，所以转换后的二叉树的根结点必定无右子树。 （3）一棵树采用长子、兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的。 （4）一般树转换为二叉树以后，将使树的深度增加。如图6-19的树深度为4，转换为二叉树以后，深度就变成7了，见图6-21（c）。

（1）将森林中的每一棵树转换成相应的二叉树。 6-4-2 森林转换为二叉树 森林是若干棵树的集合。只要将森林中的每一棵树的根视为兄弟，而每一棵树又可以用二叉树表示，这样，森林也同样可以用二叉树来表示了。 森林转换为二叉树的方法如下： （1）将森林中的每一棵树转换成相应的二叉树。 （2）第一棵二叉树保持不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右子树，直到把最后一棵二叉树的根结点作为其前一棵二叉树的右子树为止。 

【例6-5】将图6-22给出的森林转换为二叉树。 A B C K J F E D L G H I 图6-22(a) 森林

6-4-3 二叉树转换为树和森林 A C B G D E H I K F L J 6-4-3 二叉树转换为树和森林 树转换为二叉树以后，其根结点必定无右子树；而森林转换为二叉树以后，其根结点有右分支。显然这一转换过程是可逆的，即可以依据二叉树的根结点有无右子树，将一棵二叉树还原为树或森林。

（1）若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子，直到最后一个右孩子都与该结点的父结点连起来；   二叉树转换为树或森林的方法： （1）若某结点是其父结点的左孩子，则把该结点的右孩子、右孩子的右孩子，直到最后一个右孩子都与该结点的父结点连起来； （2）删掉原二叉树中所有的父结点与右孩子结点的连线； （3）整理（1）、（2）的结果，使之层次分明，显示出树或森林的形状。 A B C J F E D G H I 图6-23(a) 二叉树

A B C J F E D G H I (b) 加连线 (c) 删除父结点与右孩子的连线  图6-23 二叉树还原深林的过程

A B C J F E D G H I (d) 还原后的森林  图6-23 二叉树还原深林的过程

【例6-6】将图6-24(a)给出的二叉树转换为一般树 B C F E D G H I (a) 二叉树 (b) 加连线 (c)删除父结点与右孩子的连线 图6-24 二叉树转换为树的过程

A B C F E D G H I 图6-24(d) 还原后的二叉树 返 回

6-5 二叉树的应用 6-5-1 二叉树的基本应用 1．统计二叉树叶子结点数 （1）基本思想： 若二叉树结点的左子树和右子树都为空，则该结 6-5 二叉树的应用 6-5-1 二叉树的基本应用 1．统计二叉树叶子结点数 （1）基本思想： 若二叉树结点的左子树和右子树都为空，则该结 点为叶子结点，count+1； 递归统计T的左子树叶结点数； 递归统计T的右子树叶结点数。

（2）算法 void Leafnum(BT *T) // 求二叉树叶结点数 {if(T) // 若树不为空 { // 开始时，BT为根结点所在链结点的指针，返回值为BT的叶子数 if(T->lchild==NULL && T->rchild==NULL) // 若左子树和右子树都为空 count++; // 统计叶结点个数变量count（初值为0）加1 Leafnum(T->lchild); // 递归统计T的左子树叶结点数 Leafnum(T->rchild); // 递归统计T的右子树叶结点数 }

2．求二叉树结点总数 （1）基本思想： 若二叉树根结点不为空，则计数器count加1； 递归统计T的左子树结点数； （2）算法： void Nodenum(BT *T) // 求二叉树总结点数 { if(T) // 如果二叉树不空 { count++; // 结点个数+1(count初值为0) Nodenum(T->lchild); // 递归统计T的左子树结点数 Nodenum(T->rchild); // 递归统计T的右子树结点数 }

3．求二叉树的深度 （1）基本思想： 若二叉树为空，则返回0，否则 递归统计左子树的深度； 递归统计右子树的深度； 递归结束，返回其中大的一个，即是二叉树 的深度。

（2）算法： int TreeDepth(BT *T) // 求二叉树深度 {int ldep,rdep; // 定义两个整型变量，存放左、右子树的深度 if(T= =NULL) // 若树空则返回0 return 0; else {ldep=TreeDepth(T->lchild);// 递归统计左子树深度 rdep=TreeDepth(T->rchild);// 递归统计右子树深度 if(ldep>rdep) return ldep+1; // 左子树深度加1 return rdep+1; // 否则返回右子树深度加1 }

4．查找数据元素 在bt为根结点指针的二叉树中查找数据元素x。查找成功时返回该结点的指针；查找失败时返回空指针。 （1）基本思想： 先判别二叉树的根结点是否与x相等，若相等则返回，否则： 递归在bt->lchild为根结点指针的二叉树中查找数据元素x； 递归在bt->rchild为根结点指针的二叉树中查找数据元素x。

（2）算法 BiTree Search（BiTree bt，elemtype x） { BiTree p; if (bt->data= =x) return bt; // 若查找根结点成功，即返回。否则，分别在左、右子树查找 if (bt->lchild!=NULL) return (Search (bt->lchild,x)); // 在bt->lchild为根结点指针的二叉树中查找数据元素x if (bt->rchild!=NULL) return (Search (bt->rchild,x)); // 在bt->rchild为根结点指针的二叉树中查找数据元素x return NULL; // 查找失败返回 }

6-5-2 标识符树与表达 将算术表达式用二叉树来表示，称为标识符树，也称为二叉表示树。 标识符树的特点： （1）运算对象（标识符）都是叶结点； （2）运算符都是根结点。 2．从表达式产生标识符树的方法： （1）读入表达式的一部分产生相应二叉树后，再读入运算符时，运算符与二叉树根结点的运算符比较优先级的高低： 读入优先级高于根结点的优先级，则读入的运算符作为根的右子树，原来二叉树的右子树，成为读入运算符的左子树； 读入优先级不高（等于或低于根结点的优先级），则读入运算符作为树根，而原来二叉树作为它的左子树；

* 3. 应用举例 （2）遇到括号，先使括号内的表达式产生一棵二叉树，再把它的根结点连到前面已产生的二叉树根结点的右子树上去； （3） 单目运算符+、- ，加运算对象θ（表示0）。 例如：-A ，表示为：θ- A 3. 应用举例 【例6-7】画出表达式：A*B*C的标识符树，并求它的前序序列和后序序列。 * C B A 前序序列： * * A B C   后序序列： A B * C *

* * 【例6-8】画出表达式：A*（B*C）的标识符树，并求它的前序序列和后序序列。 前序序列： * A * B C

【例6-9】 画出表达式：-A+B-C+D 的标识符树，并求它的前序序列和后序序列。 θ C B A 前序序列：+ – + –θA B C D 后序序列：θA – B + C – D +

前序序列：/ + A–B C * + D E–+ F G H - C B + D E * F H G 前序序列：/ + A–B C * + D E–+ F G H 后序序列：A B C–+ D E + F G + H–* / 返 回

6-6 哈夫曼树极其应用 6-6-1 哈夫曼树的引入 1．几个术语 哈夫曼（Haffman）树，也称最优二叉树。 6-6 哈夫曼树极其应用 哈夫曼（Haffman）树，也称最优二叉树。 6-6-1 哈夫曼树的引入 1．几个术语 （1）路径长度——从树中的一个结点到另一个结点之间的分支构成两个结点间的路径，路径上的分支数目，称作路径长度。 （2）树的路径长度——从树根到每个结点的路径长度之和称为树的路径长度。 （3）结点的带权路径长度——从该结点到树根之间路径长度与该结点上权的乘积。 （4）树的带权路径长度——树中所有叶子结点的带权路径长度之和，称为树的带权路径长度。 （5）最优二叉树——带权路径长度最小的二叉树，称为最优二叉树。

2．如何求树的带权路径长度？ 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度（WPL），记为：   其中： Wk——为第k个叶结点的权值； L k ——为第k个叶结点到根结点的路径长度。 【例6-11】 设给定权值分别为2，3，5，9的四个结点，图6-26构造了5个形状不同的二叉树。请分别计算它们的带权路径长度。

图6-25

五棵树的带权路径长度分别为： （a）WPL＝2×2＋3×2＋5×2＋9×2＝38 （b）WPL＝2×3＋3×3＋5×2＋9×1＝34 （c）WPL＝2×2＋3×3＋5×3＋9×1＝37 （d）WPL＝9×3＋5×3＋3×2＋2×1＝50 （e）WPL＝2×1＋3×3＋5×3＋9×2＝44 五个图的叶结点具有相同权值，由于其构成的二叉树形态不同，则它们的带权路径长度也各不相同。其中以图(b)的带权路径长度最小，它的特点是权值越大的叶结点越靠近根结点，而权值越小的叶结点则远离根结点，事实上它就是一棵最优二叉树。由于构成最优二叉树的方法是由D · Haffman 最早提出的，所以又称为哈夫曼树。

3．为什么要使用哈夫曼树 if (n<60) b=”E”; else if (n<70) b=”D” 在分析一些决策判定问题的时候，利用哈夫曼树，可以获得最佳的决策算法。 例如，要编制一个将百分制数（n）转换为五级分制的程序。这是一个十分简单的程序，只要用简单的条件选择语句即可完成。如： if (n<60) b=”E”; else if (n<70) b=”D” else if (n<80) b=”C” else if (n<90) b=”B” else b=”A”;

上述判定过程可以用图6-26（a）的判定树来表示

表6-1：学生成绩分布表 分数 n 0~59 60~69 70~79 80~89 90~100 比例数 5% 15% 40% 30% 10% 等级 b E D C B A 图6-26(b)

如果以百分比值5、15、40、30、10为权构造一棵有五个叶子结点构成的哈夫曼树，则可得到图6-26（b）所示的判定树，它使大部分数据经过较少的比较次数，就能得到换算结果。由于每个判定框都有两次比较，将这两次比较分开，就可以得到如图6-26 (c)所示的判定树，按此判定树编写出的程序，将大大减少比较的次数，从而提高运算的速度。 图6-26(c)

6-6-2 哈夫曼树的建立 1．哈夫曼树构成的基本思想是： （1）由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合: F＝{T1，T2，…，Tn}； （2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和； （3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中； （4）重复（2）、（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。

5 【例6-11】的叶结点权值：2，3，5，9为例，介绍哈夫曼树的构造过程： 19 10 9 10 5 5 2 3 2 3 2 3 (a) 权值之和为5 (b) 其权值之和为10 (c) 其权值之和为19 图6-27 哈夫曼树建立过程 带权路径长度为： WPL=9*1+5*2+3*3+2*3=34 对于同一组给定叶结点权值所构造的哈夫曼树，树的形状可能不同，但其带权路径长度值是相同的，而且必定是最小的。

【例6-12】设结点的权集W ={10，12，4，7，5，18，2}，建立一棵哈夫曼树，并求出其带权路径长度。

图6-28 哈夫曼树建立过程 2．哈夫曼树的构造算法（了解）

6-6-3 哈夫曼编码 1．什么是哈夫编码？ 在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制代码，称之为编码。 如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。哈夫曼编码是一种用于构造使电文的编码总长最短的编码方案。 2．求哈夫曼编码的方法 （1）构造哈夫曼树 设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树。

【例6-13】设有A，B，C，D，E，F 6个数据项，其出现的频度分别为6、5、4、3、2、1，构造一棵哈夫曼树，并确定它们的哈夫曼编码。 图6-29 构造哈夫曼树到哈夫曼编码的过程

（2）在哈夫曼树上求叶结点的编码。 规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，如图6-29（b）编码为： A=11；B=01；C=00；D=100；E=1011；F=1010。 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长。采用哈夫曼树构造的编码是一种能使电文代码总长为最短的、不等长编码。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。

*3．哈夫曼树及哈夫曼编码的程序： 小 结 #include <stdio.h> #define MAXLEN 100 typedef struct // 定义结构体 {int weight; // 定义一个整型权值变量 int lchild,rchild,parent; // 定义左、右孩子及双亲指针 }HTNode; typedef HTNode HFMT [MAXLEN]; // 是向量类型的 int n; void InitHFMT (HFMT T) // 初始化 {int i; printf ("\n\t\t请输入共有多少个权值 (小于100)："); scanf ("%d",&n);getchar(); for (i=0; i<2*n-1; i++) {T[i].weight=0; T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; } } 小 结

void InputWeight(HFMT T) // 输入权值 {int w; int i; for (i=0; i<n;i++) {printf ("\n\t\t输入第%d个权值:",i+1); scanf ("%d",&w);getchar(); T[i].weight=w; } } void SelectMin (HFMT T, int i, int *p1,int *p2) // 选择两个结点中小的结点 {long min1=999999; // 预设两个值，并使它大于可能出现的最大权值 long min2=999999; int j; for (j=0;j<=i;j++)

{if (T[j].parent==-1) {if (min1>T[j].weight) {min1=T[j].weight; // 找出最小的权值 *p1=j; // 通过*p1带回序号 } for (j=0;j<=i;j++) {if (min2>T[j].weight&&j!=(*p1)) {min2=T[j].weight; // 找出次最小的权值 *p2=j; // 通过*p2带回序号 } // 选择结束

void CreatHFMT (HFMT T) // 构造哈夫曼树，T[2*n-1]为其根结点 {int i,p1,p2; InitHFMT (T); InputWeight (T); for (i=n;i<2*n-1;i++) { SelectMin (T,i-1,&p1,&p2); T[p1].parent=T[p2].parent=i; T[i].lchild=T[p1].weight; T[i].rchild=T[p2].weight; T[i].weight=T[p1].weight+T[p2].weight; }

 void PrintHFMT (HFMT T) // 输出向量状态表 {int i,k=0; for (i=0; i<2*n-1; i++) while (T[i].lchild!= -1) { if (!(k%2)) printf ("\n"); printf("\t\t(%d%d),(%d%d)",T[i].weight, T[i].lchild,T[i].weight,T[i].rchild); k++;break; }  

void hfnode (HFMT T,int i,int j) {j=T[i].parent; if (T[j].rchild= =T[i].weight) printf("1"); else printf("0"); if(T[j].parent!= -1) i=j,hfnode (T,i,j); } void huffmannode (HFMT T) // 求哈夫曼编码 { int i,j,a,k=0; printf ("\n"); for (i=0;i<n;i++) { j=0; a=i; if (!(k%2)) printf ("\n"); printf("\t\t%i: ",T[i].weight);k++; hfnode(T,i,j); i=a; }

void main() // 主函数 { HFMT HT; CreatHFMT(HT); PrintHFMT(HT); huffmannode(HT); printf("\n"); }

小 结 （1）树是一种以分支关系定义的层次结构，除根结点无直接前趋，其余每个结点有且仅有一个直接前趋，但树中所有结点都可以有多个直接后继。树是一种具有一对多关系的非线性数据结构。 （2）一棵非空的二叉树，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。它的左、右子树又分别都是二叉树。二叉树是本章的重点，必须重点掌握。 （3）若所有分支结点都存在左子树和右子树，且所有叶子结点都在同一层上，这样的一棵二叉树就是满二叉树。若除最后一层外，若其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点，则称此二叉树为完全二叉树。要求熟悉二叉树、满二叉树和完全二叉树之间的一些基本性质。

（4）二叉树的遍历是指按某种顺序访问二叉树中的所有结点，使得每个结点都被访问，且仅被访问一次。通过一次遍历，使二叉树中结点的非线性排列转变线性排列。要求熟练掌握二叉树的前根遍历、中根遍历、后根遍历和层次遍历的概念和算法。 （5）二叉树具有顺序存储和链式存储两种存储结构。在顺序存储时，若采用一维数组则必须按完全二叉树格式存储；在二叉链式存储时，每个结点有两个指针域，具有n个结点的二叉树共有2n个指针，其中指向左、右孩子的指针有n-1个，空指针有n+1个。 （6）利用二叉树n+1个空指针来指示某种遍历次序下的直接前趋和直接结后继，这就是二叉树的线索化。 （7）一般树的存储比较麻烦，但只要将一般树转换为二叉树存储就比较方便了。要求掌握一般树转换为二叉树的方法。

（8）用二叉树表示图形数据结构时，如果去掉结点的指针项，只按结点的中序序列存储，并给出这棵树的前序（或后序）“序表”；图形调入内存时，由中序的结点表及前序（或后序）“序表”来恢复二叉树，是数据结构中的一种重要应用。 （9）将算术表达式用二叉树来表示称为标识符树，也称为二叉表示树，利用表识符树的后序遍历可以得到算术表达式的后缀表达式，是二叉树的一种应用。 （10）带权路径长度最小的二叉树称为哈夫曼树，要求能按给出的结点权值的集合，构造哈夫曼树，并求带权路径长度。在程序设计中，对于多分支的判别（各分支出现的频度不同），利用哈夫曼树可以提高程序执行的效率，必须予以重点掌握。哈夫曼编码在通信中有着广泛的应用，应该有一定的了解。

实验6 树子系统 1．实验目的 2．实验内容 （1）掌握二叉树的特点及其存储的方式。 （2）掌握二叉树的创建和显示方法。 实验6 树子系统 1．实验目的 （1）掌握二叉树的特点及其存储的方式。 （2）掌握二叉树的创建和显示方法。 （3）复习二叉树遍历的概念，掌握二叉树遍历的基本方法 （4）掌握求二叉树的叶结点数、总结点数和深度等基本算法。 2．实验内容 （1）按屏幕提示用前序方法建立一棵二叉树，并能按凹入法显示二叉树结构； （2）编写前序遍历、中序遍历、后序遍历、层次遍历程序。 （3）编写求二叉树的叶结点数、总结点数和深度的程序。 （4）设计一个选择式菜单，以菜单方式选择下列操作。

二 叉 树 子 系 统 ******************************************** * 1---------建 二 叉 树 * * 2---------凹 入 显 示 * * 3---------先 序 遍 历 * * 4---------中 序 遍 历 * * 5---------后 序 遍 历 * * 6---------层 次 遍 历 * * 7---------求 叶 子 数 * * 8---------求 结 点 数 * * 9---------求 树 深 度 * * 0---------返 回 * 请选择菜单号:

3. 实验步骤： （1） 输入并调试程序； （2） 按下图建立二叉树； A E D C B F

请输入按先序建立二叉树的结点序列： （‘0’代表后继结点为空,请逐个输入,按回车输入下一结点） 请输入根结点：A<CR> 请输入A结点的左子结点：B<CR> 请输入B结点的左子结点：D<CR> 请输入D结点的左子结点：0<CR> 请输入D结点的右子结点：0<CR> 请输入B结点的右子结点：0<CR> 请输入A结点的右子结点：C<CR> 请输入C结点的左子结点：E<CR> 请输入E结点的左子结点：0<CR> 请输入E结点的右子结点：0<CR> 请输入C结点的右子结点：F<CR> 请输入F结点的左子结点：0<CR> 请输入F结点的右子结点：0<CR>

（3）凹入法显示树的结构： A▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ B▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ D▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ C▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ E▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ F▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃▃ （4）进行程序的其它调试。

习题6 参考习题解答 返 回