大学数据结构课件--第6章 树和二叉树.ppt

《大学数据结构课件--第6章 树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、F6.1树的定义和基本术语F6.2二叉树F6.3遍历二叉树和线索二叉树F6.4树和森林F6.6赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）第6章树和二叉树11.树的定义注：树的定义具有递归性，即树中还有树。由一个或多个（n≥0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n>1时，其余的结点分为m（m≥0）个互不相交的有限集合T1、T2…Tm。每个集合本身又是棵树，被称作这个根的子树。6.1树的定义和基本术语2A只有根结点的

2、树ABCDEFGHIJKLM根子树6.1树的定义和基本术语3树的抽象数据类型定义D是具有相同特性的数据元素的集合。ADTTree{}Tree数据对象D:数据操作P:数据关系R:若D是空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①Root唯一//关于根的说明②Dj∩Dk=//关于子树不相交的说明③…//关于数据元素的说明//至少15个6.1树的定义和基本术语4图形表示法嵌套集合表示法广义表表示法凹入表示法（目录表示法）树的表示方法6.1树的定义和基本术语5

3、①图形表示法：…大连工业大学信息学院生物与食品学院外语学院数学物理电信计算机根子树ABCDEFGH6.1树的定义和基本术语6②广义表表示法：ABCDEFGH根作为由子树森林组成的表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），D）③凹入表示法：ABCDEFGH6.1树的定义和基本术语7ABCDEFGH④嵌套表示法：ABDCEGFH6.1树的定义和基本术语82.若干术语ABCDJEFGHIKLM根----根结点（没有前驱）森林----指m棵不相交的树的集合有序树----结点各子树从左至右有

4、序，不能互换（左为第一）无序树----结点各子树可互换位置双亲----上层的那个结点（直接前驱）孩子----下层结点的子树的根（直接后继）兄弟----同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟----双亲位于同一层的结点（但并非同一双亲）祖先----从根到该结点所经分支的所有结点子孙----该结点下层子树的任一结点6.1树的定义和基本术语9ABCDJEFGHIKLM结点----树中的数据元素结点的度----结点拥有的子树的数目（有几个直接后继度就是几）结点的层次----从根到该结点的层数（根结点算第

5、一层）叶子----度为0的点（终端结点）分支结点----度不为0的点（非终端结点）树的度----所有结点度中的最大值（Max{各结点的度}）树的深度----所有结点中最大的层数（Max{各结点的层次}）（或高度）6.1树的定义和基本术语10二叉树的结构最简单，规律性最强；可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构6.2二叉树111、二叉树的定义①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。基本特

6、征：基本形态：①②③④⑤Æ具有3个结点的二叉树可能有几种不同形态？普通树呢？6.2二叉树---定义122、二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i>0）。问：第i层上至少有个结点？性质2：深度为k的二叉树至多有2k-1个结点（k>0）。性质3：对于任何一棵二叉树，若度2的结点数有n2个，叶子结点数为n0，则n0=n2+1。6.2二叉树---性质13证明性质3：∵二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数)又∵二叉树中全部结点数n=B+1(总分支数+根结

7、点)（除根结点外，每个结点必有一个直接前驱，即一个分支）而总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继)三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+16.2二叉树---性质14满二叉树：深度为k且有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号。489510116121371415231完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全

8、二叉树。特点:（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次数必为h或h+1。489510672316.2二叉树---特例1512311458912136710141512311458912671012345671234566.2二叉树---特例16对于特殊性质的二叉树，还具备以下2个性质：性质4：具有n个结点的完全二叉树的深度必为log2n＋1