第四章树和二叉树.pptx

第4章 树和二叉树内容提要 特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n）F 4.1 树的定义和基本术语F 4.2 二叉树F 4.3 遍历二叉树和线索二叉树F 4.5 树和森林F 4.6 赫夫曼树及其应用4.1 树的定义和基本术语1.树的定义由一个或多个（n≥ 0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n1时，其余的结点分为m（m≥ 0）个 互不相交的有限集合T1、T2…Tm。每个 集合本身又是棵树，被称作这个根的子树。注：树的定义具有递归性，即树中还有树。ABCDEFGHIJKLM4.1 树的定义和基本术语只有根结点的树A根子树若D是空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：① Root唯一//关于根的说明② Dj∩Dk=//关于子树不相交的说明③ …//关于数据元素的说明4.1 树的定义和基本术语树的抽象数据类型定义ADT Tree {D是具有相同特性的数据元素的集合。数据对象D:数据关系R://至少15个数据操作P:}Tree4.1 树的定义和基本术语树的表示方法图形表示法嵌套集合表示法广义表表示法凹入表示法（目录表示法）根上海工业大学…生物与食品学院信息学院外语学院数学物理电信计算机ABCD子树HEFG4.1 树的定义和基本术语①图形表示法：ABCEAFBCDGHHFGED4.1 树的定义和基本术语②广义表表示法：根作为由子树森林组成的表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），D）③凹入表示法：AACBCDHFGE4.1 树的定义和基本术语④嵌套表示法：DBEFGHABCDEFGHIJMKL4.1 树的定义和基本术语2.若干术语 根----根结点（没有前驱） 森林----指m棵不相交的树的集合有序树----结点各子树从左至右有序，不能互换（左为第一）无序树----结点各子树可互换位置 双亲----上层的那个结点（直接前驱） 孩子----下层结点的子树的根（直接后继） 兄弟----同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟----双亲位于同一层的结点（但并非同一双亲） 祖先----从根到该结点所经分支的所有结点 子孙----该结点下层子树的任一结点ABCDEFGHIJKLM例如A只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树树的基本术语1层A2层BCDheight= 43层EFGHIJ4层KLM结点结点的度叶结点分支结点树的深度树的度森林子女双亲兄弟祖先子孙结点层次ABCDEFGHIJMKL4.1 树的定义和基本术语 结点----树中的数据元素 结点的度----结点拥有的子树的数目（有几个直接后继度就是几）结点的层次----从根到该结点的层数（根结点算第一层） 叶子----度为0的点（终端结点） 分支结点----度不为0的点（非终端结点） 树的度----所有结点度中的最大值（Max{各结点的度}）树的深度----所有结点中最大的层数（ Max{各结点的层次} ）（或高度）4.2 二叉树 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。 1. 二叉树的定义2. 二叉树的性质3. 二叉树的存储结构①②③④⑤?4.2 二叉树---定义1、二叉树的定义基本特征：① 每个结点最多只有两棵子树（不存在度大于2的结点）；② 左子树和右子树次序不能颠倒（有序树）。基本形态： 具有3个结点的二叉树可能有几种不同形态？普通树呢？4.2 二叉树---性质2、二叉树的性质 性质1：在二叉树的第i层上至多有2i-1个结点（i0）。问：第i层上至少有 个结点？ 性质2：深度为k的二叉树至多有2k-1个结点（k0）。 性质3：对于任何一棵二叉树，若度2的结点数有n2个， 叶子结点数为n0，则n0=n2+1。4.2 二叉树---性质证明性质3：∵二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数)又∵ 二叉树中全部结点数n=B+1(总分支数 + 根结点)（除根结点外，每个结点必有一个直接前驱，即一个分支）而 总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继)三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+1123456789101112131415123456789104.2 二叉树---特例满二叉树：深度为k且有 2k-1个结点的二叉树。 特点：每一层上的结点数都是最大结点数。 可以对满二叉树的