什么是二叉树？-六虎

本文已收录到 AndroidFamily，技能和职场问题，请重视公众号 [彭旭锐] 提问。

前语

大家好，我是小彭。

在前面的文章里，咱们聊到过数组、链表、栈和队列等根底数据结构，也聊到过它们的一些衍生数据结构，例如单调栈、单调队列、散列表等等，这些都是线性表或许是以线性表为主体的数据结构。

从这篇文章开端，咱们来评论非线性的数据结构 —— 树和图。非线性数据结构比较于线性表结构要杂乱得多，涉及到的内容也更广。尽管树也是一种特别的图，可是考虑到树的特色更简单了解也更常用，所以咱们把树单独分类，而把图当成树的衍生数据结构。

今日，咱们就先从树的基本概念开端，并逐步延伸到二叉堆、红黑树、线段树、树状数组、图等更杂乱的数据结构上，请重视。

思维导图：

1. 隐藏在递归代码中的树

其实，很多代码中都存在树型结构，比方递归代码。

递归是一种经过 “函数自己调用自己” 的方法，将问题重复地分化为同类子问题，并最终解决问题的编程技巧。当你在运用递归思维解决问题的时分，往往你也是在运用树型结构解决问题。

举个比如，要求一个数 $n$ 的阶乘 $n! = n * (n - 1) * (n - 2) * \dots * 2 * 1$ 。假如运用递归思维解决问题是，咱们能够把 $n!$ 的问题拆分为一个 $(n - 1)!$ 的问题，假如咱们知道 $(n - 1)!$ 的解，那么将它乘以 $n$ 就能够得出 $n!$ 的解。以此类推。

求 n!

因为阶乘在每次递归调用时，原问题和子问题仅仅 “线性” 地减少一个问题规模，所以这里面的树型结构可能还不太明显。 那咱们能够再举一个稍微杂乱的比如：求斐波那契数列，LeetCode 509. 斐波那契数：该数列从 $1$ 开端，每一项数字都是前面两项数字的和。

这个问题咱们能够运用递归的方法自顶向下地分化问题，在编码上是很简单完成的。假如咱们把代码一层层分化的过程画成图形，咱们会发现代码天然地构成了一个树。 这棵在递归调用中隐式存在的树咱们也称之为递归树。

递归（未优化）

class Solution {
    fun fib(N: Int): Int {
        if(N == 0){
            return 0
        }
        if(N == 1){
            return 1
        }
        // 拆分问题 + 组合成果
        return fib(N - 1) + fib(N - 2)
    }
}

递归是一种树型结构

2. 什么是树（Tree）？

2.1 树的逻辑结构

树这种数据结构与现实中的 “树” 在形状上非常相似， 树的逻辑结构是一种非线性结构，相邻的父子节点构成 1 对 N 的联系，树的节点中包括元素值和一切子节点的列表。

从这阶乘和斐波那契数列的比如能够看出，线性表和树在结构上的首要区别在于相邻节点的引证联系上：

1、线性结构： 前驱节点和后继节点的引证联系为 1 对 1；
2、树型结构： 前驱节点和后继节点的引证联系为 1 对 N；
3、图型结构： 再进一步延伸，当前驱节点和后继节点的引证联系为 N 对 N 时便是图型结构。假如按照图的理论来说，树能够看作是一种特别的图，即包括 N 个节点和 N – 1 条边的有向无环图，树的方向是从根节点指向叶子节点。

2.2 树的物理完成

树的物理结构能够选用数组或链表完成：

1、链表完成： 即经过引证来建立节点之间的父子联系，每个节点都持有子节点的引证。树的链表完成更简单直接，所以大部分的二叉树代码也是经过链表结构来完成的；
2、数组完成： 即经过数组下标来建立节点之间的父子联系，节点内部不需求存储子节点引证的内存空间。

在额定内存耗费上，链表完成在子节点指针有额定内存占用，而数组完成会在数组自身上存在额定内存占用。假如树是一棵非常稀疏的树的话，树的数组完成会导致数组中存在非常多的搁置空间。

树的数组完成有 2 种计算节点位置的方法：

