数据结构C语言版--第7章--树形结构

第7章树形结构7.1树的基本概念7.2二叉树概念和性质7.3二叉树存储结构7.4二叉树的遍历7.5二叉树的基本运算及其实现7.6二叉树的构造7.8哈夫曼树本章小结7.7线索二叉树7.1树的基本概念7.1.1树的定义7.1.3树的基本术语7.1.2树的表示7.1.4树的性质7.1.5树的基本运算7.1.6树的存储结构7.1.1树的定义形式化定义：树：T＝{K,R}。K是包含n个结点的有穷集合(n0),关系R满足以下条件:(1)有且仅有一个结点k0∈K,它对于关系R来说没有前驱结点,结点k0称作树的根。(2)除结点k0外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。(3)K中每个结点对于关系R来说可以有多个后继结点。递归定义：树是由n(n≥0)个结点组成的有限集合(记为T)。其中,如果n=0,它是一棵空树,这是树的特例；如果n0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分为m(m0)个互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。7.1.2树的表示(1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。下图就是采用这种表示法。ACGJBEDFIHMKL树形表示法(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。HLDKIMCGJEBF文氏图表示法A(3)凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。(4)括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。括号表示法A(B(E,F),C(G(J)),D(H,I(K,L,M)))7.1.3树的基本术语1.结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。2.分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点,其余类推。3.路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。4.孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。5.结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。7.有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树。7.森林：n(n＞0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。7.1.4树的性质性质1树中的结点数等于所有结点的度数加1。证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数(度数),从而可得树中的结点数等于所有结点的度数加1。性质2度为m的树中第i层上至多有mi-1个结点,这里应有i≥1。证明(采用数学归纳法)对于第一层,因为树中的第一层上只有一个结点,即整个树的根结点,而由i=1代入mi-1,得mi-1=m1-1=1,也同样得到只有一个结点,显然结论成立。假设对于第(i-1)层(i＞1)命题成立,即度为m的树中第(i-1)层上至多有mi-2个结点,则根据树的度的定义,度为m的树中每个结点至多有m个孩子结点,所以第i层上的结点数至多为第(i-1)层上结点数的m倍,即至多为mi-2×m=mi-1个,这与命题相同,故命题成立。性质3高度为h的m次树至多有个结点。证明：由树的性质2可知,第i层上最多结点数为mi-1(i=1,2,…,h),显然当高度为h的m次树(即度为m的树)上每一层都达到最多结点数时,整个m次树具有最多结点数,因此有：整个树的最多结点数=每一层最多结点数之和=m0+m1+m2+…+mh-1=。11mmh11mmh性质4具有n个结点的m次树的最小高度为logm(n(m-1)+1)。证明：设具有n个结点的m次树的高度为h,若在该树中前h-1层都是满的,即每一层的结点数都等于mi-1个(1≤i≤h-1),第h层(即最后一层)的结点数可能满,也可能不满,则该树具有最小的高度。其高度h可计算如下：根据树的性质3可得：＜n≤乘(m-1)后得：mh-1＜n(m-1)+1≤mh以m为底取对数后得：h-1＜logm(n(m-1)+1)≤h即logm(n(m-1)+1)≤h＜logm(n(m-1)+1)+1因h只能取整数,所以h=logm(n(m-1)+1)结论得证。111mmh11mmh例7.1含n个结点的三次树的最小高度是多少？解：设含n个结点的(为完全三次树时高度最小)的三次树的最小高度为h,则有：1+3+9+…+3h-2＜n≤1+3+9+…+3h-1(3h-1-1)/2＜n≤(3h-1)/23h-1＜2n+1≤3h即：h=log3(2n+1)7.1.5树的基本运算树的运算主要分为三大类：第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等；第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等；第三类,遍历树中每个结点,这里着重介绍。树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历运算的算法主要有先根遍历和后根遍历两种。注意,下面的先根遍历和后根遍历算法都是递归的。1.先根遍历先根遍历过程为：(1)访问根结点；(2)按照从左到右的次序先根遍历根结点的每一棵子树。2.后根遍历后根遍历过程为：(1)按照从左到右的次序后根遍历根结点的每一棵子树；(2)访问根结点。7.1.6树的存储结构1.双亲存储结构这种存储结构是一种顺序存储结构,用一组连续空间存储树的所有结点,同时在每个结点中附设一个伪指针指示其双亲结点的位置。ADBCGEFA-1B0C0D0E2F2G20123456(a)(b)树的双亲存储结构示意图2.孩子链存储结构孩子链存储结构可按树的度(即树中所有结点度的最大值)设计结点的孩子结点指针域个数。下图(a)的树对应的孩子链存储结构如图(b)所示。ABCFDE(a)GA∧BC∧∧∧D∧∧∧E∧∧F∧∧∧G∧∧∧(b)树的孩子链存储结构示意图3.孩子兄弟链存储结构孩子兄弟链存储结构是为每个结点设计三个域：一个数据元素域,一个该结点的第一个孩子结点指针域,一个该结点的下一个兄弟结点指针域。下图(a)的树对应的孩子兄弟链存储结构如图(b)所示。ABCFDE(a)GA∧B∧D∧C∧E∧G∧∧F∧(b)树的孩子兄弟链存储结构示意图7.2二叉树概念和性质7.2.1二叉树概念7.2.2二叉树性质7.2.3二叉树与树、森林之间的转换7.2.1二叉树概念二叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树的定义是一种递归定义。二叉树有五种基本形态,如下图所示,任何复杂的二叉树都是这五种基本形态的复合。从定义看到,二叉树是一种特殊的树,其表示法也与树的表示法一样,有树形表示法、文氏图表示法、凹入表示法和括号表示法等。在一棵二叉树中,如果所有分支结点都有左孩子结点和右孩子结点,并且叶结点都集中在二叉树的最下一层,这样的二叉树称为满二叉树。下图所示就是一棵满二叉树。可以对满二叉树的结点进行连续编号,约定编号从树根为1开始,按照层数从小到大、同一层从左到右的次序进行。图中每个结点外边的数字为对该结点的编号。ABCDEHIJKFGLMNO123456789101511121314满二叉树若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶结点都依次排列在该层最左边的位置上,则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中每个结点进行连续编号,编号的方法同满二叉树相同。图中每个结点外边的数字为对该结点的编号。ABCDEHIJKFG1234567891011完全二叉树7.2.2二叉树性质性质1非空二叉树上叶结点数等于双分支结点数加1。证明：设二叉树上叶结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数=n0+n1+n2。在一棵二叉树中,所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍,即总的分支数=n1+2n2。由于二叉树中除根结点以外,每个结点都有惟一的一个分支指向它,因此二叉树中有：总的分支数=总结点数-1。由上述三个等式可得：n1+2n2=n0+n1+n2-1即：n0=n2+1性质2非空二叉树上第i层上至多有2i-1个结点,这里应有i≥1。由树的性质2可推出。性质3高度为h的二叉树至多有2h-1个结点(h≥1)。由树的性质3可推出。性质4对完全二叉树中编号为i的结点(1≤i≤n,n≥1,n为结点数)有：(1)若i≤n/2,即2i≤n,则编号为i的结点为分支结点,否则为叶子结点。(2)若n为奇数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为偶数,则编号最大的分支结点(编号为)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点。(3)若编号为i的结点有左孩子结点,则左孩子结点的编号为2i；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+1)。(4)除树根结点外,若一个结点的编号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子结点,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子结点。性质5具有n个(n＞0)结点的完全二叉树的高度为log2(n+1)或log2n+1。由完全二叉树的定义和树的性质3可推出。7.2.3二叉树与树、森林之间的转换1．森林、树转换为二叉树(1)在所有相邻兄弟结点(森林中每棵树的根结点可看成是兄弟结点)之间加一水平连线。(2)对每个非叶结点k,除了其最左边的孩子结点外,删去k与其他孩子结点的连线。(3)所有水平线段以左边结点为轴心顺时针旋转45度。通过以上步骤,原来的森林就转换为一棵二叉树。一般的树是森林中的特殊情况,由一般的树转换的二叉树的根结点的右孩子结点始终为空,原因是一般的树的根结点不存在兄弟结点和相邻的树。ABCDEFGHIABEFGCDHI(a)(c)ABCDEFGHI(b)将森林转换为二叉树的过程2.二叉树还原为森林、树(1)对于一棵二叉树中任一结点k0,沿着k1右孩子结点的右子树方向搜索所有右孩子结点,即搜索结点序列k2,k3,…,km,其中ki+1为ki的右孩子结点(1≤i＜m),km没有右孩子结点。(2)删去k1,k2,…,km之间连线。(3)若k1有双亲结点k,则连