[理学]第6章树

1、第六章 树树形结构是一种日常生活中应用非常广泛的非线性结构。算机领域中的操作系统、 数据库系统都是树状结构的应用实例，是利用树状结构的原理设计的。从单位的组织结构、 家谱到计甚至某些数据库管理系统就6.1 树简介什么是树结构？先看一下它的定义：树（ Tree）是一种特殊的数据结构，它可以用来描 述有分支的结构，是由一个或一个以上的结点所组成的有限集合，具有下列性质：存在一个特殊的结点，称为根（ Root）。其余结点为 n0 个互斥的集合，即 T1， T2， T3， Tn，且每个集合称为子树。如下图所示， A 为根结点， B 、 C 、 D 、 E 均为 A 的子结点。比较下面的两个图形图(a)

2、是一种合法的树，符合树的定义：树由一个或一个以上的结点组成，结点间有连接且不形成回路。图 (b)中结点有连接但却形成了回路，故不是一棵合法的树。接下来了解一下树的专有名词，以下图为例进行说明。树根或根结点（ Root）：没有父结点的结点称为根结点，如 A 。父结点 （Parend）： 每一个结点的上层结点称为其父结点， 如 B 的父结点为A， G 的父结点为 C。子结点（ Children）：每一个结点的下层结点称为其子结点，如为 E 及 F， A 的子结点为 B 、 C、 D 。兄弟结点（ Siblings）：有共同父结点的结点称为兄弟结点，如B 的子结点B 、C 、 D 的父结点都是 A

3、，所以彼此为兄弟结点。结点的度（ Degree）：子结点的个数为该结点的度，如 A 的度为 3， B 的度为 2 。叶子结点 （Terminal Node）： 没有子结点的结点， 即度为零的结点， 例如 E、 F、 G、 H 、 D 都是叶子结点。非叶子结点（Non-Terminal Node)：叶子结点以外的所有结点为非叶子结点， 即度不为零的点，如 A 、 B 、 C 都是非叶子结点。边（Edge）：连接两个结点的线段，称之为边。上图中的边共有 7 条，一般地，具有 n个结点的树，其边数为 n-1。层（ Level）：树的层，即树根 A 为层 1， B 、 C 、 D 为层 2， E、 F

4、、 G、 H为层 3。高度（ Height）：树的最大层数。森林（ Forest）：森林是由 n棵互斥的树组成的集合（ n0）。【范例 1】下列哪一种结构不是树（A. 一个结点C. 一个没有回路的连通图Tree）。B. 环形序列D. 一个边数比结点数少 1 的连通图解答：选择 B ，因为环形序列会形成循环回路现象，不符合树的定义。【范例 2】下图中的树（ Tree）中有几个叶子结点？A. 4 B. 5 C. 9 D. 11解答：由上图可以看出答案为 A ，共有 E 、 C 、 H 、 I 共 4 个叶子结点。6.2 二叉树简介一般的树状结构在内存中的存储方式以链表为主， 对于 n 叉树来说，

5、每个结点的度不一定相同，但为了方便起见，必须取 n+1 为链表结点的最长固定长度，其数据结构如下：data link1 link2 linkn假设 n 叉树有 m 个结点，那么此树共需要 (n+1) m 个存储单元。而每个结点不一定都会指向下一层的 n 个结点，会有大量的空值， 如此一来，会造成大量的内存空间浪费， 为了克服这一缺点，常使用二叉树结构来取代树状结构。6.2.1 二叉树的定义二叉树是由有限个结点组成的集合， 此集合可以为空集合， 也可由一个树根或者一个树根与左右两棵子树所组成。简单的说，二叉树最多只能有两个子结点，即结点的度小于等于 2，其数据结构如下：left data rig

6、ht二叉树和一般树的不同点如下：树不可为空集合，但是二叉树可以。树的度 d0，但二叉树的结点度 0d2。树的子树间没有次序关系，但二叉树有次序关系。1h6.2.2 特殊二叉树的介绍1. 满二叉树如果二叉树高度为 n，树的结点为 2 n - 1，则称此树为满二叉树，如下图所示。2. 完全二叉树如果二叉树的高度为 n，则 1 n-1 层都是满的，第 n 层的叶子结点严格按从左至右依次排列，则称此二叉树为完全二叉树，如下图所示。【性质 1】假设一棵完全二叉树具有 n个节点，则它的高度（层） h log 2 ( n 1) 。证明：设完全二叉树的高度为 h ，则有2 1 n 2h 1， 2 h 1 n

