数据结构：树的基本概念

树结构是一类重要的非线性数据结构。直观来看，树是以分支关系定义的层次结构。

树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用，尤以二叉树最为常用。如在操作系统中，用树来表示文件目录的组织结构，在编译系统中，用树来表示源程序的语法结构，在数据库系统中，树结构也是信息的重要组织形式之一。

树这种非线性结构比线性结构要复杂得多，内容也比较多，所以这部分知识会分多篇文章来讨论。接下来，我们先从树的基本概念开始讲起。

一、树

1.1、定义

树（Tree）是n（n>=0）个结点的有限集，它或为空树，或为非空树。对于非空树T：

  • 有且仅有一个称之为根的结点；
  • 除根结点以外的其余结点可分为m（m>0）个互不相交的有限集T1T_1，T2T_2，…，TnT_n，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树的结构定义是一个递归的定义，即在树的定义中又用到树的定义。如下图所示：图（a）是只有一个根结点的树；图（b）是有13个结点的树，其中A是根，其余结点可分成3个互不相交的子集：T1T_1={B, E, F, K, L}，T2T_2={C, G}，T3T_3={D, H, I, J, M}。T1T_1、T2T_2和T3T_3都是根A的子树，且本身也是一棵树。比如，在树T1T_1中，B是根，其余结点可分成2个互不相交的子集：T11T_{11}={E, K, L}，T12T_{12}={F}。T11T_{11}和T12T_{12}都是B的子树；而在树T11T_{11}中，E是根，{K}和{L}是E的两棵互不相交的子树，其本身又是只有一个根结点的树。

img

1.2、表示方法

树的表示方法，除了前面所使用的树形表示法之外，还有三种常用的表示方法：嵌套集合表示法、广义表表示法和凹形表示法。如下图所示：图（a）采用的是嵌套集合表示法，即一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个；图（b）采用的是广义表表示法，根作为表的名字写在表的左边；图（c）采用的是凹形表示法，类似书的编目。

img

表示方法的多样化，说明了树结构在日常生活中及计算机程序设计中的重要性。一般来说，分等级的分类方案都可用层次结构来表示，也就是说，都可由一个树结构来表示。

1.2、基本术语

image-20240120174516210

下面，以上图为例，介绍树结构中的一些基本术语：

  • 结点：树中的一个独立单元。例如，在上图中有A、B、C、D等13个结点。
  • 结点的度：结点拥有的子树数。例如，上图中A的度为3，C的度为1，F的度为0。
  • 树的度：树内结点度的最大值。例如，上图所示树的度为3。
  • 结点的层次：从根开始定义，根为第一层，根的孩子为第二层。树中任一结点的层次等于其双亲结点的层次加1。
  • 树的深度（高度）：树中结点层次的最大值。例如，上图所示树的深度为4。
  • 终端结点（叶子节点）：度为0的结点。例如，上图中的结点K、L、F、G、M、I、J都是树的叶子。
  • 非终端结点（分支结点）：度不为0的结点。例如，上图中除K、L、F、G、M、I、J之外的结点都是非终端结点。
  • 内部结点：除根结点和叶子结点之外的结点。例如，上图中除A、K、L、F、G、M、I、J之外的结点都是内部结点。
  • 双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。例如，在上图中B是A的孩子，A是B的双亲。
  • 兄弟：双亲相同的结点之间是兄弟关系。例如，上图中H、I和J互为兄弟，它们的双亲都是D。
  • 堂兄弟：双亲互为兄弟的结点之间是堂兄弟关系。例如，上图中G与E、F、H、I、J互为堂兄弟。
  • 祖先：从根到该结点所经分支上的所有结点。例如，上图中A、D和H都是M的祖先。
  • 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。例如，上图中E、K、L和F都是B的子孙。
  • 有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
  • 森林：m（m>=0）棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。

就逻辑结构而言，任何一棵树都是一个二元组Tree=(root, F)，其中root是数据元素，称作树的根结点；F是m（m>=0）棵树的森林，F=(T1T_1,T2T_2,…,TmT_m)，其中TiT_i=(rir_i, FiF_i)称作根root的第i棵子树；当m≠0时，在树根和其子树森林之间存在下列关系：

RF={<root,ri>∣i=1,2,...,m(m>0)}RF=\{ <root,r_i>|i=1,2,...,m(m>0) \}

