数据结构zmz52叉树.ppt

数据结构;数据结构; 1．数据的逻辑结构 ;五子棋游戏;/ (root); 树是一类重要的非线性数据结构，是以分支关系定义的层次结构;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;A;ADT Tree { 数据对象D: D是具有相同特性的数据元素的集合 数据关系R: 若D为空集，则称为空树 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互不相交的 有限集T1, T2, …, Tm，其中每一棵子集本身又是 一棵符合本定义的树，称为根root的子树 基本操作： 查找类操作 插入类操作 删除类操作 } ADT Tree;基本操作：;LeftChild(T, cur_e)初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非叶子结点,返回其最左孩子;否则,返回空;插入类：;DeleteChild(T, p,i)初始条件：树T存在,p指向T中结点,1≤i ≤ p指结点度 操作结果：删除T中p指结点的第i棵子树;结点(node)——表示树中的元素，以及构造元素之间关系的指针 结点的度(degree)——结点拥有的子树数 树的度——一棵树中最大的结点度数 叶子(leaf)——度为0的结点，终端结点 分支结点——度不为0的结点，非终端结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的双亲 ;兄弟(sibling)——同一双亲的孩子 祖先——从根到该结点所经分支上的所有结点 子孙（后裔）——一个节点所有子树上的节点 节点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 堂兄弟——同一层的结点 深度(depth)——树中结点的最大层次数, 又称高度;森林(forest)——m(m?0)棵互不相交的树的集合 无序树——子树之间不存在确定的次序关系 有序树——各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子 ;树的表示 ;G;(A(B(E(k,L),F),C(G),D(H(M),I,J)));图型表示法 ;结点A的度： 结点B的度： 结点M的度： ;数据结构;6.2 二叉树;定义：二叉树是n(n?0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树 (不存在度大于2的结点) 子树有左、右之分，且其次序不能任意颠倒 基本形态 ;有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 问：一棵度为2的树和一棵二叉树有何区别？ 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。;二叉树的抽象数据类型定义;性质1：;二叉树的性质 ;性质3：对任何一棵二叉树T，如果其叶子结点数 为n0，度为2的结点数为n2，则n0=n2+1 ; 满二叉树 定义：; 完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为~ 特点 叶子结点只可能在最后层和倒数第二层上出现 ;1;性质4：;性质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 ;二叉树性质小结;课堂讨论：;5. 深度为9的完全二叉树中至少有 个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1;二叉树的存储结构 ;一、完全二叉树 实现：按结点层次编号，依次存放二叉树中的数据元素（用数组实现）;不是完全二叉树怎么办？ 特点： 结点间关系蕴含在其存储位置中 浪费空间,k层需要长度多少的数组？;A;思考：请画出下列二叉树的图;二叉链表;一、计算题： 1）高度为h的完全二叉树，最多有几个结点，最少几个？ 2）完全