《树和二叉树 》ppt课件

《《树和二叉树 》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、曾祖父爷爷二爷三爷父亲二叔独生子族谱树是以分支关系定义的层次结构。第十章树树型结构是一类重要的非线性结构。学习重点:树的基本概念二叉树的基本概念、相关操作树和森林与二叉树之间的相互转换二叉树的应用第十章树树的定义和基本术语树(Tree):是具有层次结构的n(n>0)个结点的有限集。ABCDEFGHIJKLM一般树第十章树只有根结点的树A树(Tree):是n(n>0)个结点的有限集。n＞0，有且仅有一个称为根的结点。n＞1，除根结点外，其余结点可分为m(m＞0)个互不相交的有限子集T1,T2,…Tm，其中每个子集都称为根结点的子树。A...T1T2Tmn＞1第十章树和二叉树基本

2、术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数深度(depth)——树中结点的最大层次数第十章树和二叉树ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结

3、点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先第十章树和二叉树树的其它表示方法a.嵌套集合大集合表示树，小集合表示子树，相互嵌套。ABDCEFKLGHJIM第六章树b.层次表示法类似书的编目ABCDEFGHIJKLM第六章树二叉树二叉树的定义二叉树是n(n≥0)个结点的有限集，它或者是空集，或者是由一个根和称为左、右子树的两个互不相交的二叉树组成。二叉树是一个递归定义。树的子树次序不作规定，二叉树的两个子树有左、右之分。树中结点的度没有限制，二叉树中结点的度只能取0、1、2。Φ空二叉树ABCDEF一般二叉树根左子

4、树右子树第十章树和二叉树根据定义，二叉树通常具有5种基本形态:Φ空二叉树A仅有根结点的二叉树A右子树为空的二叉树A左、右子树均非空的二叉树A左子树为空的二叉树关于树的基本术语也都适用于二叉树。二叉树与树的区别树：1、树最少有一个根结点（n>0）2、树的度≥03、树不要求子树顺序二叉树：1、二叉树可以为空(n≥0)2、二叉树的度≤23、二叉树是有序树，有左、右子树之分。例10-1：试写出具有3个结点的所有不同形态的树和二叉树。二叉树的性质性质1:在二叉树的第i层上至多有2i-1个结点(i≥1)。归纳法证明:(1)i=1，只有一个根结点，2i-1=20=1，正确；(2)假设i-1

5、成立，即第i-1层上至多有2i-2个结点；(3)由于二叉树的结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2i-2=2i-1。性质2:深度为k的二叉树至多有2k–1个结点(k≥1)。∑i=1k(第i层上的最大结点数)＝∑i=1k2i-1＝2k–1练习:归纳法证明。引论:一棵树有n个结点，则必有n–1条分支。证明:除根结点外，其它结点都有一个分支进入，设B为分支总数，故n=B+1，故B=n-1得证。ABCDEF性质3:对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明:(1)已知，终端结点数为n0，度为2

6、的结点数为n2，设度为1的结点数为n1，由于二叉树中的所有结点的度只能为0、1、2，故二叉树的结点总数为n=n0+n1+n2；(2)除根结点外，其它结点都有一个分支进入，设B为分支总数，故n=B+1，由于这些分支均是由度为1或2的结点引出的，所以有B=n1+2n2，故n=n1+2n2+1，由(1)和(2)，可得n0+n1+n2=n1+2n2+1，故有n0=n2+1。两种特殊形态二叉树:满二叉树、完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。特点:1245满二叉树367(1)每一层的结点数都达到最大结点数。(2)叶子结点在最大层。(3)任一结点，其左、右分支下

7、的子孙的最大层次相等。对满二叉树的结点进行连续编号，从根结点起，自上而下，自左至右，1、2、3、……、2k-1。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。12453612345非完全二叉树12453完全二叉树(1)特点:(1)叶子结点只可能在层次最大的两层上出现。(2)对任一结点，若其右分支的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。完全二叉树(2)1245367满二叉树和完全二叉树的区别：1、满二叉树