第5章树和二叉树 前面几章分别介绍了几种常见的线性结构，本章的树与第6章的图属于非线性数据结构。线性结构中的每个元素有唯一的前驱元素和唯一的后继元素，即前驱元素和后继元素是一对一的关系。非线性结构中元素间的前驱和后继关系并不具有唯一性，树形结构结点间的关系是前驱唯一而后继不唯一，即结点间是一对多的关系； 图结构结点间的关系是前驱和后继都不唯一，即结点间是多对多的关系； 树形结构应用非常广泛，特别是在大量数据处理(如文件系统、编译系统、目录组织等)方面显得更加突出。 本章主要内容：  树的相关概念、性质及存储结构  二叉树的概念、性质及存储结构  二叉树的遍历  二叉树的线索化  树、森林和二叉树的相互转换  哈夫曼树的定义及编码实现 视频讲解 5.1树 树是一种非线性的数据结构，树中各元素之间的关系是一对多的层次关系。 视频讲解 5.1.1树的定义 树(tree)是n(n≥0)个结点的有限集合。当n=0时，称为空树； 当n>0时，称为非空树。非空树满足以下条件： (1) 有且只有一个称为根(root)的结点。 (2) 当n>1时，其余n-1个结点可以划分为m个有限集合T1，T2，…，Tm，且这m个有限集合不相交。其中，Ti(1≤i≤m)也是一棵树，称为根的子树。 图51给出了一棵树的逻辑结构，它像一棵倒立的树。 图51树的逻辑结构 在图51中，A为根结点，左边的树只有根结点，右边的树有14个结点，除了根结点外，其余的13个结点分为3个不相交的子集： T1={B,E,F,K,L}、T2={C,G,H,I,M,N}和T3={D,J}。其中，T1、T2和T3是根结点A的子树，并且它们本身也是一棵树。例如，T2的根结点是C，其余的5个结点又分为3个不相交的子集： T21={G,M}、T22={H}和T23={I,N}。其中，T21、T22和T23是T2的子树，G是T21的根结点，{M}是G的子树，I是T23的根结点，{N}是I的子树。 表51是关于树的一些基本概念，表中举例基于图51(b)的树。 表51树的基本概念 术语定义示例 树的结点包含一个数据元素及若干指向子树分支的信息A、B、C、F和M等都是结点 结点的度一个结点拥有子树的个数称为结点的度结点C有3个子树，度为3 叶子结点没有子树（度为0）的结点称为叶子结点也称为终端结点K、L、F、M、H、N和J都是叶子结点 分支结点度不为0的结点称为非终端结点，也称为非终端结点B、C、D、E等都是分支结点 孩子结点一个结点的子树的根结点称为孩子结点B是A的孩子结点，E是B的孩子结点，H是C的孩子结点 双亲结点如果一个结点存在孩子结点，则该结点称为孩子结点的双亲结点，也称父结点A是B的双亲结点，B是E的双亲结点，I是N的双亲结点 子孙结点一个根结点的子树中的任何一个结点都称为该根结点的子孙结点{G,H,I,M,N}是C的子树，子树中的结点G、H、I、M和N都是C的子孙结点 祖先结点从根结点开始到达一个结点，所经过的所有分支结点都称为该结点的祖先结点N的祖先结点为A、C和I 兄弟结点一个双亲结点的所有孩子结点之间互相称为兄弟结点E和F是B的孩子结点，因此E和F互为兄弟结点 树的度树中所有结点的度的最大值结点C的度为3，结点A的度为3，这两个结点的度是树中拥有最大的度的结点，因此树的度为3 结点的层次从根结点开始，根结点为第1层，根结点的孩子结点为第2层……如果某一个结点是第L层，则其孩子结点位于第L+1层A的层次为1，B的层次为2，G的层次为3，M的层次为4 树的深度树中所有结点的层次最大值称为树的深度，也称为树的高度树的深度为4 有序树如果树中各个子树的次序是有先后次序的，则称该树为有序树 无序树如果树中各个子树的次序是没有先后次序的，则称该树为无序树 森林m棵互不相交的树构成一个森林。如果把一棵非空树的根结点删除，则该树就变成了一个森林，森林中的树由原来根结点的各个子树构成。如果把一个森林加上一个根结点，将森林中的树变成根结点的子树，则该森林就转换为一棵树 视频讲解 5.1.2树的逻辑表示 树的逻辑表示可分为4种： 树形表示法、文氏图表示法、广义表表示法和凹入表示法。 (1) 树形表示法。图51就是树形表示法。树形表示法是最常用的一种表示法，它能直观、形象地表示出树的逻辑结构，能够清晰地反映出树中结点之间的逻辑关系。树中的结点使用圆圈表示，结点间的关系使用直线表示，位于直线上方的结点是双亲结点，直线下方的结点是孩子结点。 (2) 文氏图表示法。文氏图表示是利用数学中的集合来图形化描述树的逻辑关系。图51的树的文氏图表示如图52所示。 (3) 广义表表示法。采用广义表的形式表示树的逻辑结构，广义表的子表表示结点的子树。图51的树的广义表表示如下。 (A(B(E(K,L),F),C(G(M),H,I(N)),D(J))) (4) 凹入表示法。图51的树的凹入表示如图53所示。 图52树的文氏图表示法 图53树的凹入表示法 在这4种树的表示法中，树形表示法最为常用。 5.1.3树的抽象数据类型 树的抽象数据类型定义了树中的数据对象、数据关系及基本操作。树的抽象数据类型如表52所示。 表52树的抽象数据类型描述 数据对象D是具有相同特性的数据元素的集合 数据关系若D为空集，则称为空树。若D仅含一个数据元素，则D为空集，否则D与H的关系如下。 (1) 在D中存在唯一的根数据元素root，它在关系H下无前驱。 (2) 若D{root}≠，则存在D{root}的一个划分D1，D2，…，Dm(m>0)，对任意的j≠k(1≤j,k≤m)，有Dj∩Dk=，且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di，有∈H。 (3) 对应于D{root}的划分，H{},…,}有唯一的一个划分H1，H2，…，Hm(m>0)，对任意的j≠k(1≤j,k≤m)，有Dj∩Dk=，且对任意的i(1≤i≤m)，Hi是Di上的二元关系。(Di,{Hi})是一棵符合本定义的树，称为root的子树 基本操作 InitTree(&T)初始条件： 树T不存在。 操作结果： 构造空树T DestroyTree(&T)初始条件： 树T存在。 操作结果： 销毁树T CreateTree(&T)初始条件： 树T存在。 操作结果： 根据给定条件构造树T TreeEmpty(T)初始条件： 树T存在。 操作结果： 若树T为空树，则返回1； 否则，返回0 Root(T)初始条件： 树T存在。 操作结果： 若树T非空，则返回树的根结点； 否则，返回null Parent(T,e)初始条件： 树T存在，e是T中的某个结点。 操作结果： 若e不是根结点，则返回该结点的双亲； 否则返回空 续表 基本操作 FirstChild(T,e)初始条件： 树T存在，e是T中的某个结点。 操作结果： 若e是树T的非叶子结点，则返回该结点的第一个孩子结点；否则，返回null NextSibling(T,e)初始条件： 树T存在，e是T中的某个结点。 操作结果： 若e不是其双亲结点的最后一个孩子结点，则返回它的下一个兄弟结点； 否则，返回null InsertChild(&T,p,Child)初始条件： 树T存在，p指向T中的某个结点，非空树Child与T不相交且无右子树。 操作结果： 将非空树Child插入T中，使Child成为p指向的结点的子树 DeleteChild(&T,p,i)初始条件： 树T存在，p指向T中的某个结点，1≤i≤d，d为p所指向结点的度。 操作结果： 将p所指向的结点的第i棵子树删除。如果删除成功，则返回1； 否则，返回0 TraverseTree(T)初始条件： 树T存在。 操作结果： 按照某种次序对T的每个结点访问且仅访问一次 TreeDepth(T)初始条件： 树T存在。 操作结果： 若树T非空，返回树的深度； 否则，返回0 5.2二叉树 在深入学习树之前，需要先认识一种比较简单的树——二叉树。 视频讲解 5.2.1二叉树的定义 二叉树(binary tree)是另一种树结构，它的特点是每个结点最多只有两棵子树。在二叉树中，每个结点的度只可能是0、1或2，每个结点的孩子结点有左右之分，位于左边的孩子结点称为左孩子结点或左孩子，位于右边的孩子结点称为右孩子结点或右孩子。如果n=0，则称该二叉树为空二叉树。 下面给出二叉树的5种基本形态，如图54所示。 图54二叉树的5种基本形态 一个由12个结点构成的二叉树如图55所示。F是C的左孩子结点，G是C的右孩子结点，L是G的右孩子结点，G的左孩子结点不存在。 图55二叉树示意图 对于深度为k的二叉树，若结点数为2k-1，即除了叶子结点外，其他结点都有两个孩子结点，则称这样的二叉树为满二叉树。在满二叉树中，每层的结点都具有最大的结点个数，每个结点的度为2或0(即叶子结点)，不存在度为1的结点。从根结点出发，从上到下、从左到右地依次对每个结点进行连续编号。一棵深度为4的满二叉树及其编号如图56所示。 图56一棵深度为4的满二叉树及其编号 如果一棵二叉树有n个结点，并且二叉树的n个结点的结构与满二叉树的前n个结点的结构完全相同，则称这样的二叉树为完全二叉树。完全二叉树及其编号如图57所示。图58所示为一棵非完全二叉树。 图57完全二叉树及其编号 图58非完全二叉树 由此可以看出，如果二叉树的层数为k，则满二叉树的叶子结点一定是在第k层，而完全二叉树的叶子结点一定在第k层或第k1层。满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。 视频讲解 5.2.2二叉树的性质 二叉树具有以下重要的性质。 性质1在二叉树中，第m(m≥1)层上至多有2m-1个结点(规定根结点为第1层)。 证明： 利用数学归纳法证明。 当m=1时，即根结点所在的层次，有2m-1=21-1=20=1，命题成立。 假设当m=k时，命题成立，即第k层至多有2k-1个结点。因为在二叉树中，每个结点的度最大为2，则第k+1层结点的个数最多是第k层的2倍，即2×2k-1=2k-1+1=2k。当m=k+1时，命题成立。 性质2深度为k(k≥1)的二叉树至多有2k-1个结点。 证明： 第i层结点的个数最多为2i-1，将深度为k的二叉树中的每层结点的最大值相加，即可得到二叉树中结点的最大值。因此，深度为k的二叉树的结点总数至多为 ∑ki=1(第i层结点的最大个数)=∑ki=12i－1=20+21+…+2k-1=20(2k－1)2－1=2k-1。 由此得证，命题成立。 性质3对任何一棵二叉树T，如果叶子结点总数为n0，度为2的结点总数为n2，则有n0=n2+1。 证明： 假设在二叉树中，结点总数为n，度为1的结点总数为n1。二叉树中结点的总数n等于度为0、度为1和度为2的结点总数的和，即n=n0+n1+n2。 假设二叉树的分支数为Y。在二叉树中，除了根结点外，每个结点都存在一个进入的分支，所以有n=Y+1。 又因为二叉树的所有分支都是由度为1和度为2的结点发出，所以分支数Y=n1+2×n2。故n=Y+1=n1+2×n2+1。 联合n=n0+n1+n2和n=n1+2×n2+1两式，得到n0+n1+n2=n1+2×n2+1，即n0=n2+1。 由此得证，命题成立。 性质4如果完全二叉树有n个结点，则深度为log2n+1。符号x表示不大于x的最大整数，而x表示不小于x的最小整数。 证明： 假设具有n个结点的完全二叉树的深度为k。k层完全二叉树的结点个数介于k-1层满二叉树与k层满二叉树结点个数之间。根据性质2，k-1层满二叉树的结点总数为n1=2k-1-1，k层满二叉树的结点总数为n2=2k-1。因此有n11，则序号为i的结点的双亲结点序号为i/2。 5.2 如果2i>n，则序号为i的结点没有左孩子结点。如果2×i≤n，则序号为i的结点的左孩子结点序号为2i。 5.3 如果2i+1>n，则序号为i的结点没有右孩子结点。如果2i+1≤n，则序号为i的结点的右孩子结点序号为2i+1。 证明： (1)利用性质5.2和性质5.3证明性质5.1。当i=1时，该结点一定是根结点，根结点没有双亲结点。当i>1时，假设序号为m的结点是序号为i的结点的双亲结点。如果序号为i的结点是序号为m的结点的左孩子结点，则根据性质5.2有2m=i，即m=i/2。如果序号为i的结点是序号为m的结点的右孩子结点，则根据性质5.3有2m+1=i，即m=(i-1)/2=i/2-1/2。综合以上两种情况，当i>1时，序号为i的结点的双亲结点序号为i/2。结论成立。 (2) 利用数学归纳法证明。当i=1时，有2i=2，如果2>n，则二叉树中不存在序号为2的结点，也就不存在序号为i的左孩子结点。如果2≤n，则该二叉树中存在两个结点，序号2是序号为i的结点的左孩子结点序号。 假设序号i=k，当2k≤n时，序号为k的结点的左孩子结点存在且序号为2k； 当2k>n时，序号为k的结点的左孩子结点不存在。 当i=k+1时，在完全二叉树中，如果序号为k+1的结点的左孩子结点存在2i≤n，则其左孩子结点的序号为k的结点的右孩子结点序号加1，即序号为k+1的结点的左孩子结点序号为(2k+1)+1=2×(k+1)=2i。因此，当2i>n时，序号为i的结点的左孩子不存在。结论成立。 (3) 同理，利用数学归纳法证明。当i=1时，如果2i+1=3>n，则该二叉树中不存在序号为3的结点，即序号为i的结点的右孩子结点不存在。如果2i+1=3≤n，则该二叉树存在序号为3的结点，且序号为3的结点是序号i的结点的右孩子结点。 假设序号i=k，当2k+1≤n时，序号为k的结点的右孩子结点存在且序号为2k+1，当2k+1>n时，序号为k的结点的右孩子结点不存在。 当i=k+1时，在完全二叉树中，如果序号为k+1的结点的右孩子结点存在2i+1≤n，则其右孩子结点的序号为k的结点的右孩子结点序号加2，即序号为k+1的结点的右孩子结点序号为(2k+1)+2=2×(k+1)+1=2i+1。因此，当2i+1>n时，序号为i的结点的右孩子不存在。结论成立。 视频讲解 5.2.3二叉树的抽象数据类型 二叉树的抽象数据类型定义了二叉树中的数据对象、数据关系及基本操作。二叉树的抽象数据类型描述如表53所示。 表53二叉树的抽象数据类型描述 数据对象D是具有相同特性的数据元素的集合 数据关系若D=，则称为空二叉树。 若D≠，则D与H的关系如下 (1) 在D中存在唯一的根数据元素root，它在关系H下无前驱。 (2) 若D{root}≠，则存在D{root}={Dl，Dr}，且Dl∩Dr=。 (3) 若Dl≠，则D1中存在唯一的元素x1，∈H，且存在D1上的关系H1H； 若Dr≠，则Dr中存在唯一的元素xr，∈H，且存在Dr上的关系HrH； H={,,Hl,Hr}。 (4) (D1，{H1})是一棵符合本定义的二叉树，称为根的左子树； (Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树 基本操作 InitBiTree(&T)初始条件： 二叉树T不存在。 操作结果： 构造空二叉树T CreateBiTree(&T)初始条件： 给出了二叉树T的定义。 操作结果： 创建一棵非空的二叉树T DestroyBiTree(&T)初始条件： 二叉树T存在。 操作结果： 销毁二叉树T InsertLeftChild(p,c)初始条件： 二叉树c存在且非空。 操作结果： 将c插入p所指向的左子树，使p所指结点的左子树成为c的右子树 InsertRightChild(p,c)初始条件： 二叉树c存在且非空。 操作结果： 将c插入p所指向的右子树，使p所指结点的右子树成为c的右子树 LeftChild(&T,e)初始条件： 二叉树T存在，e是T中的某个结点。 操作结果： 若结点e存在左孩子结点，则将e的左孩子结点返回，否则，返回空 RigthChild(&T,e)初始条件： 二叉树T存在，e是T的某个结点。 操作结果： 若结点e存在右孩子结点，则将e的右孩子结点返回，否则返回空 DeleteLeftChild(&T,p)初始条件： 二叉树T存在，p指向T中的某个结点。 操作结果： 将p所指向的结点的左子树删除。如果删除成功，则返回1，否则，返回0 DeleteRightChild(&T,p)初始条件： 二叉树T存在，p指向T中的某个结点。 操作结果： 将p所指向的结点的右子树删除。如果删除成功，则返回1，否则，返回0 PreOrderTraverse(T)初始条件： 二叉树T存在。 操作结果： 先序遍历二叉树T。即先访问根结点，再访问左子树，最后访问右子树，对二叉树中的每个结点访问且仅访问一次 InOrderTraverse(T)初始条件： 二叉树T存在。 操作结果： 中序遍历二叉树T。即先访问左子树，再访问根结点，最后访问右子树，对二叉树中的每个结点访问且仅访问一次 PostOrderTraverse(T)初始条件： 二叉树T存在。 操作结果： 后序遍历二叉树T。即先访问左子树，再访问右子树，最后访问根结点，对二叉树中的每个结点访问且仅访问一次 续表 基本操作 LevelTraverse(T)初始条件： 二叉树T存在。 操作结果： 对二叉树进行层次遍历。即按照从上到下、从左到右的顺序依次对二叉树中的每个结点进行访问 BiTreeDepth(T)初始条件： 二叉树T存在。 操作结果： 若二叉树非空，则返回二叉树的深度； 若二叉树为空，则返回0 视频讲解 5.2.4二叉树的存储表示 二叉树的存储结构有两种： 顺序存储表示和链式存储表示。 1. 二叉树的顺序存储 完全二叉树中的结点编号可以通过公式计算得到，因此，完全二叉树的存储可以按照从上到下、从左到右的顺序依次存储在一维数组中。完全二叉树的顺序存储如图59所示。 图59完全二叉树的顺序存储表示 按照从上到下、从左到右的顺序将非完全二叉树也进行同样的编号，将结点依次存放在一维数组中。为了能够正确反映二叉树中结点之间的逻辑关系，需要在一维数组中将二叉树中不存在的结点位置空出，并用'^'填充。非完全二叉树的顺序存储结构如图510所示。 图510非完全二叉树的顺序存储表示 顺序存储对于完全二叉树来说是比较适合的，因为采用顺序存储能够节省内存单元，并能够利用公式得到每个结点的存储位置。但是，对于非完全二叉树来说，这种存储方式会造成内存空间的浪费。在最坏的情况下，如果每个结点只有右孩子结点而没有左孩子结点则需要占用2k-1个存储单元，而实际上该二叉树只有k个结点。 2. 二叉树的链式存储 在二叉树中，每个结点有一个双亲结点和两个孩子结点。从一棵二叉树的根结点开始， 通过结点的左右孩子地址就可以找到二叉树的每一个结点。 因此，二叉树的链式存储结构包括3个域： 数据域、左孩子指针域和右孩子指针域。 图511二叉链表的结点结构 其中，数据域存放结点的值，左孩子指针域指向左孩子结点，右孩子指针域指向右孩子的结点。这种链式存储结构称为二叉链表存储结构，如图511所示。 如果二叉树采用二叉链表存储结构表示，则其二叉树的存储表示如图512所示。 图512非完全二叉树的二叉链表存储表示 图513三叉链表结点结构 有时为了方便找到结点的双亲结点，在二叉链表的存储结构中增加一个指向双亲结点的指针域parent。这种存储结构称为三叉链表结点存储结构，如图513所示。 通常情况下，二叉树采用二叉链表进行表示。二叉链表存储结构的类型定义描述如下： class BiTreeNode//二叉树的结点类型 { char data; BiTreeNode lchild,rchild; BiTreeNode(char data) { this.data=data; lchild=null; rchild=null; } } 在定义了二叉树的存储结点后，为了实现二叉树的插入、删除、遍历和线索化，必须先创建二叉树。二叉树的操作可通过定义BiTree类来实现。二叉树的初始化如下： public class BiTree { BiTreeNode root; int num; static int pi=0; final int MAXSIZE=20; BiTree() { root = new BiTreeNode(); num = 0; } } 创建二叉树的算法实现如下： BiTreeNode CreateBiTree(char str［］) { if (str［pi］ == '#') //本层构建root、root.lchild、root.rchild三个结点 { ++pi; return null; } BiTreeNode root = new BiTreeNode(); root.data = str［pi］; ++pi; root.lchild = CreateBiTree(str); //构造左子树 root.rchild = CreateBiTree(str); //构造右子树 return root; //递归结束返回构造好的树的根结点 } 5.3二叉树的遍历 在二叉树的应用中，常常需要对二叉树中的每个结点进行访问，即二叉树的遍历。 视频讲解 5.3.1二叉树遍历的定义 二叉树的遍历，即按照某种规律对二叉树的每个结点进行访问，使得每个结点仅被访问一次。这里的访问可以是对结点的输出、统计结点的个数等。 图514二叉树结点 的基本结构 二叉树的遍历过程是将二叉树的非线性序列转换成一个线性序列的过程。二叉树是一种非线性的结构，通过遍历二叉树，按照某种规律对二叉树中的每个结点访问一次，即可得到一个顺序序列。 由二叉树的定义，二叉树是由根结点、左子树和右子树构成的。将这3个部分依次遍历，就完成了整个二叉树的遍历。二叉树结点的基本结构如图514所示。如果用D、L、R分别代表遍历根结点、遍历左子树和遍历右子树，则根据组合原理，可以得到6种遍历方案： DLR、DRL、LDR、LRD、RDL和RLD。 如果限定先左后右的次序，则只剩下3种方案： DLR、LDR和LRD。其中，DLR称为先序遍历，LDR称为中序遍历，LRD称为后序遍历。 5.3.2二叉树的先序遍历 二叉树先序遍历的递归定义如下。 如果二叉树为空，则执行空操作； 如果二叉树非空，则执行以下操作： (1) 访问根结点； (2) 先序遍历左子树； (3) 先序遍历右子树。 图515二叉树 根据二叉树先序遍历的递归定义，可以得到图515的二叉树的先序序列为ABDGEHICFJ。 在二叉树先序遍历的过程中，对每一棵二叉树重复执行以上的递归遍历操作，就可以得到先序序列。例如，在遍历根结点A的左子树{B,D,E,G,H,I}时，根据先序遍历的递归定义，先访问根结点B，然后遍历B的左子树{D,G}，最后遍历B的右子树{E,H,I}。在访问B之后，开始遍历B的左子树{D,G}，先访问根结点D，因为D没有左子树，所以遍历其右子树，右子树只有一个结点G，所以访问G。B的左子树遍历完毕，按照以上方法遍历B的右子树。最后得到结点A的左子树先序序列： BDGEHI。 依据二叉树的先序递归定义，可以得到二叉树的先序递归算法。 public void PreOrderTraverse(BiTreeNode T) //先序遍历二叉树的递归实现 { if(T!=null) { System.out.print(T.data+" "); //访问根结点 nodal point(T.lchild); //先序遍历左子树 subtree(T.rchild); //先序遍历右子树 } } 下面介绍二叉树的非递归算法实现。在第4章学习栈时，已经对递归的消除进行了具体讲解，现在利用栈来实现二叉树的非递归算法。 算法实现： 从二叉树的根结点开始，访问根结点，然后将根结点的指针入栈，重复执行以下两个步骤。 (1) 如果该结点的左孩子结点存在，则访问左孩子结点，并将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在。 (2) 将栈顶的元素(指针)出栈，如果该指针指向的右孩子结点存在，则将当前指针指向右孩子结点。 重复执行以上两个步骤，直到栈空为止。 以上算法思想的执行流程如图516所示。 图516二叉树非递归先序遍历的执行流程图 二叉树先序遍历的非递归算法实现如下。 public void PreOrderTraverse2(BiTreeNode T) //二叉树先序遍历的非递归实现 { BiTreeNode stack［］ =new BiTreeNode［MAXSIZE］;//定义一个栈，用于存放结点的指针 int top = 0; //定义栈顶指针, 初始化栈 BiTreeNode p = T; while(p != null || top>0) { while (p != null) //如果p不空，则访问根结点，遍历左子树 { System.out.print(p.data + " "); //访问根结点 stack［top++］=p; p = p.lchild; //遍历左子树 } if(top > 0) //如果栈不空 { p = stack［--top］; //栈顶元素出栈 p = p.rchild; //遍历右子树 } } } 以上算法是直接利用数组来模拟栈的实现，当然也可以定义一个栈类型实现。如果用链式栈实现，则需要将数据类型改为指向二叉树结点的指针类型。 视频讲解 5.3.3二叉树的中序遍历 二叉树中序遍历的递归定义如下。 如果二叉树为空，则执行空操作； 如果二叉树非空，则执行以下操作： (1) 中序遍历左子树； (2) 访问根结点； (3) 中序遍历右子树。 根据二叉树中序遍历的递归定义，图515的二叉树的中序序列为DGBHEIAFJC。 在二叉树中序遍历的过程中，对每一棵二叉树重复执行以上的递归遍历操作，就可以得到二叉树的中序序列。 例如，如果要中序遍历A的左子树{B,D,E,G,H,I}，根据中序遍历的递归定义，需要先中序遍历B的左子树{D,G}，然后访问根结点B，最后中序遍历B的右子树{E,H,I}。在子树{D,G}中，D是根结点，没有左子树，因此访问根结点D，接着遍历D的右子树，因为右子树只有一个结点G，所以直接访问G。 在左子树遍历完毕后，访问根结点B。遍历B的右子树{E,H,I}，E是子树{E,H,I}的根结点，需要先遍历左子树{H},因为左子树只有一个H，所以直接访问H，然后访问根结点E； 最后遍历右子树{I}，右子树也只有一个结点，所以直接访问I，B的右子树访问完毕。因此，A的右子树的中序序列为DGBHE和I。 从中序遍历的序列可以看出，A左边的序列是A的左子树元素，A右边的序列是A的右子树元素。同样，B的左、右序列分别为其左、右子树元素。根结点把二叉树的中序序列分为左右两棵子树序列，左边为左子树序列，右边为右子树序列。 依据二叉树的中序递归定义，可以得到二叉树的中序递归算法如下。 public void InOrderTraverse(BiTreeNode T) //中序遍历二叉树的递归实现 { if(T!=null) { InOrderTraverse(T.lchild); //中序遍历左子树 subtree(T.data+" "); //访问根结点 nodal point(T.rchild); //中序遍历右子树 } } 下面介绍二叉树中序遍历的非递归算法实现。 二叉树中序遍历的非递归算法实现： 从二叉树的根结点开始，将根结点的指针入栈，执行以下两个步骤。 (1) 如果该结点的左孩子结点存在，则将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在。 (2) 将栈顶的元素(指针)出栈，并访问该指针指向的结点，如果该指针指向的右孩子结点存在，则将当前指针指向右孩子结点。 重复执行以上两个步骤，直到栈空为止。 以上算法思想的执行流程如图517所示。 二叉树中序遍历的非递归算法实现如下。 public void InOrderTraverse2(BiTreeNode T) //中序遍历二叉树的非递归实现 { BiTreeNode stack［］ = new BiTreeNode［MAXSIZE］; //定义一个栈，用于存放结点的指针 int top = 0; //定义栈顶指针, 初始化栈 BiTreeNode p = T; while (p != null || top > 0) { while (p != null) //如果p不空，则遍历左子树 { stack［top++］ = p; //将p入栈 p = p.lchild; //遍历左子树 } if (top > 0) //如果栈不空 { p = stack［--top］; //栈顶元素出栈 System.out.print(p.data + " ");//访问根结点 p = p.rchild; //遍历右子树 } } } 图517二叉树非递归中序遍历的执行流程图 视频讲解 5.3.4二叉树的后序遍历 二叉树后序遍历的递归定义如下。 如果二叉树为空，则执行空操作； 如果二叉树非空，则执行以下操作： (1) 后序遍历左子树； (2) 后序遍历右子树； (3) 访问根结点。 根据二叉树后序遍历的递归定义，图515的二叉树的后序序列为GDHIEBJFCA。 在二叉树后序遍历的过程中，对每一棵二叉树重复执行以上的递归遍历操作，就可以得到二叉树的后序序列。 例如，如果要后序遍历A的左子树{B,D,E,G,H,I}，根据后序遍历的递归定义，需要先后序遍历B的左子树{D,G}，然后后序遍历B的右子树{E,H,I}，最后访问根结点B。在子树{D,G}中，D是根结点，没有左子树，因此遍历D的右子树，因为右子树只有一个结点G，所以直接访问G，接着访问根结点D。 在左子树遍历完毕后，需要遍历B的右子树{E,H,I}。E是子树{E,H,I}的根结点，需要先遍历左子树{H},因为左子树只有一个H，所以直接访问H； 然后遍历右子树{I}，右子树也只有一个结点，所以直接访问I，最后访问子树{E,H,I}的根结点E。B的左、右子树均访问完毕，此时访问结点B。因此，A的右子树的后序序列为GDHIEB。 依据二叉树的后序递归定义，可以得到二叉树的后序递归算法如下。 public void PostOrderTraverse(BiTreeNode T) //后序遍历二叉树的递归实现 { if(T!=null) //如果二叉树不为空 { PostOrderTraverse(T.lchild); //后序遍历左子树 subtree(T.rchild); //后序遍历右子树 subtree(T.data+" "); //访问根结点 } } 下面介绍二叉树后序遍历的非递归算法实现。 二叉树后序遍历的非递归算法实现： 从二叉树的根结点开始，将根结点的指针入栈，执行以下两个步骤。 (1) 如果该结点的左孩子结点存在，则将左孩子结点的指针入栈。重复执行此操作，直到结点的左孩子不存在。 (2) 取栈顶元素(指针)并赋给p，如果p.rchild==null或p.rchild=q，即p没有右孩子或右孩子结点已经访问过，则访问p指向的根结点，并用q记录刚刚访问过的结点指针，将栈顶元素退栈； 如果p有右孩子且右孩子结点没有被访问过，则执行p=p.rchild。重复执行以上两个步骤，直到栈空为止。 以上算法思想的执行流程如图518所示。 图518二叉树非递归后序遍历的执行流程图 二叉树后序遍历的非递归算法实现如下。 public void PostOrderTraverse2(BiTreeNode T)//后序遍历二叉树的非递归实现 { BiTreeNode stack［］ = new BiTreeNode［MAXSIZE］;//定义一个栈，用于存放结点的指针 int top = 0; BiTreeNode p = T; BiTreeNode q = null; //初始化结点的指针 while (p != null || top > 0) { while (p != null) //如果p不空，则遍历左子树 { stack［top++］ = p; //将p入栈 p = p.lchild; //遍历左子树 } if (top > 0) //如果栈不空 { p = stack［top-1］; //取栈顶元素 if(p.rchild == null || p.rchild == q)//如果p没有右孩子结点或右孩子结点已 //经访问过 { System.out.print(p.data+" ");//访问根结点 q = p; //记录刚刚访问过的结点 p = null; //为遍历右子树做准备 top--; //出栈 } else p = p.rchild; } } 5.4二叉树的线索化 在二叉树中，采用二叉链表作为存储结构，只能找到结点的左孩子结点和右孩子结点。要想找到结点的直接前驱或直接后继，必须对二叉树进行遍历，但这并不是最直接、最简便的方法。通过对二叉树进行线索化，可以很方便地找到结点的直接前驱和直接后继。 视频讲解 5.4.1二叉树的线索化定义 在二叉树的遍历过程中，为了能够直接找到结点的直接前驱或直接后继，可在二叉链表结点中增加两个指针域： 一个用来指向结点的前驱，另一个用来指向结点的后继。这样做需要为结点增加更多的存储单元，会使结点结构的利用率大大下降。 在二叉链表的存储结构中，具有n个结点的二叉链表有n+1个空指针域。由此，可以利用这些空指针域存放结点的直接前驱和直接后继的信息。为此进行以下规定： 如果结点存在左子树，则指针域lchild指向其左孩子结点，否则指针域lchild指向其直接前驱结点； 如果结点存在右子树，则指针域rchild指向其右孩子结点，否则指针域rchild指向其直接后继结点。 为了区分指针域指向的是左孩子结点还是直接前驱结点，是右孩子结点还是直接后继结点，增加两个标志域ltag和rtag。结点的存储结构如图519所示。 图519结点的存储结构 其中，当ltag=0时，lchild指向结点的左孩子结点； 当ltag=1时，lchild指向结点的直接前驱结点。当rtag=0时，rchild指向结点的右孩子结点； 当rtag=1时，rchild指向结点的直接后继结点。 由这种存储结构构成的二叉链表称为线索二叉树。采用这种存储结构的二叉链表称为线索链表。指向结点的直接前驱和直接后继的指针称为线索。在二叉树的先序遍历过程中，加上线索即可得到先序线索二叉树。同理，在二叉树的中序(后序)遍历过程中，加上线索即可得到中序(后序)线索二叉树。二叉树按照某种遍历方式使二叉树变为线索二叉树的过程称为二叉树的线索化。图520就是将二叉树进行先序、中序和后序遍历得到的线索二叉树。 图520线索二叉树 线索二叉树的存储结构类型描述如下。 class BiThrNode //线索二叉树结点 { String data; BiThrNode lchild,rchild; int ltag,rtag; BiThrNode() { this.data="null"; //二叉树的结点值 this.lchild=null; //左孩子 this.rchild=null; //右孩子 this.ltag=0; //线索标志域 this.rtag=0; //线索标志域 } BiThrNode(String data) { this.data=data; //二叉树的结点值 this.lchild=null; //左孩子 this.rchild=null; //右孩子 this.ltag=0; //线索标志域 this.rtag=0; //线索标志域 } public String getData() { return data; } } 视频讲解 5.4.2二叉树的线索化算法实现 二叉树的线索化就是利用二叉树中结点的空指针域表示结点的前驱或后继信息。而要得到结点的前驱信息和后继信息，则需要对二叉树进行遍历，同时将结点的空指针域修改为其直接前驱或直接后继信息。因此，二叉树的线索化就是对二叉树的遍历过程。这里以二叉树的中序线索化为例介绍二叉树的线索化。 为了方便表示，在二叉树的线索化时，可增加一个头结点。头结点的指针域lchild指向二叉树的根结点，指针域rchild指向二叉树中序遍历时的最后一个结点，二叉树中的第一个结点的线索指针指向头结点。在初始化时，使二叉树的头结点指针域lchild和rchild均指向头结点，并将头结点的标志域ltag置为Link，标志域rtag置为Thread。 经过线索化的二叉树类似于一个循环链表，操作线索二叉树就像操作循环链表一样，既可以从线索二叉树中的第一个结点开始，根据结点的后继线索指针遍历整个二叉树，也可以从线索二叉树的最后一个结点开始，根据结点的前驱线索指针遍历整个二叉树。经过线索化的二叉树及其存储结构如图521所示。 图521中序线索二叉树及链表 中序线索二叉树的算法实现如下。 public BiThrNode InOrderThreading(BiThrNode T) //通过中序遍历二叉树T，使T中序线索化。thrt是指向头结点的指针 { BiThrNode thrt = new BiThrNode(); //将头结点线索化 thrt.ltag = 0;//修改前驱线索标志 thrt.rtag = 1; //修改后继线索标志 thrt.rchild = thrt; //将头结点的rchild指针指向自己 if (T == null) //如果二叉树为空，则将lchild指针指向自己 thrt.lchild = thrt; else { thrt.lchild = T; //将头结点的左指针指向根结点 pre = thrt; //将pre指向已经线索化的结点 T = InThreading(T); //中序遍历进行中序线索化 //将最后一个结点线索化 pre.rchild = thrt; //将最后一个结点的右指针指向头结点 pre.rtag = 1; //修改最后一个结点的rtag标志域 thrt.rchild = pre; //将头结点的rchild指针指向最后一个结点 thrt.lchild = T; //将头结点的左指针指向根结点 } return thrt; } public BiThrNode InThreading(BiThrNode p) { //二叉树中序线索化 if (p != null) { InThreading(p.lchild); //左子树线索化 if (p.lchild == null) //前驱线索化 { p.ltag = 1; p.lchild = pre; } if (pre.rchild == null) //后继线索化 { pre.rtag = 1; pre.rchild = p; } pre = p; //pre指向的结点线索化完毕，使p指向的结点成为前驱 InThreading(p.rchild); //右子树线索化 } return p; } 视频讲解 5.4.3线索二叉树的遍历 利用在线索二叉树中查找结点的前驱和后继的思想，遍历线索二叉树。 1. 查找指定结点的中序直接前驱 在中序线索二叉树中，对于指定的结点p，即指针p指向的结点，如果p.ltag=1，则p.lchild指向的结点就是p的中序直接前驱结点； 如果p.ltag=0，则p的中序直接前驱就是p的左子树的最右下端的结点。例如，在图521中，结点E的前驱标志域为1（即Thread），则中序直接前驱为A，即lchild指向的结点； 结点A的中序直接前驱结点为D,即结点A的左子树的最右下端的结点。 查找指定结点的中序直接前驱的算法实现如下。 public BiThrNode InOrderPre(BiThrNode p) //在中序线索树中找结点 p的中序直接前驱 { if (p.ltag == 1) //如果p的标志域ltag为线索，则p的左子树结点即为前驱 return p.lchild; else { pre = p.lchild; //查找p的左孩子的最右下端结点 end node(pre.rtag == 0) //当右子树非空时，沿右链往下查找 pre = pre.rchild; return pre; //pre就是最右下端结点 } } 2. 查找指定结点的中序直接后继 在中序线索二叉树中，查找指定结点p的中序直接后继，与查找指定结点的中序直接前驱类似。如果p.rtag=1，那么p.rchild指向的结点就是p的直接后继结点； 如果p.rtag=0,则p的中序直接后继就是p的右子树的最左下端的结点。例如，在图521中，结点G的后继标志域为1（即Thread），则中序直接后继为D，即rchild指向的结点； 结点B的中序直接后继为G，即结点B的右子树的最左下端的结点。 查找指定结点的中序直接后继的算法实现如下。 public BiThrNode InOrderPost(BiThrNode p) // 在中序线索树中查找结点p的中序直接后继 { if(p.rtag == 1) //如果p的标志域ltag为线索，则p的右子树结点即为后继 return p.rchild; else { pre = p.rchild; //查找p的右孩子的最左下端结点 end node(pre.ltag == 0) //左子树非空时，沿左链往下查找 pre = pre.lchild; return pre; //pre就是最左下端结点 } } 3. 中序遍历线索二叉树 中序遍历线索二叉树的实现思想分为以下3个步骤： ①从第一个结点开始，找到二叉树的最左下端的结点，并访问该结点； ②判断该结点的右标志域是否为线索指针，如果是线索指针即p.rtag==1，说明p.rchild指向结点的中序后继，则将指针指向右链结点，并访问该结点； ③将当前指针指向该右孩子结点。重复以上3个步骤，直到遍历完毕。 整个中序遍历线索二叉树的过程，就是线索查找后继和查找右子树的最左下端结点的过程。 中序遍历线索二叉树的算法实现如下。 public void InOrderTraverse(BiThrNode T) //中序遍历线索二叉树 { BiThrNode p = T.lchild;//将根结点赋给p while(p!=T){ while(p!=T&&p.ltag == 0) //顺着左孩子线索进行搜索 p = p.lchild; Print(p); while(p.rtag == 1&&p.rchild!=T){ //如果存在孩子线索，则搜索后继结点 p = p.rchild; Print(p); } p = p.rchild; } } 5.4.4线索二叉树的应用示例 【例51】编写程序，建立如图521所示的二叉树，并将其中序线索化。任意输入一个结点，输出该结点的中序前驱和中序后继。例如，结点D的中序直接前驱是G，其中序直接后继是A。 程序代码如下。 public BiThrNode CreateBiTree(String S) { int top=-1; //初始化栈顶指针 int k = 0; BiThrNode T= null; int flag=0; BiThrNode stack［］ =new BiThrNode［MAXSIZE］; char ch=S.charAt(k); BiThrNode p=null; while(krank［root_y］，则将秩较小的root_y作为root_x的孩子结点，此时root_x的秩不变。 (3) 若x所在子树的秩rank［root_x］==rank［root_y］，则可将root_x作为root_y的孩子结点，也可将root_y作为root_x的孩子结点，合并后子树的秩加1。 两棵子树的合并如图535所示。 图535两棵子树的合并 合并算法实现如下。 public void Merge(int x, int y) { int root_x = Find (x); int root_y = Find (y);//找到两个根结点 nodal point(rank［root_x］ <= rank［root_y］)//若前者树的高度小于或等于后者 parent［root_x］ = root_y; else //否则 parent［root_y］ = root_x; if(rank［root_x］ == rank［root_y］ && root_x !=root_y) //如果高度相同且根结点不同，则新的根结点的高度 + 1 rank［root_y］++; } 5.6.3并查集的应用示例 【例54】给定一个包含 N 个顶点 M 条边的无向图 G ，判断 G 是否为一棵树。 【分析】判断包含N个顶点、M条边的无向图是否为一棵树的充分必要条件是N=M+1且N个顶点连通。因此，关键在于判断这N个顶点是不是连通的。判断连通性一般有两种方法： (1) 利用图的连通性来判断。从一个顶点(比如1号顶点)开始进行深度或广度优先搜索遍历，将搜索时遇到的顶点都进行标记，最后检查这N个顶点是否都被标记了。统计被标记顶点的数量，若为N则表明这是一棵树； 否则不是一棵树。 (2) 用并查集的基本操作实现判断。依次搜索每一条边，把每条边相关联的两个顶点都合并到一个集合里，最后检查这N个顶点是否都在同一个集合中。若N个顶点都在同一个集合中，则表明这是一棵树； 否则不是一棵树。 【算法实现】 public int FindParent(int x,int parent［］) //在并查集中查找x结点的根结点 { if(x == parent［x］) return x; parent［x］ = FindParent(parent［x］, parent); return parent［x］; } public static void main(String args［］) { int SIZE = 100; int parent［］ = new int［SIZE］; System.out.println("请分别输入顶点数和边数:"); Scanner sc=new Scanner(System.in); String str［］ = sc.nextLine().split(" "); int n=Integer.parseInt(str［0］); int m=Integer.parseInt(str［1］); boolean flag=false; DisjointSet Djs=new DisjointSet(n); if(m != n - 1) flag = true; for(int i=1;i s=Select (HT,i - 1);//查找树中权值最小的两个结点 int s1=s.get(0),s2=s.get(1); 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; } //从叶子结点到根结点，求每个字符的哈夫曼编码 //求n个叶子结点的哈夫曼编码 for(int i=1;i<=n;i++) { char cd［］=new char［n+1］; int start=n-1; for(int 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］=new String(); String str=new String(cd); HC［i］=str; //将当前求出结点的哈夫曼编码复制到HC } } （2） 查找权值最小和次小的两个结点。 这部分主要是在结点的权值中选择权值最小和次小的两个结点，将其作为二叉树的叶子结点，其程序代码实现如下。 public List Select(HTNode t［］,int n) //在n个结点中选择两个权值最小的结点序号，其中s1最小，s2次小 { List result=new ArrayList(); int s1 = Min(t, n); int s2 = Min(t,n); if(t［s1］.weight>t［s2］.weight)//如果序号s1的权值大于序号s2的权值，将两者交换，使 //s1最小，s2次小 { int x = s1; s1 = s2; s2 = x; } result.add(s1); result.add(s2); return result; } public int Min(HTNode t［］, int n) //返回树的n个结点中权值最小的结点序号 { int f = Integer.MAX_VALUE; //f为一个无限大的值 int flag=0; for (int i = 1; i < n + 1; i++) { if (t［i］.weight < f && t［i］.parent == 0) { f = t［i］.weight; flag = i; } } t［flag］.parent = 1; //给选中的结点的双亲结点赋值1，避免再次查找该结点 return flag; } （3） 将哈夫曼编码翻译为字符串序列。 这部分主要是将哈夫曼编码翻译为字符串序列，其实现原理及程序代码实现如下。 根据哈夫曼树的构造原理，从根结点开始遍历，如果遇到的编码是0，则沿着左孩子结点往下遍历； 若遇到的编码是1，则沿着右孩子结点往下遍历。以此类推，对其他结点重复执行以上操作，直到遍历到叶子结点为止，此时扫描到的编码就是该叶子结点对应的字符。 public void GetStr(HTNode HT［］, int nums, char w［］, char str［］) { int i = 0, n = 2 * nums - 1; int length = str.length; for (i = 0; i < length; i++) { if (str［i］ == '1') n = HT［n］.rchild; else if (str［i］ == '0') n = HT［n］.lchild; else return; for (int j = 1; j <= nums; j++) { if (j == n) { n = 2 * nums - 1; System.out.print(w［j-1］+" "); break; } } } } （4） 运行测试代码。 这部分是运行测试代码，测试代码主要包括头文件、宏定义、函数的声明和主函数，其程序代码实现如下。 public static void main(String args［］) { System.out.print("请输入叶子结点的个数: "); Scanner sc=new Scanner(System.in); int n=Integer.parseInt(sc.nextLine()); int m=2*n-1; HTNode HT［］=new HTNode［m+1］; String HC［］=new String［n+1］; int w［］=new int［n］; //为n个结点的权值分配内存空间 for(int i=0;i= n) j--; BitNode p = T.CreateETree(String.valueOf(data), null, null); Expt.Push(p); } else { if (Precede(Optr.GetTop(), str.substring(i, i + 1)) == '<') { Optr.Push(str.substring(i, i + 1)); i += 1; } else if (Precede(Optr.GetTop(), str.substring(i, i + 1)) == '>') { String theta = Optr.Pop(); BitNode rcd = Expt.Pop(); BitNode lcd = Expt.Pop(); BitNode p = T.CreateETree(theta, lcd, rcd); Expt.Push(p); } else if (Precede(Optr.GetTop(), str.substring(i, i + 1)) == '=') { String theta = Optr.Pop(); i += 1; } } } return Expt.GetTop(); } 根据得到的表达式树，利用二叉树的后序遍历即可求出表达式的值，其算法实现如下。 public float CalcExpTree(BitNode T) throws Exception //后序遍历表达树进行表达式求值 { float lvalue = 0, rvalue = 0; int len=0; if (T.lchild == null && T.rchild == null) { len=0; for(int i=0;i='0'&&T.data.charAt(i)<='9') len++; } return StrtoInt(T.data,len); } else { lvalue = CalcExpTree(T.lchild); rvalue = CalcExpTree(T.rchild); return GetValue(T.data, lvalue, rvalue); } } 求表达式值的主函数如下。 public class ExpressTree { //7种运算符 operator()#"; //运算符优先级比较表 char prior_table［］［］ = {{'>', '>', '<', '<', '<', '>', '>'}, {'>', '>', '<', '<', '<', '>', '>'}, {'>', '>', '>', '>', '<', '>', '>'}, {'>', '>', '>', '>', '<', '>', '>'}, {'<', '<', '<', '<', '<', '=', ' '}, {'>', '>', '>', '>', ' ', '>', '>'}, {'<', '<', '<', '<', '<', ' ', '='}}; public boolean IsOperator(char ch) //判断ch是否为运算符 { int i = 0; int length = operator.length(); while (i < length && operator.charAt(i) != ch) i += 1; if (i >= length) return false; else return true; } public int StrtoInt(String str, int n) //将数值型字符串转换为int型 { int res = 0; int i = 0; while (i < n) { res = res * 10 + str.charAt(i) - '0'; i += 1; } return res; } public char Precede(String ch1, String ch2) //判断运算符的优先级 { int i = 0, j = 0; while (i < operator.length() && !ch1.equals(String.valueOf(operator.charAt(i)))) i += 1; while (j < operator.length() && !ch2.equals(String.valueOf(operator.charAt(j)))) j += 1; return prior_table［i］［j］; } public float GetValue(String ch, float a, float b) throws Exception //求值 { if (ch.equals("+")) return a + b; else if (ch.equals("-")) return a - b; else if (ch.equals("*")) return a * b; else if (ch.equals("/")) return a / b; else throw new Exception("运算符错误!"); } public static void main(String args［］) throws Exception //测试方法 { System.out.println("请输入算术表达式串:"); Scanner sc=new Scanner(System.in); String str=sc.nextLine(); ExpressTree Tree=new ExpressTree(); BitNode T = Tree.CreateExpTree(str); ExpBiTree root=new ExpBiTree(); System.out.println("先序遍历:"); root.PreOrderTree(T); System.out.println("＼n中序遍历:"); root.InOrderTree2(T); System.out.print("＼n表达式的值:"); float value = Tree.CalcExpTree(T); System.out.println(value); } } 程序运行结果如下。 请输入算术表达式串： 6+(7-1)×3+9/2# 先序遍历： ++6×-713/92 中序遍历： 6+7-1×3+9/2 表达式的值： 28.5 思政元素 哈夫曼树的构造是整体和部分关系的具体体现，由于每次选择的都是权值最小的结点，因此最终构成的二叉树的权值才会最小。在做任何事情时都应该有全局观念，把握好整体和局部的关系，增强大局意识和协同意识，只有这样才能把事情做到最好。“大河有水小河满，小河无水大河干”“不谋全局者，不足谋一域”体现了整体与部分的关系，整体和部分不可分割且相互影响，任何部分的变化都会影响整体，整体的变化也会影响部分。 5.8实验 5.8.1基础实验 1. 基础实验1： 实现二叉树的基本运算 图542二叉树示例 实验目的： 理解二叉树的存储结构，熟练掌握其基本操作。 实验要求： 创建一棵如图542所示的二叉树，并要求进行以下基本运算： (1) 创建二叉树； (2) 按照先序遍历方式输出二叉树的各结点； (3) 按照中序遍历方式输出二叉树的各结点； (4) 按照后序遍历方式输出二叉树的各结点； (5) 按照层次遍历方式输出二叉树的各结点。 2. 基础实验2： 利用二叉树的遍历方式构造二叉树 实验目的： 熟练掌握二叉树的先序、中序、后序遍历算法思想。 实验要求： 已知二叉树的先序遍历序列为ABDEGCF，中序遍历序列为DBGEACF，编写算法创建二叉树。创建一个BiTree类，该类应至少包含以下基本运算。 (1) 构造二叉树； (2) 按后序遍历方式输出二叉树的各结点； (3) 按层次遍历方式输出二叉树的各结点； (4) 输出二叉树的高度。 5.8.2综合实验 1. 综合实验1： 哈夫曼树及其应用 实验目的： 深入理解二叉树的存储结构，熟练掌握哈夫曼树的构造及哈夫曼编码。 实验要求： 一个单位有12个部门，每个部门都有一部电话，但是整个单位只有一根外线。当有电话打过来时，由转接员转到内线电话。已知各部门使用外线电话的频率为5、20、10、12、8、43、5、6、9、15、19、32(次/天)。 利用哈夫曼树算法思想设计内线电话号码，使得接线员拨号次数尽可能少，具体设计要求如下。 (1) 依据使用外线电话的频率构造二叉树。 (2) 输出设计出的各部门内线电话号码。 实验思路： 将各部门外线电话的使用频率作为权值，以此构造哈夫曼树，对哈夫曼树进行先序遍历即可得到内线电话号码。 2. 综合实验2： 求解算术表达式的值 实验目的： 深入理解二叉树的存储结构，熟练掌握二叉树的先序、中序、后序遍历思想及其应用。 实验要求： 实现一个简单的运算器。通过键盘输入一个包含圆括号、加、减、乘、除等符号组成的算术表达式字符串，输出该算术表达式的值。该运算器的设计要求如下。 (1) 系统应至少能实现加、减、乘、除等运算。 (2) 利用二叉树算法思想求解表达式的值。先构造由表达式构成的二叉树，然后对二叉树进行后序遍历，以此求解算术表达式的值。 实验思路： 依次扫描输入的算术表达式中的每个字符，当遇到运算符时，则将扫描到的运算符与栈顶运算符的优先级比较，若栈顶运算符的优先级小于当前运算符优先级，则将当前运算符入栈； 若栈顶运算符优先级高于当前运算符优先级，则将栈顶运算符出栈，且将操作数栈中的元素出栈两次，由该运算符作为根结点构造二叉树，其左、右孩子结点为操作数栈出栈的操作数。对构造好的二叉树进行后序遍历即可得到后序遍历序列，最后利用栈对该后缀表达式求值。 小结 树在数据结构中占据着非常重要的地位，树反映的是一种层次结构的关系。在树中，每个结点只允许有一个直接前驱结点，但允许有多个直接后继结点，结点与结点之间是一种一对多的关系。 树的定义是递归的。一棵非空树或者为空，或者是由m棵子树T1，T2，…，Tm构成的，这m棵子树又是由其他子树构成的。树中的孩子结点没有次序之分，是一种无序树。 二叉树最多有两棵子树，这两棵子树分别叫作左子树和右子树。二叉树可以看作是树的特例，但是与树不同的是，二叉树的两棵子树有次序之分。二叉树也是递归定义的，二叉树的两棵子树由左子树和右子树构成。 在二叉树中，存在两种特殊的树： 满二叉树和完全二叉树。满二叉树中的每个非叶子结点都存在左子树和右子树，所有的叶子结点都处在同一层次上。完全二叉树的前n个结点结构与满二叉树相同。满二叉树是一种特殊的完全二叉树。 采用顺序存储的完全二叉树可以实现随机存取，实现起来也比较方便。但是，如果二叉树不是完全二叉树，则采用顺序存储会浪费大量的存储空间。因此，一般情况下，二叉树采用链式存储——二叉链表。在二叉链表中，结点有一个数据域和两个指针域，其中，一个指针域指向左孩子结点，另一个指针域指向右孩子结点。 二叉树的遍历分为先序遍历、中序遍历和后序遍历。二叉树遍历的过程就是将二叉树这种非线性结构转换成线性结构。通过将二叉树线索化，不仅可以充分利用二叉链表中的空指针域，而且能很方便地找到指定结点的前驱结点。 在哈夫曼树中，只有叶子结点和度为2的结点。哈夫曼树是带权路径最小的二叉树，通常用于解决最优化问题。 树、 森林和二叉树可以相互进行转换。在实际应用中，树实现起来不是很方便，为此可以将树的问题转化为二叉树的相关问题加以解决。 习题 本书提供在线测试习题，扫描下面的二维码，可以获取本章习题。 在线测试