二、二叉树

2.1、定义

二叉树（Binary Tree）是n个结点所构成的集合，它或为空树；或为非空树，对于非空树T：

  • 有且仅有一个称之为根的结点；
  • 除根结点以外的其余结点可分为两个互不相交的子集T1T_1和T2T_2，分别称为T的左子树和右子树，且T1T_1和T2T_2本身又都是二叉树。

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

  • 二叉树中每个结点最多只有两颗子树（即二叉树中不存在度大于2的结点）；
  • 二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由于这两棵子树也是二叉树，则由二叉树的定义可知，它们也可以是空树。由此，二叉树可以有5种基本形态，如下图所示：

image-20240120180029418

2.2、性质

性质1：在二叉树的第i层上最多有2i−12^{i-1}（i>=1）个结点

该性质可用归纳法证得：

  • 当i=1时，只有一个根结点。显然，2i−12^{i-1}=202^0=1，命题成立。
  • 现假定对所有的j（1<=j<i），命题是成立的，即在第j层上最多有2j−12^{j-1}个结点。那么，可以证明j=i时，命题也成立。
  • 由归纳假设，第i-1层上最多有2i−22^{i-2}个结点。由于二叉树中每个结点的度最多2，故在第i层上结点数的最大值为第i-1层上结点数的最大值的2倍，即2i−22^{i-2} * 2 = 2i−12^{i-1}。

性质2：在深度为k的二叉树中最多有2k−12^k-1（k>=1）个结点

在深度为k的二叉树中，结点数的最大值应该是该二叉树中每一层上结点数最大值的总和。由性质1可知，在深度为k的二叉树中，结点数的最大值为：

20+21+⋅⋅⋅+2k−1=∑i=1k2i−1=2k−12^0+2^1+···+2^{k-1}=\sum_{i=1}^k 2^{i-1}=2^k-1

性质3：对任何一棵二叉树T，如果度为0的结点数为n0n_0，度为2的结点数为n2n_2，则n0n_0=n2n_2+1

假设在二叉树T中，度为1的结点数为n1n_1。因为二叉树中所有结点的度均小于或等于2，所以二叉树T的结点总数为：

n=n0+n1+n2(公式1)n=n_0+n_1+n_2 \tag{公式1}

再看二叉树中的分支数。除了根结点外，其余结点都有一个分支进入，假设二叉树T的分支总数为B，则n
=B+1。由于这些分支是由度为1或2的结点射出的，所以又有B=n1n_1+2n2n_2。于是可得：

n=n1+2n2+1(公式2)n=n_1+2n_2+1 \tag{公式2}

由公式1和公式2可得：

n0=n2+1n_0=n_2+1

满二叉树

满二叉树：一棵深度为k且有2k2^k-1个结点的二叉树。如下图所示，是一棵深度为4的满二叉树。

image-20240121105800301

满二叉树的特点是：每一层上的结点数都达到最大值，即每一层i的结点数都具有最大值2i−12^{i-1}。这也就是说，在满二叉树中，不存在度数为1的结点，且所有叶子结点都在第k层上。

完全二叉树

完全二叉树：若一棵深度为k的二叉树，其前k-1层是一棵满二叉树，而在第k层上所有结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。如下图所示，是一棵深度为4的完全二叉树。

image-20240121110037379

而下图所示的两棵二叉树都不是完全二叉树。在图（a）中，最下面一层上的结点6和7都不在最左边的位置上。在图（b）中，最下面一层上的结点6不在最左边的位置上。

image-20240121111606790

完全二叉树的特点是：

  • 叶子结点只可能在层次最大的两层上出现；
  • 对任一结点，若其右分支下的子孙的最大层次为m，则其左分支下的子孙的最大层次必为m或m+1。

性质4：具有n个结点的完全二叉树的深度为⌊log⁡2n⌋\lfloor \log_2n \rfloor + 1

假设二叉树的深度为k，则根据完全二叉树的定义可知，它的前k-1层是深度为k-1的满二叉树，共有2k−1−12^{k-1}-1个结点。由于二叉树的深度为k，所以第k层上还有结点，因此该二叉树的节点数n>2k−1−12^{k-1}-1。再由性质2可知n<=2k−12^k-1，所以有：