7、1 2h， h 1 log 2 ( n 1) h故 h log 2 ( n 1) 。3. 严格二叉树如果二叉树的每个非叶子结点都有非空的左、 右子树， 则称此二叉树为严格二叉树， 如下图所示。4. 歪斜树当一个二叉树完全没有右结点或左结点时，称为左歪斜树或右歪斜树，如下图所示。5. 排序二叉树设结点由关键字值来表示，用所有结点的关键字值互异，排序二叉树或者是一棵空树，或者是满足以下条件的树：（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（3）左、右子树也分别是二叉排序树。创建这种二叉树是最为方便的

8、， 它的中序遍历是关键字值的升序排序， 故而称之为二叉排序树。【性质 2】高度为 h 的二叉树的结点总数 n2 h - 1。证明：其结点总数为各层中度最大的结点数之和，即12ih i1【性质0 1 22 2 2h 1 23】对于非空二叉树 T，如果数是 n2，试证明： n 0=n 2+1 。证明：假设结点总数为 n， n1 是度为 n= n 0+n 1+n 2， e= n-1， e =2n 2+n 1 由上述三个式子，有 n 0=n 2+1 。h2 12 1h2 1n0 为叶子（即度为 0 的结点）结点数，且度为 2 的结点1 的结点数，边数为 e，于是，我们有以下关系式6.3 二叉树的存储方

9、式树状结构在程序中的建立大多使用链表来处理， 因为链表的指针用来处理树是相当方便的， 只需改变指针即可。 当然也可以使用数组这样的连续结构来表示二叉树， 使用数组或者链表各有利弊，下面将给予说明。！6.3.1 二叉树的数组表示法如果用一维数组来存储二叉树， 首先应将二叉树想象成一棵完全二叉树， 凡空值结点均用特殊字符或者数字替代，并且依序将结点值存放到一维数组中。【范例 3】将下图所示的二叉树，用一维字符数组进行表示。首先将二叉树想象成一棵完全二叉树，其空值结点用 * 代替，结束符用！表示。其一维字符数组的表示形式为：索引值内容值1A2B3C4*5*6D7【范例程序】用一维字符数组表示结点值为

10、字符的二叉树。/*名称： ch06_01.cpp示范：用一维字符数组表示结点值为字符的二叉树*/#include#includeusing namespace std;#define MaxSize 100/ 数组的最大维数#define MaxLevel 6/ 设定可输出的二叉树最大层数int NodeNum=0;/ 结点计数变量char NodeMaxSize;/ 字符型的结点数组/创建二叉树的结点数组void CreateTreeArray() cout 按完全二叉树方式输入，若某层有元素为空，用 * 替代，结束用 !替代 NodeNodeNum;/ 输入结点值if(NodeNodeNu

11、m=!)break;if(NodeNum=MaxSize) cout 输入字符个数超限 ,无法存储，请增大 MaxSize 的值endl;exit(0);/输出树void DisplayTree() int i,j,k;/ 循环控制变量int hight,level,SerialNum;/hight 树高， level 树层 ,SerialNum 序号/确定树的高度for(i=0;iNodeNum)break;hight=i;/从第 1 层至第 hight 层进行二叉树的输出level=1;SerialNum=1;while(level=hight)/每层前端空格输出控制for(i=0;ipo

12、w(2,hight-level);i+)cout ;/每层输出的结点个数控制for(j=0;jpow(2,level-1);j+,SerialNum+)if(NodeSerialNum!=*&NodeSerialNum!=!)coutNodeSerialNum;/ 输出元素else if(NodeSerialNum=*)cout ;/ 输出空格elsebreak;/遇到结束符 !,跳出输出for(k=0;kpow(2,hight-level+1)-1;k+)cout ;/ 每层后端空格输出控制coutendl;/ 一层输出完毕 ,换行level+;/ 层数增 1coutendl;/输出数组vo

13、id DisplayArray() int i=1;do coutNodei ;i+;while(Nodei!=!);coutendl;/主函数void main() CreateTreeArray();/ 创建二叉树结点的一维数组cout 二叉树为 endl;DisplayTree();/ 输出树cout 结点数组为 endl;DisplayArray();/ 输出数组system(pause);如果二叉树的结点值是由整数给出的，对它的处理也是类似的。【范例 4】将下图所示的二叉树，用一维整型数组进行表示。首先将二叉树想象成一棵完全二叉树，其空值结点用 0 代替，结束符用 -1 表示。14-

14、1其一维整型数组的表示形式为：索引值 1 2 3 4 5 6 7 8 9 10 11 12 13内容值 6 3 9 2 5 7 0 0 0 4 0 0 8仅需要对上述示范程序作几处简单的修改，就可以用于解决上述问题的编程。【范例程序】用一维整型数组表示结点值为整数的二叉树。/*名称： ch06_02.cpp示范：用一维整型数组表示结点值为整数的二叉树*/#include#includeusing namespace std;#define MaxSize 100/ 数组的最大维数#define MaxLevel 6/ 设定可输出的二叉树最大层数int NodeNum=0;/ 结点计数变量int

