数据结构41(树)VIP免费

一、树的概念：是n（n>=0）个结点的有限集合。第四章树第四章树4.14.1树的结构定义和基本术语树的结构定义和基本术语非空树:只有一个根结点还可以有m个互不相交的有限集合：T1，T2，…，Tm其中每一个集合Ti(i=1,2,..,m)本身又是一棵树，并且称为根的子树。ABCDEFGHIJA是根T1={B,E,F}T2={C,G,I,J}T3={D,H}在树中，每个结点被定义为它的每个子树的根结点的前驱。二、树的表示：(1)结点连线。隐含：上方结点是下方结点的前驱。(2)集合图表示法:每棵树对应一个圆形，圆内包含根结点和子树。ABCDEFGHIJAEBDHFCGIJ（3）凹入表示法:每棵树的根对应着一个条形，子树的根对应着一个较短的条形。ABCDEFGHIJABEFCGIJDH(1)树的结点：包含一个数据元素及若干指向其子树的分支。(2)结点的度（degree）：结点拥有的子树数。(3)根结点：无前驱。(4)叶子（终端结点）：度为零的结点。无后继。(5)分支结点（非终端结点）：度不为零的结点。除根结点外，分支结点也称内部结点（一个前驱，多个后继）。(6)树的度:树内各结点的度的最大值。ABCDEFGHIJ三、基本术语(7)孩子：结点的子树的根称为该结点的孩子。相应地，该结点称为孩子的双亲。(8)兄弟：同一双亲的孩子之间互为兄弟。(9)堂兄弟:有相同的祖父(10)祖先：结点的祖先是从根到该结点所经分支上的所有结点。(11)子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。ABCDEFGHIJABCDEFGHIJ(12)结点的层次：根为第一层，根的孩子为第二层。(13)树的深度（高度）：树中结点的最大层次。(14)有序树及无序树：如：AABCCB是两棵不同的有序树。(15)森林：是m棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。树和森林可以互相递归定义：Tree=(root,F)F=(T1,T2,…,Tm)(m≥0)Ti=(ri,Fi)当m≠0时，树根和子树森林之间存在下列关系：RF={|1≤i≤m,m>0}四、树的基本操作：求根：ROOT(T);结果：树T的根结点。求双亲：PARENT(T,X);结果：结点X在树T的双亲。求孩子：CHILD(T，X，i);结果：树T上X结点的第i个孩子。建树：CREATE(X,T1,T2,…,Tn);结果：建立一棵以X为根，以T1，T2，…，TN为子树的树剪枝：DELETE(T,X,i);结果：删除树T上结点X的第i棵子树。线性结构(1)第一个数据元素(无前驱)(2)最后一个数据元素(无后继)(3)其它数据元素(一个前驱、一个后继)树结构(1)根结点(无前驱)(2)多个叶子结点(无后继)(3)树中其它结点（有一个直接前驱和多个直接后继）树结构与线性结构的比较二叉树是一种特殊的树结构。特点：每个结点至多只有两棵子树，子树有左右之分，其次序不能任意颠倒，分别称为左右子树。五种形态：4.24.2二叉树二叉树4.2.14.2.1二叉树的定义和基本操作二叉树的定义和基本操作二叉树的基本操作与树的基本操作相类似。特殊的二叉树：(1)满二叉树：二叉树中每一层的结点数都达到最大。(2)完全二叉树：特点：叶子结点只可能在层次最大的两层上出现;对任一结点，若其右分支下的子孙的最大层次为L,则其左分支下的子孙的最大层次必为L或L+1。123456789101112131415123456789101112满二叉树完全二叉树4.2.24.2.2二叉树的性质二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点（i≥1）。用归纳法证明：(1)i=1时,2i-1=1，即只有一个根结点。(2)设对1≤j≤i-1,命题成立，则可以证明j=i时命题也成立。由于第i-1层上至多有2i-2个结点，由于二叉树中每个结点的度至多为2，故第i层上的结点数最多为2i-2*2=2i-1。性质2：深度为k的二叉树至多有2k-1个结点，（k≥1）。k（第i层上的最大结点数）i=1k=2i-1i=1=(1+2+22+…+2k-1)=2k-1性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则有n0=n2+1。设度为1的结点数为n1,总结点数为n，则有n=n0+n1+n2设分支数为B，n=B+1（除根结点外，每一个结点都有一个分支到达）又由于这些分支数是由度为1和度为2的结点发出的，因此，B=n1+2n2n0+n1+n2=n1+2n2+1n0=n2+1性质4：具有n个结点的完全二叉树的深度为log2(n+1)(不小于log2(n+1)的整数)或log2n（不大于log2n的整数)+1。假设深度为k，由性质2，最大结...