数据结构课件第八章.ppt

第 8 章 树与二叉树 ;8.1 树的基本概念 ;图 8.1 树的例子 ; 在这种树型的表示方法中，代表着某个实体的圆圈通常被称作结点，而在所有的结点中，会有一个处于最高层次的结点。 在图8.1(a)中， 代表李富贵的结点是处于最高层次的结点，因为李富贵是其他所有人的祖先；在图8.1(b)中，代表长沙大学的结点是处于最高层次的结点，因为它领导着所有其他结点所代表的机构。这个处于最高层次的结点通常被称为根结点，它就如同树的根一般，其他的所有结点均是以这个“根”为基础得到的， 全部结点在一起就构成了一棵“树”。 ; 例如，一个算术表达式也可以用树型结构来表示。运算符作为根结点，参与运算的两个运算对象分别作为根结点的左、 右两棵子树。图8.1(c)所示的树表示的算术表达式可理解为 a×b+(c-d/e)×f 。  作为一种数据结构，树的定义如下：树(tree)是n≥0个结点的有限集合。n＝0的树称为空树。在任何一棵非空树T中， 有一个特定的结点t∈T，称为T的根结点； 其余的结点T-{t}被分割成m0个不相交的有穷子集T1-Tm，其中每个这样的子集Ti(i≤m)本身又是一棵树， 称为根结点的子树。 由此可见， 树的定义是一个递归定义。 ;图 8.2 树的示意图 ; 图8.2所示是一棵具有14个结点的树T={A，B，…，N}。 其中，A为T的根结点；其余结点T-{A}被分割成三个不相交的子集T1={B, E, F, K, L}， T2={C, G, H, I, M，N}， T3={D，J}。 T1、T2、T3都是T的子树。其中，T1的根结点为B，其余结点T-{B}又分为两个不相交的子集T11={E}，T12={F, K, L}，它们都是T1的子树。T12的根结点为F，并且包含两棵结点数为1的子树， T11的根结点为E，没有子树。 ;;8.1.2 树的逻辑表示 ; 2. 文氏图表示法 文氏图表示法也称集合图表示法，其中每一个圆形对应着一棵树，圆内包含根结点和子树。图8.2所示的以B为根结点的子树为例， 其文氏图表示法如图8.3(a)所示。 ;图 8.3 树的逻辑表示方法 (a) 文氏图表示法； (b) 凹入表示法； (c) 嵌套括号表示法 ; 3. 凹入表示法 凹入表示法中的每个条形对应着一个树根，子树的树根对应的条形较短，并在其直接前驱对应的条形之下，图8.3(a)所示的子树若采用凹入表示法，则如图8.3(b)所示。  4. 嵌套括号表示法 嵌套括号表示法也称为广义表表示法，每棵树的根可作为由子树构成的表的名字，放在表的左边，如图8.3(c)所示。 ;8.1.3 基本术语 1. 结点的度和树的度 每个结点具有的子树数或者说后继结点数被定义为该结点的度(degree)。所有结点的度的最大值被定义为该树的度。如在图8.2的树T中，B、F、H结点的度为2，A、C结点的度均为3， D结点的度为1，其余结点的度均为0。因结点中度最大的为3， 所以树T的度为3。 ; 2. 分支结点和叶结点 度大于0的结点称作分支结点或非终端结点；度等于0的结点称作叶结点或终端结点。在分支结点中，又把度为1的结点叫做单分支结点， 度为2的结点叫做双分支结点，以此类推。如在图8.2的树T中，A、 B、 C、 D、 F、 H都是分支结点， E、 K、 L、 G、 M、 N、 I、 J都是叶结点。在分支结点中， D为单分支结点， B、 F、 H分别为双分支结点，A、C为三分支结点。 ; 3. 儿子结点、 双亲结点和兄弟结点 每个结点的子树的根，或者说每个结点的后继，被习惯地称作该结点的儿子或孩子(child)，相应地，该结点被称作儿子结点的双亲。 具有同一双亲的孩子互称兄弟(sibiling)。 每个结点的所有子树中的结点被称作该结点的子孙。每个结点的祖先被定义为从树根结点到达该结点的路径上经过的所有结点。如在图8.2的树T中， B结点的孩子为E、 F结点，双亲为A结点；E、F互为兄弟； B结点的子孙为E、F、K、L结点。I结点的祖先为A、C结点。对于树T中的其他结点亦可进行同样的分析。由孩子结点和双亲结点的定义及树结构的特点可知：在一棵树中，根结点没有双亲结点， 叶结点没有儿子结点。如在图8.2的树T中，A结点没有双亲结点， E、K、L等结点没有儿子结点。  ; 4. 结点的层数和树的高度 树既是一种递归结构，也是一种层次结构。 树中的每个结点都处在一定的层次上。结点的层