2k−1−1<n<=2k−12^{k-1}-1<n<=2^k-1

由此可推出：

2k−1<=n<2k2^{k-1}<=n<2^k

三项取对数后有k-1<=log⁡2n\log_2n<k，因为k为整数，所以k=⌊log⁡2n⌋\lfloor \log_2n \rfloor + 1

性质5：如果对一棵有n个结点的完全二叉树（其深度为⌊log⁡2n⌋\lfloor \log_2n \rfloor + 1）的结点按层序编号（从第1层到第⌊log⁡2n⌋\lfloor \log_2n \rfloor + 1层，每层从左到右），则对任一结点i（1<=i<=n），以下结论均成立：

  • 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲PARENT(i)是结点⌊i/2⌋\lfloor i/2 \rfloor。
  • 如果2i>n，则结点i无左孩子，即结点i为叶子结点；否则其左孩子LCHILD(i)是结点2i。
  • 如果2i+1>n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1。

该性质可通过下图所描述的结点与编号的对应关系直观地看出：

image-20240121161800426

2.3、存储结构

和线性表类似，二叉树的存储结构也可采用顺序存储和链式存储两种方式。

2.3.1、顺序存储结构

在C语言中，二叉树的顺序存储结构的类型描述如下：

1
2
3
4
5
6
7
// 二叉树的结点数最大值
#define MAXSIZE 100

// 0号单元存储根结点
typedef TElemType SqBiTree[MAXSIZE];

SqBiTree bt;

顺序存储结构使用一组地址连续的存储单元来存储数据元素，为了能够在存储结构中反映出结点之间的逻辑关系，必须将二叉树中的结点依照一定的规律安排在这组单元中。

对于完全二叉树，只要从根起按层序存储即可，依次自上而下、从左至右存储结点元素，即将完全二叉树上编号为i的结点元素存储在一维数组中下标为i−1的分量中。例如，下图（b）是下图（a）所示完全二叉树的顺序存储结构。

image-20240121124012724

对于一般二叉树，采用顺序存储时，为了使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。例如，下图（b）是下图（a）所示一般二叉树的顺序存储结构，图中以“0”表示不存在此结点。

image-20240121124520361

由此可见，顺序存储结构仅适用于完全二叉树。因为，在最坏的情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2k−12^k-1的一维数组。这造成了存储空间的极大浪费，所以对于一般二叉树，更适合采用链式存储结构。

2.3.2、链式存储结构

设计不同的结点结构可构成不同形式的链式存储结构。

image-20240121142533136

由二叉树的定义可知，二叉树的结点（见上图a）由一个数据元素和分别指向其左、右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域（见上图b）：数据域和左、右指针域。有时，为了便于找到结点的双亲，还可以在结点结构中增加一个指向其双亲结点的指针域（见上图c）。使用这两种结点结构所得到的二叉树的存储结构分别称之为二叉链表和三叉链表。例如，下图a为单支树的二叉链表，下图b为非单支树的二叉链表，下图c为非单支树的三叉链表。其中，链表的头指针均指向二叉树的根结点。

img

二叉链表是一种常用的二叉树存储结构，在二叉树上的有关运算一般都是采用这种链式存储结构。在C语言中，二叉树的二叉链表存储结构的类型描述如下：

1
2
3
4
5
6
typedef struct BiTNode {
    // 结点数据域
    TElemType data;
    // 左、右孩子指针
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

注：在不同的存储结构中，实现二叉树的操作方法也不同，如找结点x的双亲PARENT(T, e)，在三叉链表中很容易实现，而在二叉链表中则需从根指针出发巡查。由此，在具体应用中采用什么存储结构，除根据二叉树的形态之外还应考虑需进行何种操作。

三、小结

树是一种具有层次关系的非线性数据结构。二叉树是一种最常用的树形结构，而满二叉树和完全二叉树又是两种特殊形态的二叉树；二叉树具有一些特殊的性质；二叉树有两种存储表示：顺序存储和链式存储。

img

四、参考

《数据结构（C语言版 第2版）》

《数据结构与算法之美》

《数据结构 自考02331》

数据结构
#数据结构
数据结构：树的基本概念
https://kuberxy.github.io/2024/01/07/数据结构：树的基本概念/
作者
Mr.x
发布于
2024年1月7日
许可协议