数据结构二叉树精.ppt

数据结构二叉树第1页，本讲稿共44页请安静请安静 6.1树的定义和基本术语树的定义和基本术语第2页，本讲稿共44页 1数据的逻辑结数据的逻辑结构构 2、数据的存储结构、数据的存储结构 3、对数据的操作：检索、排序、插入、删除、修改、对数据的操作：检索、排序、插入、删除、修改A线性结构线性结构 B非线性结构非线性结构A 顺序存储顺序存储 B 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构数数据据结结构构的的三三个个主主要要问问题题 Data Structure树的逻辑结构树的逻辑结构?一对多（一对多（1：n）第3页，本讲稿共44页五子棋游戏.树的实例第4页，本讲稿共44页/(root)libuseretcbinmathdsswyintaoxieStack.cppQueue.cppTree.cpp人类的族谱各种社会关系各类分类编码编译程序的语法树Internet中的DNS（域名系统）UNIX文件系统结构树的实例第5页，本讲稿共44页 树是一类重要的非线性数据结构，是以分支关系定义的层次结构定义：树定义：树(tree)是是n(n0)个结点的有限集，其中：个结点的有限集，其中：n=0，称为，称为空树空树有且仅有一个特殊的结点，称为树的有且仅有一个特殊的结点，称为树的根根(root)当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交的互不相交的子集子集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的其中每一个集合本身又是一棵树，称为根的子树子树(subtree)特点：特点：树中至少有一个结点树中至少有一个结点根根树的定义是树的定义是递归递归定义的，各定义的，各子树子树也满足上面定义。也满足上面定义。树的定义 第6页，本讲稿共44页线性结构线性结构 树型结构树型结构 第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素 (一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素 (一个前驱、一个前驱、多个后继多个后继)第7页，本讲稿共44页A只有根结点的树 ABCDEFGHIJKLM有子树的树 根 子树 叶子叶子叶子 第8页，本讲稿共44页ADT Tree 数据对象数据对象D:D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合 数据关系数据关系R:若若D为空集，则称为为空集，则称为空树空树 否则否则:(1)在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root；(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交互不相交的的 有限集有限集T1,T2,Tm，其中每一棵子集本身又是，其中每一棵子集本身又是 一棵符合本定义的树，称为根一棵符合本定义的树，称为根root的的子树子树 基本操作基本操作：查找类查找类操作操作 插入类插入类操作操作 删除类删除类操作操作 ADT Tree树的抽象数据类型定义第9页，本讲稿共44页基本操作：基本操作：TreeEmpty(T)初始条件初始条件：树：树T已存在已存在操作结果操作结果：空树，返回：空树，返回 TRUE;否则否则 FALSETreeDepth(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中非根结点中非根结点,返回其双亲返回其双亲;否则否则,返回空返回空树的抽象数据类型定义第10页，本讲稿共44页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()查找类：查找类：基本操作：基本操作：树的抽象数据类型定义第11页，本讲稿共44页插入类：插入类：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,value)初始条件初始条件：树：树T已存在已存在,cur_e是是T中结点中结点操作结果操作结果：结点：结点cur_e赋值为赋值为valueInitTree(&T)操作结果操作结果：构造空树：构造空树T基本操作：基本操作：树的抽象数据类型定义第12页，本讲稿共44页DeleteChild(&T,&p,i)初始条件初始条件：树：树T存在存在,p指向指向T中结点中结点,1i p指结点度指结点度操作结果操作结果：删除：删除T中中p指结点的第指结点的第i棵子树棵子树ClearTree(&T)初始条件初始条件：树：树T 已存在已存在操作结果操作结果：将树：将树T 清为空树清为空树DestroyTree(&T)初始条件初始条件：树：树T 已存在已存在操作结果操作结果：销毁树：销毁树T删除类：删除类：基本操作：基本操作：树的抽象数据类型定义第13页，本讲稿共44页结点结点(node)表示树中的元素，以及构造元素表示树中的元素，以及构造元素之间关系的指针之间关系的指针 结点的度结点的度(degree)结点拥有的子树数结点拥有的子树数 树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数 叶子叶子(leaf)度为度为0的结点，终端结点的结点，终端结点 分支结点分支结点度不为度不为0的结点，非终端结点的结点，非终端结点 孩子孩子(child)结点子树的根称为该结点的孩子结点子树的根称为该结点的孩子 双亲双亲(parents)孩子结点的上层结点叫该结孩子结点的上层结点叫该结点的双亲点的双亲 树的基本术语 第14页，本讲稿共44页兄弟兄弟(sibling)同一双亲的孩子同一双亲的孩子 祖先祖先从根到该结点所经分支上的所有结点从根到该结点所经分支上的所有结点 子孙（后裔）子孙（后裔）一个节点所有子树上的节点一个节点所有子树上的节点节点的节点的层次层次(level)从根结点算起，根为第一从根结点算起，根为第一层，它的孩子为第二层层，它的孩子为第二层 堂兄弟堂兄弟同一层的结点同一层的结点深度深度(depth)树中结点的最大层次数树中结点的最大层次数,又称又称高度高度树的基本术语 第15页，本讲稿共44页森林森林(forest)m(m 0)棵互不相交的树的集棵互不相交的树的集合合 无序树无序树子树之间不存在确定的次序关系子树之间不存在确定的次序关系 有序树有序树各子树从左至右有严格的次序，不能各子树从左至右有严格的次序，不能互换，最左边的节点称为第一个孩子，最右边的节互换，最左边的节点称为第一个孩子，最右边的节点称为最后一个孩子点称为最后一个孩子 任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=（root，F）其中：其中：root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林 树的基本术语 第16页，本讲稿共44页树的表示 JIACBDHGFEKLM图形表示法图形表示法嵌套集合表示法嵌套集合表示法广义表表示法广义表表示法凹入表示法凹入表示法第17页，本讲稿共44页GCKLEFBMHJIDA嵌套集合表示法嵌套集合表示法 图型表示法图型表示法 树的表示 JIACBDHGFEKLM第18页，本讲稿共44页(A(B(E(k,L),F),C(G),D(H(M),I,J)括号括号(广义表广义表)表示法表示法 图型表示法图型表示法 树的表示 JIACBDHGFEKLM第19页，本讲稿共44页图型表示法图型表示法 ABCDEFGHIJKLM凹入表示法凹入表示法 树的表示 JIACBDHGFEKLM第20页，本讲稿共44页结点结点A的度：的度：结点结点B的度：的度：结点结点M的度：的度：叶子：叶子：结点结点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 兄弟兄弟 兄弟兄弟 堂兄弟堂兄弟 祖先祖先 子孙子孙 请同学回答 第21页，本讲稿共44页请安静请安静 6.2二二 叉叉 树树第22页，本讲稿共44页6.2 6.2 二叉树二叉树 为为何何要要重重点点研研究究每每结结点点最最多多只只有有两两个个 “叉叉叉叉”的树？的树？的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可以证明，所有树都能转换为唯一的一棵二叉树与可以证明，所有树都能转换为唯一的一棵二叉树与其对应，不失一般性。其对应，不失一般性。6.2.1 二叉树的定义二叉树的定义二叉树的定义二叉树的定义6.2.2 6.2.2 二叉树的性质二叉树的性质6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构第23页，本讲稿共44页定义：二叉树是定义：二叉树是n(n 0)个结点的有限集，它或为个结点的有限集，它或为空树空树(n=0)，或由一个根结点和两棵分别称为或由一个根结点和两棵分别称为左子树左子树和和右子树右子树的互不相交的的互不相交的二叉树构成二叉树构成 特点特点 每个结点每个结点至多至多有二棵子树有二棵子树 (不存在度大于不存在度大于2的结点的结点)子树有子树有左、右之分左、右之分，且其次序不能任意颠倒，且其次序不能任意颠倒 基本形态基本形态 空二叉树 左、右子树均非空 DRL只有根结点二叉树 D右子树为空 DL左子树为空 DR二叉树的定义 第24页，本讲稿共44页有关二叉树下列说法正确的是（）A二叉树的度为2 B一棵二叉树的度可以小于2C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2问：一棵度为2的树和一棵二叉树有何区别？试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。二叉树的定义 第25页，本讲稿共44页二叉树的抽象数据类型定义ADT BinaryTreeADT BinaryTree数据对象数据对象数据对象数据对象D:D:数据关系数据关系数据关系数据关系R:R:基本操作基本操作基本操作基本操作 P P：ADT BinaryTreeADT BinaryTree若若若若D=D=，则，则，则，则R=R=；若若若若DD，则，则，则，则R=HR=H；存在二元关系：；存在二元关系：；存在二元关系：；存在二元关系：root root 唯一唯一唯一唯一 /关于根的说明关于根的说明关于根的说明关于根的说明 D Dl lDDr r=/关于子树不相交的说明关于子树不相交的说明关于子树不相交的说明关于子树不相交的说明 /关于二元关系的说明关于二元关系的说明关于二元关系的说明关于二元关系的说明 /关于左子树和右子树的说明关于左子树和右子树的说明关于左子树和右子树的说明关于左子树和右子树的说明D D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。/至少有至少有至少有至少有2020个个个个第26页，本讲稿共44页性质1：在二叉树的第在二叉树的第 i 层上至多有层上至多有_个结点个结点(i1)第一层第一层：第二层：第二层：第三层：第三层：第第i层：层：只有一个根结点：只有一个根结点：21-1=20=1；二叉树上每个结点至多有两棵子二叉树上每个结点至多有两棵子 树，树，则第则第 i 层的结点数层的结点数=2i-1。二叉树的性质 最多：最多：20 2=21=2；最多：最多：21 2=22=4；2i-1第27页，本讲稿共44页二叉树的性质 思考：具有具有 n 个节点的二叉树的深度个节点的二叉树的深度 最小最小 _，最大，最大_高度高度 h 的二叉树最多有的二叉树最多有2h-1个节点（性质个节点（性质2）n 2h-1 h log2(n+1)解答：性质2：12311458912 13671014 15深度为深度为 k 的二叉树上至多含的二叉树上至多含 _个结点（个结点（k1）证明：基于上一条性质，深度为证明：基于上一条性质，深度为 k 的二叉树上的结点数至多为的二叉树上的结点数至多为 20+21+2k-1=2k-1 2k-1第28页，本讲稿共44页性质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 123456二叉树的性质 第29页，本讲稿共44页满二叉树 定义：特点：每一层上的结点数都是最大结点数特点：每一层上的结点数都是最大结点数 123114589121367101415满二叉树及其编号满二叉树及其编号 指的是深度为指的是深度为k且含有且含有2k-1个结点的二叉树个结点的二叉树 特殊形式的二叉树 第30页，本讲稿共44页完全二叉树完全二叉树定义：深度为定义：深度为k，有，有n个结点的二叉树当且仅当其每一个个结点的二叉树当且仅当其每一个结点都与深度为结点都与深度为k的的满满二叉树中编号从二叉树中编号从1至至n的结点的结点一一一一对应对应时，称为时，称为特点特点 叶子结点叶子结点只可能在只可能在最后层和倒数第二层最后层和倒数第二层上出现上出现 特殊形式的二叉树第31页，本讲稿共44页1231145891213671014151231145891267101234567123456 完全二叉树中可能有完全二叉树中可能有度为度为1 1的结点吗？的结点吗？?第32页，本讲稿共44页性质性质4 4：123114589126710证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k 根据第二条性质得根据第二条性质得 n 2k-1 且且 (2k-1-1)+1 n 即即 log2 n 1,则其双亲是则其双亲是 i/2 (2)如果如果2in,则结点则结点i无左孩子无左孩子;如果如果2i n,则其左孩子是则其左孩子是2i(3)如果如果2i+1n,则结点则结点i无右孩子无右孩子;如果如果2i+1 n,则其右孩子是则其右孩子是2i+1 123114589126710完全二叉树性质第34页，本讲稿共44页二叉树性质小结二叉树的第二叉树的第 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 第35页，本讲稿共44页课堂讨论：课堂讨论：二叉树是不是树的特殊情况？二叉树是不是树的特殊情况？答答：不不不不是是是是！它它它它是是是是单单单单独独独独定定定定义义义义的的的的一一一一种种种种树树树树状状状状结结结结构构构构，并并并并非非非非一一一一般般般般树的特例。树的特例。树的特例。树的特例。它它的的子子树树有有顺顺序序规规定定，分分为为左左左左子子子子树树树树和和和和右右右右子子子子树树树树。不不不不能能能能随随随随意颠倒。意颠倒。意颠倒。意颠倒。：满二叉树和：满二叉树和完全二叉树完全二叉树有什么区别？有什么区别？答：答：答：答：满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。满二叉树是完全二叉树的一个特例。完全二叉树最底层却允许在右边缺少连续若干个结点。完全二叉树最底层却允许在右边缺少连续若干个结点。第36页，本讲稿共44页5.5.5.5.深度为深度为深度为深度为9 9的完全二叉树中至少有的完全二叉树中至少有的完全二叉树中至少有的完全二叉树中至少有 个结点。个结点。个结点。个结点。)9 9 )8 8 8 8 )9 9 9 91 1 1 14.4.4.4.深度为深度为深度为深度为k k 的二叉树的结点总数，最多为的二叉树的结点总数，最多为的二叉树的结点总数，最多为的二叉树的结点总数，最多为 个。个。个。个。)k-1k-1k-1k-1 )log)log)log)log2 2 2 2k k k k )k k k k )k k k k3.3.3.3.树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的树中各结点的度的最大值称为树的 。)高度高度高度高度 )层次层次层次层次 )深度深度深度深度 )度度度度课堂讨论：课堂讨论：第37页，本讲稿共44页二叉树的存储结构 顺序存储结构顺序存储结构链式存储结构链式存储结构第38页，本讲稿共44页一、完全二叉树一、完全二叉树一、完全二叉树一、完全二叉树实现：按结点层次编号，依实现：按结点层次编号，依次存放二叉树中的数据元素次存放二叉树中的数据元素（用（用数组数组实现）实现）A AB BC CD DE EF FG GH HI I112233445566778899A AB BC CGGE EI ID DHHF F问：顺序存储后能否唯一对应一颗二叉树？问：顺序存储后能否唯一对应一颗二叉树？问：顺序存储后能否唯一对应一颗二叉树？问：顺序存储后能否唯一对应一颗二叉树？有规律：有规律：有规律：有规律：下标值为下标值为i i i i的结点，其左孩子的下标值必为的结点，其左孩子的下标值必为的结点，其左孩子的下标值必为的结点，其左孩子的下标值必为2i2i2i2i，其，其，其，其右孩子的下标值必为右孩子的下标值必为右孩子的下标值必为右孩子的下标值必为2i2i2i2i1 1 1 1（即性质（即性质5 5 5 5）二叉树的存储结构顺序存储结构第39页，本讲稿共44页不是完全二叉树怎么办？不是完全二叉树怎么办？特点：特点：结点间结点间关系蕴含关系蕴含在其存储位置中在其存储位置中浪费空间浪费空间,k层需要长度多少的数组？层需要长度多少的数组？abcdefg 1 2 3 4 5 6 7 8 9 10 11a bcd e0000fg该存储结构能否反映该存储结构能否反映结点之间的关系？结点之间的关系？?0二叉树的存储结构顺序存储结构适于适于满二叉树满二叉树满二叉树满二叉树和和和和完全二叉树完全二叉树完全二叉树完全二叉树补补“虚结点虚结点”！第40页，本讲稿共44页ABCDEF思考：思考：将该二叉树进行顺序存储将该二叉树进行顺序存储二叉树的存储结构顺序存储结构第41页，本讲稿共44页思考：请画出下列二叉树的图思考：请画出下列二叉树的图 1 2 3 4 5 6 7 8 9 10 11a b c0def00g h0二叉树的存储结构顺序存储结构 1 2 3 4 5 6 7 8 9 10 11 12a bcd 0e000000f第42页，本讲稿共44页二叉链表二叉链表lchild data rchild ABCDEFG在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个个空空指针域指针域 AB C D E F G二叉树的存储结构链式存储结构typedef struct BitNode TElemType data;struct BitTNode*lchild,*rchild;BitNode,*BitTree;第43页，本讲稿共44页一、计算题：一、计算题：一、计算题：一、计算题：1 1 1 1）高度为）高度为）高度为）高度为h h h h的完全二叉树，最多有几个结点，最少几个？的完全二叉树，最多有几个结点，最少几个？的完全二叉树，最多有几个结点，最少几个？的完全二叉树，最多有几个结点，最少几个？2 2 2 2）完全二叉树中编号为）完全二叉树中编号为）完全二叉树中编号为）完全二叉树中编号为11111111的结点的左右孩子是？的结点的左右孩子是？的结点的左右孩子是？的结点的左右孩子是？3 3 3 3）某二叉树共有）某二叉树共有）某二叉树共有）某二叉树共有8 8 8 8个叶子，度为个叶子，度为个叶子，度为个叶子，度为2 2 2 2的结点数为？的结点数为？的结点数为？的结点数为？4 4 4 4）某二叉树共有）某二叉树共有）某二叉树共有）某二叉树共有51515151个结点，它的深度是？个结点，它的深度是？个结点，它的深度是？个结点，它的深度是？二、画图题：二、画图题：二、画图题：二、画图题：1 1 1 1）深度为）深度为）深度为）深度为4 4 4 4、结点数为、结点数为、结点数为、结点数为7 7 7 7的二叉树；的二叉树；的二叉树；的二叉树；2 2 2 2）深度为）深度为）深度为）深度为4 4 4 4、结点数为、结点数为、结点数为、结点数为10101010的完全二叉树；的完全二叉树；的完全二叉树；的完全二叉树；3 3 3 3）深度为）深度为）深度为）深度为3 3 3 3的满二叉树的满二叉树的满二叉树的满二叉树 4 4 4 4）深度为）深度为）深度为）深度为3 3 3 3、度为、度为、度为、度为4 4 4 4的树；的树；的树；的树；三、问答题：三、问答题：三、问答题：三、问答题：1 1 1 1）结点）结点）结点）结点H H H H的兄弟？祖先？孩子？的兄弟？祖先？孩子？的兄弟？祖先？孩子？的兄弟？祖先？孩子？2 2 2 2）结点）结点）结点）结点G G G G的堂兄弟？双亲？的堂兄弟？双亲？的堂兄弟？双亲？的堂兄弟？双亲？3 3 3 3）度为）度为）度为）度为2 2 2 2的结点有哪些？的结点有哪些？的结点有哪些？的结点有哪些？4 4 4 4）叶子的结点有哪些？）叶子的结点有哪些？）叶子的结点有哪些？）叶子的结点有哪些？作业：ABCDEFGHIJKLM第三题图 第44页，本讲稿共44页