一、树的概念：是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=1k=2i-1i=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，最大结...
