【5A文】树和二叉树.ppt

《【5A文】树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1数据结构6树和二叉树2树的类型定义二叉树的类型定义二叉树的存储结构遍历二叉树和线索二叉树树和森林赫夫曼树主要内容3社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系树型结构实例41.树的类型定义树的定义(Tree)树是由n(n>0)个结点组成的有限集合如果n=0，称为空树如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树递归定义5ABCDEFGHIJKLM根子树树(逻辑上)的特点每棵子

2、树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继6ABCDEFGHIJKLM树的基本概念结点分支结点叶子结点根结点内部结点结点度不为0的结点度为0的结点7树的基本概念结点的度和树的度结点的度即结点拥有的子树个数。树的度是树内各结点的度的最大值。ABCDEFGHIJKLM32132001000008树的基本概念结点的层次和树的深度(高度)结点的层次从根开始定义。根位于第1层，根的孩子位于第2层，余则类推。树的深度即树中结点的最大层次。第1层第2层第3层第4层树的高度为4ABCDEFGHIJKLM9树的基本概念孩子、双亲、兄弟结点的子树的根称为结点的孩子。该结点

3、称为其孩子的双亲。同一双亲的孩子间互称兄弟。ABCDEFGHIJKLM孩子双亲10树的基本概念祖先、子孙结点的祖先是从根到该结点所经分支上的所有结点；以某结点为根的子树中的任一结点都称该结点的子孙。ABCDEFGHIJKLMABCDEFGHIJKLM11树的基本概念森林：m(m>=0)棵互不相交的树的集合BEFKLDHMIJCGACGBDEFKLHMIJ12树的有序性：若树中结点的子树的相对位置不能随意改变，则称该树为有序树，否则称该树为无序树。树的基本概念==有序树无序树ABDCACBD13有序树中最左边的子树的根称其第一个孩子，最右边的子树的根称其最后一个孩子。老

4、大老二老三有序树的第一个孩子和最后一个孩子树的基本概念ABDC14树的常用表示法AEFBIJGHCDFGIJABCEDH凹入表示嵌套集合广义表A(B(E,F),C,D(G(J),H,I))ABEFCDGJHI15为何要重点研究每结点最多只有两个“叉”的树？树太一般，子树的个数无限制，表示困难二叉树的结构最简单，规律性最强可以证明，所有树都能转为唯一对应的二叉树，不失一般性。2.二叉树16二叉树的基本定义二叉树的定义是n≥0个结点的有穷集合该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。逻辑结构：一

5、对二(1:2)基本特征:树的一种每个结点最多有2棵子树(即度<=2)BCADE17二叉树与树的区别树至少应有一个结点，而二叉树可以为空；树的孩子结点没有限制，而二叉树中的每个结点最多有2个孩子结点；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。18二叉树的五种基本形态2.只有树根A1.空树ΦBADE3.只有左子树4.只有右子树BADEBCADE5.左右子树都有19问：具有3个结点的二叉树可能有几种不同形态？有5种Φ二叉树的基本形态201.度为2的树是二叉树。2.度为2的有序树是二叉树。3.具有三个

6、结点的树可以有以下五种形态：1种21二叉树的性质性质1：在二叉树的第i层最多有2i-1个结点(i>=1)证明：当i=1时，显然成立假设当i=k时，也成立，即第k层最多2k-1个结点当i=k+1时，由于二叉树的每个结点最多有2个孩子，所以第k+1层最多有2*2k-1=2(k+1)-1个结点故对于任意i(i>=1)，二叉树的第i层最多有2i-1个结点提问：第i层上至少有个结点？122二叉树的性质性质2：深度为k的二叉树最多有2k-1个结点(k>=1)证明：由性质1可知：第i层最多有2i-1个结点所以总的结点数最多为k=4123423二叉树的性质性质3：对任何一棵二叉树T，

7、若叶子结点数(即度为0的结点数)为n0，度为2的结点数为n2，则n0=n2+1证明：总结点数n=n0+n1+n2设分支数为B，则n=B+1又B=n1+2n2结点无外乎度为0、1、2三种情况”五个手指四个叉”除了树根，其余每个结点”上方”都有一个分支度为2的结点“下方”有2个分支度为1的结点“下方”有1个分支度为0的结点“下方”有0个分支解方程组：得：n0=n2+124树的叶子数与其它结点数的关系设度为m的树中度为0,1,2,…,m的结点数分别为n0,n1,n2,…,nm，结点总数为n，分支数为B，则下面二式成立n=n0+n1+n2+…+nm(1)n=