数据结构zmz5二叉树.ppt

数据结构,主讲：郑梦泽,信息工程学院,请安静,第六章 树和二叉树（上）,数据结构,请安静,6.1 树的定义和基本术语,1数据的逻辑结构,2、数据的存储结构,3、对数据的操作：检索、排序、插入、删除、修改,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个主要问题,Data Structure,树的逻辑结构?,一对多（1：n）,五子棋游戏,树的实例,人类的族谱 各种社会关系 各类分类编码 编译程序的语法树 Internet中的DNS（域名系统）,UNIX文件系统结构,树的实例,树是一类重要的非线性数据结构，是以分支关系定义的层次结构,定义：树(tree)是n(n0)个结点的有限集，其中： n=0，称为空树 有且仅有一个特殊的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的子集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点根 树的定义是递归定义的，各子树也满足上面定义。,树的定义,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),根,子树,叶子,叶子,叶子,ADT Tree 数据对象D: D是具有相同特性的数据元素的集合 数据关系R: 若D为空集，则称为空树 否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互不相交的 有限集T1, T2, , Tm，其中每一棵子集本身又是 一棵符合本定义的树，称为根root的子树 基本操作： 查找类操作 插入类操作 删除类操作 ADT Tree,树的抽象数据类型定义,基本操作：,TreeEmpty(T) 初始条件：树T已存在 操作结果：空树，返回 TRUE;否则 FALSE,TreeDepth(T) 初始条件：树T已存在 操作结果：返回 T 的深度,查找类：,Root(T) 初始条件：树T已存在 操作结果：返回T的根,Value(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：返回cur_e 的值,Parent(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非根结点,返回其双亲;否则,返回空,树的抽象数据类型定义,LeftChild(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非叶子结点,返回其最左孩子;否则,返回空,RightChild(T, cur_e) 初始条件：树T已存在,cur_e是T中结点 操作结果：若cur_e是T中非叶子结点,返回其最右孩子;否则,返回空,TraverseTree(T, visit() 初始条件：树T已存在 操作结果：按某种次序对T 的每个元素调用函数visit(),查找类：,基本操作：,树的抽象数据类型定义,插入类：,InsertChild(&T, &p,i,c) 初始条件：树T存在,p指向T中结点,1i p指结点度+1,非空树c与T不相交 操作结果：将以c为根的树插入为T中p指结点的第i棵子树,CreateTree(&T, definition) 初始条件： definition给出树的定义 操作结果：按definition构造树T,Assign(T, cur_e, value) 初始条件：树T已存在,cur_e是T中结点 操作结果：结点cur_e赋值为value,InitTree(&T) 操作结果：构造空树T,基本操作：,树的抽象数据类型定义,DeleteChild(&T, &p,i) 初始条件：树T存在,p指向T中结点,1i p指结点度 操作结果：删除T中p指结点的第i棵子树,ClearTree(&T) 初始条件：树T 已存在 操作结果：将树T 清为空树,DestroyTree(&T) 初始条件：树T 已存在 操作结果：销毁树T,删除类：,基本操作：,树的抽象数据类型定义,结点(node)表示树中的元素，以及构造元素之间关系的指针 结点的度(degree)结点拥有的子树数 树的度一棵树中最大的结点度数 叶子(leaf)度为0的结点，终端结点 分支结点度不为0的结点，非终端结点 孩子(child)结点子树的根称为该结点的孩子 双亲(parents)孩子结点的上层结点叫该结点的双亲,树的基本术语,兄弟(sibling)同一双亲的孩子 祖先从根到该结点所经分支上的所有结点 子孙（后裔）一个节点所有子树上的节点 节点的层次(level)从根结点算起，根为第一层，它的孩子为第二层 堂兄弟同一层的结点 深度(depth)树中结点的最大层次数, 又称高度,树的基本术语,森林(forest)m(m0)棵互不相交的树的集合 无序树子树之间不存在确定的次序关系 有序树各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子,任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林,树的基本术语,树的表示,图形表示法 嵌套集合表示法 广义表表示法 凹入表示法,嵌套集合表示法,图型表示法,树的表示,(A(B(E(k,L),F),C(G),D(H(M),I,J),括号(广义表)表示法,图型表示法,树的表示,图型表示法,树的表示,结点A的度： 结点B的度： 结点M的度：,叶子：,结点A的孩子： 结点B的孩子：,结点I的双亲： 结点L的双亲：,结点B，C，D为 结点K，L为,树的度：,结点A的层次： 结点M的层次：,树的深度：,结点F，G为 结点A是结点F，G的 结点F，G 是A结点的,3,2,0,B, C, D,E, F,3,1,4,4,K, L, F, G, M, I, J,D,E,兄弟,兄弟,堂兄弟,祖先,子孙,请同学回答,数据结构,请安静,6.2 二 叉 树,6.2 二叉树,为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。,6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构,定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树 (不存在度大于2的结点) 子树有左、右之分，且其次序不能任意颠倒 基本形态,二叉树的定义,有关二叉树下列说法正确的是（ ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 问：一棵度为2的树和一棵二叉树有何区别？ 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。,二叉树的定义,二叉树的抽象数据类型定义,ADT BinaryTree 数据对象D: 数据关系R: 基本操作 P： ADT BinaryTree,若D=，则R= ； 若D，则R= H；存在二元关系： root 唯一 /关于根的说明 DlDr= /关于子树不相交的说明 /关于二元关系的说明 /关于左子树和右子树的说明,D是具有相同特性的数据元素的集合。,/至少有20个,性质1：,在二叉树的第 i 层上至多有_个结点(i1),第一层： 第二层： 第三层： 第i层：,只有一个根结点：21-1 = 20 = 1；,二叉树上每个结点至多有两棵子 树， 则第 i 层的结点数 = 2i-1 。,二叉树的性质,最多：20 2 = 21 = 2；,最多：21 2 = 22 = 4；,2i-1,二叉树的性质,思考：,具有 n 个节点的二叉树的深度 最小 _ ，最大_,高度 h 的二叉树最多有2h-1个节点（性质2） n 2h-1 h log2(n+1),解答：,性质2：,深度为 k 的二叉树上至多含 _个结点（k1）,证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1,2k-1,性质3：对任何一棵二叉树T，如果其叶子结点数 为n0，度为2的结点数为n2，则n0=n2+1,证明： 设 n1 为度为1的节点数 二叉树中所有节点的度2 结点总数 n=n0+n1+n2 除根节点外，其余节点都是“别人”的孩子 又 叶子（n0）没有孩子！ 所有的孩子数n-1=n1+2n2 n=n1+2n2+1=n0+n1+n2 n0=n2+1,二叉树的性质,满二叉树 定义：,特点：每一层上的结点数都是最大结点数,指的是深度为k且含有2k-1个结点的二叉树,特殊形式的二叉树,完全二叉树 定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为 特点 叶子结点只可能在最后层和倒数第二层上出现,特殊形式的二叉树,性质4：,证明：设完全二叉树的深度为 k 根据第二条性质得 n 2k -1 且 (2k-1 -1)+1 n 即 log2 n k log2n+1 因为 k 只能是整数， 因此， k = log2n +1 。,完全二叉树性质,具有n个结点的完全二叉树深度为 _,log2n +1,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有： (1)如果i=1,则结点i是二叉树的根, 如果i1,则其双亲是i/2 (2)如果2in,则结点i无左孩子; 如果2in,则其左孩子是2i (3)如果2i+1n,则结点i无右孩子; 如果2i+1n,则其右孩子是2i+1,完全二叉树性质,二叉树性质小结,二叉树的第 i 层上至多有2i-1 个结点,性质1：,性质2：,深度为 k 的二叉树上至多含 2k-1 个结点,性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1,性质4：,具有n个结点的完全二叉树的深度为 log2n+1 ,性质5：对完全二叉树有： (1) 如果i1,则其双亲是i/2 (2)如果2in,则结点i无左孩子;否则其左孩子是2i (3)如果2i+1n,则结点i无右孩子;否则其右孩子是2i+1,课堂讨论：, 二叉树是不是树的特殊情况？ 答：不是！它是单独定义的一种树状结构，并非一般树的特例。 它的子树有顺序规定，分为左子树和右子树。不能随意颠倒。 ：满二叉树和完全二叉树有什么区别？ 答：满二叉树是完全二叉树的一个特例。 完全二叉树最底层却允许在右边缺少连续若干个结点。,5. 深度为9的完全二叉树中至少有 个结点。 )9 )8 ) )91,4.深度为k 的二叉树的结点总数，最多为 个。 )k-1 ) log2k ) k )k,3. 树中各结点的度的最大值称为树的 。 ) 高度 ) 层次 ) 深度 ) 度,课堂讨论：,二叉树的存储结构,顺序存储结构,链式存储结构,一、完全二叉树 实现：按结点层次编号，依次存放二叉树中的数据元素（用数组实现）,A B C D E F G H I,问：顺序存储后能否唯一对应一颗二叉树？ 有规律：下标值为i的结点，其左孩子的下标值必为2i，其右孩子的下标值必为2i1（即性质5）,二叉树的存储结构顺序存储结构,不是完全二叉树怎么办？ 特点： 结点间关系蕴含在其存储位置中 浪费空间,k层需要长度多少的数组？,a,b,c,d,e,0,0,0,0,f,g,二叉树的存储结构顺序存储结构,适于满二叉树和完全二叉树,补“虚结点”！,思考：将该二叉树进行顺序存储,二叉树的存储结构顺序存储结构,思考：请画出下列二叉树的图,a,b,c,0,d,e,f,0,0,g,h,二叉树的存储结构顺序存储结构,a,b,c,d,0,e,0,0,0,0,0,f,二叉链表,在n个结点的二叉链表中，有n+1个空指针域,二叉树的存储结构链式存储结构,typedef struct BitNode TElemType data; struct BitTNode *lchild, *rchild;