《数据结构第次课第六章树和二叉树精.ppt》由会员分享，可在线阅读，更多相关《数据结构第次课第六章树和二叉树精.ppt（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构第次课第六章树和二叉树第1页，本讲稿共29页 树结构是一类重要的非线性结构。树型结构是结点树结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组表示源程序的语法结构；在数
2、据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过织信息；在分析算法的行为时，可用树来描述其执行过程等等。程等等。树是递归结构，在树的定义中又用到了树的概念树是递归结构，在树的定义中又用到了树的概念树是递归结构，在树的定义中又用到了树的概念树是递归结构，在树的定义中又用到了树的概念第2页，本讲稿共29页树的定义树的定义 树是由树是由 n(n 0)个结点组成的有限集合。如个结点组成的有限集合。如果果 n=0，称为空树；如果，称为空树；如果 n 0，则，则 有一个特定的称之为有一个特定的称之为根根(root)的结点，它只的结点，它只有直接后继，但没有直接前驱；有直接后继，但没有
3、直接前驱；除根以外的其它结点划分为除根以外的其它结点划分为 m(m 0)个个 互互不相交的有限集合不相交的有限集合T0,T1,Tm-1，每个集合又，每个集合又是一棵树，并且称之为根的是一棵树，并且称之为根的子树子树。第3页，本讲稿共29页例：下面的图是一棵树例：下面的图是一棵树T=A,B,C,D,E,F,G,H,I,JT=A,B,C,D,E,F,G,H,I,JA A是根，其余结点可以划分为是根，其余结点可以划分为3 3个个互不相交的集合：互不相交的集合：T1=B,E,F,T2=C,G,T3=D,H,I,JT1=B,E,F,T2=C,G,T3=D,H,I,J这些集合中的每一集合都本身又是一棵树，
4、它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。例如例如 对于对于 T1T1，B B是根，其余结点可以划分为是根，其余结点可以划分为2 2个个互不相交的集合：互不相交的集合：T11=E，T12=F，T11,T12 是是B的子树。的子树。height=3ACGBDEFHIJ第4页，本讲稿共29页树的树的 基本术语基本术语 树结点：树结点：包含一个数据元素及若干指向子树的分支；包含一个数据元素及若干指向子树的分支；孩子结点：孩子结点：结点的子树的根称为该结点的孩子；结点的子树的根称为该结点的孩子；双亲结点：双亲结点：B结点是结点是A结点的孩子，则结点的孩子，则A结点是结点是B结
5、点的双亲；结点的双亲；兄弟结点：兄弟结点：同一双亲的孩子结点；同一双亲的孩子结点；堂兄结点：堂兄结点：同一层上结点；同一层上结点；结点层次：结点层次：根结点的层定义为根结点的层定义为1；根的孩子为第二层结点，依次类推；根的孩子为第二层结点，依次类推；树的高（深）度：树的高（深）度：树中结点的最大层数；树中结点的最大层数；结点的度：结点的度：结点子树的个数；结点子树的个数；树的度：树的度：树中最大的结点度。树中最大的结点度。叶子结点：叶子结点：也叫终端结点，是度为也叫终端结点，是度为0的结点；的结点；分枝结点：分枝结点：度不为度不为0的结点（非终端结点）；的结点（非终端结点）；森林：森林：互不相
6、交的树集合；互不相交的树集合；有序树：有序树：将数中每个结点的各子树看成是从左到右有次序的；将数中每个结点的各子树看成是从左到右有次序的；无序树：无序树：不考虑子树的顺序；不考虑子树的顺序；第5页，本讲稿共29页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的层次：的层次：
7、4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先第6页，本讲稿共29页练习练习 1.1.假设在树中，结点假设在树中，结点假设在树中，结点假设在树中，结点x x是结点是结点是结点是结点y y的双亲时，用（的双亲时，用（的双亲时，用（的双亲时，用（x,yx,y）来表示树边，）来表示树边，）来表示树边，）来表示树边，已知一棵树边的集合为：已知一棵树边的集合为：已知一棵树边的集合为：已知一棵树边的集合为：(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)
8、(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：(1)(1)哪个是根结点？哪个是根结点？哪个是根结点？哪个是根结点？(2)(2)哪些是叶子结点？哪些是叶子结点？哪些是叶子结点？哪些是叶子结点？(3)(3)哪个是哪个是哪个是哪个是g g的双亲？的双亲？的双亲？的双亲？(4)(4)哪些是哪些是哪些是哪些是g g的祖先？的祖先？的祖先？的祖先？(5)(5
9、)哪些是哪些是哪些是哪些是g g的孩子？的孩子？的孩子？的孩子？(6)(6)哪些是哪些是哪些是哪些是e e的子孙？的子孙？的子孙？的子孙？(7)(7)哪些是哪些是哪些是哪些是e e的兄弟？哪些是的兄弟？哪些是的兄弟？哪些是的兄弟？哪些是f f的兄弟？的兄弟？的兄弟？的兄弟？(8)(8)结点结点结点结点b b和和和和n n的层次各是多少？的层次各是多少？的层次各是多少？的层次各是多少？(9)(9)树的深度是多少？树的深度是多少？树的深度是多少？树的深度是多少？(10)(10)以结点以结点以结点以结点c c为根的子树的深度是多少？为根的子树的深度是多少？为根的子树的深度是多少？为根的子树的深度是多
10、少？(11)(11)树的度数是多少？树的度数是多少？树的度数是多少？树的度数是多少？第7页，本讲稿共29页练习练习 1.1.假设在树中，结点假设在树中，结点假设在树中，结点假设在树中，结点x x是结点是结点是结点是结点y y的双亲时，用（的双亲时，用（的双亲时，用（的双亲时，用（x,yx,y）来表示树边，已知一棵树边的集合为：）来表示树边，已知一棵树边的集合为：）来表示树边，已知一棵树边的集合为：）来表示树边，已知一棵树边的集合为：(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)(i,m)
11、,(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：用树形图表示出此树，并回答下列问题：(1)(1)哪个是根结点？哪个是根结点？哪个是根结点？哪个是根结点？(2)(2)哪些是叶子结点？哪些是叶子结点？哪些是叶子结点？哪些是叶子结点？(3)(3)哪个是哪个是哪个是哪个是g g的双亲？的双亲？的双亲？的双亲？(4)(4)哪些是哪些是哪些是哪些是g g的祖先？的祖先？的祖先？的祖先？(5)(5)哪些是哪
12、些是哪些是哪些是g g的孩子？的孩子？的孩子？的孩子？(6)(6)哪些是哪些是哪些是哪些是e e的子孙？的子孙？的子孙？的子孙？(7)(7)哪些是哪些是哪些是哪些是e e的兄弟？哪些是的兄弟？哪些是的兄弟？哪些是的兄弟？哪些是f f的兄弟？的兄弟？的兄弟？的兄弟？(8)(8)结点结点结点结点b b和和和和n n的层次各是多少？的层次各是多少？的层次各是多少？的层次各是多少？(9)(9)树的深度是多少？树的深度是多少？树的深度是多少？树的深度是多少？(10)(10)以结点以结点以结点以结点c c为根的子树的深度是多少？为根的子树的深度是多少？为根的子树的深度是多少？为根的子树的深度是多少？(11
13、)(11)树的度数是多少？树的度数是多少？树的度数是多少？树的度数是多少？abcidhfgmnlekj(1)a(1)a(1)a(1)a(2)m(2)m(2)m(2)m、n n n n、d d d d、l l l l、f f f f、k k k k、j j j j(3)c(3)c(3)c(3)c(4)a(4)a(4)a(4)a、c c c c(5)k(5)k(5)k(5)k、j j j j(6)i(6)i(6)i(6)i、m m m m、n n n n(7)d(7)d(7)d(7)d；h h h h、g g g g(8)2(8)2(8)2(8)2；5 5 5 5(9)5(9)5(9)5(9)5(
14、10)3(10)3(10)3(10)3(11)3(11)3(11)3(11)3第8页，本讲稿共29页树的抽象数据类型定义，树的抽象数据类型定义，p118第9页，本讲稿共29页6.2 6.2 二叉树二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二树相互转换，这样就解决了许多操作算法简单，而任何树都可以与二树相互转换，这样就解决了许多操作算法简单，而任何树都可以与二树相互转换，这样
15、就解决了许多操作算法简单，而任何树都可以与二树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。树的存储结构及其运算中存在的复杂性。树的存储结构及其运算中存在的复杂性。树的存储结构及其运算中存在的复杂性。6.2.1 6.2.1 6.2.1 6.2.1 二叉树的定义二叉树的定义二叉树的定义二叉树的定义定义：二叉树是由定义：二叉树是由定义：二叉树是由定义：二叉树是由n(n=0)n(n=0)n(n=0)n(n=0)个结点的有限集合构成，此集合或者为空个结点的有限集合构成，此集合或者为空个结点的有限集合构成，此集合或者为空个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的
16、左右子树组成，并且左右子集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。树都是二叉树。树都是二叉树。树都是二叉树。这也是一个这也是一个这也是一个这也是一个递归递归递归递归定义。二叉树可以是空集合，根可以有空的定义。二叉树可以是空集合，根可以有空的定义。二叉树可以是空集合，根可以有空的定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个左子树或空的右子树。二叉树不是树的特殊情况，它们是两个左子树或空的右子树。二叉
17、树不是树的特殊情况，它们是两个左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。概念。概念。概念。第10页，本讲稿共29页 二叉树结点的子树要区分左子树和右子树，即使只有二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的这是二叉树与树的最主要的差别。下图列出二叉树的5 5种种基本形态，基本形态，(C)C)和（和（d d）是不同的两棵二叉树。是不同的两棵二叉树。(a)空二叉树空二叉树AAAA (b)根和空的左根和空的左右子树右子树 (c)根和左子
18、树根和左子树(d)根和右子树根和右子树(e)根和左右子树根和左右子树第11页，本讲稿共29页 A A A A F F F F G G G G E E E E D D D D C C C C B B B B (a)(a)(a)(a)、(b)(b)(b)(b)是不同的二叉树，是不同的二叉树，是不同的二叉树，是不同的二叉树，(a)(a)(a)(a)的左子树有四个结点，的左子树有四个结点，的左子树有四个结点，的左子树有四个结点，(b)(b)(b)(b)的左子树有两个结点，的左子树有两个结点，的左子树有两个结点，的左子树有两个结点，(a)(a)(a)(a)A A A A G G G G E E E E
19、D D D D B B B B C C C C F F F F(b)(b)(b)(b)第12页，本讲稿共29页应用举例例1 可以用二叉树表示表达式 a+b*(c-d)-e/f e e d d c c b b f f a a +*/-第13页，本讲稿共29页6.2.2 6.2.2 二叉树的性质二叉树的性质二叉树具有下列重要性质：二叉树具有下列重要性质：性质性质1 1：在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i=1)i=1)。证明：用数学归纳法证明：证明：用数学归纳法证明：证明：用数学归纳法证明：证明：用数学归纳法证明：归纳基础：归纳基础：归纳基础：归纳基
20、础：i=1i=1i=1i=1时，有时，有时，有时，有2 2 2 2i-1i-1i-1i-1=2=2=2=20 0 0 0=1,=1,=1,=1,因为第因为第因为第因为第1 1 1 1层上只有一个根结点，所以层上只有一个根结点，所以层上只有一个根结点，所以层上只有一个根结点，所以命题成立。命题成立。命题成立。命题成立。归纳假设：归纳假设：归纳假设：归纳假设：假设对所有的假设对所有的假设对所有的假设对所有的j j j j（1 1 1 1jijijij=1)k=1)。证明：证明：证明：证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数在具有相同深度的二叉树中，仅当每一层都含有最大结点数在具有
21、相同深度的二叉树中，仅当每一层都含有最大结点数在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。时，其树中结点数最多。时，其树中结点数最多。时，其树中结点数最多。因此利用性质因此利用性质因此利用性质因此利用性质1 1 1 1可得，深度为可得，深度为可得，深度为可得，深度为k k k k的二叉树的结点数至多为：的二叉树的结点数至多为：的二叉树的结点数至多为：的二叉树的结点数至多为：2 2 2 20 0 0 0+2+2+2+21 1 1 1+2+2+2+2k-1k-1k-1k-1 =1*(1-2 =1*(1-2 =1*(1-2 =1*(1-2k k k k)/(1-2)/(
22、1-2)/(1-2)/(1-2)=2 =2 =2 =2k k k k-1-1-1-1故命题正确。故命题正确。故命题正确。故命题正确。等比数列求和公式：等比数列求和公式：等比数列求和公式：等比数列求和公式：a1*(1-qa1*(1-qa1*(1-qa1*(1-qn n n n)/(1-q)/(1-q)/(1-q)/(1-q)第15页，本讲稿共29页1234567123114589121367101415性质性质3 3：对任何一棵二叉树，如果其终端结点数为对任何一棵二叉树，如果其终端结点数为n n0 0，度为度为2 2的结点数为的结点数为n n2 2，则则n n0 0n n2 21 1。证明：证明
23、：n n1 1为二叉树为二叉树T T中度为中度为1 1的结点数的结点数 因为：二叉树中所有结点的度均小于或等于因为：二叉树中所有结点的度均小于或等于2 2 所以：其结点总数所以：其结点总数n=nn=n0 0+n+n1 1+n+n2 2 又二叉树中，除根结点外，其余结点都有一个分支进入又二叉树中，除根结点外，其余结点都有一个分支进入 设设B B为分支总数，则为分支总数，则n=B+1n=B+1 又：分支由度为又：分支由度为1 1和度为和度为2 2的结点引出，的结点引出，B=nB=n1 1+2n+2n2 2 于是，于是，n=B+1=n=B+1=n n1 1+2n+2n2 2+1=n+1=n0 0+n
24、+n1 1+n+n2 2 n n0 0=n=n2 2+1+1第16页，本讲稿共29页 两种特殊形态的二叉树：满二叉树和完全二叉树。两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为一棵深度为k k且有且有2 2k k-1-1个结点的二叉树称为个结点的二叉树称为满二叉树满二叉树。下图是一棵。下图是一棵满二叉树，对结点进行了顺序编号。依层序编号。满二叉树，对结点进行了顺序编号。依层序编号。123114589121367101415第17页，本讲稿共29页 如果深度为如果深度为k k、有有n n个结点的二叉树中各结点能够与深度为个结点的二叉树中各结点能够与深度为k k的顺序的顺序编号的满二叉树从
25、编号的满二叉树从1 1到到n n标号的结点相对应，则称这样的二叉树为标号的结点相对应，则称这样的二叉树为完全二叉完全二叉树树，满二叉树是完全二叉树的特例。，满二叉树是完全二叉树的特例。123114589126710完全二叉树完全二叉树1234567123456非完全二叉树非完全二叉树第18页，本讲稿共29页从从从从满满满满二二二二叉叉叉叉树树树树及及及及完完完完全全全全二二二二叉叉叉叉树树树树定定定定义义义义还还还还可可可可以以以以知知知知道道道道，满满满满二二二二叉叉叉叉树树树树一一一一定定定定是是是是一一一一棵棵棵棵完完完完全全全全二二二二叉叉叉叉树树树树，反反反反之之之之完完完完全全全全
26、二二二二叉叉叉叉树树树树不不不不一一一一定定定定是是是是一一一一棵棵棵棵满满满满二二二二叉叉叉叉树树树树。满满满满二二二二叉叉叉叉树树树树的的的的叶叶叶叶子子子子结结结结点点点点全全全全都都都都在在在在最最最最底底底底层层层层，而而而而完完完完全全全全二二二二叉叉叉叉树树树树的的的的叶叶叶叶子子子子结结结结点点点点可可可可以以以以分分分分布布布布在在在在最最最最下下下下面面面面两两两两层层层层。图图图图6-66-6所所所所示示示示为为为为两两两两个个个个深深深深度度度度为为为为3 3的的的的满满满满二二二二叉叉叉叉树树树树和和和和完完完完全全全全二叉树。二叉树。二叉树。二叉树。A A G G
27、F F E E D D C C B B A A E E D D C C B B图图图图 深度为深度为深度为深度为3 3 3 3的满二叉树和完全二叉树的满二叉树和完全二叉树的满二叉树和完全二叉树的满二叉树和完全二叉树第19页，本讲稿共29页 A A E E D D C C B B G G A A E E D D C C B B(a)a)a)a)(c)c)c)c)(b)b)b)b)(a)(a)(a)(a)、(b)b)b)b)完全二叉树完全二叉树完全二叉树完全二叉树(c)c)c)c)不是不是不是不是完全二叉树完全二叉树完全二叉树完全二叉树 A A G G F F E E D D C C B B第20
28、页，本讲稿共29页性质性质4 4：具有：具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为loglog2 2n n+1符号符号 x x表示不大于表示不大于x x的最大整数。的最大整数。证明：设完全二叉树的深度为证明：设完全二叉树的深度为证明：设完全二叉树的深度为证明：设完全二叉树的深度为k k k k，由完全二叉树定义可得：深度为，由完全二叉树定义可得：深度为，由完全二叉树定义可得：深度为，由完全二叉树定义可得：深度为k k k k的的的的完全二叉树的前完全二叉树的前完全二叉树的前完全二叉树的前k-1k-1k-1k-1层是满二叉树，共有层是满二叉树，共有层是满二叉树，共有层是满二叉
29、树，共有2 2 2 2k-1k-1k-1k-1-1-1-1-1个结点，第个结点，第个结点，第个结点，第k k k k层上还有若层上还有若层上还有若层上还有若干个结点，因此有干个结点，因此有干个结点，因此有干个结点，因此有n2n2n2n2k-1k-1k-1k-1-1,-1,-1,-1,另一方面，另一方面，另一方面，另一方面，n n n n又不会超过深度为又不会超过深度为又不会超过深度为又不会超过深度为k k k k的满二叉树的总结点数的满二叉树的总结点数的满二叉树的总结点数的满二叉树的总结点数2 2 2 2k k k k-1-1-1-1，又可得：，又可得：，又可得：，又可得：n2n2n2n2k
30、k k k-1,-1,-1,-1,由由由由可推出可推出可推出可推出2 2 2 2k-1k-1k-1k-1 n 2 n 2 n 2 n 2k k k k ：，取对数后有：，取对数后有：，取对数后有：，取对数后有：k-1k-1k-1k-1 loglogloglog2 2 2 2n n n n k k k1i1，则其双亲的编号是则其双亲的编号是 i i/2/2 （2 2）如果）如果2 2inin，无左孩子；否则，其左孩子是结点无左孩子；否则，其左孩子是结点2 2i i。（3 3）如果如果2 2i i1n1n，则结点则结点i i无右孩子；否则，其右孩无右孩子；否则，其右孩子是结点子是结点2 2i i1
31、 1。123114589126710第24页，本讲稿共29页i=1i=1时，时，2i=22i=2，2i+1=32i+1=3。左孩子和右孩子刚。左孩子和右孩子刚好是结点好是结点2 2和和3 3。对于对于i1，分两种情况：，分两种情况：设第设第j j层的第一个结点的编号为层的第一个结点的编号为i i；1 1j j loglog2 2n n ,i=2,i=2j-1j-1 =j+1层第一个结点的编号层第一个结点的编号层第一个结点的编号层第一个结点的编号 j层第一个结点的左孩子必为第层第一个结点的左孩子必为第层第一个结点的左孩子必为第层第一个结点的左孩子必为第j+1j+1层的第一个结点，其层的第一个结点
32、，其层的第一个结点，其层的第一个结点，其编号为编号为编号为编号为2(j+1)-1=2=2j j=2(2=2(2j-1j-1)=2i)=2i，若，若n2in2i，则无左孩子；，则无左孩子；，则无左孩子；，则无左孩子；j j层第一个结点的右孩子必为第层第一个结点的右孩子必为第层第一个结点的右孩子必为第层第一个结点的右孩子必为第j+1层的第二个结点，其编层的第二个结点，其编层的第二个结点，其编层的第二个结点，其编号为号为号为号为2i+12i+1，若，若，若，若n2i+1n1，分两种情况：，分两种情况：设第设第设第设第j j j j层的第一个结点的编号为层的第一个结点的编号为层的第一个结点的编号为层的
33、第一个结点的编号为i i i i；1 1 1 1 j j j j loglog2 2n n ,i=2,i=2j-1j-1 =j+1 =j+1层第一个结点的编号层第一个结点的编号层第一个结点的编号层第一个结点的编号 设第设第设第设第j j j j层上某个结点的编号为层上某个结点的编号为层上某个结点的编号为层上某个结点的编号为i i i i，且，且，且，且2i+1n2i+1n2i+1n2i+1n，则其左孩子为则其左孩子为则其左孩子为则其左孩子为2i2i2i2i，右孩子为，右孩子为，右孩子为，右孩子为2i+12i+12i+12i+1。1 1 1 1 j j j j loglog2 2n n ,2,2
34、j-1 j-1 i i i i =编号为编号为编号为编号为i+1i+1的结点，右兄弟或者堂兄弟的结点，右兄弟或者堂兄弟的结点，右兄弟或者堂兄弟的结点，右兄弟或者堂兄弟若编号为若编号为若编号为若编号为i+1i+1的结点有左孩子，则编号必为的结点有左孩子，则编号必为的结点有左孩子，则编号必为的结点有左孩子，则编号必为2i+1+1=2(i+1)2i+1+1=2(i+1)，若编号为若编号为若编号为若编号为i+1i+1的结点有右孩子，则编号必为的结点有右孩子，则编号必为的结点有右孩子，则编号必为的结点有右孩子，则编号必为2i+3=2(i+1)+12i+3=2(i+1)+1。所以，性质所以，性质所以，性质
35、所以，性质5 5 5 5的的的的(2)(2)(2)(2)和和和和(3)(3)(3)(3)得证，得证，得证，得证，（2 2 2 2）如果）如果）如果）如果2in2in2in2in，无左孩子；否则，其左孩子是结点，无左孩子；否则，其左孩子是结点，无左孩子；否则，其左孩子是结点，无左孩子；否则，其左孩子是结点2i2i2i2i。（3 3 3 3）如果）如果）如果）如果2i2i2i2i1n1n1n1n，则结点，则结点，则结点，则结点i i i i无右孩子；否则，其右孩子是结点无右孩子；否则，其右孩子是结点无右孩子；否则，其右孩子是结点无右孩子；否则，其右孩子是结点2i2i2i2i1 1 1 1。推出，性
36、质推出，性质推出，性质推出，性质5 5 5 5的的的的(1)(1)(1)(1)（1 1）如果）如果i i1 1，则结点则结点i i无双亲，是二叉树的根；如果无双亲，是二叉树的根；如果i1i1，则其双亲的编号是则其双亲的编号是 i i i i/2/2/2/2 第26页，本讲稿共29页练习练习一颗完全二叉树上有一颗完全二叉树上有1001个结点，其中叶子结个结点，其中叶子结点的个数是点的个数是_。A.250 B.500 C.501 D.505解答：解答：由二叉树的性质可知：由二叉树的性质可知：n n0 0=n=n2 2+1+1，且完全二叉树的，且完全二叉树的n n1 1=0=0或者或者n n1 1=
37、1=1；已；已知二叉树的总结点数知二叉树的总结点数n=nn=n0 0+n+n1 1+n+n2 2，即有，即有 n=2nn=2n0 0+n+n1 1-1-1将总结点数将总结点数10011001代入，得代入，得 100110012n2n0 0+n+n1 1-1-1，即，即1002=2n1002=2n0 0+n+n1 1 因因10021002为偶数，所以为偶数，所以n n1 1=0=0，解之得：，解之得：n n0 0=501=501第27页，本讲稿共29页练习练习在一棵在一棵 具有具有n个结点的完全二叉树，树枝结点个结点的完全二叉树，树枝结点的最大编号为的最大编号为_。A.B.C.D.解答：解答：由
38、二叉树的性质由二叉树的性质5 5可知答案为可知答案为D D。性质性质5 5：如果对一棵有如果对一棵有n n个结点的完全二叉树的结点按层序编号个结点的完全二叉树的结点按层序编号,则则对任一结点对任一结点i i（1in),1in),有：有：P125P125 （1 1）如果）如果i i1 1，则结点则结点i i无双亲，是二叉树的根；如果无双亲，是二叉树的根；如果i1i1，则其则其双亲的编号是双亲的编号是 i i/2/2 （2 2）如果）如果2 2inin，无左孩子；否则，其左孩子是结点无左孩子；否则，其左孩子是结点2 2i i。（3 3）如果如果2 2i i1n1n，则结点则结点i i无右孩子；否则，其右孩子是结点无右孩子；否则，其右孩子是结点2 2i i1 1。第29页，本讲稿共29页