第6章-树

数据结构第6章树第6章树•知识点树的基本概念与术语二叉树及二叉树的存储结构二叉树的遍历及线索二叉树一般树和二叉树的转换哈夫曼树及哈夫曼编码•难点二叉树遍历算法的设计利用二叉树遍历算法，解决简单应用问题哈夫曼树的算法•要求熟练掌握以下内容:树的基本概念和术语二叉树定义和存储结构二叉树遍历的概念和二叉树遍历的算法哈夫曼树的建立了解以下内容：树和二叉树之间的相互转换方法线索二叉树的概念哈夫曼编码第6章目录•6-1树的定义和术语•6-2二叉树•6-3遍历二叉树和线索二叉树•6-4二叉树的转换•6-5二叉树树的应用•6-6哈夫曼树及其应用•小结•实验6树子系统•习题66-1树的定义和术语6-1树的定义1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。在任意一棵非空树T中：（1）有且仅有一个特定的称为树根（Root）的结点，根结点无前趋结点；（2）当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树，并且称为根的子树。树的定义采用了递归定义的方法，即在树的定义中又用到树的概念，这正好反映了树的固有特性。1234图6-1树结构示意图2．树的其它表示法图6-1是树的结构表示法，是一种直观的画法，其特点是对树的逻辑结构的描述非常直观、清晰。是使用最多的一种描述方法。除此以外，还有以下几种描述树的方法：ABCHGFEDJI（1）嵌套集合法嵌套集合法，也称为文氏图法（VennDiagram），它是用集合以及集合的包含关系来描述树形结构，每个圆圈表示一个集合，套起来的圆圈表示包含关系。图6-2(a)就是一棵树的嵌套集合表示。ABCEIJDFGH图6-2（a）嵌套集合表示(2)圆括号表示法圆括号表示法也称为广义表表示法，它是使用括号将集合层次与包含关系显示出来。下式即是图6-1所示树的圆括号表示法：(A(B(D,E(I,J),F),C(G,H)))(3)凹入法凹入法是用不同宽度的行来显示各结点，而行的凹入程度体现了各结点集合的包含关系，图6-1所示树的凹入法表示如图6-2(b)。树的凹入表示法主要用于树的屏幕显示和打印输出。ABCEDJFGH图6-2（b）凹入表示法I6-1-2基本术语（1）结点——树的结点包含一个数据及若干指向其子树的分支。（2）结点的度——结点所拥有的子树数称为该结点的度（Degree）。（3）树的度——树中各结点度的最大值称为该树的度。（4）叶子（终端结点）——度为零的结点称为叶子结点。（5）分枝结点——度不为零的结点称为分支结点。（6）兄弟结点——同一父亲结点下的子结点称为兄弟结点。（7）层数——树的根结点的层数为1，其余结点的层数等于它双亲结点的层数加1。（8）树的深度——树中结点的最大层数称为树的深度（或高度）。（9）森林——零棵或有限棵互不相交的树的集合称为森林。在数据结构中，树和森林并不象自然界里有一个明显的量的差别。任何一棵树，只要删去根结点就成了森林，见图6-3。(a)树(b)移去根结点后成为森林图6-3（10）有序树和无序树——树中结点的各子树从左到右是有次序的（即不能互换位置），称这样的树为有序树；否则称为无序树。ABCHGFEDJIKJBCDEFGHIK6-2二叉树6-2-1二叉树的定义1．定义二叉树是有n（n=0）个结点的有限集合。（1）该集合或者为空（n=0）；（2）或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树；（3）左子树和右子树同样又都是二叉树。通俗地讲：在一棵非空的二叉树中，每个结点至多只有两棵子树，分别称为左子树和右子树，且左右子树的次序不能任意交换。所以，二叉树是特殊的有序树。2．二叉树的形态根据定义，二叉树可以有五种基本形态，如图6-4所示。(a)(b)(c)(d)(e)图6-4二叉树的基本形态其中：（a）空二叉树；（b）仅有根结点的二叉树；（c）右子树为空的二叉树；（d）左子树为空的二叉树；（e）左、右子树均非空的二叉树。ФLchildLchildRchildRchild3．二叉树的基本操作：（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层上最多有2i–1个结点（i≥1）。一棵非空二叉树的第一层有1个结点，第二层最多有2个结点，第三层最多有4个结点……，利用归纳法即可证明第i层上最多有2i–1个结点。性质2深度为h的二叉树中，最多具有2h－1个结点（h≥1）。证明：根据性质1，当深度为h的二叉树每一层都达到最多结点数时，它的和（n）最大，即：∴命题正确。（1）满二叉树一棵深度为h，且有2h‐1个结点的二叉树称为满二叉树。图6-5所示是一棵深度为4的满二叉树，其特点是每一层上的结点都具有最大的结点数。如果对满二叉树的结点进行连续的编号，约定编号从根结点起，从上往下，自左向右（如图6-5），由此可以引出完全二叉树的定义。123876541091112131415图6-5满二叉树（2）完全二叉树深度为h，有n个结点的二叉树，当且仅当每一个结点都与深度为h的满二叉树中编号从1至n的结点一一对应时，称此二叉树为完全二叉树。如图6-6（a）所示为一棵完全二叉树。ABCHGFEDJI图6-6（a）一棵完全二叉树如图6-6（b）所示则不是完全二叉树。图6-6（b）一棵非完全二叉树完全二叉树除最后一层外，其余各层都是满的，并且最后一层或者为满，或者仅在右边缺少连续若干个结点。ABCGFEDH性质3对于一棵有n个结点的完全二叉树，若按满二叉树的同样方法对结点进行编号，（见图6-5）则对于任意序号为i的结点，有：（1）若i1，则序号为i的结点的父结点的序号为i/2；若i＝1，则序号为i的结点是根结点。（2）若2i≤n，则序号为i的结点的左孩子结点的序号为2i；若2in，则序号为i的结点无左孩子。（3）若2i＋1≤n，则序号为i的结点的右孩子结点的序号为2i＋1；若2i＋1n，则序号为i的结点无右孩子。证明略。性质4具有n（n0）个结点的完全二叉树（包括满二叉树）的深度（h）为：证明：由性质2和完全二叉树定义可知，当完全二叉树的深度为h、结点个数为n时有：2h－1–1n≤2h-1即：2h－1≤n2h对不等式取对数有：h–1≤log2nh由于h是整数，所以有h＝。1log2n1log2n性质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＋1n0＝n2＋1∴命题正确。6-2-3二叉树的存储1．顺序存储结构二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。一般可以采用一维数组或二维数组的方法进行存储。（1）一维数组存储法二叉树中各结点的编号与等深度的完全二叉树中对应位置上结点的编号相同。其编号过程为：首先把根结点的编号定为1，然后按照层次从上至下、从左到右的顺序，对每一个结点编号。当双亲结点为i时,其左孩子的编号为2i，其右孩子的编号为2i+1。在图6-7(a)中,各结点右边的数字就是该结点的编号。如果按从上至下、从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增加一些并不存在的空结点，使之成为一棵完全二叉树的形式才能用一维数组进行存储。图7-6（a），经过改造以后成为图6-7（b）所示的完全二叉树。ABCHEDJI16510231213图6-7(a)一般二叉树图6-7(b)改造为完全二叉树ABCEDFGH其顺序存储状态示意图如图7-6（c）。图6-7(c)二叉树在一维数组中的存储显然，这种存储结构会造成空间的大量浪费，如图6-8(a)所示，一棵4个结点的二叉树，却要扩充为(b)的完全二叉树，分配14个存储单元如(c)。可以证明，深度为h的（右向）单支二叉树，虽然只有h个结点，却需分配2h-1个存储单元。ABCABCD图6-8(a)原二叉树图6-8(b)改造后的完全二叉树D图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二叉树二维数组存储示意图顺序存储小结：（1）当二叉树为满二叉树或完全二叉树时，采用一维数组可以节省存储空间；（2）当二叉树层数高而结点较少时，采用二维数组比较好，只要n行3列存储空间；（3）顺序存储的优点是找父结点的位置方便；（4）顺序存储缺点是进行插入或删除操作要进行大量的数据移动，且存储空间的扩充不方便。（1）二叉链表存储二叉链表结点由一个数据域和两个指针域组成，其结构如下：lchilddatarchild其中：data为数据域，存放结点的数据信息；lchild为左指针域，存放该结点左子树的存储地址；rchild为右指针域，存放该结点右子树的存储地址。当左子树或右子树不存在时，相应指针域值为空，用符号∧表示。设一棵二叉树如图6-10所示，其二叉链表的存储表示如图6-11所示。2．链式存储结构二叉树的链式存储结构是用链表来表示二叉树，即用链指针来指示结点的逻辑关系。通常有下面两种形式。图6-10二叉树图6-11二叉树的链式存储示意图容易证明，在含有n个结点的二叉链表中有n+1个空指针域。利用这些空指针域存储其它有用信息，从而可以得到另外一种存储结构——线索化链表，关于这一概念将在6-3-3节介绍。下面给出二叉树的二叉链表描述：typedefstructBT//定义二叉树结构体{datatypedata;//定义数据域BT*lchild;//定义结点的左指针BT*rchild;//定义结点右指针}BT;//将BT定义为指向二叉树结点结构体的指针类型（2）三叉链表存储三叉链表结点由一个数据域和三个指针域组成，其结构如下：lchilddatarchildparent其中：data为数据域，存放结点的数据信息；lchild为左指针域，存放该结点左子树的存储地址；rchild为右指针域，存放该结点右子树的存储地址。parent为父指针域，存放结点的父结点存储地址。这种存储结构既便于查找左、右子树的结点，又便于查找父结点；但付出的代价是，增加了存储空间的开销。图6-12给出了二叉树的三叉链表存储示意图。6-3遍历二叉树和线索二叉树6-3-1遍历二叉树二叉树的遍历是指按某种顺序访问二叉树中的所有结点，使得每个结点都被访问，且仅被访问一次。通过一次遍历，使二叉树中结点的非线性序列转变为线性序列。也就是说，使得遍历的结点