中山大学树和二叉树最终版.ppt

1、，第1，2020/7/31页，第6章树和二叉树，了解学习目标树和二叉树类型定义，了解树和二叉树结构差异。熟记二叉树的主要特征，掌握他们的证明方法。掌握二叉树的各种巡回算法，通过算法实现二叉树其他工作的灵活性。精通多种二叉树存储结构和算法构建。第2页，2020/7/31页，重点和难点重点：遍历和应用二叉树和树。困难：构建实现二叉树和树的各种任务的递归算法知识点树的类型定义，二叉树类型定义二叉树存储是指二叉树遍历和其他任务的实现。第3，2020/7/31页，树案例和特征，社会组织结构家族系谱计算机的目录配置，说明层次，一对多逻辑关系，第4页，第5页，2020/7/31页，6.1树定义和基本术语，树

2、(树)所有非空树都只有一个特定节点，称为树的根(根)。在N1中，剩馀节点可被徐璐不相交的m(m0)个有限集T1，T2，Tm整除。其中，每个集本身都是一棵树，称为根子树。特征：非空树至少有一个节点根。树中的每个子树都是徐璐不相交的集合。第6，2020/7/31页，a，仅具有根节点的树，具有子树的树，根，子树，第7，2020/7/31页，树数据关系：如果d为空集，则称为空树如果d仅包含一个数据元素，则关系r为空集。如果d包含多个数据元素，则R=H，H为以下二元关系：(1) D具有唯一名为root的数据元素根，关系H下没有前兆。(2) n1，剩余数据元素m(m0)徐璐不相交(非空)有限集T1，T2，

3、Tm。其中，每个子集本身是符合牙齿定义的树，称为根根的子树，每个子树的根Xi是根根根根。第8，2020/7/31页，默认操作：InitTree(初始条件：树t存在)。操作结果：如果t是空树，则返回TRUE否则返回FALSE。第9，2020/7/31页，树状目录(t)；初始条件：树t存在。操作结果：返回t的深度。根(t)；初始条件：树t存在。操作结果：返回t的根。值(t，cur _ e)；初始条件：具有树t，cur_e是t的节点。操作结果：返回cur_e的值。第10，2020/7/31页，父级(t，cur _ e)；初始条件：具有树t，cur_e是t的节点。操作结果：如果cur_e是t的根以外的

4、节点，则返回父节点，否则返回“空”。LeftChild(T，cur _ e)；初始条件：具有树t，cur_e是t的节点。操作结果：如果cur_e是t的非叶节点，则返回最左侧的孩子，否则返回“空”。RightSibling(T，cur _ e)；初始条件：具有树t，cur_e是t的节点。作业结果：如果cur_e有右兄弟，则返回右兄弟，否则返回“空”。第11，2020/7/31页，traversetree (t，visit()；初始条件：节点作业的应用程序节目函数，树T存在。操作结果：对t中的每个节点依次调用函数visit()一次、一次或多次。如果Visit()失败，则操作失败。Assign(T，

5、cur_e，value)；初始条件：具有树t，cur_e是t的节点。操作结果：为节点cur_e指定值value。ClearTree(初始条件：存在树t)。任务结果：将树t清空为空树。页面12，2020/7/31，insert child(初始条件：树t存在，p指向t中的节点之一，1ip表示节点的角度)。操作结果：删除T中P指向的节点的第I个子树。Adttree、第13页、2020/7/31页、主术语节点(节点):包含指向数据元素和子树的多个分支。节点度数：节点拥有的子树的数量。叶：角度为零的节点。分支节点：角度不是零牙齿的节点。树的度：一棵树中每个节点的最大度值。儿童：节点的子树的根称为该节点

6、的孩子。父节点：子节点的父节点。兄弟：同一个双亲的孩子叫徐璐兄弟。祖先：从根部点到该节点通过的分支中的所有节点。后代：以一个节点为根的子树的所有节点称为该节点的后代。第14页，2020/7/31页，节点层次结构(level):从根节点，根是一层，根孩子是二层。表哥：那位双亲是同一层结上的徐璐表亲。深度：树中节点的最大层次。有序树：从左到右查看树中节点的每个子树时，都有顺序。也就是说，不能徐璐交换。无序树：可以交换树中节点的每个子树，将树视为从左到右没有顺序。树系：m (m0)徐璐不相交的树集合。第15页，2020/7/31页，节点a的度：节点b的度：节点m的度：叶：节点a的孩子：节点b的孩子：

7、节点I的父：节点l的父：节点b C，D凹面表达：类似书目；显示嵌套括号：显示光表。树，页面17，2020/7/31，树和线性结构比较，页面18，2020/7/31，62二叉树，二叉树定义n=0节点的限制，根节点，左侧子树，右侧子树，特征每个节点最多包含两个子树(即不存在的程度大于2的节点)。二叉树子树区分左右，不能随机颠倒顺序。基本形式：A、空二叉树、仅具有根节点的二叉树、右侧子树为空、左侧子树为空、左侧和右侧子树为空。第20页，2020/7/31页，二叉树属性，属性1:二叉树I，证明：I=1，仅根节点，显然在设置I=k时成立，最大2k-1节点i=k 1时的最大节点数： 证明：n1从T设置为中

8、间1的节点数，摘要点数：n=n0 n1 N2 (1)。此外，除根节点外，所有节点都只有一个父节点。 也就是说，如果仅进入一个分支，B是分支数，则N=B 1=N1。Page 23，2020/7/31，几种茄子特殊形式的二叉树，二叉树总深度为K，2k-1节点二叉树。属性每个层中的节点数是最大节点数。所有分支节点的角度均为2。树叶节点都在同一层。Page 24，2020/7/31，从上到下对完全二叉树的整个二叉树节点编号。深度为K，具有N个节点的二叉树(整个二叉树)全部(仅当每个节点对应K深度的二叉树总数时)。特征叶节点只能出现在级别最大的两层。前面k-1层的节点全部为“全部”，层K的节点集中在左侧。第25页，2020/7/31页，判断是否完全二叉树，说明原因。思想：整