第五章树 5.1树的基本概念和术语 树型结构是一类重要的非线性数据结构,在C语言中,从指 针应用的角度出发,介绍了一种特殊类型的树即二叉树的一些 基本概念和基本操作.本章从更一般的角度来介绍树型数据结 构 树的定义:树是m(m>=0)个结点的有限集在一棵非空树中: (1)有且仅有一个特定的称为根的结点; (2)当n>时,其余结点可分为m(m>0)个互不相交的有限集 132 ,Tn,且T(1≤i≤m)本身又是一棵树,称 为根的子树 这是一个递归的定义,即在树的定义中又用到了树
第 五 章 树 5 . 1 树的基本概念和术语 树型结构是一类重要的非线性数据结构, 在C语言中, 从指 针应用的角度出发, 介绍了一种特殊类型的树即二叉树的一些 基本概念和基本操作. 本章从更一般的角度来介绍树型数据结 构. 树的定义: 树是n(n>=0)个结点的有限集.在一棵非空树中: (1) 有且仅有一个特定的称为根的结点; (2) 当n>1时, 其余结点可分为m(m>0)个互不相交的有限集 T T Ti T m , , , , , 1 2 ,且 T (1 i m) i 本身又是一棵树, 称 为根的子树. 这是一个递归的定义, 即在树的定义中又用到了树
下面给出树型结构的一种较为直观的逻辑示意图 ④(a)图是只有一个根结点的树 (a)(b)图是有13个结点的树,其中A是整棵树 的根结点,其余结点分成三个互不相交的 子集:T={B,E,FK,L} T=CG ⑥⑤ T=D,H1,J, M T2T2,7是根A的子树,且本身也 是一棵树.例如7,其根为B,其余结点 (b) 分成互不相交的两个子集:1={E,K,D} 2={F},而T中E是根,{K}和{L}是E的两棵互不相交的 子树,其本身又是只有一个根结点的树.下面给出树型结 构的一些基本术语 树的结点:包含一个数据元素及若干指向其子树的分 支
下面给出树型结构的一种较为直观的逻辑示意图. A (a)图是只有一个根结点的树； (a) (b)图是有13个结点的树, 其中A是整棵树 A 的根结点, 其余结点分成三个互不相交的 B C E F K L G H I J D M (b) 子集: T D H I J M T C G T B E F K L , , , , , , , , , 3 2 1 = = = 1 2 3 T ,T ,T 是根A的子树, 且本身也 是一棵树. 例如 , T1 其根为B,其余结点 分成互不相交的两个子集: T11 = E,K,L T12 = F , 而 T11 中E是根, {K}和{L}是E的两棵互不相交的 子树, 其本身又是只有一个根结点的树. 下面给出树型结 构的一些基本术语. 树的结点:包含一个数据元素及若干指向其子树的分 支
结点的度结点拥有的子树的棵数 例如左图中,结点A的度为3,C的 度为1,F的度为0 间④@①叶子度为结点叫叶子也叫终端 结点.如K,L,G,JJ,M都是树的叶 子 非终端结点:度不为0结点也叫分支结点.除根结点外,分 支结点也叫内部结点 树的度树内各结点的度的最大值,如上图所示树的度为3 孩子:结点的子树的根称为该结点的孩子,相应地,该结点 称为孩子的双亲如上图所示的树中,D为A的子树的根,则 D是A的孩子,A是D的双亲 兄弟:同一个双亲的孩子之间互称兄弟例如,H,L,J互为兄弟 树支:连接两个结点的线段,又叫树边
结点的度:结点拥有的子树的棵数. 例如左图中, 结点A的度为3, C的 度为1, F的度为0. 叶子:度为0结点叫叶子,也叫终端 结点. 如K,L,G,I,J,M都是树的叶 子. A B C E F K L G H I J D M 非终端结点:度不为0结点,也叫分支结点. 除根结点外, 分 支结点也叫内部结点. 树的度:树内各结点的度的最大值, 如上图所示树的度为3. 孩子:结点的子树的根称为该结点的孩子, 相应地, 该结点 称为孩子的双亲.如上图所示的树中, D为A的子树的根, 则 D是A的孩子, A是D的双亲. 兄弟:同一个双亲的孩子之间互称兄弟.例如, H,I,J互为兄弟 树支:连接两个结点的线段, 又叫树边
一层层次:从根开始定义,根 二层为第一层,根的孩子为第 国⊙0@①①“三层则其子树的根就在第K+1 层 四层深度:树结点的最大层次 数称为树的深度或高度.上图所示树的深度为4 若树中结点的各子树从左至右是有次序的(即不能互换) 则称该树为有序树,否则为无序树 森林:是零棵或多棵树的集合.对上图的树,只要把它的 根结点去掉,就可变成由三棵树组成的森林.如下图:
层次:从根开始定义, 根 为第一层, A B C E F K L G H I J D M 一层 二层 三层 四层 根的孩子为第 二层. 若某结点在第K层, 则其子树的根就在第K+1 层. 深度:树结点的最大层次 数称为树的深度或高度. 上图所示树的深度为4. 若树中结点的各子树从左至右是有次序的(即不能互换), 则称该树为有序树, 否则为无序树. 森林:是零棵或多棵树的集合. 对上图的树, 只要把它的 根结点去掉, 就可变成由三棵树组成的森林. 如下图: B C E F K L G H I J D M
5.4二叉树 54.1二又树的定义和性质 二叉树也称为二分树或二元树,是树型结构的一个重 要类型 定义:二叉树是n>=0个结点的有限集合,它或者是 空集(即n=0时,或者由一个根结点及两棵互不相交的分别 称为根的左子树和右子树的二叉树组成 二叉树的定义也是递归的.二叉树有下面五种基本 形态 (a)空树 (b)只有根结点(c)只有左子树(d)只有右子树(l)左右子树均不空
5 . 4 二叉树 5.4.1 二叉树的定义和性质 二叉树也称为二分树或二元树, 是树型结构的一个重 要类型. 定义: 二叉树是n>=0个结点的有限集合, 它或者是 空集(即n=0时),或者由一个根结点及两棵互不相交的分别 称为根的左子树和右子树的二叉树组成. 二叉树的定义也是递归的. 二叉树有下面五种基本 形态: (a)空树 (b)只有根结点 (c)只有左子树 (d)只有右子树 (e)左右子树均不空
下面介绍二叉树的性质: 性质1在二叉树中,第层的结点数最多为2(≥1) 证明:应用归纳法有,=1时,为第1层,只有一个根结点, 显然21=20=1正确;现假定对所有的1≤j< 命题成立,即第/层上至多有2个结点,那么可证明 j=i时命题也成立由归纳假设:第—1层上至多有 2-2个结点,因二叉树中的每个结点的度最大为2,故在第讠 层上的最大结点数为第一1层上的最大结点数的2倍,即 2×21-2=21 性质2深度为/的二叉树至多有2-1(k≥1)个结点 证明:由性质1,深度为的二叉树的最大结点数为 ∑(第i层上的最大结点数) ∑2 2-1(q=2,a1=1)
下面介绍二叉树的性质： 性质1 在二叉树中, 第 i 层的结点数最多为 2 ( 1). 1 − i i 证明: 应用归纳法有, i =1 时, 为第1层,只有一个根结点, 显然 2 2 1 1 0 = = i− 正确; 现假定对所有的 j,1 j i 命题成立, 即第 j 层上至多有 1 2 j− 个结点, 那么可证明 j = i 时命题也成立.由归纳假设: 第 i −1 层上至多有 2 2 i− 个结点,因二叉树中的每个结点的度最大为2, 故在第 i 层上的最大结点数为第 i −1 层上的最大结点数的2倍, 即 2 2 2 . −2 −1 = i i 性质2 深度为 k 的二叉树至多有 2 −1(k 1) k 个结点. 证明: 由性质1,深度为 k 的二叉树的最大结点数为: = k i 1 (第 i 层上的最大结点数) 2 1( 2, 1) 1 (1 ) 2 1 1 1 1 = − = = − − = = = − q a q a q k k k i i
性质3对任何一棵二叉树T,如果其终端结点数(即叶子 数)为m,度为2的结点数为n2,则m=n2+1 证明:设m1为二叉树T中度为1的结点数(即此结点仅有 棵子树,左子树或右子树,但非叶子),因二叉树中所有 结点的度均小于或等于2,所以其结点数为n=n0+n1+n2 又因为,除根结点外,其余结点都有一条分支进入,设B为 分支总数,则n=B+1,由于这些分支是由度为1或2射出的 所以又有B=n1+2n2,从而n=n+2n2+1,故可得 b+n1+n2=n1+2n2+1,m0=n2+1 下面介绍两种特殊形态的二叉树,即满二叉树和完全二 叉树.定义一棵深度为k且有2-1个结点的二叉树为满二叉 树,其特点是每一层上的结点数都是最大结点数
性质3 对任何一棵二叉树T, 如果其终端结点数(即叶子 数)为 0 n ,度为2的结点数为 2 n , 则 n0 = n2 +1 证明: 设 1 n 为二叉树T中度为1的结点数(即此结点仅有一 棵子树, 左子树或右子树, 但非叶子), 因二叉树中所有 结点的度均小于或等于2, 所以其结点数为 n = n0 + n1 + n2 : 又因为, 除根结点外, 其余结点都有一条分支进入, 设B为 分支总数, 则 n = B +1 ,由于这些分支是由度为1或2射出的 所以又有 B = n1 + 2n2 , 从而 n = n1 + 2n2 +1 , 故可得 n0 + n1 + n2 = n1 + 2n2 +1, n0 = n2 +1 下面介绍两种特殊形态的二叉树, 即满二叉树和完全二 叉树. 定义一棵深度为 k 且有 2 −1 k 个结点的二叉树为满二叉 树, 其特点是每一层上的结点数都是最大结点数
下面这棵树就是满二叉树,对左边的满二叉树的结点进行 连续编号,并约定编号顺序是 从根结点起,自上而下,自左 至右进行.则可引出 另一种特殊形态的二 叉树,即完全三 (⑨①@③④④定义:深度为 k的有n个结点的二叉树,当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一对应,称此二叉 树为完全二叉树.如下图所示
下面这棵树就是满二叉树, 对左边的满二叉树的结点进行 连续编号, 并约定编号顺序是 从根结点起, 自上而下, 自左 1 2 15 4 5 8 9 11 12 13 14 3 10 6 7 至右进行. 则可引出 另一种特殊形态的二 叉树, 即完全二 叉树. 定义: 深度为 k 的有 n 个结点的二叉树, 当且仅当其每一个结点都与深度 为 k 的满二叉树中编号从1至 n 的结点一一对应, 称此二叉 树为完全二叉树. 如下图所示. 1 2 4 5 8 9 3 10 6 7
下图是非完全二叉树,即为一棵一般的二叉树 有10个结点的完全二叉树重新显示 在下面.可分析出其特点为 1.叶子结点只可能在第 k层及第k-1层上出现 G⑨(为最大层次 2对任一结点,若其右分支下的子孙 的最大层次为l,则其左分支下的子孙 ①的最大层次必为域或H 3.完全二叉树可从满二 3)叉树中,自最高层次向 上,且每层自右至 左顺序删除叶子结 点而获得 8)⑧@注意:满足特点1或2,或满足特点1和2的二 叉树不一定是完全二叉树,但若二叉树是完全二叉树,则一定
下图是非完全二叉树, 即为一棵一般的二叉树. 1 有10个结点的完全二叉树重新显示 2 4 5 8 9 11 3 6 7 在下面. 1 2 4 5 8 9 3 10 6 7 可分析出其特点为: 1.叶子结点只可能在第 k层及第k -1层上出现 (k为最大层次). 2.对任一结点, 若其右分支下的子孙 的最大层次为l, 则其左分支下的子孙 的最大层次必为l或l+1. 3.完全二叉树可从满二 叉树中, 自最高层次向 上, 且每层自右至 左顺序删除叶子结 点而获得. 注意: 满足特点1或2, 或满足特点1和2的二 叉树不一定是完全二叉树, 但若二叉树是完全二叉树, 则一定
满足特点1和2.而从特点3得到的二叉树一定是完全二叉 树.完全二叉树有两个重要的性质 性质4具有n个结点的完全二叉树的深度为Log2n」+1 证明:假设具有n个结点的完全二叉树的深度为k,则由 性质2和完全二叉树的定义有2k-1-11 则其双亲是结点i/2」
满足特点1和2. 而从特点3得到的二叉树一定是完全二叉 树. 完全二叉树有两个重要的性质. 性质4 具有n个结点的完全二叉树的深度为 log2 n +1 证明: 假设具有n个结点的完全二叉树的深度为 k , 则由 性质2和完全二叉树的定义有 2 1 2 1 1 − − k− k n (注意到 深度为 k , 如 n k − = − 2 1 1 , 则深度为 k −1) 由上式得 k k 2 n 2 1 − ,则 k − n k 2 1 log ,因为 k 是整数, 所以 log 1. k = 2 n + 性质5 如果对一棵具有n个结点的完全二叉树(其深度为 log 1) 2 n + 的结点按层序编号(从第一层到第 log2 n +1 层, 每层从左到右),则对任一结点 i(1 i n) , 有 (1) 如果 i =1 ,则结点是二叉树的根, 无双亲; 如果 i 1 则其双亲是结点 i / 2