数据结构――第6章_二叉树和树

数据结构的内容回顾一下线性结构（线性表、栈、队列等）有什么特点？？第6章二叉树和树树形结构特点：非线性结构，只有一个直接前驱，但可能有多个直接后继（1：n）2003级2004级2005级2006级韶关学院叶子根子树计算机系数学系中文系……教师学生……树型结构（非线性结构）结点之间一对多关系具有层次关系例自然界：树人类社会家谱行政组织机构计算机领域国务院山东省北京市西藏自治区…济南市青岛市威海市…历下区市中区…商河县第6章二叉树和树6.1二叉树6.2二叉树遍历6.3树和森林6.4树的应用数据结构第六章二叉树和树韶关学院§6.1二叉树二叉树是什么？二叉树有什么特点？二叉树的模型二叉树如何在计算机中实现？二叉树的顺序存储结构？二叉树的链式存储结构？?!数据结构第六章二叉树和树韶关学院【教学内容】二叉树的定义和基本术语、性质和存储结构。【教学要求】了解二叉树的结构特性，掌握相应的证明方法。掌握二叉树的各种存储结构【重点与难点】二叉树的定义和基本术语二叉树的基本性质、满二叉树、完全二叉树的概念二叉树的存储方法二叉树的基本性质的运用6.1二叉树为何要先研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。6.1.1二叉树的定义和基本术语6.1.2二叉树的基本性质6.1.3二叉树的存储结构ABEDC定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。基本形态：6.1.1二叉树(BinaryTree)的定义和基本术语1、二叉树定义RL(1)左右子树均非空的二叉树(5)空二叉树(2)只有左子树的二叉树L(3)只有右子树的二叉树R(4)只有根的二叉树ABEDC二叉树的逻辑结构：由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。树中任一结点都可以有0-2个直接后继结点但至多只能有一个直接前趋结点。T2T12、基本术语结点的度：结点直接后继结点数。度=0叶子终端结点度≠0分支结点非终端结点树的度：树中结点的度的最大值.二叉树中结点度的最大值为2。直接前驱称为父亲结点直接后继称为孩子结点兄弟结点的祖先：从根到该结点所经分支上的所有结点。结点的子孙：以该结点为根的子树中的任一结点。第1层第2层第3层二叉树的深度：树中结点的最大层次。有序树：树中结点的各子树从左至右有次序（最左边为第一个孩子）无序树：树中结点的各子树无次序。结点：数据元素+指向子树的分支根结点：非空树中无前驱结点的结点EFHABDJKLM第4层堂兄弟他们的父亲是兄弟的结点直接前驱结点相同兄弟二叉树的层数：根所在的层次为1，其孩子的层次为2，依次类推。结点A的孩子：结点B的孩子：叶子结点：结点J的双亲：结点L的双亲：ABDEFHJKLM结点A的度：结点H的度：结点M的度：结点B，D为兄弟结点K，L为兄弟二叉树的度：结点A的层次：结点M的层次：树的深度：结点F，H为堂兄弟结点A是结点F，H的祖先B，DE，F210K，L，F，M，J144DE2课堂练习二叉树的抽象数据类型定义（见教材P116-117）ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTreeD是具有相同特性的数据元素的集合。InitBiTree(&T);//初始化二叉树，即构造一棵空二叉树DestroyBiTree(&T);//销毁二叉树TBiTreeEmpty(T);//若T为空二叉树，返回TRUE，否则返回FALSEBiTreeDepth(T);//返回T的深度PreOrderTraverse(T,visit());//先序遍历TInsertChild(&T,p,LR,c);//在p所指结点插入左或右结点DeleteChild(&T,p,LR);//删除T中p所指结点的左或右子树…………略6.1.2二叉树的性质（3+2）性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。证明：采用数学归纳法证明此性质。归纳基础：当i=1时只有根结点，2i-1=20=1，命题成立。归纳假设：假设i=k(k≥1)时结论成立，即第k层上结点总数最多为2k-1个。那么可证明当i=k+1时，结论成立：归纳证明：因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×2k-1=2(k+1)-1，故结论成立。证毕。对于二叉树来说，每层结点最多的情况如下图所示：891011121314154567231……………………第1层1个结点，21-1=1第2层2结点，即22-1=2第3层4结点，即23-1=4第4层4结点，即24-1=8第i层2i-1证明:由性质1可知二叉树第1层到第k层各层最多的结点个数分别为：202122...2k-1性质2深度为k的二叉树最多有2k-1个结点。(k1)深度为k的二叉树最多的结点个数也就是各层上的最多的结点个数的和。即:20+21+22+...+2k-1可以看到这是一个等比级数的前k项之和。用求等比级数前k项和的公式可以得出结果为：2k-1122)(111kkiikii层上的最大结点数第891011121314154567231性质3：对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。（叶子数＝2度结点数＋1）证：设二叉树中结点总数为n，n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均≤2，所以其结点总数为：n=n0+n1+n2(叶子数＋1度结点数＋2度结点数)……⑴再看二叉树中的分支数，除根结点外，其余结点都有一个分支进入，设B为分支总数，则有：n=B＋1(总分支数＋根结点)……⑵（除根结点外，每个结点必有一个直接前趋，即一个分支）因这些分支都是由度为1和2的结点射出的(1度结点必有1个直接后继，2度结点必有2个)，所以有：B=n0*0+n1*1+n2*2=n1+2n2……⑶由⑵⑶式得：n=B+1＝n1+2n2+1联立⑴有：n=n0+n1+n2=n1+2n2+1即：n0=n2+1证毕。ABCGEIDHFJ思路：(1)结点总数(2)分支总数(3)两者关系1.深度为k的二叉树的结点总数，最多为个。Ａ)２k-1Ｂ)log2kＣ)２k－１Ｄ)２k2.深度为9的二叉树中至少有个结点。Ａ)２9Ｂ)２8Ｃ)９Ｄ)２9－13．二叉树有n个叶子，没有度为1的结点，共有个结点分析：度为2的结点有n-1个，所以共2n-1个结点。√√课堂练习：2n-1满二叉树(Fullbinarytree)特点：每一层上的结点数都达到最大。叶子全部在最底层。编号规则：从根结点开始，按层次自上而下，从左到右。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。2453671(续)二叉树的基本术语(P115)完全二叉树(Completebinarytree)深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。特点：叶子只可能分布在层次最大的两层上。对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次必为l或l+1。满二叉树完全二叉树是定一不一定是245361完全二叉树245361非完全二叉树1231145891213671014151231145891267101234567123456下列二叉树是满二叉树吗？是完全二叉树？完全二叉树的性质性质4：具有n个结点的完全二叉树的深度为log2n+1或者log2(n+1)。说明：x表示不大于x的最大整数x表示不小于x的最小整数证：假设此二叉树的深度为k，k-1层为满二叉树的结点总数为2k-1-1，k层满二叉树的结点总数为2k-1，则根据性质2及完全二叉树的定义得到：2k-1–1n≤2k–1或2k-1≤n2k（因为n为整数）取对数得：k–1log2(n+1)≤k或k–1≤log2nk因为k是整数，所以有：k＝log2n+1或k＝log2(n+1)性质5：如果对一棵有n个结点的完全二叉树(深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是结点i/2。(2)如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。(3)如果2i+1n，则结点i无右孩子；否则，其右孩子是结点2i+1。证明：略1．完全二叉树的第3层有2个叶子，则共有个结点分析：注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。课堂练习：5、10或1112311458967101234512345896710课堂讨论：Q1：满二叉树和完全二叉树有什么区别？A1：满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。Q3:设一棵完全二叉树具有1024个结点，则它有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。48948810Q2：为什么要研究满二叉树和完全二叉树这两种特殊形式？A2：因为只有这两种形式可以实现顺序存储！由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现非空右子树(0个)。A3：易求出总层数和末层叶子数。总层数k=log2n＋1=10;且前9层总结点数为29-1=511(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。××请注意叶子结点总数≠末层叶子数！还应当加上第k-1层（靠右边）的0度结点个数。分析：末层的489个叶子只占据了上层的245个结点（489/2)上层（k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1（255）个结点肯定都是2度的（完全二叉）另外，末层叶子（刚才已求出为489）所对应的双亲也是度＝2，（共有489/2＝244个）。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝度为2的结点数＋1=500个。第i层上的满结点数为2i-1所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。123114589126710二叉树的定义及基本术语二叉树的定义二叉树的特点二叉树五种基本形态二叉树的基本性质（3+2）满二叉树完全二叉树二叉树性质上堂课要点回顾定义：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。基本形态：空（二叉树）；只有根结点；根结点和左子树；根结点和右子树；根结点和左右子树。定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。特点：每一层上的结点数都达到最大。叶子全部在最底层。定义：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。特点：叶子只可能分布在层次最大的两层上。若完全二叉树深度为k，则k-1层一定是满二叉树。【性质1】在二叉树的第i层上至多有2i-1个结点(i≥1)。【性质2】深度为k的二叉树至多有2k-1个结点（k≥1）。【性质3】对任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1。（叶子数＝结点的度为2的结点数＋1）【性质4】具有n个结点的完全二叉树的深度为log2n+1或者log2(n+1)。【性质5】n个结点的完全二叉树，结点按层次编号有：1)i的双亲是，如