数据结构与算法之树与二叉树（理论篇）

作者：未见花闻

2022 年 7 月 18 日
本文字数：2680 字
阅读完需：约 9 分钟

1.树

1.1 树的概念

树是一种非线性的数据结构，它是由 n（n>=0） 个有限结点组成一个具有层次关系的集合。当 n 为 0 时，该树表示一棵空树。

当树不为空树时，即 n>0 时，树有以下特点：

[x] 有且仅有一个结点 root，它没有前驱结点，结点 root 称作树的根结点。
[x] 除根结点外，每个结点有且仅有一个前驱结点。
[x] 树中每个结点可以有零个或多个后继结点。

从递归的角度出发，一棵树（空树除外）是由 m 棵子树构成的（m >= 0），树形结构中，子树之间不能有交集，否则就不是树形结构。

国->省->市->县...就是一种树形结构，除此之外还有我们电脑里面的文件夹也是这种结构。

关于树的一些术语：

结点的度与树的度： 树中一个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度，通常将度为 m 的树称为 m 次树或者 m 叉树。

分支结点与叶结点： 度不为零的结点称为非终端结点，又叫分支结点。度为零的结点称为终端结点或叶结点（或叶子结点）。度为 $1$ 的结点称为单分支结点；度为 $2$ 的结点称为双分支结点，依此类推。

孩子结点、双亲结点和兄弟结点： 在一棵树中，每个结点的后继，被称作该结点的孩子结点（或子女结点）。相应地，该结点被称作孩子结点的双亲结点（或父母结点）。具有同一双亲的孩子结点互为兄弟结点。

结点的层次和树的高度： 树中的每个结点都处在一个层次上。结点的层次从树根开始定义，根结点为第 $1$ 层，它的孩子结点为第 $2$ 层，以此类推，一个结点所在的层次为其双亲结点所在的层次加 $1$ 。树中结点的最大层次称为树的高度（或树的最深深度）。

路径与路径长度： 两个结点 d~i~和 d~j~的结点序列称为路径。路径长度等于路径所通过的结点数目减 $1$ （即路径上分支数目）。

子孙结点和祖先结点： 在一棵树中，一个结点的所有子树中的结点称为该结点的子孙结点。从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。

有序树和无序树： 若树中各结点的子树是按照一定的次序从左向右安排的，且相对次序是不能随意变换的，则称为有序树，否则称为无序树，不指明是否是有序树，则一般默认是有序树。

森林： $n （ n > 0 ）$ 个互不相交的树的集合称为森林。把含有多棵子树的树的根结点删去就成了森林。反之，给 $m （ m > 1 ）$ 棵独立的树加上一个结点，并把这 $m$ 棵树作为该结点的子树，则森林就变成了一颗树。

1.2 树的表示

1.2.1 树的逻辑表示

（1）树形表示法。使用一棵倒置的树表示树结构，非常直观和形象。

（2）文氏图表示法。使用集合以及集合的包含关系描述树结构。

（3）凹入表示法。使用线段的伸缩关系描述树结构。

（4）括号表示法。用一个字符串表示树。

基 本 形 式 ： 根 (子 树 1 ， 子 树 2 ， \dots ， 子 树 m)

1.2.2 树的储存表示法

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子表示法（二叉树用的最多），孩子兄弟（非二叉树用的较多）表示法。

所谓孩子表示法就是一个结点中有一个数据域和一些指针域（数目不确定，二叉树是两个，三叉树是三个，以此类推），这些指针都指向孩子结点。孩子兄弟表示法就是一个结点中有一个数据域和两个指针域，一个指针指向左边的孩子结点，另一个指针指向右边的兄弟结点。

1.3 树的性质

性质 1 树中的结点数等于所有结点的度数之和加 1

。树中每个分支计为一个结点的度（每条分支线从一个结点引出来的）,除了根结点，每条分支线都指向一个结点。

所 有 结 点 的 度 之 和 ＝ 分 支 数 = 结 点 数 - 1

性质 2

设树的度为 $m$ ， $n$ 为总结点个数， $n_{i}$ 为度为 $i （ 0 \leq i \leq m ）$ 的结点个数，则:

n = n_{0} + n_{1} + \dots + n_{m}

