第3章--非线性数据结构.ppt

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

1、计算机软件技术基础©2010WuhanUniversity,LIESMARS主讲人：樊红教授测绘遥感国家重点实验室（武汉大学）第3章非线性数据结构3.1树及其基本概念3.2二叉树3.3二叉树的遍历3.4树的存储结构和遍历3.5树、森林与二叉树的转换3.6霍夫曼树及其应用3.7图及其基本概念3.8图的存储结构3.9图的遍历3.10图的连通性及最小生成树习题3.1树及其基本概念树型结构是一种应用十分广泛的非线性数据结构，它很类似自然界中的树，直观地讲，树型结构是以分支关系定义的层次结构。树(Tree)是n(n≥0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中

2、：(1)有且仅有一个称为该树之根的结点；(2)除根结点之外的其余结点可分为m(m≥0)个互不相交的集合T1，T2，…，Tm，且其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。图3-1树型结构这是一个递归定义，即在树的定义中又用到了树，它显示了树的固有特性。树中的每一个结点都是该树中某一棵子树的根。如图3-1所示的树中，A为根结点，其余的结点分为三个互不相交的有限集合：T1={B，E，F}，T2={C，G，J}，T3={D，H，I}。T1、T2和T3都是A的子树，而它们本身也是一棵树。例如，T1是一棵以B为根的树，其余结点分为互不相交的两个集合{E}

3、和{F}，而{E}和{F}本身又是仅有一个根结点的树。下面结合图3-1，给出树型结构中的一些基本术语。结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。森林：森林是m(m≥0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。双亲(paren

4、t)：一个结点是它的那些子树的根的双亲结点。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如G与E、F、H、I互为堂兄弟。有序树：树T中各子树T1，T2，…，Tn的相对次序是有意义的，则称T为有序树。在有序树中，改变了子树的相对次序就变成了另一棵树。在计算机中表示一棵树时，就隐含着一种确定的相对次序，所以后面我们讨论的都是有序树。3.2二叉树3.2.1二叉树的定义及其性质1．二叉树的定义一个二叉树是一个有限结点的集合，该集合或者为空，或

5、由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。这是一个递归定义，由定义可知二叉树有下面两个主要特点：(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态，如图3-2所示。图3-2二叉树的五种基本形态例3-1画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，如图3-3所示。图3-3有3个结点的所有树的不同形态图3-3有3个结点的所有树的不同形态(2)具有3个结点的二叉树有5种不同的形态，如图3-4所示。图3-43个结点的

6、所有二叉树的不同形态注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。如二叉树T和T′是不同的二叉树，但作为树，它们就是相同的。如图3-5所示。图3-5二叉树与树的区别(a)二叉树T；(b)二叉树T'；(c)树T''2．二叉树的性质二叉树具有下列重要特性。性质1：在二叉树中，第i层的结点数最多有2i-1(i≥1)个。例如：层次i第i层最多结点数120=1221=2322=4k2k−1此性质可以用数学归纳法证明。性质2：在深度为k的二叉树中结点总数最多有2k–1个。由性质1可见，深

7、度为k的二叉树的最大结点数为：=2k−1性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：(1)由于在二叉树中，任一结点的度数小于或等于2，所以其结点总数n=n0+n1+n2(2)设B为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一个分支进入，所以B=n−1即n=B+1而这些分支只能是由度数为1或2的结点所发出，所以B=n1+2n2于是得：n=n1+2n2+1(3)由(1)和(2)得：n0+n1+n2=n1+2n2+1所以n0=n2+1证毕下面介绍两种特殊形态的二叉树，满二叉树和完全二叉树。如果一