方法 1 – 根节点存储在第 [0] 位：
- 关于第 [i] 位上的节点，第 [2 * i +1] 位是左节点，第 [2 * i + 2] 位是右节点；
- 关于第 [i] 位上的节点，第 [(i-1) / 2] 位是父节点。
方法 2 – 根节点存储在第 [1] 位：
- 第 [0] 位不存储，根节点存储在第 [1] 位
- 关于第 [i] 位上的节点，第 [2 * i] 位是左节点，第[2 * i + 1] 位是右节点
- 关于第 [i] 位上的节点，第 [i / 2] 位是父节点

2.3 树的基本概念

深度（Depth）： 表明节点到根节点的间隔（能够参阅递归栈的深度了解，递归越深的节点深度越大）；
层级（Level）： 也是表明节点的深度，数值是深度 + 1；
高度（Height）： 表明节点到叶子节点的间隔；
宽度： 表明一层节点中最左节点与最右节点之间的长度（两头之间的空节点也计入宽度）；

2.4 树的途径

途径 / 最短途径： 指两个节点之间经过的一切节点。因为树是有方向的，因而途径一定会经过两个节点的最近一起先人，树中的途径概念自身便是最短途径；
间隔 / 最短间隔： 即途径长度，指两个节点的途径上一切边的个数。同理树中的间隔概念自身便是最短间隔；
权：表明一个节点的权重；
带权途径长度： 表明一个节点到根节点的途径长度与节点权重的乘积；
树的带权途径长度： 表明一棵树中一切节点的带权途径长度之和，简称 WPL，Weighted Path Length of Tree；
最优树： 表明带权途径长度最小的树，即哈夫曼树。哈夫曼树其实仅仅生成哈夫曼编码的一个东西，咱们在专栏后续文章里再评论。

树的途径

3. 二叉树与特别二叉树

前面咱们将的树都是普通的树的特征，也叫多叉树，即节点的子节点个数不固定，能够是一个，两个或许多个。不过咱们最常见的仍是二叉树，即每个节点最多只要两个子节点，分别是左子节点和右子节点。

下面评论常见的几种特别的二叉树：

3.1 满二叉树（Full Binary Tree）

关于一棵满二叉树来说，任何一棵子树上都是满二叉树。

满二叉树的每一层节点都是铺满的，除了最底层的节点外，一切节点都有左右两个子节点，一切的叶子节点也集中在树的最底层。

3.2 彻底二叉树（Complete Binary Tree）

关于一棵彻底二叉树来说，任何一棵子树都是彻底二叉树。

彻底二叉树与满二叉树类似，但没有那么 “满”。除了最底下两层节点外，大部分节点都有左右两个子节点，一切的节点也都铺满在树的左上角，一切的叶子节点都集中在树的最底下两层。

那么，为什么要界说彻底二叉树这种数据结构呢？这就需求跟稀疏的树做比较了。稀疏的树假如用数组完成的话，会存在非常多的搁置空间。而彻底二叉树或满二叉树能够彻底利用数组的一切空间或前部分空间，数组的利用率更高。

3.3 二叉查找树（Binary Search Tree，BST）

关于一棵二叉查找树来说，任何一棵子树上都是二叉查找树。

在二叉查找树中，树中的任意一个节点的值，都大于（或小于）左子树上一切节点的值，且均小于（或大于）右子树上一切节点的值。

那么，为什么要界说二叉查找树这种数据结构呢？ 这就需求跟链表做对比了，二叉查找树是为了优化链表的查询功率而发生的。链表在进行查询、刺进和删去时的时刻杂乱度是 O(n)，而在二叉查找树上进行查询、刺进和删去时的时刻杂乱度是 O(Height)，与树的高度有关。

3.4 平衡二叉查找树（Balance Binary Search Tree）

关于一棵平衡二叉树来说，任何一棵子树上都是平衡二叉树。

平衡二叉查找树是一种特别的二叉查找树，简称便是平衡二叉树。在平衡二叉树中，任何节点的左右子树高度差不大于 1。

那么，为什么要界说平衡二叉树这种数据结构呢？ 这就需求跟二叉查找树做对比了，平衡二叉树能够避免二叉查找树退化为链表。

