第二章jiu常用数据结构及其运算2

《第二章jiu常用数据结构及其运算2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章常用数据结构及其运算2.5树与二叉树2.5.1树及其基本概念2.5.2树的存储结构2.5.3二叉树二叉树的定义及其存储结构二叉树的性质树与二叉树的转换二叉树的遍历2.5.4哈夫曼树及其应用12.6图2.6.1图及其基本概念2.6.2图的存储结构邻接矩阵邻接表2.6.3图的遍历2.6.4图的应用习题22.5树与二叉树2.5.1树及其基本概念2.5.2树的存储结构2.5.3二叉树2.5.4哈夫曼树及其应用32.5树与二叉树2.5.1树及其基本概念树型结构是一种应用十分广泛的非线性数据结构，它很类似自然界中的树，直观地讲，树型结构是以分支关系定义的层次结构。图2-1树型结构4这是一个递

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

3、交的两个集合{E}和{F}，而{E}和{F}本身又是仅有一个根结点的树。6下面结合图2-1，给出树型结构中的一些基本术语。结点：表示树中的元素。结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。双亲(parent)：一个结点是它的那些子树的根的双亲结点。孩子(child)：除根结点外每个结点都是其前趋结点的孩子。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。7结点的层次：根结点的层数为1，其它任何结点的层数等于它

4、的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。森林：森林是m(m≥0)棵互不相交的树的集合。树的度：一棵树上所有结点的度的最大值就是这棵树的度。有序树：树中结点在同层中按从左到右有序排列、不能互换的称为有序树，反之，称为无序树。82.5.2树的存储结构树的存储结构根据应用可以有多种形式，这里只讨论链式存储结构。对于链表中每个结点结构的设计可以有两种形式：a.根据每个结点的子树数设置相应的指针域，结点是异构的。b.每个结点的指针域均为树的度数，结点是同构型，这种形式运算方便，但很浪费空间。9图2-2树的链式存储结构10分析：假设有一棵具有n

5、个结点的k叉树，则有nk个指针域，其中有用的指针域为n-1个，因此空链域的个数为：nk-(n-1)=n(k-1)+1个。对k值进行讨论：n(k-1)+1nkk值无限大时：1k=32/3k=21/2112.5.3二叉树一、二叉树的定义及其存储结构二、二叉树的性质三、特殊形式的二叉树四、树与二叉树的转换五、二叉树的遍历122.5.3二叉树一、二叉树的定义及其存储结构1．二叉树的定义一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。这是一个递归定义，由定义可知二叉树有下面两个主要特点：13(1)每个结点最多只能有两个孩子，即

6、二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态，如图2-3所示。14图2-3二叉树的五种基本形态15例2-1画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，如图2-4所示。图2-4有3个结点的所有树的不同形态16(2)具有3个结点的二叉树有5种不同的形态，如图2-5所示。图2-53个结点的所有二叉树的不同形态17注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。如图2-6所示。二叉树T和T′是不同的二

7、叉树，但作为树，它们就是相同的。18图2-6二叉树与树的区别(a)二叉树T；(b)二叉树T'；(c)树T''192.二叉树的存储结构通常用具有两个指针域的链表作为二叉树的存储结构，其中每个结点由数据域(data)、左指针(Lchild)、右指针(Rchild)组成。LchildDataRchild20二叉树具有下列重要特性。性质1：在二叉树中，第i层的结点数最多有2i-1(i≥1)个。例如：层次i第i层最多结点数120=1221=2322=4…