关于数据结构:树结构系列一从普通树到二叉查找树

文章首发于「陈树义」公众号及集体博客 shuyi.tech

树结构是数据结构中十分重要的一种类型，本文将从最根底的一般树结构入门，延长到二叉树，再延长至二叉查找树。通过这种思路，让大家构建起对于树的最根本的常识链路。

一般树

树是一种非线性数据结构，它是数据元素按分支关系组织起来的构造，很像自然界中的树那样。

对于树的官网定义是：一棵树是由 N（N>0）个元素组成的无限汇合，其中：

1. 每个元素称为结点（node）。
2. 有一个特定的结点，称为根结点或根（root）。
3. 除根结点外，其余结点被分成 m（m>=0）个互不相交的无限汇合，而每个子集又都是一棵树（称为原树的子树）。

对于树有几个重要的概念，这里简略做下介绍：

• 度

度即节点的分支数，例如上图树中节点 A 有三个子节点，那么咱们称节点 A 的度是 3。

• 档次

节点的档次，示意节点在书中的地位。根结点的档次为 1，其余结点的档次等于它的父结点的档次数加 1。例如上图中节点 F 的档次为 3。

• 深度

树的深度，即组成该树各节点的最大档次。例如上图中节点的最大档次为 K/L/M，那么树的深度就为 K/L/M 任何一个的档次，即树的深度为 4。

• 门路

对于一棵子树中的任意两个不同的结点，如果从一个结点登程，按档次自上而下沿着一个个树枝能达到另一结点，称它们之间存在着一条门路。可用门路所通过的结点序列示意门路，门路的长度等于门路上的结点个数减 1。

例如上图中 A 到 L 的门路为：A > B > E > L，其门路结点个数为 4，那么其长度为 3。

二叉树

二叉树其实就是在一般树的根底上，加上了对树的度限度，即每个节点最多只能有两个子节点。 二叉树有五种根本的状态：

1、空二叉树 —— 如图 a 所示。
2、只有一个根结点的二叉树 —— 如图 b 所示。
3、只有左子树 —— 如图 c 所示。
4、只有右子树 —— 如图 d 所示。
5、齐全二叉树 —— 如图 e 所示。

二叉树是一种简略且重要的树，许多其余类型的树都建设在二叉树的根底之上。依据叶子节点的不同情景，咱们能够将二叉树再细分为：完美二叉树、齐全二叉树、满二叉树。

完美二叉树，指的是所有非叶子节点的度都是 2（只有你有孩子，你必然有两个孩子）。

齐全二叉树 ，指的是深度为 k，有 n 个结点的二叉树当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应。简略地说，齐全二叉树是满二叉树的一个子集。 简略地说，齐全二叉树就是非叶子节点都有两个子节点，并且必须是从左到右、从上到下的程序。

满二叉树 ，指的是一棵二叉树只有度为 0 的结点和度为 2 的结点，并且度为 0 的结点在同一层上，则这棵二叉树为满二叉树。 简略地说，就是所有叶子节点都在同一个层上，每一层都铺满了节点。

二叉查找树

下面学了那么多树结构的常识，但都没有理论利用，只能说是在打基础，理解基本概念。而二叉查找树能够说是一个十分实用的数据结构，能够用来疾速查找元素。

二叉查找树（Binary Search Tree，BST），有些称其为二叉排序树，其均匀查找效率为 O(logN)，最差查找效率为 O(N)（进化为链表）。而其能实现如此疾速的查找速度，次要是其对于数据存储程序的限度。

二叉查找树的定义为：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 左、右子树也别离为二叉排序树
4. 没有键值相等的结点

依据下面二叉查找树的定义，咱们不难画出上面的二叉查找树。能够看到根节点的 7 元素，大于右边的 3 元素，小于左边的 11 元素。而左右子树 3、11 也同样合乎这样的法则。

依据这样的元素排序，要查找一个元素最多只须要查找树的深度次数就够了。例如要查找元素 5，那么咱们的查找门路是：7 > 3 > 5，只须要查找 3 次。而如果要查找 4，那么咱们的查找门路是：7 > 3 > 5 > 4，只须要查找 4 次。依据二叉树的深度与节点数量的关系，咱们就能够算出二叉查找树的深度为 O(LogN），即二叉查找树的工夫复杂度为 O(LogN）。

二叉查找树在查问方面的效率晋升是微小的，比起链表来说晋升了几万倍。特地是在数据量一直增大的状况下，其晋升性能更加恐怖。例如咱们有 1 亿个元素，如果应用链表存储，那么其均匀须要比拟 5000 万次。而应用二叉查找树存储，咱们只须要比拟 27 次就能够了。5000 万次与 27 次想比拟，相差了 185 万倍！

但二叉查找树也有一个问题，即它在极其状况下会进化成链表。例如咱们有这样一组数字：30、20、10、1，它们组成二叉查找树之后就会进化成一般链表。

那么如何补救二叉查找树的这个缺点呢？这就波及到了树的均衡这个概念。依据树均衡这个思路，先贤们又发明出了均衡二叉树这个概念，发明出了 AVL 树、红黑树等经典的数据结构。咱们下回持续聊均衡二叉树。

总结

明天咱们介绍了一般树结构，以及其相干的根底概念。接着咱们介绍了十分根底的二叉树构造，接着将其扩大到完美二叉树、齐全二叉树、满二叉树。最初，介绍了二叉查找树结构，以及存在的问题。从明天的文章中，咱们能够得出一些论断：

• 二叉树是非凡的树结构，示意其最多只有两个节点。
• 完美二叉树是非叶子节点都有 2 个节点的二叉树。
• 齐全二叉树是在完美二叉树的根底上，加上左右到有、从上到下都有节点的限度。
• 满二叉树是是在齐全二叉树的根底上，加上每层的节点都是满的这个限度。
• 二叉查找树能实现 O（logN）的工夫复杂度查找，然而会有进化成链表的危险。

到目前为止，咱们将学习到的的树结构搭建起来，能够画出如下的树结构小道。

参考资料

• 完满二叉树，齐全二叉树和完美二叉树 – veli – 博客园
• 6 天通吃树结构 —— 第一天 二叉查找树 – 一线码农 – 博客园