15、 NodeMaxSize;/ 整型结点数组/创建二叉树的结点数组void CreateTreeArray()cout 按完全二叉树方式输入，若某层有元素为空，用 0 替代，结束用 -1 替代 endl;Node0=0;/ 使 Node0 闲置while(1) NodeNum+;cout 请输入第 NodeNumNodeNodeNum;/ 输入结点值if(NodeNodeNum=-1)break;if(NodeNum=MaxSize) cout 输入字符个数超限 ,无法存储，请增大 MaxSize 的值endl;exit(0);/输出树void DisplayTree() int i,j,k;/

16、 循环控制变量int hight,level,SerialNum;/hight 树高， level 树层 ,SerialNum 序号/确定树的高度for(i=0;iNodeNum)break;hight=i;/从第 1 层至第 hight 层进行二叉树的输出level=1;SerialNum=1;while(level=hight)/每层前端空格输出控制for(i=0;ipow(2,hight-level);i+)cout ;/每层输出的结点个数控制for(j=0;jpow(2,level-1);j+,SerialNum+)if(NodeSerialNum!=0 & NodeSerialNum

17、!=-1)coutNodeSerialNum;/ 输出元素else if(NodeSerialNum=0)cout ;/ 输出空格elsebreak;/遇到结束符 -1,跳出输出for(k=0;kpow(2,hight-level+1)-1;k+)cout ;/ 每层后端空格输出控制coutendl;/ 一层输出完毕 ,换行level+;/ 层数增 1coutendl;/输出数组void DisplayArray()int i=1;do coutNodei ;i+;while(Nodei!=-1);coutendl;/主函数void main() CreateTreeArray();/ 创建二

18、叉树结点的一维数组cout 二叉树为 endl;DisplayTree();/ 输出树cout 结点数组为 endl;DisplayArray();/ 输出数组system(pause);用一维数组表示二叉树， 这一方法的优点是： 方法直观且容易实现， 而且形象地输出二叉树的实际结构。其缺点是：访问、插入、删除操作难以实现，特别是当二叉树不是完全二叉树时，会占用过多的内存空间。例如， 存储以下含 4 结点的二叉树， 却要多花费了 8 个存储单元，才能完整地表现这一结构。6.3.2 二叉树的链表表示法二叉树的链表表示法是利用链表来存储二叉树，立二叉树。其结点结构如下：*left data二叉树的

19、结点定义如下：struct BinTreeNode char data;struct BinTreeNode *left,*right;【范例 5】对下图所示的二叉树即运用动态存储结构和指针的方式来建*right用链表来表示它，其结构图如下：构建过程如下：（1）先将倒数第一层的三个结点建子二叉树，并用相应的结点指针指向其根结点。（2）再将二层的两个结点建子二叉树，并用相应的结点指针指向其根结点。（3）最后将第一层的一个结点建子二叉树，并用一个结点指针指向其根结点。上述子二叉树经过连接之后， 便成了我们所需要构建的二叉树。 这种建二叉树的过程是， 由叶子结点开始，向上逐层扩建成树。【范例程序】用

20、链表来表示二叉树。/*名称： ch06_03.cpp示范：二叉树的链表表示法*/#includeusing namespace std;/二叉树结点定义struct BinTreeNode;char data;/结点数据struct BinTreeNode *left,*right;/ 左、右指针/建二叉树BinTreeNode *MakeBinTree(char data,BinTreeNode *left,BinTreeNode *right)/ 以 data 为数据 ,left,right 为左右子树建树BinTreeNode *newnode;newnode=new BinTreeNo

21、de;newnode-data=data;newnode-left=left;newnode-right=right;return newnode;/主函数void main() BinTreeNode *aptr,*bptr,*cptr,*dptr,*eptr,*fptr;dptr=MakeBinTree(D,NULL,NULL);eptr=MakeBinTree(E,NULL,NULL);fptr=MakeBinTree(F,NULL,NULL);bptr=MakeBinTree(B,dptr,eptr); cptr=MakeBinTree(C,NULL,fptr); aptr=MakeB

22、inTree(A,bptr,cptr); system(pause);从上述创建链式二叉树的程序可以发现， 其程序控制， 而且还无法输出它的实际结构，这种结构在程序实现上十分复杂， 不便于实现也无法查找结点的父结点。 但这种结构也有其优点： 那就是查找、 插入和删除操作方便。二叉树结点值的输出需要用它二叉树的遍历，在下一节进行介绍。6.4 二叉树的遍历遍历二叉树最简单的方法就是遍历树中所有结点各一次， 并且在遍历后将树的数据转化为线性关系。 其实二叉树的遍历， 并不像之前所提到的线性结构那样简单， 就一个简单二叉树结点而言，每个结点都可以区分左、右两个分支。如下图所示的二叉树共有 ABC 、

