第四章 非线性数据结构.ppt

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

1、第四章非线性数据结构本章内容4.1树4.2图4.1树树和二叉树的递归定义、有关术语二叉树的性质，二叉树的存储结构二叉树的遍历树的存储结构树的遍历树、森林与二叉树的转换树的应用一、树的定义张欢树是由n（n≥0）个结点元素组成的有限集合T。当n=0时称为空树；否则，任意一棵非空树必符合以下两个条件：1）树中有且仅有一个特定的结点元素，称为根的结点；2）除根结点外，其余结点可分为m个互不相交的有限集合T1，T2，T3，，Tm，其中每一个集合本身又是一棵树，称之为根的子树。张亮张丽张阳张琳张唯张明张敏张杰张磊张静树的主要特点（形态与

2、自然界中的树十分相似）1.只有一个根结点2.结点分布呈明显的层次关系3.递归定义BCDEHFAGI树的示意图树的各种表示方法嵌套集合表示法凹入表示法广义表表示法父结点、子结点和边兄弟结点祖先和子孙结点的层次：规定根结点的层次为1，其它结点的层次等于其父结点层次加1。树的深度：树中结点的最大层次数。结点的度：每个结点的子树个数。树的度：树中所有结点的度的最大值。树的有关术语BCDEHFAGI第一层第三层第二层树叶结点：无后继结点。分支结点：度大于0的节点。堂兄弟：其双亲不相同，但其双亲在同一层次的结点互为堂兄弟。有序树和无序树：

3、如果将树中结点的各子树看成从左到右是有次序的，则称该树为有序树，反之则称为无序树。森林：是m（m>0）棵互不相交的树的集合。BCDEHFAGI二.树的逻辑结构分析：对于树中的任意结点来说，若其为根结点，则其无双亲结点；若其为叶子，则其无孩子结点；否则，此结点有且仅有一个双亲结点，并且有若干个孩子结点。结论：树中结点的逻辑关系是一种一对多的关系，体现在一个结点只能有一个双亲，但可以有多个孩子。树的逻辑结构是非线性的。三.二叉树1.二叉树的定义二叉树是一个由n（n≥0）个结点构成的有限集合，它或者为空树，或者是由一个根结点和两个互

4、不相交的被称为左子树和右子树构成，其左、右子树也是二叉树。BCDEGFHA二叉树示意图二叉树的特点（1）度小于等于2，即树中不存在度大于2的结点；（2）有序树，即每个结点的子树有左右之分，不能交换。问：具有3个结点的二叉树可能有几种不同形态？有5种1.度为2的树是二叉树。2.度为2的有序树是二叉树。3.具有三个结点的树可以有以下五种形态。2.两种特殊的二叉树（1）满二叉树定义2：若一棵二叉树的深度为k，其结点总数为2k-1个，则称此二叉树为满二叉树。定义1：在一棵二叉树中，如果所有分支结点都存在左右子树，并且所有叶子结点都在同

5、一层上，这样的二叉树称作满二叉树。（2）完全二叉树BCDEA定义1：在一棵二叉树中，如果至多只有最下面两层上的结点的度数可以小于2，并且最下一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：所有的叶结点都出现在第k层或k-1层。若任一结点，如果其右子树的最大层次为i，则其左子树的最大层次为i或i+1.满二叉树完全二叉树3.二叉树的性质（1）具有n个结点的非空二叉树共有n-1个分支。除了根结点以外，每个结点有且仅有一个双亲结点，即每个结点与其双亲结点之间仅有一个分支存在，因此，具有n个结点的非空二叉树的分

6、支总数为n-1。（2）二叉树的第i层上至多有2i-1个结点。证明：当i=1时，21-1=20=1，结论显然成立。非空二叉树的第1层有且仅有一个结点，即树的根结点。假设对于第j层（1≤j≤i-1）结论也成立，即第j层最多有2j-1个结点。由定义可知，二叉树中每个结点最多只能有两个孩子结点。若第i-1层的每个结点都有两棵非空子树，则第i层的结点数目达到最大，而第i-1层最多有2i-2个结点已由假设证明，于是，应有：2×2i-2=2i-1（3）深度为k的二叉树的结点总数至多为2k-1个证明：由性质2可知，若深度为k的二叉树的每一层的

7、结点数目都达到各自所在层的最大值，则二叉树的结点总数一定达到最大。即有：20+21+22+……+2i-1+2k-1=2k-1（等比数列求和）（4）若一棵二叉树上度为0和度为2的结点数分别为n0和n2，则：n0=n2+1。推广：n0=n2+2*n3+3*n4+…+(m-1)*nm+1完全二叉树的性质：[性质1]一棵具有n个结点的完全二叉树的深度为log2n+1。[性质2]若一棵完全二叉树中共有n个结点，对于其中编号为i（1≤i≤n）的结点，有：1）若i≠1，则i结点的双亲结点为i/2；若i=1，则其为根结点，无双亲。2）

8、若2i≤n，则i结点的左孩子为2i；若2i>n，则i结点无左孩子。3）若2i+1≤n，则i结点的右孩子为2i+1；若2i+1>n，则i结点无右孩子。4.二叉树的存储结构（1）顺序存储结构实现方法：把二叉树的所有结点按照一定的次序（从上到下，从左到右）存储到计算机内存中的一块连