数据结构zmz5二叉树课件

1、数据结构zmz5二叉树主讲：郑梦泽主讲：郑梦泽信息工程学院信息工程学院请安静请安静 第六章第六章 树和二叉树（上）树和二叉树（上）数据结构zmz5二叉树请安静请安静 6.1树的定义和基本术语树的定义和基本术语数据结构zmz5二叉树 1数据的逻辑数据的逻辑结构结构 2、数据的存储结构、数据的存储结构 3、对数据的操作：检索、排序、插入、删除、修改、对数据的操作：检索、排序、插入、删除、修改A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数据结构的三个主要问题数据结构的三个主要问题 数据结构zmz5二叉树

2、五子棋游戏.树的实例数据结构zmz5二叉树/ (root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱人类的族谱各种社会关系各种社会关系各类分类编码各类分类编码编译程序的语法树编译程序的语法树Internet中的中的DNS（域名系统）（域名系统）UNIX文件系统结构树的实例数据结构zmz5二叉树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构v定义：树定义：树(tree)是是n(n0)个结点的有限集，其中：个结点的有限集，其中：ln=0，称为，称为空树空树l有且仅有一个特殊的结点，称为树的有且仅有一个特殊的

3、结点，称为树的根根(root)l当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交的互不相交的子子集集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的其中每一个集合本身又是一棵树，称为根的子树子树(subtree)v特点：特点：l树中至少有一个结点树中至少有一个结点根根l树的定义是树的定义是递归递归定义的，各定义的，各子树子树也满足上面定义。也满足上面定义。树的定义 数据结构zmz5二叉树线性结构线性结构 树型结构树型结构 第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个

4、叶子结点多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 多个后继多个后继) )数据结构zmz5二叉树A只有根结点的树只有根结点的树 ABCDEFGHIJKLM有子树的树有子树的树 根根 子树子树 叶子叶子叶子叶子叶子叶子 数据结构zmz5二叉树ADT Tree 数据对象数据对象D: D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合 数据关系数据关系R: 若若D为空集，则称为为空集，则称为空树空树 否则否则: (1) 在在D中存在唯一的称为中存在唯一的称为根根的数

5、据元素的数据元素root； (2) 当当n1时，其余结点可分为时，其余结点可分为m (m0)个个互不相交互不相交的的 有限集有限集T1, T2, , Tm，其中每一棵子集本身又是，其中每一棵子集本身又是 一棵符合本定义的树，称为根一棵符合本定义的树，称为根root的的子树子树 基本操作基本操作： 查找类查找类操作操作 插入类插入类操作操作 删除类删除类操作操作 ADT Tree树的抽象数据类型定义数据结构zmz5二叉树基本操作：基本操作：TreeEmpty(T)初始条件初始条件：树：树T已存在已存在操作结果操作结果：空树，返回：空树，返回 TRUE;否则否则 FALSETreeDepth(T)

6、初始条件初始条件：树：树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中非根结点中非根结点,返回其双亲返回其双亲;否则否则,返回空返回空树的抽象数据类型定义数据结构zmz5二叉树LeftChild