23、ACB 、 BAC 、 BCA 、 CAB 、 CBA 等 6 种遍历方式。如果是依照二叉树特性一律由左向右遍历，那么只剩下三种遍历方式，即 BAC 、 ABC 、 BCA 。以上三种遍历的方式的命名如下。中序遍历（ BAC， Preorder）：左子树 -树根 -右子树。前序遍历（ ABC， Inorder）：树根 -左子树 -右子树。后序遍历（ BCA， Postorder）：左子树 -右子树 -树根。所谓的中序、前序、 后序都是针对根结点而言的， 例如中序遍历是根结点在中间， 前序遍历是根结点在前面，后序遍历是根结点在后面。而遍历方式一定是先左子树后右子树。6.4.1 中序遍历中序遍历的

24、顺序为：左子树 -树根 -右子树，即沿树的左子树一直往下，直到无法前进时退后到父结点， 而后再往右子树一直往下。 如果右子树也走完了就退回上层的左结点， 重复左、中、右的顺序遍历，下图是【范例 5】中所给出的二叉树，它的中序遍历为： DBEACF 。中序遍历的递归（回溯）算法如下：void Inorder(BinTreeNode *ptr)if(ptr!=NULL) Inorder(ptr-left); / 遍历左子树coutdata; / 访问树根Inorder(ptr-right);/ 遍历右子树6.4.2 前序遍历前序遍历的顺序为：树根 - 左子树 -右子树，即从根结点开始处理，根结点处

25、理完后往左子树走，直到无法前进再处理右子树。 【范例 5】的前序遍历为 ABDECF 。前序遍历的递归（回溯）算法如下：void Preorder(BinTreeNode *ptr)if(ptr!=NULL) coutdata; / 访问树根Preorder(ptr-left);/ 遍历左子树Preorder(ptr-right); / 遍历右子树6.4.3 后序遍历后序遍历的顺序为：左子树 - 右子树 -树根。后序遍历和前序遍历相反，它是把左、右子树的结点都处理完才处理树根。 【范例 5】的后序遍历为： DEBFCA 。后序遍历的递归（回溯）算法如下：void Postorder(BinTr

26、eeNode *ptr)if(ptr!=NULL) Postorder(ptr-left);/ 遍历左子树Postorder(ptr-right); / 遍历右子树coutdata; / 访问树根6.4.4 二叉树的遍历实例对【范例 5】中二叉树，进行中序、前序与后序遍历的操作。并将其结果输出，请与上 面的讨论加以对照。【范例程序】对【范例 5】中的二叉树进行中序、前序与后序遍历，并输出其结果。/*名称： ch06_04.cpp示范：二叉树的中序、前序、后序遍历*/#includeusing namespace std;/二叉树结点定义struct BinTreeNode char data;

27、/结点数据struct BinTreeNode *left,*right;/ 左、右指针;/建二叉树BinTreeNode *MakeBinTree(char data,BinTreeNode *left,BinTreeNode *right)/ 以 data 为数据 ,left,right 为左右子树建树BinTreeNode *newnode;newnode=new BinTreeNode;newnode-data=data;newnode-left=left;newnode-right=right;return newnode;/中序遍历void Inorder(BinTreeNode

28、*ptr)if(ptr!=NULL) Inorder(ptr-left); / 遍历左子树coutdata; / 访问树根Inorder(ptr-right);/ 遍历右子树/前序遍历void Preorder(BinTreeNode *ptr)if(ptr!=NULL) coutdata; / 访问树根Preorder(ptr-left);/ 遍历左子树Preorder(ptr-right); / 遍历右子树/后序遍历void Postorder(BinTreeNode *ptr)if(ptr!=NULL) Postorder(ptr-left);/ 遍历左子树Postorder(ptr-r

29、ight); / 遍历右子树coutdata; / 访问树根/主函数void main()BinTreeNode *aptr,*bptr,*cptr,*dptr,*eptr,*fptr;dptr=MakeBinTree(D,NULL,NULL);eptr=MakeBinTree(E,NULL,NULL);fptr=MakeBinTree(F,NULL,NULL);bptr=MakeBinTree(B,dptr,eptr);cptr=MakeBinTree(C,NULL,fptr);aptr=MakeBinTree(A,bptr,cptr);/aptr 成为二叉树的根结点指针cout 中序遍历为

