数据结构第5章 树 ppt课件.ppt

《数据结构第5章 树 ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.1树的基本概念5.1.1树的定义和表示方法5.1.2树的基本术语5.1.3树的性质5.1.4树的基本操作5.1.5树的存储结构作业5.1.1树的定义和表示方法1．树的定义树（Tree）是n（n≥0）个有限数据元素的集合。当n＝0时，称这棵树为空树。在一棵非空树T中：⑴有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。⑵若n>1，除根结点之外的其余数据元素被分成m（m≥0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。可以看出，树的定义是递归的，即

2、用树来定义树。树具有以下两个特点：①树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。②树中所有结点可以有零个或多个后继结点。ABCDEFGHI2．树的表示方法⑵二元组表示法Tree＝(D,R)其中D为树中结点的集合，R为树中结点之间关系的集合。上图的树用二元组表示为：ABCDEFGHI⑴直观表示法（形象描述表示法）树的直观表示法就是以倒着的分支树的形式表示。其特点就是对树的逻辑结构的描述非常直观,如图所示。Tree＝(D,R)其中D={A,B,C,D,E,F,G,H,I}，R=rr={,,

3、,,,,,}⑶集合表示法（文氏图表示法）用集合的形式表示树，就是将根结点视为一个大的集合，其若干棵子树构成这个大集合中若干个互不相交的子集，如此嵌套下去，即构成一棵树的嵌套集合表示。用集合表示法表示前面的树。BADEHIFGC(A(B(D,E(H,I),F),C(G)))CGABEIH⑷凹入表示法集合表示法表示的树⑸广义表表示法树用广义表表示，就是将根作为由子树森林组成的表的名字写在表的左边，这样依次将树表示出来。凹入表示法表示的树广义表表示法表示的树5.1.2树的基本术语1．树的结点包含

4、一个数据元素及若干个指向其子树的分支。2．根结点、父结点、子结点和兄弟结点树中一个结点若无前驱结点，则称为根结点；某结点的直接前驱结点，则称为该结点的父结点（双亲结点）；而该结点（父结点的后继结点）就称子结点；具有同一个双亲的孩子结点互称为兄弟结点。3．结点的度和树的度结点所拥有的子树的个数称为该结点的度。树中各结点度的最大值称为该树的度。4．结点的层数和树的层数结点的层数从根结点开始定义，规定树的根结点的层数为第一层，根的孩子为第二层，以次类推，各结点的层数等于它的双亲结点的层数加1。树中所有结点的最大层数称为树的层数（或称树的深度）。

5、5．叶子结点度为0的结点称为叶子结点，或者称为终端结点。6．分支结点度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。7．有序树和无序树。如果一棵树中结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成不同的树，称这棵树为有序树；反之，则称为无序树。8．森林是m(m≥0)棵互不相交树的集合称为森林。自然界中树和森林是不同的概念，但在数据结构中，树和森林只有很小的差别。任何一棵树，删去根结点就变成了森林。5.1.3树的性质性质1树中的结点数等于所有结点的度数加1。证明：根据树的定

6、义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向它的一个分支一一对应。所以除树根结点之外的结点数等于所有结点的分支数（即度数），从而可得树中的结点数等于所有结点的度数加1。性质2度为k的树中第i层上至多有ki-1个结点(i≥1)。证明：（下面用数学归纳法证明）对于第一层显然是成立的，因为树中的第一层上只有一个结点，而用i=1代入ki-1计算，也同样得到只有一个结点，即ki-1=k1-1=k0=1；假设对于第i-1层（i>1）命题成立，即度为k的树中第i-1层上至多有k(i-1)-1=ki-2个结点，则根

7、据树的度的定义，度为k的树中每个结点至多有k个孩子，所以第i层上的结点数至多为第i-1层上结点数的k倍，即至多为ki-2*k=ki-1个，这与命题相同，故命题成立。性质3深度为h的k叉树至多有(kh-1)/(k-1)个结点。证明：当深度为h的k叉树（即度为k的树）上每一层都达到最多结点数时，所有结点的总和才能最大，即整个k叉树具有最多结点数。可变换为kh-1

8、，第h层（即最后一层）的结点数可能满，也可能不满，则该树具有最小的深度。根据性质3，其深度h的计算公式为：因此得到具有n个结点的一般k叉树的最小深度为logk(n(k-1)+1)h=logk(