第五章树 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)左右子树均不空