7、(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 的每个元素调用函数的每个元素调用函数vi

8、sit()查找类：查找类：基本操作：基本操作：树的抽象数据类型定义数据结构zmz5二叉树插入类：插入类：InsertChild(&T, &p,i,c)初始条件初始条件：树树T存在存在,p指向指向T中结点中结点,1i p指结点度指结点度+1,非空树非空树c与与T不相交不相交操作结果操作结果：将以：将以c为根的树插入为为根的树插入为T中中p指结点的第指结点的第i棵子树棵子树CreateTree(&T, definition)初始条件初始条件： definition给出树的定义给出树的定义操作结果操作结果：按：按definition构造树构造树TAssign(T, cur_e

9、, value)初始条件初始条件：树：树T已存在已存在,cur_e是是T中结点中结点操作结果操作结果：结点：结点cur_e赋值为赋值为valueInitTree(&T)操作结果操作结果：构造空树：构造空树T基本操作：基本操作：树的抽象数据类型定义数据结构zmz5二叉树DeleteChild(&T, &p,i)初始条件初始条件：树：树T存在存在,p指向指向T中结点中结点,1i p指结点度指结点度操作结果操作结果：删除：删除T中中p指结点的第指结点的第i棵子树棵子树ClearTree(&T)初始条件初始条件：树：树T 已存在已存在操作结果操作结果：将树：将树T 清为

10、空树清为空树DestroyTree(&T)初始条件初始条件：树：树T 已存在已存在操作结果操作结果：销毁树：销毁树T删除类：删除类：基本操作：基本操作：树的抽象数据类型定义数据结构zmz5二叉树结点结点(node)表示树中的元素，以及构造表示树中的元素，以及构造元素之间关系的指针元素之间关系的指针 结点的度结点的度(degree)结点拥有的子树数结点拥有的子树数 树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数 叶子叶子(leaf)度为度为0的结点，终端结点的结点，终端结点 分支结点分支结点度不为度不为0的结点，非终端结点的结点，非终端结点 孩子孩子(child)结点子树的根称

11、为该结点的结点子树的根称为该结点的孩子孩子 双亲双亲(parents)孩子结点的上层结点叫该孩子结点的上层结点叫该结点的双亲结点的双亲 树的基本术语 数据结构zmz5二叉树兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子 祖先祖先从根到该结点所经分支上的所有结从根到该结点所经分支上的所有结点点 子孙（后裔）子孙（后裔）一个节点所有子树上的节一个节点所有子树上的节点点节点的节点的层次层次(level)从根结点算起，根为从根结点算起，根为第一层，它的孩子为第二层第一层，它的孩子为第二层 堂兄弟堂兄弟同一层的结点同一层的结点深度深度(depth)树中结点的最大层次数树中结点的最大层次数, 又称

12、高度又称高度树的基本术语 数据结构zmz5二叉树森林森林(forest)m(m 0)棵互不相交的树的棵互不相交的树的集合集合 无序树无序树子树之间不存在确定的次序关系子树之间不存在确定的次序关系 有序树有序树各子树从左至右有严格的次序，各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，不能互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子最右边的节点称为最后一个孩子 任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree = （root，F）其中：其中：root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林 树的基本术语 数据结构zmz5二叉树

13、树的表示 JIACBDHGFEKLM数据结构zmz5二叉树GCKLEFBMHJIDA嵌套集合表示法嵌套集合表示法 图型表示法图型表示法 树的表示 JIACBDHGFEKLM数据结构zmz5二叉树(A(B(E(k,L),F),C(G),D(H(M),I,J)括号括号( (广义表广义表) )表示法表示法 图型表示法图型表示法 树的表示 JIACBDHGFEKLM数据结构zmz5二叉树图型表示法图型表示法 ABCDEFGHIJKLM凹入表示法凹入表示法 树的表示 JIACBDHGFEKLM数据结构zmz5二叉树结点结点A的度：的度： 结点结点B的度：的度： 结点结点M的度：的度： 叶子：叶子： 结点

14、结点A的孩子：的孩子： 结点结点B的孩子：的孩子： 结点结点I的双亲：的双亲： 结点结点L的双亲：的双亲： 结点结点B，C，D为为结点结点K，L为为树的度：树的度： 结点结点A的层次：的层次： 结点结点M的层次：的层次： 树的深度：树的深度：结点结点F，G为为结点结点A是结点是结点F，G的的结点结点F，G 是是A结点的结点的ABCDEFGHIJKLM3 2 0 B, C, D E, F 31 4 4 K, L, F, G, M, I, J D E 兄弟兄弟 兄弟兄弟 堂兄弟堂兄弟 祖先祖先 子孙子孙 请同学回答 数据结构zmz5二叉树请安静请安静 6.2二二 叉叉 树树数据结构zmz5二叉树数

15、据结构zmz5二叉树 定义：二叉树是定义：二叉树是n(n 0)个结点的有限集，它或为个结点的有限集，它或为空树空树(n=0)，或由一个根结点和两棵分别称为或由一个根结点和两棵分别称为左子树左子树和和右子树右子树的互不相交的的互不相交的二叉树构成二叉树构成 特点特点 每个结点每个结点至多至多有二棵子树有二棵子树 (不存在度大于不存在度大于2的结点的结点) 子树有子树有左、右之分左、右之分，且其次序不能任意颠倒，且其次序不能任意颠倒 基本形态基本形态 空二叉树空二叉树 左、右子树均非空左、右子树均非空 DRL只有根结点二叉树只有根结点二叉树 D右子树为空右子树为空 DL左子树为空左子树为空 DR二

16、叉树的定义 数据结构zmz5二叉树 有关二叉树下列说法正确的是（ ）A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 问：一棵度为2的树和一棵二叉树有何区别？ 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。二叉树的定义 数据结构zmz5二叉树数据结构zmz5二叉树性质1： 在二叉树的第在二叉树的第 i 层上至多有层上至多有_个结点个结点(i1) 第一层第一层： 第二层：第二层： 第三层：第三层： 第第i层：层：只有一个根结点：只有一个根结点：21-1 = 20 = 1； 二叉树上每个结点至多有两棵子二叉树上每个结点至多

17、有两棵子 树，树，则第则第 i 层的结点数层的结点数 = 2i-1 。 二叉树的性质 最多：最多：20 2 = 21 = 2； 最多：最多：21 2 = 22 = 4； 2i-1数据结构zmz5二叉树二叉树的性质 思考：具有具有 n 个节点的二叉树的深度个节点的二叉树的深度 最小最小 _ ，最大，最大_高度高度 h 的二叉树最多有的二叉树最多有2h-1个节点（性质个节点（性质2） n 2h-1 h log2(n+1) 解答：性质2：12311458912 13671014 15深度为深度为 k 的二叉树上至多含的二叉树上至多含 _个结点（个结点（k1） 证明：基于上一条性质，深度证明：基于上一

18、条性质，深度为为 k 的二叉树上的结点数至多为的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 2k-1数据结构zmz5二叉树性质3：对任何一棵二叉树T，如果其叶子结点数 为n0，度为2的结点数为n2，则n0=n2+1 证明：证明： 设设 n1 为度为为度为1的节点数的节点数 二叉树中所有节点的度二叉树中所有节点的度2 结点总数结点总数 n=n0+n1+n2 除根节点外，其余节点都是除根节点外，其余节点都是“别人别人”的孩子的孩子 又又 叶子（叶子（n0）没有孩子！）没有孩子！ 所有的孩子数所有的孩子数n-1=n1+2n2n=n1+2n2+1=n0+n1+n2 n0=n2+1

19、123456二叉树的性质 数据结构zmz5二叉树满二叉树 定义：特点：每一层上的结点数都是最大结点数特点：每一层上的结点数都是最大结点数 123114589121367101415满二叉树及其编号满二叉树及其编号 指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树个结点的二叉树 特殊形式的二叉树 数据结构zmz5二叉树完全二叉树完全二叉树定义：深度为定义：深度为k，有，有n个结点的二叉树当且仅当个结点的二叉树当且仅当其每一个结点都与深度为其每一个结点都与深度为k的的满满二叉树中编号从二叉树中编号从1至至n的结点的结点一一对应一一对应时，称为时，称为特点特点 叶子结点叶子结点只可能在只

20、可能在最后层和倒数第二层最后层和倒数第二层上出上出现现 特殊形式的二叉树数据结构zmz5二叉树1231145891213671014151231145891267101234567123456 完全二叉树中可能有完全二叉树中可能有度为度为1 1的结点吗？的结点吗？数据结构zmz5二叉树 性质性质4 4：123114589126710证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k 根据第二条性质得根据第二条性质得 n 2k -1 且且 (2k-1 -1)+1 n 即即 log2 n 1,则其双亲是则其双亲是 i/2 (2)如果如果2in,则结点则结点i无左孩子无左孩子;如果如果2i n

21、,则其左孩子是则其左孩子是2i (3)如果如果2i+1n,则结点则结点i无右孩子无右孩子;如果如果2i+1 n,则其右孩子是则其右孩子是2i+1 123114589126710完全二叉树性质数据结构zmz5二叉树二叉树性质小结二叉树的第二叉树的第 i 层上至多有层上至多有2i-1 个结点个结点 性质1： 性质2：深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点个结点 性质3：对任何一棵二叉树T，如果其叶子结点数为n0，度为2 2的结点数为n2，则n0=n2+1 性质4：具有具有n个结点的完全二叉树的个结点的完全二叉树的深度深度为为 log2n+1 性质5：对完全二叉树对完全二叉树有：有： (1) 如果如果i1,则其双亲是则其双亲是 i/2 (2)如果如果2in,则结点则结点i无左孩子无左孩子;否则其左孩子是否则其左孩子是2i (3)如果如果2i+1n,则结点则结点i无右孩子无右孩子;否则其右孩子是否则其右孩子是2i+1 数据结构zmz5二叉树数据结构zmz5二叉树数据结构zmz5二叉树二叉树的存储结构