第6章(树)

数据结构NorthChinaElectricPowerUniversityDataStructure华北电力大学计算机科学与工程系Dept.ofComputerScience&EngineeringofNorthChinaElectricPowerUniversity第六章树★基本术语★树的抽象数据类型和存储★二叉树★二叉树的遍历及线索二叉树★树的遍历★哈夫曼树及其应用NorthChinaElectricPowerUniversity§6.1基本术语树型结构是一类重要的非线性数据结构，其中以二叉树最为常用。树是以分支关系定义的层次结构，它为计算机应用中出现的具有层次关系或分支关系的数据提供了一种自然的表示方法。用树结构描述的信息模型在客观世界普遍存在。计算机科学与工程系办公室教研室实验室研究室行政办公室总支办公室计算机教研室软件教研室软件实验室综合实验室数字逻辑实验室组成原理试验室管理信息系统研究室知识工程研究室微机应用研究室NorthChinaElectricPowerUniversity1.树的定义：树是n(n≥0)个结点的有限集T,在一棵非空树中：1)有且仅有一个特定的称为根的结点；2)当n1时,其余结点可分为m(m0)个互不相交的有限集合T1,T2,…,Tm,其中每个集合本身又是一棵树，并且称为根的子树。树的定义可以用如下形式化描述来表示：Tree=(D,R)其中：D是具有相同特性的数据元素的集合；若D只含有一个元素，则R为空集；否则R是D上的某个二元关系H的集合，即R={H}，H为如下描述的二元关系:NorthChinaElectricPowerUniversity2.树的几种表示方法：1)有且仅有一个结点没有前驱，该结点被称为树的根；2)除树根结点外，其余每个结点有且仅有一个前驱结点；3)包含树根结点在内的每个结点，可以有任意多个(包含0个)后继。ABCDEFGHIJKLM1)二元组表示D={A,B,C,D,E,F,G,H,I,J,K,L.M}R={A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J,F,K,F,L,J,M}NorthChinaElectricPowerUniversity4)广义表表示法：A(B(E,F(K,L)),C(G),D(H,I,J(M)))ABEKLFCGHIMDJ2)集合图表示3)凹入表表示NorthChinaElectricPowerUniversityJIHGFEACDB5)树形表示法华电计算机系借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。NorthChinaElectricPowerUniversity树型结构和线性结构的比较树型结构线性结构根结点无前驱结点第一个数据元素无前驱多个叶子结点无后继最后一个数据元素无后继其它数据元素有一个前驱和多个后继其它元素有且仅有一个直接前驱和一个直接后继NorthChinaElectricPowerUniversity3.树中的基本术语：ABCDEFGHIJKLM1.结点、结点的度、树的度2.叶子结点、分支结点3.孩子、双亲、兄弟、堂兄弟、祖先、子孙4.结点的层次、树的深度5.有序树和无序树6.森林BCDEFGHIJKLMNorthChinaElectricPowerUniversity4.树的性质：性质1:树中的结点数等于所有结点的度加1。ABCDEFGHIJKLM证明：除树的根结点外每个结点有且只有一个直接前驱，除树的根结点之外的结点数等于所有结点的分指数。性质2:度为k的树中第i层至多有ki-1个结点。性质3:深度为h的k叉树至多有(kh-1)/(k-1)个结点。性质4:具有n个结点的k叉树的最小深度为└logk(n(k-1)+1┙。NorthChinaElectricPowerUniversity§6.2树的抽象数据类型和存储1.树的基本运算1.Root(T):求树T的根结点，若T为空则返回结果为“空”。2.Parent(T,x):求结点x在树T上的双亲结点，若结点x是树T的根结点或x不在树T中，则返回结果为“空”。3.Initiate(T):置T为空树。4.Child(T,x,i):求树T上结点x在的第i个孩子，若x不在树T上或x没有第i个孩子，则返回结果为“空”。5.Create(x,T1,T2,…,Tk):建立一棵以x为根，以T1,T2,…,Tk为第1,2,3…,k棵子树的树。6.Delete(T,x,i):删除树T上结点x的第i棵子树，若结点x无第i棵子树，则为空操作。7.Traverse(T):按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。NorthChinaElectricPowerUniversity2.树的存储结构1.孩子表示法由于树中每个结点可能有多棵子树，可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，则结点形式有如下两种：datachild1child2childd…datachild1child2childd…degree在第一种形式中，结点是同构的，存储空间浪费较大，在第二种形式中，结点是不同构的，虽能节约存储空间，但实现和运算很不方便。(1)(2)NorthChinaElectricPowerUniversity可以把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，n个结点有n个孩子链表，n个头指针有组成一个线性表，为了便于查找，可用向量表示。typedefstructTNode{intchild;structTNode*next;}*TreeNode;typedefTreenodeTree[maxn];12345623456^^123456^^^^23456^^123456011222^^^^NorthChinaElectricPowerUniversity2.孩子兄弟表示法又称二叉链表表示法，即以二叉链表作树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为first-child和nextsibling。datafirst-childnextsibling123456123456^^^^^^^在孩子兄弟表示法中，要找结点x的第i个孩子,则只要先从first-child域找到第一个孩子结点上，然后沿着该孩子结点的nextsibling域连续走i-1步，便可找到x的第i个孩子。NorthChinaElectricPowerUniversity3.双亲表示法用一个数组顺序地存放树的各个结点，结点存放的顺序是任意的。每一结点有两个域组成：数据域和指针域，分别存储树上结点中的数据元素和用于指示本结点之双亲所在的存储结点。指针域的类型定义有两种：高级语言中的指针类型和整型或子界类型，与之对应的链表分别成为动态链表和静态链表。静态双亲链表的定义：#definesize结点数typedefstructTNode{ElemTypedata;intparent;}TreeNode;typedefTreeNodestalist[size];123456^123456132456dataparent011333结点序号NorthChinaElectricPowerUniversity§6.3二叉树二叉树是一种重要的数据结构类型，它有许多良好的性质和简单的物理表示，它的特点是最多有两个孩子，并且二叉树的子树有左右之分，且其子树的顺序不能任意颠倒。1.二叉树的定义二叉树是由n(n≥0)个结点的有限集合，此集合或者是空的，或者是有一个根结点加上两棵分别称为左右子树的、互不相交的二叉树组成。注意：二叉树和树是两个不同的概念，树的子树不必区分其次序，而二叉树的子树有左右之分，另外，二叉树也不能简单地看成是一有序树，因为只有一棵子树时，无法区分其次序。NorthChinaElectricPowerUniversity2.二叉树的基本形态：(空)根根左子树根右子树根左子树右子树具有三个结点的二叉树具有以下五种基本形态：NorthChinaElectricPowerUniversity3.两种特殊形态的二叉树若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树NorthChinaElectricPowerUniversity1.一棵非空二叉树的第i层最多有2i–1个结点(i1)。证明(采用归纳法)(1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个结点,即树的根结点.(2).假设对于第j层(1ji–1)结论也正确,即第j层最多有2j-1个结点.(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第i–1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大.而第i–1层最多有2i–2个结点已由假设证明,于是,应有22i–2=2i–1证毕.4.二叉树的性质NorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversity2.深度为h的非空二叉树最多有2h-1个结点.证明:由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有20+21+22+…+2i-1+…+2h-1=2h-1证毕.华电计算机系NorthChinaElectricPowerUniversity3.若非空二叉树有n0个叶结点,有n2个度为2的结点,则n0=n2+1证明:设该二叉树有n1个度为1的结点,结点总数为n,有n=n0+n1+n2--------(1)设二叉树的分支数目为B,有B=n-1--------(2)这些分支来自度于为1的结点与度度为2结点,即B=n1+2n2--------(3)联列关系(1),(2)与(3),可得到n0=n2+1证毕.4.具有n个结点的完全二叉树的深度h=log2n+1.证明:(略)推论：n0=n2+2n3+3n4++(m-1)nm+1NorthChinaElectricPowerUniversity5.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)当i=1,则编号为i的结点为二叉树的根结点;若i1,则编号为i的结点的双亲结点的编号为i/2;(2)若in/2,即2i≤n,则编号为i的结点为分支结点,否则为叶子结点,n/2时最后一个分支结点;(3)若n为奇数,则树中每个分支结点都有左右孩子,若n为偶数,则编号最大的分支结点只有左孩子、无右孩子，其余分支结点都有左右孩子；(4)若编号为i的结点有左孩子，则左孩子结点的编号为2i;若编号为i的结点有右孩子，则右孩子的编号为2i+1;NorthChinaElectricPowerUniversity5二叉树的存储结构一.二叉树的顺序存储结构12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ根据完全二叉树的性质5,对于深度为h的完全二叉树,将树中所有结点的数据信息按照编号的顺序依次存储到一维数组BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构华电计算机系NorthChinaElectricPowerUniversity12345678910ABCDEFGHIJ111213123456789101112131415BT[1:15]ABCDEFGHJI2.一般二叉树的顺序存储结构华电计算机系ABCDEFHIJGNorthChinaElectricPowerUniversity对于一般二叉树,只须在二叉树中“添