30、 :endl;Inorder(aptr);coutendl;cout 前序遍历为 :endl;Preorder(aptr);coutendl;cout 后序遍历为 :endl;Postorder(aptr);coutendl;system(pause);（对于一维数组所表示的二叉树如何建立它的中序、 前序、 后序遍历函数， 请参见实验教程。另外，二叉树的插入与删除操作也较复杂，请参考相关资料。 ）【范例 6】利用后序遍历法，给出下图的遍历结果。解答：后序遍历的顺序为：左子树 -右子树 -树根，可得 DBHEGIFCA 。【范例 7】给出下图所示的二叉树的中序、前序及后序表示法。解答：中序： F

31、DHGIBEAC前序： ABDFGHIEC后序： FHIGDEBCA6.4.5 二元运算树一般的算术运算可以转换成二元运算树，其创建的方法如下：考虑算术式中运算符的结合性与优先权后先适当加上括号。由最内层的括号逐步向外， 利用运算符当树根， 左边的运算对象当左子树，右边的运算对象当右子树，其中优先权最低的运算符作为此二元运算树的树根。下面，以算术表达式“ A-B*(-C+-3.5)原表达式一目运算符负号具有最高优先级 乘法运算符具有次高优先级减法运算符具有最低优先级”为例，介绍这一问题的处理方法。A-B*(-C+-3.5)A-B*(-C)+(-3.5)A-(B*(-C)+(-3.5)(A-(B

32、*(-C)+(-3.5)构造二元运算树的过程如下图所示：前序表示式为 -A*B+-C-3.5 ，后序表示式为 ABC-3.5-+*- 。6.5 排序二叉树设结点由关键字值来表示，且所有结点的关键字值互异，排序二叉树或者是一棵空树，或者是满足以下条件的树：（1）若左子树不空，则左子树上所有结点的关键字值均小于根结点的关键字值；（2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值；（3）左、右子树也分别是二叉排序树。根据排序二叉树的定义，创建排序二叉树的规则如下：第一个输入的数据作为此二叉树的树根。其后的数据与根进行比较，小于树根的放置到左子树，大于树根的放置到右子树。从上面的规

33、则可以知道， 左子树内的值一定小于树根， 右子树的值一定大于树根。 因此，利用中序遍历就可以得到由小到大排好序的数据。【范例 8】利用数据 32 、 25 、 16 、 35 、 27 来建立一棵排序二叉树。创建过程由下图所示：【范例程序】用程序创建排序二叉树。/*名称： ch06_05.cpp示范：排序二叉树的创建*/#includeusing namespace std;#define NodeNum 5/ 结点数struct BinTreeNode/ 二叉树结点定义 int data;/ 结点数据struct BinTreeNode *left,*right;/ 左、右指针;BinTre

34、eNode *rootNode=NULL;/ 排序二叉树的根结点指针/判空int IsEmpty()if(rootNode=NULL)return 1;elsereturn 0;/创建排序二叉树void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新结点newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新结点是否入树标识 ,flag=0 表示未入树if(IsEmpty()/ 空树rootNod

35、e=newnode;else/非空树 ptr=rootNode;/ 探测指针指向根结点while(!flag)/ 当新结点未入树时 /如果新结点关键字值小于其父结点的关键字值if(datadata) / 进入左子树if(ptr-left=NULL)/ 如果左子树为空 ptr-left=newnode;/ 直接作为左子树flag=1;/ 标识符置 1，表示已入树else/如果左子树非空ptr=ptr-left;/ 探测指针向左下移else/如果新结点关键字值大于其父结点的关键字值 /中序遍历/进入右子树if(ptr-right=NULL) ptr-right=newnode;flag=1;els

36、eptr=ptr-right;void Inorder(BinTreeNode *ptr) if(ptr!=NULL)Inorder(ptr-left);/ 遍历左子树coutdataright);/ 遍历右子树/主函数void main() int data;cout请输入二叉树结点的值 endl;for(int i=0;iNodeNum;i+) cout 请输入第 i+1data;CreateSortBinTree(data);/ 创建排序二叉树cout 中序遍历为 :endl;Inorder(rootNode);coutendl;system(pause);排序二叉树的突出优点是： 将结

37、点按关键字值进行了中序排序， 结点按关键字值的插入、查找操作变得极为简单。因此，有时也称排序二叉树为线索二叉树（或二分查找树） 。【范例 9】利用数据 32、 25 、 16 、 35 、 27 先建一棵排序二叉树，并画出该排序二叉树的结 构图。再将数据 33、 40 插入，再画出其结构图。并用程序验证你的结果。解答：由范例 9 可知， 32 、 25 、 16 、 35 、 27 构建的排序二叉树为按照排序二叉树的构建原理， 33 大于根结点的关键字值 32，它向右子树插入，又因右子树结点的关键字值为 35， 33 小于 35，故它成为右子树的左小孩。40 大于 32， 它向右子树插入， 4

38、0 大于 35， 它又要向右插入， 故 40 为结点 35 的右子孩。其排序二叉树为【范例程序】对排序二叉树进行插入操作。/*名称： ch06_06.cpp示范：排序二叉树的插入操作*/#includeusing namespace std;#define NodeNum 5/ 结点数struct BinTreeNode/ 二叉树结点定义 int data;/ 结点数据struct BinTreeNode *left,*right;/ 左、右指针;BinTreeNode *rootNode=NULL;/ 排序二叉树的根结点指针/判空int IsEmpty()if(rootNode=NULL)r

39、eturn 1;elsereturn 0;/创建排序二叉树void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新结点newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新结点是否入树标识 ,flag=0 表示未入树if(IsEmpty()/ 空树rootNode=newnode;else/非空树 ptr=rootNode;/ 探测指针指向根结点while(!flag)/ 当新结点未入树时 /如

40、果新关键字值小于其父结点的关键字值if(datadata) / 进入左子树if(ptr-left=NULL)/ 如果左子树为空 ptr-left=newnode;/ 直接作为左子树flag=1;/ 标识符置 1，表示已入树else/如果左子树非空ptr=ptr-left;/ 探测指针向左下移else/如果新关键字值大于或等于其父结点的关键字值 /进入右子树if(ptr-right=NULL) ptr-right=newnode;flag=1;elseptr=ptr-right;/中序遍历void Inorder(BinTreeNode *ptr) if(ptr!=NULL)Inorder(pt

41、r-left);/ 遍历左子树coutdataright);/ 遍历右子树/主函数void main()int data;cout请输入二叉树结点的值 endl;for(int i=0;iNodeNum;i+) cout 请输入第 i+1data;CreateSortBinTree(data);/ 创建排序二叉树cout 中序遍历为 :endl;Inorder(rootNode);CreateSortBinTree(33);/ 插入 33CreateSortBinTree(40);/ 插入 40coutn 中序遍历为： endl;Inorder(rootNode);coutendl;syste

42、m(pause);【范例程序】对于上例所创建的排序二叉树，编程查找关键字值为 16 、 38，若找到了，显示找到了的信息，否则显示找不到的信息。/*名称 ： ch06_07.cpp示范：利用排序二叉树进行查找操作*/#includeusing namespace std;#define NodeNum 7/ 结点数struct BinTreeNode/ 二叉树结点定义 int data;/ 结点数据struct BinTreeNode *left,*right;/ 左、右指针;BinTreeNode *rootNode=NULL;/ 排序二叉树的根结点指针/判空int IsEmpty()if(

43、rootNode=NULL)return 1;elsereturn 0;/创建排序二叉树void CreateSortBinTree(int data) BinTreeNode *ptr,*newnode;/建立新结点newnode=new BinTreeNode;newnode-data=data;newnode-left=NULL;newnode-right=NULL;int flag=0;/ 新结点是否入树标识 ,flag=0 表示未入树if(IsEmpty()/ 空树rootNode=newnode;else/非空树 ptr=rootNode;/ 探测指针指向根结点while(!fla

44、g)/ 当新结点未入树时 /如果新关键字值小于其父结点的关键字值if(datadata) / 进入左子树if(ptr-left=NULL)/ 如果左子树为空 ptr-left=newnode;/ 直接作为左子树flag=1;/ 标识符置 1，表示已入树else/如果左子树非空ptr=ptr-left;/ 探测指针向左下移else/如果新关键字值大于或等于其父结点的关键字值 /进入右子树if(ptr-right=NULL) ptr-right=newnode;flag=1;elseptr=ptr-right;/中序遍历void Inorder(BinTreeNode *ptr) if(ptr!=

45、NULL)Inorder(ptr-left);/ 遍历左子树coutdataright);/ 遍历右子树/查找关键字值BinTreeNode *Search(BinTreeNode *ptr,int keyVal)while(1) if(ptr=NULL) /没有找到返回 NULLreturn NULL;if(ptr-data=keyVal)/ 结点值等于搜索值return ptr;else if(ptr-datakeyVal)/ 结点值大于搜索值ptr=ptr-left;/ 朝左子树搜索else/结点值小于搜索值ptr=ptr-right;/ 朝右子树搜索/主函数void main() in

46、t data;cout请输入二叉树结点的值 endl;for(int i=0;iNodeNum;i+) cout 请输入第 i+1data;CreateSortBinTree(data);/ 创建排序二叉树cout 中序遍历为 :endl;Inorder(rootNode);while(1) coutdata;if (data=-1)break;else if(Search(rootNode,data)!=NULL)/ 搜索cout 你要找的值 data ，已找到 !endl;elsecout 你要找的值没有找到 !k1=17 ， k0=32k2 ，符合最大堆要求，不作调整。 k3=24k1=

47、17 ，故交换。 k4=35k1=24 ，故交换。 k1=35k0=32 ，故交换。 k5=87k2 ，故交换；而交换之后的 k2=87k0=35 ，故再交换，使它的位置继续上升（这就是上滑法的涵义） 。 k6=65k2=35 ，故交换。 k7=4k3=17 ，而 k8=12k3=17 ，故不交换。调整完毕，业已成为最大堆。此时，关键码集合 K=87,32,65,17,24,16,35,4,12 。【范例程序】给出上述方法的程序演示。/*名称 ： ch06_08.cpp示范：利用上滑法调最大堆*/#include#includeusing namespace std;#define NodeN

48、um 9 / 完全二叉树的结点数/输出void Display(int *data) for(int i=0;iNodeNum;i+)coutsetw(3)datai;cout0) if(temp=dataj)break;/双亲的值大 ,不做交换else datai=dataj;/ 交换i=j;/i 指向交换结点位置j=(i-1)/2;/j 指向双亲datai=temp;/ 原 datastart 归位/创建最大堆void CreateHeap(int *data) int i,j;cout 原始数组 : ;Display(data);for(i=1;iNodeNum;i+)/ 从下标 1 的

49、结点开始 ,采用上滑法调最大堆 SiftUpAdjustHeap(data,i);couti 次调堆 : ;Display(data);/主函数void main() int dataNodeNum=32,17,16,24,35,87,65,4,12;/ 完全二叉树的结点值CreateHeap(data);/将 data 改造成最大堆system(pause);2. 下滑法调最大堆【范例 11】采用上滑法将关键码集合K=32,17,16,24,35,87,65,4,12 调成一个最大堆。（1）将该关键码集合按完全二叉树存储到数组 K ，其对应的结构图是以下二叉树。（2）这并非最大堆，采用下滑调

50、堆算法，可将它调成最大堆，具体步骤如下： 从下标为 NodeNum/2=9/2=4 的结点开始， k4 无子女，不需要调。 再从下标为 3 的结点开始， k3 的值大于其子女的值，也不需要调。 再从下标为 2 的结点开始， k2=16k5=87 ，故交换。 再从下标为 1 的结点开始， k1=17k4=35 ，故交换。 再从下标为 0 的结点开始， k0=32k2 ，故交换。 由于 k2=32k6=65 ，故 k2 的位置继续下滑（这就是下滑法的涵义所在） 交换。 调整完毕，业已成为最大堆。此时， 关键码集合 K=87,35,65,24,17,16,32,4,12 ， 与上滑法做出的最大堆不一

51、样，与 k6 做但仍是最大堆，这表明一棵完全二叉树对应的最大堆是不惟一的。【范例程序】给出下滑法调最大堆的程序演示。/*名称 ： ch06_9.cpp示范：利用下滑法调最大堆*/#include#includeusing namespace std;#define NodeNum 9/ 完全二叉树的结点数/输出void Display(int *data)for(int i=0;iNodeNum;i+)coutdataisetw(4);coutendl;/下滑法调最大堆void SiftDownAdjustHeap(int *data,int start,int end)/ 从下标为 star

52、t 的结点开始 , 到下标为 end的结点为止 , 向下调堆int i,j,temp,flag;i=start;temp=datai;/temp 暂存结点 i 的值j=2*i+1;/j 指向结点 i 的左子女flag=0;/ 假设树根值小 , 需要做交换while(j=end&flag=0) if(jend) if(dataj=dataj)flag=1;/ 若树根较大 ,不做交换else datai=dataj;/ 交换i=j;/i 指向交换结点位置j=2*i+1;/j 指向其左子女datai=temp;/ 结点值归位/创建最大堆void CreateHeap(int *data) int i

53、;cout=0;i-)/ 从完全二叉树的首个非叶子结点开始 ,采用下滑调最大堆 SiftDownAdjustHeap(data,i,NodeNum-1);coutNodeNum/2-i 次调堆 : ;Display(data);/主函数void main()int dataNodeNum=32,17,16,24,35,87,65,4,12;/ 完全二叉树的结点值CreateHeap(data);/将 data 改造成最大堆system(pause);将上滑法、 下滑法调最大堆的程序稍作改动， 可得到调最小堆的程序代码， 这里不作叙述，留作练习。6.7 哈夫曼树在学习本节内容之前，让我们先处理一