在二叉查找树中，查找、刺进、删去等操作的时刻杂乱度跟树的高度成正比，在最好情况下会优化为彻底二叉树，而在最坏情况下会退化为链表，各项操作的时刻杂乱度也会退化 O(n)。而平衡二叉树会避免树的左右子树高度相差太大，各项操作的时刻杂乱度能够稳定在 O(logn)，可是在添加和删去操作上会添加维护平衡性的开销。

3.5 红黑树（Red-Black Tree，R-B）

平衡二叉树追求的是 “彻底平衡” 的状况，可是考虑到维护树的平衡性自身也是一种本钱，因而实践中运用的平衡二叉树往往是 ”近似平衡“ 或 ”弱平衡“ 的。即只保证左右子树高度相对均匀，而不严厉准守树的高度差不大于 1 的界说，经过献身一部分查找的功率，来节省保持树的平衡状况的本钱。

这些 “弱平衡” 的红黑树尽管不符合平衡二叉树的严厉界说，但一般也视为平衡二叉树。平衡二叉查找树有很多种，例如伸展树（Splay Tree）、树堆（Treap）、红黑树（AVL），但其中最常见的莫过于红黑树。在 Java HashMap 的分离链表法中，就选用了链表 + 红黑树的计划。

红黑树的性质如下：

1、节点非红即黑；
2、Null 节点是叶子节点；
3、根节点和 Null 叶子节点是黑色的；
4、赤色节点不会接连，赤色节点的子节点一定是黑节点；
5、任何节点到叶子节点的途径上黑色节点的数量。

红黑树的界说很杂乱， 关键在于红黑树能够满足一个节点到叶子节点的最长途径的长度不超越最短途径的 2 倍， 所以红黑树不会呈现左右子树特别不平衡的情况。

为什么呢？假定最长途径上存在 N 个黑节点和 N – 1 个赤色节点，因为要满足 “5、任何节点到叶子节点的途径上黑色节点的数量相同”，所以最短途径上也存在 N 个黑节点。那么即便最短途径上一个赤色节点都没有，至少也有 N 个节点，所以不会超越两倍。

3.6 二叉堆（Binary Heap）

关于一个二叉堆来说，任何一棵子树上都是二叉堆。

二叉堆是一种特别彻底二叉树，在二叉堆中，树中的任意一个节点的值，都大于等于（或小于等于）左右子树上一切节点的值。

二叉堆看起来和二叉查找树很像，但其实两者差别很大，二叉堆也并不是二叉查找树。在二叉查找树中会要求节点与左右子树的联系是 “左子树 < 节点 < 右子树” ，而二叉堆只要求 “节点 > 左子树 and 右子树” 。所以，二叉查找树中兄弟节点之间也是有序的，而二叉堆不关心兄弟节点之间的相对联系，所以关于同一组数据，咱们能够构建多种不同形状的堆。

3.7 哈夫曼树（Huffman Tree）

哈夫曼树与哈夫曼编码有关。

哈夫曼编码是一种变长编码，对呈现频率高的字符选用较短的码元，对呈现频率低的字符选用较长的码元，然后达到无损压缩编码长度的目的。哈夫曼树也成最优二叉树，是 WPL 带权途径长度最小的树。

其实，哈夫曼树便是生成哈夫曼编码的东西，经过哈夫曼树这个数据结构能够将 “设计最优编码” 的问题转换为求 “最小带权途径长度” 的问题。

4. 总结

今日，咱们评论了树的基本概念，也介绍了最常见的二叉树以及特别的二叉树。在专栏接下来的文章中，咱们会逐步延伸到这些特别的二叉树，请重视。

版权声明

本文为稀土技能社区首发签约文章，14天内制止转载，14天后未获授权制止转载，侵权必究！

参阅资料

数据结构与算法分析 Java 语言描绘（第 4、6 章）—— [美] Mark Allen Weiss 著
算法导论（第 6、12、13 章散列表）—— [美] Thomas H. Cormen 等著
300分钟搞定算法面试 —— 力扣&拉勾网出品
数据结构与算法之美（第 23~29 讲） —— 王争著，极客时刻出品

什么是二叉树？

前语