北京邮电大学自动化学院：《数据结构》第六章 树与二叉树

第六章树和二叉树 6.1树的定义和基本概念 62二叉树 6.3遍历二叉树 ●64树和森林 65赫夫曼树及其应用 北京邮电大学自动化学院

北京邮电大学自动化学院 1 第六章 树和二叉树 ⚫ 6.1 树的定义和基本概念 ⚫ 6.2 二叉树 ⚫ 6.3 遍历二叉树 ⚫ 6.4 树和森林 ⚫ 6.5 赫夫曼树及其应用

61树的定义和基本术语 树型结构是一类重要的非线性结构。树结构在客观世界里是大 量存在的,树在计算机领域中也有着广泛的应用,例如在编译 程序中,用树来表示源程序的语法结构;在数据库系统中,可 用树来组织信息;在分析算法的行为时,可用树来描述其执行 过程等等。 1、定义树是n(m>=0)个结点的有限集T,T为空时称为空 树,否则它满足如下两个条件 ●(1)有且仅有一个特定的称为根的结点; ·(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集 T1,T2T3Tm,其中每个子集又是一棵树,并称其为根的子 树。 北京邮电大学自动化学院

北京邮电大学自动化学院 2 ⚫ 树型结构是一类重要的非线性结构。树结构在客观世界里是大 量存在的，树在计算机领域中也有着广泛的应用，例如在编译 程序中，用树来表示源程序的语法结构；在数据库系统中，可 用树来组织信息；在分析算法的行为时，可用树来描述其执行 过程等等。 6.1 树的定义和基本术语 ⚫ 1、定义 树是n(n>=0)个结点的有限集T，T为空时称为空 树，否则它满足如下两个条件： ⚫ （1）有且仅有一个特定的称为根的结点； ⚫ （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为根的子 树

1、定义 只有根结点的树 A 有子树的树A根 B)IIC D E F从G(H K 子树 北京邮电大学自动化学院

北京邮电大学自动化学院 3 A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树 1、定义

2、基本术语 结点一表示树中的元素,包括数据项及若干指向其子树的分支 结点的度( degree)一结点拥有的子树数 叶子(eaf—一度为0的结点 孩子chid)—结点子树的根称为该结点的孩子 双亲( parents)——孩子结点的上层结点叫该结点的 兄弟( sibling——同一双亲的孩子 ●树的度—一棵树中最大的结点度数 结点的层次(eve)——从根结点算起,根为第一层,它的孩子 为第二层 ·深度( depth)—树中结点的最大层次数 森林( forest)-—m(m≥0)棵互不相交的树的集合 北京邮电大学自动化学院 4

北京邮电大学自动化学院 4 ⚫ 结点——表示树中的元素，包括数据项及若干指向其子树的分支 2、基本术语 ⚫ 结点的度(degree)——结点拥有的子树数 ⚫ 叶子(leaf)——度为0的结点 ⚫ 孩子(child)——结点子树的根称为该结点的孩子 ⚫ 双亲(parents)——孩子结点的上层结点叫该结点的~ ⚫ 兄弟(sibling)——同一双亲的孩子 ⚫ 树的度——一棵树中最大的结点度数 ⚫ 结点的层次(level)——从根结点算起，根为第一层，它的孩子 为第二层…… ⚫ 深度(depth)——树中结点的最大层次数 ⚫ 森林(forest)——m(m0)棵互不相交的树的集合

2、基本术语 结点A的度:3 叶子:K,L,F,G,M,l,J 结点B的度:2 结点M的度:0 A 树的深度:4 树的度:3 结点A的层次 D 结点M的层次: 结点双亲:D E F(G(H 结点L的双亲:E K 结点F,G为堂兄弟 结点A是结点F,G的祖先 结点A的孩子:B,C,D 结点B,C,D为兄弟 结点B的孩子:E,F 结点K,L为兄弟 北京邮电大学自动化学院

北京邮电大学自动化学院 5 A B C D E F G H I J K L M 结点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的祖先 2、基本术语

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