54、个实际问题：在某通信系统中，要发送由 A 、 B 、 C 、 D 四个字符组成的信息， A 出现的概率为 0.5，B 出现的概率为 0.25， C 出现的概率为 0.1， D 出现的概率为 0.15。如何对 A 、 B 、 C、 D 四个字符进行编码，能使总的编码长度最短？分析：对于该问题，读者很容易想到用如下表 6.1 所示：表 6.1 等长编码字符ABC2 位等长的二进制数 (0 或 1)。其具体表示方法字符编码000110D 11在 10000 次的通信过程中，通信传输的长度L=( 2 0.5+2 0.25+2 0.1+2 0.15) 10000=20000 个 bit假定按表 6.2

55、编码表 6.2 不等长编码字符 字符编码A 0B 10C 110D 111在 10000 次的通信过程中，通信传输的长度为L=( 1 0.5+2 0.25+3 0.1+3 0.15) 10000=14500 个 bit显然第二种编码方案优于第一种编码方案， 因为通信过程中出现次数较多的字符采用了较短编码，而出现次发数较少的字符则采用较长编码，从而使总的编码长度变短为什么不同的编码方案会出现不同的效果？第二种编码较优的理论根据是什么？它是最好的编码吗？如何编码能够使得存储效率高？在学习哈夫曼树之后， 我们就能够回答这些问题了。首先介绍有关哈夫曼树的基本术语和基本概念。6.7.1 基本术语路径 (

56、path) 从树中一个结点到另一结点之间的分支构成两个结点之间路径。路径长度 (path length) 路径上的分支数目。树的路径长度 (tree path length) 根结点到每个叶子结点的路径长度之和。树的带权路径长度 (weighted path length) 树中所有叶子结点的带权路径长度之和，且记作nWPL wil ii1其中 wi 是第 i 个叶子结点的权值， li 为从根到第 i 个叶子结点的路径长度， n为树的叶子结点的个数。最优二叉树 (Huffman 哈夫曼树 ) 设有 n个权值 w1 , w2 , , wn ，构造一棵有 n个叶子结点的二叉树，第 i 个叶子结点的

