数据结构zmz5二叉树.pptVIP

树是一类重要的非线性数据结构，是以分支关系定义的层次结构 结点(node)——表示树中的元素，以及构造元素之间关系的指针 结点的度(degree)——结点拥有的子树数 树的度——一棵树中最大的结点度数 叶子(leaf)——度为0的结点，终端结点 分支结点——度不为0的结点，非终端结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的双亲 兄弟(sibling)——同一双亲的孩子 祖先——从根到该结点所经分支上的所有结点 子孙（后裔）——一个节点所有子树上的节点 节点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 堂兄弟——同一层的结点 深度(depth)——树中结点的最大层次数, 又称高度 森林(forest)——m(m?0)棵互不相交的树的集合 无序树——子树之间不存在确定的次序关系 有序树——各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子 6.2 二叉树 为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。 定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树 (不存在度大于2的结点) 子树有左、右之分，且其次序不能任意颠倒 基本形态 有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 问：一棵度为2的树和一棵二叉树有何区别？ 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 二叉树的抽象数据类型定义 性质1： 满二叉树 定义： 性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1?i?n)，有： (1)如果i=1,则结点i是二叉树的根, 如果i1,则其双亲是?i/2? (2)如果2in,则结点i无左孩子; 如果2i?n,则其左孩子是2i (3)如果2i+1n,则结点i无右孩子; 如果2i+1?n,则其右孩子是2i+1 课堂讨论： 不是完全二叉树怎么办？ 特点： 结点间关系蕴含在其存储位置中 浪费空间,k层需要长度多少的数组？ 思考：请画出下列二叉树的图 二叉链表 完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~ 特点 叶子结点只可能在最后层和倒数第二层上出现 特殊形式的二叉树 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1 2 3 11 4 5 8 9 12 13 6 7 10 14 15 1 2 3 11 4 5 8 9 12 6 7 10 1 2 3 4 5 6 7 1 2 3 4 5 6 完全二叉树中可能有 度为1的结点吗？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 性质4： 1 2 3 11 4 5 8 9 12 6 7 10 证明：设完全二叉树的深度为 k 根据第二条性质得 n ≤ 2k -1 且 (2k-1 -1)+1≤ n 即 log2 n k ≤ log2n+1 因为 k 只能是整数， 因此， k = ? log2n ? +1 。 完全二叉树性质 具有n个结点的完全二叉树深度为 _________ ?log2n? +1 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 1 2 3 11 4 5 8 9 12 6 7 10 完全二叉树性质 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 二叉树