性质 3

设树的总结点数为 $n$ ，树的度为 $m$ ， $n_{i}$ 为度为 $i （ 0 \leq i \leq m ）$ 的结点个数，则有：

所 有 结 点 度 之 和 = n_{1} + 2 n_{2} + \dots + m n_{m} = n - 1

性质 4 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i - 1}$ 个结点 $（ i \geq 1 ）$ 。性质 5

高度为 $h$ 的 $m$ 次树至多有

\frac{m ^{h} - 1}{m - 1}

个结点。

性质 6

具有 $n$ 个结点的 $m$ 次树的最小高度为

l o g_{m} (n (m - 1) + 1)

例题：

2.二叉树

2.1 二叉树的概念

一棵树上所有结点的度均不大于 $2$ ，则这棵树是一棵二叉树，空树是一棵特殊的二叉树。一棵树是二叉树，其子树均为二叉树，二叉树的储存表示方法常用孩子表示法和孩子双亲表示法进行储存。

// 孩子表示法class Node {   int val; // 数据域   Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树   Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 }// 孩子双亲表示法class Node {   int val; // 数据域   Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树   Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树   Node parent; // 当前节点的根节点 }

复制代码

二叉树都是由一下几种情况复合而成：

二叉树和 2 次树有什么区别？

2 次树是度为 2 的树，至少有 3 个结点；二叉树的结点个数可以为 0。2 次树中度为 1 的结点的孩子不分左、右孩子；而二叉树中度为 1 的结点的孩子需要区分左、右孩子。

2.2 特殊的二叉树

满二叉树与完全二叉树是二叉树的两种特殊情况。满二叉树： 在一棵二叉树中，除叶子结点外，其他所有结点的度均为 2，则该树为满二叉树。

完全二叉树： 从根结点开始，每个非空结点按照层次依次递增，每层从左至右的顺序排列的二叉树，称为完全二叉树。换个说法，完全二叉树实际上是对应的满二叉树删除叶结点层最右边若干个结点得到的。

2.3 二叉树的性质

性质 1 非空二叉树上叶结点数等于双分支结点数加 1。即： $n_{0} = n_{2} + 1$ 。

性质 2 非空二叉树上第 $i$ 层上至多有 $2^{i - 1}$ 个结点 $（ i \geq 1 ）$ 。

性质 3 若规定只有根结点的二叉树的深度为 $1$ ，高度为 $h$ 的二叉树至多有 $2^{h} - 1$ 个结点 $（ h \geq 1 ）$ 。

性质 4 具有 $n$ 个结点的完全二叉树的深度 $k$ 为 $l o g_{2} (n + 1)$ 上取整。

性质 5 完全二叉树性质（含 $n$ 个结点，树的度为 $m$ ）：对于具有 $n$ 个结点的完全二叉树，默认按照从上至下从左至右的顺序对所有节点从 $1$ 开始编号，序号为 $j$ ，设 $n_{i}$ 为度为 $i （ 0 \leq i \leq m ）$ 的结点个数， $[]$ 为取整符号，完全二叉树性质:

[ ] $n$ 为奇数则 $n_{1} = 0$ ， $n$ 为偶数则 $n_{1} = 1$ 。
[ ] 若 $j \leq [n / 2]$ ，则编号为 $j$ 的结点为分支结点，否则为叶结点。
[ ] 除树根结点外，若一个结点的编号为 $j$ ，则它的双亲结点的编号为 $[j / 2]$ ，如果是从 $0$ 开始编号，则它的双亲结点的编号为 $[(j - 1) / 2]$ 。
[ ] 若编号为 $j$ 的结点有左孩子结点，则左孩子结点的编号为 $2 j$ ；若编号为 $j$ 的结点有右孩子结点，则右孩子结点的编号为 $2 j + 1$ 。如果是从 $0$ 开始编号，若编号为 $j$ 的结点有左孩子结点，则左孩子结点的编号为 $2 j + 1$ ；若编号为 $j$ 的结点有右孩子结点，则右孩子结点的编号为 $2 j + 2$ 。
[ ] 完全二叉树最大高度为 $h = [l o g_{2} (n + 1)] 向上取整或者 [l o g_{2} n] + 1 。$ (性质 4）