57、权值为 wi ，则带权路径长度 WPL 最小的二叉树被称作最优二叉树，又称哈夫曼树 (Huffman) 。【范例 12】对下图所给出的三棵二叉树，试分别计算叶子结点的 WPL 值。解答：（1） WPL= 9 1+152+33+43=60（2） WPL= 15 1+92+33+43=54（3） WPL= 4 1+152+93+33=70可见，第 (2) 棵二叉树的 WPL 值最小。6.7.2 哈夫曼算法1952 年哈夫曼 （D.A.Huffman ）针对如何减少通信系统中字符编码所需的二进制位长度， 提出了用于产生不定长的前缀编码算法，所谓前缀编码是指任一编码都不是其他编码的前缀。 由本节开始所

58、给出的例子可知， 前缀编码算法的基本思想就是对于出现概率较大的字符采用短编码方式， 而出现概率较小的字符采用长编码方式。 哈夫曼提出的算法能够使得其构造的二叉树的 WPL 值最小，从而保证在通信过程中，传输二进制位总长度最短。该算法主要是根据给定的不同字符的出现概率 （或频数） 建立一棵最优二叉树， 通常也称它为哈夫曼树。哈夫曼树应用十分广泛，哈夫曼算法也是数据库压缩最基本的算法之一。哈夫曼树的具体构造算法描述如下：根据给定的 n 个权值w 1， w2， wn ，构成 n棵二叉树的集合 T=T 1，T2， Tn ，其中每个 Ti 只有一个带权为 wi 的根结点，其左右子树均为空。从 T 中选两

