数据结构与算法分析：（十四）二叉树

骑猪看日落 2023-07-25 08:56 8阅读 0赞

## 一、前言 ##

前面我们讲了都是线性表结构，比如：数组、链表、栈、队列等。今天我们终于可以讲一讲树了，`树`是`非线性结构`。

我们都知道，对于大量的输入数据，链表的线性访问太慢，不宜使用。我们今天讲的树，其大部分操作的运行时间平均为 O( log ⁡ n \\log n logn)。

讲二叉树之前我们先来思考一下这几个问题。二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？带着问题与思考，看完以后顿时会对二叉树的设计原理豁然开朗的感觉。

好了，我们接下来开始二叉树的学习之旅吧。要想学二叉树，我们要先来了解树与树的一些特性。

## 二、树（Tree） ##

`树（Tree）`可以用几种方式定义。定义树的一种自然的方式是递归的公式。一棵树是一些节点的集合。这个集合可以是空集；若不是空集，则树由称作`根（root）`的节点 `r` 以及 0 个或多个非空的（子）树 `T1,T2,...,Tk` 组成，这些子树中每一棵的根都被来自根 `r` 的一条有向的`边（edge）`所连结。

上面关于树的定义你应该清楚了吧，什么？有点抽象？可能你刚开始接触树这种数据结构吧应该，没有关系。我下面给张图你就全部清楚了。

![在这里插入图片描述][20200413213009916.png]  
比如上图，B 节点就是 E 节点的`父节点`，E 节点是 B 节点的`子节点`。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为`兄弟节点`。们把没有父节点的节点叫作`根节点`，也就是图中的节点 A。我们把没有子节点的节点叫作`叶子节点`或者`叶节点`，比如图中的 E、I、J、G、H 都是叶子节点。

除此之外，关于树，还有三个比较相似的概念：`高度（Height）`、`深度（Depth）`、`层（Level）`。它们的定义是这样的：

*  节点的高度 = 节点到叶子节点的**最长路径**（边数）
 *  节点的深度 = 根节点到这个节点所经历的`边的个数`
 *  节点的层数 = 节点的深度 + 1
 *  树的高度 = 根节点的高度

这三个概念的定义比较容易混淆，描述起来也比较空洞。我举个例子说明一下，你一看应该就能明白。

![在这里插入图片描述][20200413214945576.png]

有一个更好记的方法：在我们的生活中，“高度”这个概念，其实就是从下往上度量，比如我们要度量第 3 层楼的高度、第 21 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点的位于第 1 层。

## 三、二叉树（Binary Tree） ##

树结构多种多样，不过我们最常用还是二叉树。

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。我下面画的都是二叉树。

![在这里插入图片描述][20200413221022719.png]

这个图里面，有两个比较特殊的二叉树，分别是编号 2 和编号 3 这两个。

其中，编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

满二叉树很好理解，也很好识别，但是完全二叉树，有的人可能就分不清了。我画了几个完全二叉树和非完全二叉树的例子，你可以对比着看看。

![在这里插入图片描述][20200413221539545.png]

上图中的编号 1 是完全二叉树， 编号 2 和编号 3 这两个不是完全二叉树。这时你会满脸疑惑的问，这三个感觉没啥区别呀。为什么编号 1 把最后一层的叶子节点靠左排列了就叫完全二叉树了？如果靠右排列就不能叫完全二叉树了吗？

要理解完全二叉树定义的由来，我们需要先了解，**如何表示（或者存储）一棵二叉树**？

想要存储一棵二叉树，我们有两种方法，一种是基于`指针或者引用`的`二叉链式存储法`，一种是`基于数组`的`顺序存储法`。

我们先来看相对简单的链式存储法，从下图你看到，每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。你闭着眼睛把根节点拎起来，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

![在这里插入图片描述][202004132240142.png]

我们再来看，基于数组的顺序存储法。我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 \* i = 2 的位置，右子节点存储在 2 \* i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 \* i = 2 \* 2 = 4 的位置，右子节点存储在 2 \* i + 1 = 2 \* 2 + 1 = 5 的位置。

![在这里插入图片描述][20200413225728856.png]

我来总结一下，如果节点 X 存储在数组中下标为 i 的位置，下标为 2 \* i 的位置存储的就是左子节点，下标为 2 \* i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。

不过，我刚刚举的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。你可以看我举的下面这个例子。

![在这里插入图片描述][2020041323041334.png]

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

## 四、二叉树的遍历 ##

前面讲了二叉树的定义与存储，我们再来看下二叉树最重要的特性，二叉树的遍历。

如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

*  前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
 *  中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
 *  后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

![在这里插入图片描述][20200413233250568.png]

实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

前序遍历的递推公式：
    preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
    
    中序遍历的递推公式：
    inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
    
    后序遍历的递推公式：
    postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

从我前面画的前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 `O(n)`。

## 五、知识拓展 ##

**1、表达式树**

![在这里插入图片描述][20200413234445530.png]

如上图所示显示的一个`表达式树（expression tree）`，表达式树的树叶是操作数，如常熟或变量名，而其它节点为操作符。

这个例子的中序遍历的话，表达式树表示的是：`（a + b * c）+ ((d * e + f) * g)`

换个前序或者后序遍历的话，表达式又会不同，是不是很有意思。

小型计算的话可以用栈来实现，大型的计算我觉得可以用表达式树来实现。

**2、我们讲了三种二叉树的遍历方式，前、中、后序。实际上，还有另外一种遍历方式，也就是按层遍历，你知道如何实现吗？**

层序遍历。

可以参考[LeetCode-102. 二叉树的层序遍历][LeetCode-102.]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    class Solution { 
        public List<List<Integer>> resultList = null;
        public List<List<Integer>> levelOrder(TreeNode root) { 
            resultList = new ArrayList<List<Integer>>();
            levelOrderHelper(root, 0);
            return resultList;
        }
    
        private void levelOrderHelper(TreeNode node, int level) { 
            if (node == null) return;
            if (resultList.size() <= level) { 
                resultList.add(new ArrayList<Integer>());
            }
            resultList.get(level).add(node.val);
            levelOrderHelper(node.left, level + 1);
            levelOrderHelper(node.right, level + 1);
        }
    }

[20200413213009916.png]: /images/20230528/d2a0d4413dd04fba8b0d4f86ae215aae.png
[20200413214945576.png]: /images/20230528/70b2afa00f634f24871289af7504479a.png
[20200413221022719.png]: /images/20230528/2f43f111472c4b39830636a474222fd6.png
[20200413221539545.png]: /images/20230528/6be08ab57d194a559242da3666043627.png
[202004132240142.png]: /images/20230528/8f766eb9e5204d79bec5f7b1bf6bc8ad.png
[20200413225728856.png]: /images/20230528/a2b8958ae26e4f9cb0add01e12e3f856.png
[2020041323041334.png]: /images/20230528/a1787e83f0bb46e68c314038ee2bc33f.png
[20200413233250568.png]: /images/20230528/e462b61fca774d86a6efdb86e4294448.png
[20200413234445530.png]: /images/20230528/94fa916c730e43ea84826b0774918242.png
[LeetCode-102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/?utm_source=LCUS&utm_medium=ip_redirect_q_uns&utm_campaign=transfer2china