数据结构-2015版(严)

树和二叉树第6章树和二叉树计算机科学与技术学院主讲:孙玉霞树和二叉树目　录6.1　树的定义和基本术语6.2　二叉树6.3　遍历二叉树和线索二叉树6.4　树和森林6.6　赫夫曼树及其应用树和二叉树●●基本要求：　1）理解并准确叙述树、二叉树、森林及其有关概念并熟悉它们的基本性质；　2）熟悉树形结构的存储结构和中序线索二叉树；　3）熟悉树的遍历方法，尤其是二叉树的前序、中序和后序遍历的递归与应用，知道树形结构的若干应用。●●学习重点：　1）二叉树的性质与存储结构；　2）二叉树的遍历算法。树和二叉树6.1　树的定义和基本术语●●　　树的定义树的定义　　　树的逻辑结构——它定义一类重要的非线性结构。树结构在计算机科学的很多领域都得到了广泛的应用。　　树结构可应用于诸如编译程序中表示源程序的语法结构数据库系统中的信息组织文件目录电路分析社会各个组织和管理机构家谱书的章节编目军队编制　　树型结构是结点之间有分支、层次关系的结构，它非常类似于自然界中的树。树型结构在客观世界中大量存在。树和二叉树6.1　树的定义和基本术语6.1.16.1.1　　树的定义树的定义　●●定义：树(tree)是n(n0)个结点的有限集T，其中：11））有且仅有一个特定的结点，称为树的根(root)22））当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。●●特点：11））树中至少有一个结点——根。22））树中各子树是互不相交的集合。注1：树的定义具有递归性，即“树中还有树”。树和二叉树6.1　树的定义和基本术语6.1.16.1.1　　树的定义树的定义　A只有根结点的树ABCDEFGHIJKLM有子树的树根图6.1　树的示例(a)　只有根结点的树(b)　一般的树树和二叉树6.1　树的定义和基本术语6.1.26.1.2　　树的基本术语树的基本术语　•结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支•结点的度(degree)——结点拥有的子树数•叶子(leaf)——度为0的结点•孩子(child)——结点子树的根称为该结点的孩子•双亲(parents)——孩子结点的上层结点叫该结点的~•兄弟(sibling)——同一双亲的孩子•树的度——一棵树中最大的结点度数（Max{各结点的度}）•结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……•深度(depth)——树中结点的最大层次数（Max{各结点的层次}）•森林(forest)——m(m0)棵互不相交的树的集合树和二叉树6.1　树的定义和基本术语6.1.26.1.2　　树的基本术语树的基本术语　ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先图6.2　树的基本术语示例树和二叉树6.1.36.1.3树的抽象数据类型数据集合:树的结点集合，每个结点由数据元素和构造数　　　　　据元素之间关系的指针组成。操作集合:(1)创建树　CreateTree(T)　(2)撤消树　DestroyTree(&T)(3)查找树中当前结点的双亲结点　Parent(T,curr)(4)查找树中当前结点的左孩子结点　LeftChild(T,curr)(5)查找树中当前结点的右孩子结点　RightSibling(T,curr)(6)遍历树　　Traverse(T,Visit())6.1　树的定义和基本术语树和二叉树图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法6.1.4树的几种表示方法树和二叉树图形表示法教师学生其他人员2001级2002级2003级2004级……湖北师范学院计算机系电信系自控系……叶子根子树树和二叉树嵌套集合表示法树和二叉树(A(B(E(K,L),F),C(G),D(H(M),I,J))约定：根作为由子树森林组成的表的名字写在表的左边广义表表示法广义表表示法树和二叉树凹入表示法凹入表示法又称目录表示法树和二叉树datalink1link2...linkn...树结点的结构：困惑：构造树的结点时应当开多少个链域?树和二叉树AABBCCDDEEFFGGHHIIJJKKLLMMdata左孩子右兄弟左孩子－右兄弟表示法左孩子－右兄弟表示法多叉树转为了二叉树树和二叉树6.2　二叉树为何要重点研究结点最多只有两个“叉”的树？　●二叉树的结构最简单，规律性最强；●可以证明，所有树都能转为唯一对应的二叉树，不失一般性。树和二叉树6.2　二叉树6.2.16.2.1　　二叉树的定义二叉树的定义　●●定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。●●特点：11））每个结点至多有二棵子树(即不存在度大于2的结点)。22））二叉树的子树有左、右之分，且其次序不能任意颠倒。树和二叉树6.2　二叉树6.2.16.2.1　　二叉树的定义二叉树的定义　●●基本形态：二叉树有5种基本形态。A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空图6.3　树的5种基本形态树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。[证]用归纳法。1）i=1，只有一个根结点。2i-1=20=1。正确。2）设命题对j成立，即有第j层上至多有2j-1个结点。由于二叉树每个结点的度至多为2，故第i层上最大结点数是第i-1层的2倍，即2j-1.2=2j=2(j+1)-1。故命题对j+1亦成立。　　证毕。树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。[证]由性质1，可得深度为k的二叉树最大结点数是　　证毕。122)(111kkikiii层的最大结点数第树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　性质3：非空二叉树T的叶结点数等于度为2的结点数加1（即n0=n2+1）证明：证明：∵∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又又∵∵二叉树中全部结点数n＝B+1(总分支数＋根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　●●满二叉树：一棵深度为k且具有2k-1个结点的二叉树称为满二叉树。简单的理解，每一层必满。●●完全二叉树：深度为k有n个结点的二叉树，当且仅当该二叉树的n个结点与深度为k的满二叉树中编号从1至n的结点位置一一对应时，则称为完全二叉树。●●完全二叉树（另一种定义）：深度为k的完全二叉树，其k-1层是一棵满二叉树，最后第k层结点都尽量排在靠左的位置上（即第k层的所有叶子结点占据树的最左边的连续位置）。树和二叉树6.2　二叉树●满二叉树与完全二叉树的区别？　满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。●●为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原。树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　●●判断是满二叉树还是完全二叉树？1231145891213671014151231145891267101234567123456图6.4　特殊形态的二叉树树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　●●性质4：具有n个结点的满二叉树或完全二叉树的深度为log2n+1.[证]对于满二叉树，n=2k-1，或n+1=2k，得k=log2(n+1).由于k是整数，故log2n+1　　对于完全二叉树，根据性质2和完全二叉树的定义知2k-1-1n≤2k-1其中2k-1-1与2k-1分别表示深度为k-1与k的最大结点数。于是2k-1≤n2k　　　　或有　　　k-1≤log2nk由于k是整数，故k=log2n+1。证毕。示例如右图，对于n=8,9,10,···,14的完全二叉树，以及n=15的满二叉树，均有：k=log2n+1=3+1=4.符号含义：x表示不大于x的最大整数。表示不小于x的最小整数。例如：5.85.8=5=6符号含义：x表示不大于x的最大整数。表示不小于x的最小整数。例如：5.85.8=5=6123114589126710树和二叉树6.2　二叉树6.2.26.2.2　　二叉树的性质二叉树的性质　●●性质5：如果对一棵有n个结点的完全二叉树（其深度为log2n+1）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），则对任一结点i(1≤i≤n)，有:　　(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲Parent(i)是i/2　　(2)如果2*in。则结点i无左孩子（结点i为叶子结点）；如果2i≤n，则其左孩子LChild(i)是结点2i;　　(3)如果2i+1n，则结点i无右孩子（但i不一定是叶结点）；如果2i+1≤n，则其右孩子RChild(i)是结点2i+1。树和二叉树一棵完全二叉树有1000个结点，则它必有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。正确答案：全部叶子数＝1000/21000/2=500500个。度为2的结点＝叶子总数－1=499个。因为最后一个结点坐标是偶数，所以必为左子树。有1个结点只有非空左子树，有0个结点只有非空右子树。练习树和二叉树6.2　二叉树　　使用一组连续的存储单元(向量，即一维数组)来存储二叉树的数据元素。●●实现：　　按满二叉树的结点层次编号，依次存放二叉树中的数据元素。●●特点：11））结点间关系蕴含在其存储位置中。22））浪费空间，适于存满二叉树和完全二叉树。6.2.36.2.3　　二叉树的存储结构二叉树的存储结构　一、顺序存储结构　　树和二叉树6.2　二叉树6.2.36.2.3　　二叉树的存储结构二叉树的存储结构　一、顺序存储结构2ibt(1:12)i2i2i+1123456789101112123114589126710●●完全二叉树的存储示例树和二叉树6.2　二叉树6.2.36.2.3　　二叉树的存储结构二叉树的存储结构　一、顺序存储结构bt(1:11)123450000671237456（0表示不存在此结点）●●非完全二叉树的存储示例一般二叉树也必须以完全二叉树的形式来确定。无结点的补0，造成了存储空间的浪费。问题：对于一般的二叉树如何存储呢？树和二叉树6.2　二叉树6.2.36.2.3　　二叉树的存储结构二叉树的存储结构　一、顺序存储结构bt(1:15)102000300000004（0表示不存在此结点）●●非完全二叉树的存储示例1243最坏情况：树和二叉树6.2　二叉树●●二叉链表6.2.36.2.3　　二叉树的存储结构二叉树的存储结构　二、链式存储结构　　ABCDEFG在n个结点的二叉链表中，有n+1个空指针域ABCDEFG^^^^^^^^typedefstructBiTNode{TElemTypedata;structBiTNode*lchild;　structBiTNode*rchild;}BiTNode,*BiTree;lchilddatarchild树和二叉树6.2　二叉树●●三叉链表6.2.36.2