59、棵根结点的权值最小的二叉树，不妨设为 Ti， Tj 并作为左右子树构成一棵新的二叉树 Tk， 并用置新二叉树的根值为左右子树的根结点的权值之和。从 T 中删除 Ti， Tj ，再将 Tk 并入 T 中。重复第 2、 3 步，直到 T 中只有一棵树为止。这棵树便是哈夫曼树。下面就以具体实例来说明哈夫曼算法的思想与哈夫曼树的构造过程。【范例 13】设集合 3， 4， 5， 6， 8， 10， 12， 18 为叶子结点的权值。（1）、构造其哈夫曼树；（2）、计算该哈夫曼树的 WPL；（3）、假设权值集合中的元素分别代表字符a、 b 、 c、 d、 e、 f 、 g、 h 在一个文本中出现的频次，请你

60、为这些字符设计一种不定长的前缀二进制编码。解答（ 1）：第 1 步 将这些数变成单结点的二叉树集合，使 T 变为：第 2 步 选出两棵根值最小的二叉树，作为左右子树，造棵新二叉树，使 T 变为：第 3 步 再选出两棵根值最小的二叉树，作为左右子树，再造棵新二叉树，使 T 变为：第 4 步 以下可类似地处理，可使 T 变为：第 5 步 T 又变为：第 6 步 T 又变为：第 7 步 T 又变为：第 8 步 T 最终变为以下形式，它已成为了一棵哈夫曼树。解答（ 2）： WPL =12 2+182+8 3+103+34+4 4+54+64=186解答（ 3）：不定长的前缀二进制编码方案：首先将哈夫曼