数据结构zmz5二叉树.ppt

1、数据结构,主讲：郑梦泽,信息工程学院,请安静,第六章 树和二叉树（上）,数据结构,请安静,6.1 树的定义和基本术语,1数据的逻辑结构,2、数据的存储结构,3、对数据的操作：检索、排序、插入、删除、修改,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个主要问题,Data Structure,树的逻辑结构?,一对多（1：n）,五子棋游戏,树的实例,人类的族谱 各种社会关系 各类分类编码 编译程序的语法树 Internet中的DNS（域名系统）,UNIX文件系统结构,树的实例,树是一类重要的非线性数据结构，是以分支关系定义的层次结构,定义：

2、树(tree)是n(n0)个结点的有限集，其中： n=0，称为空树 有且仅有一个特殊的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的子集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点根 树的定义是递归定义的，各子树也满足上面定义。,树的定义,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),根,子树,叶子,叶子,叶子,ADT Tree 数据对象D: D是

3、具有相同特性的数据元素的集合 数据关系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已存在 操作

4、结果：返回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中非叶子结点,返回其最右孩子;否则,返回空,Trav

5、erseTree(T, visit() 初始条件：树T已存在操作结果：按某种次序对T 的每个元素调用函数visit(),查找类：,基本操作：,树的抽象数据类型定义,插入类：,InsertChild( 如果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

6、+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 )

7、 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,二叉树的存储结

8、构顺序存储结构,适于满二叉树和完全二叉树,补“虚结点”！,思考：将该二叉树进行顺序存储,二叉树的存储结构顺序存储结构,思考：请画出下列二叉树的图,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; BitNode, *BitTree;,一、计算题： 1）高度为h的完全二叉树，最多有几个结点，最少几个？ 2）完全二叉树中编号为11的结点的左右孩子是？ 3）某二叉树共有8个叶子，度为2的结点数为？ 4）某二叉树共有51个结点，它的深度是？ 二、画图题： 1）深度为4