6.2二叉树 ●二叉树在树结构的应用中起着非常重要的作用,因为对二叉 树的许多操作算法简单,而任何树都可以与二叉树相互转 换,这样就解决了树的存储结构及其运算中存在的复杂性。 定义:二叉树是由n(n>=0)个结点的有限集合构成,此集合 或者为空集,或者由一个根结点及两棵互不相交的左右子树 组成,并且左右子树都是二叉树 ●这也是一个递归定义。二叉树可以是空集合,根可以有空的 左子树或空的右子树。二叉树不是树的特殊情况,它们是两 个概念。 北京邮电大学自动化学院
北京邮电大学自动化学院 6 6.2 二叉树 ⚫ 二叉树在树结构的应用中起着非常重要的作用，因为对二叉 树的许多操作算法简单，而任何树都可以与二叉树相互转 换，这样就解决了树的存储结构及其运算中存在的复杂性。 ⚫ 定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合 或者为空集，或者由一个根结点及两棵互不相交的左右子树 组成，并且左右子树都是二叉树。 ⚫ 这也是一个递归定义。二叉树可以是空集合，根可以有空的 左子树或空的右子树。二叉树不是树的特殊情况，它们是两 个概念
6.2二叉树 ●二叉树结点的子树要区分左子树和右子树,即使只有一棵 子树也要进行区分,说明它是左子树,还是右子树。这是 二叉树与树的最主要的差别。图63列出二差树的5种基本 形态,图63c)和图63(d)是不同的两棵二叉树。 A A B B (b) 根和空的(c) 空二叉树左右子树根和左子树根和右子树根和左右子树 ●图63二叉树的5种形式 北京邮电大学自动化学院
北京邮电大学自动化学院 7 (a) 空二叉树 A A B A B A B C (b) 根和空的 左右子树 (c) 根和左子树 (d) 根和右子树 (e) 根和左右子树 ⚫ 图6.3二叉树的5种形式 ⚫ 二叉树结点的子树要区分左子树和右子树，即使只有一棵 子树也要进行区分，说明它是左子树，还是右子树。这是 二叉树与树的最主要的差别。图6.3列出二差树的5种基本 形态，图6.3(C) 和图6.3（d）是不同的两棵二叉树。 6.2 二叉树
●62.2二叉树的性质 ●二叉树具有下列重要性质: 性质1:在二叉树的第退层上至多有2个结点(>=1)。 ●采用归纳法证明此性质。 当=1时,只有一个根结点,21=20=1命题成立。 现在假定对所有的,1可<i,命题成立,即第层上至多有 2)1个结点,那么可以证明=时命题也成立。由归纳假设可 知,第i-1层上至多有22个结点。 ●由于二叉树每个结点的度最大为2,故在第层上最大结点数 为第i-1层上最大结点数的二倍, ●即2×212=21。命题得到证明。 北京邮电大学自动化学院
北京邮电大学自动化学院 8 ⚫ 6.2.2 二叉树的性质 ⚫ 二叉树具有下列重要性质： ⚫ 性质1: 在二叉树的第i层上至多有2 i-1个结点(i>=1)。 ⚫ 采用归纳法证明此性质。 ⚫ 当i=1时，只有一个根结点，2 i-1=20 =1,命题成立。 ⚫ 现在假定对所有的j，1<=j<i，命题成立，即第j层上至多有 2 j-1个结点，那么可以证明j＝i时命题也成立。由归纳假设可 知，第i－1层上至多有2 i-2个结点。 ⚫ 由于二叉树每个结点的度最大为2，故在第i层上最大结点数 为第i－1层上最大结点数的二倍， ⚫ 即2×2 i-2＝2 i-1。命题得到证明
性质2:深度为k的二叉树至多有2k-1个结点(k>=1) 深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点 数之和,由性质1得到每层上的最大结点数, ∑(第禔层上的最大结点数)=∑21=24-1 性质3:对任何一棵二叉树T,如果其终端结点数为no,度为2的 结点数为n2,则no=n2+1。 设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二 叉树中所有结点均小于或等于2,所以有: notn,tn2 (6-1) ●再看二叉树中的分支数,除根结点外,其余结点都有一个进入分 支,设B为二叉树中的分支总数, ●则有 N=B+1。 北京邮电大学自动化学院
北京邮电大学自动化学院 9 ⚫ 性质2：深度为k的二叉树至多有2 k－1个结点（k>=1). 2 2 1 1 1 1 = = − = = − k k i k i i （第i层上的最大结点数） ⚫ 性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的 结点数为n2，则n0＝n2＋1。 ⚫ 深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点 数之和，由性质1得到每层上的最大结点数， ⚫ 设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二 叉树中所有结点均小于或等于2，所以有： ⚫ N＝n0＋n1＋n2 (6-1) ⚫ 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分 支，设B为二叉树中的分支总数， ⚫ 则有： N＝B＋1
性质3:对任何一棵二叉树T,如果其终端结点数为n,度为2的 结点数为12,则n0-m2+1。 ●由于这些分支都是由度为1和2的结点射出的,所以有 ●B=n+2n N=B+1=n1+2×n2+1(6-2 由式(6-1)和(6-2)得到: N=n0+n1+n2 (6-1) ●n+n1+n2=n1+2*n2+ 0 2 +1 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 ⚫ 由于这些分支都是由度为1和2的结点射出的，所以有： ⚫ B＝n1+2*n2 ⚫ N＝B＋1＝n1＋2×n2＋1 （6－2) ⚫ 由式（6－1）和（6－2）得到： ⚫ N＝n0＋n1＋n2 （6-1） ⚫ 性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的 结点数为n2，则n0＝n2＋1。 ⚫ n0+n1+n2=n1+2*n2+1 ⚫ n0＝n2＋1