典型数据结构-栈/队列/链表、哈希查找、二叉树（BT）、线索二叉树、二叉排序树（BST树）、平衡二叉树（AVL树）、红黑树（RB树）

目录

典型数据结构列举

栈/队列/链表

树

二叉树

线索二叉树

二叉排序树

平衡二叉树（AVL树）

红黑树

其它树种和应用介绍

---

典型数据结构列举

栈/队列/链表

描述略。

一些基本的简单实现参考/数据结构简单实现/文件夹里面。

• 线性表详解：数据结构线性表10分钟入门 (biancheng.net)。
• 栈(Stack)和队列(Queue)详解 (biancheng.net)。

树

以下为树的基本概念（定义、基本操作、性质、存储结构等）、二叉树（定义、基本操作、存储、遍历等）、平衡二叉树、红黑树等。

引自：树及二叉树的基本概念_青萍之末的博客-CSDN博客。

树是由一个或一个以上的节点（node）组成，存在一个特殊节点称为树根（root），它是n（n>=0）个节点的有限集。n=0时称为空树。n>0时，有限集的元素构成一个具有层次感的数据结构。

树的一些概念

• 节点的度：一个节点拥有子树的数目。例如A的度为2，B的度为1，C的度为3。
• 树的高度：也称为树的深度，树中节点的最大层次。
• 有序树：树中节点各子树之间的次序是重要的，不可以随意交换位置。
• 无序树：树种节点各子树之间的次序是不重要的。可以随意交换位置。
• 森林：0或多棵互不相交的树的集合。

引自：《数据结构教程》。

树的一些性质

1. 非空树的节点总数等于树中所有节点的度之和加1。
2. 度为 k 的非空树的第 i 层，最多有 k^(i-1) 个节点（i ≥ 1）。
3. 深度为 h 的 k 叉树最多有 (k^h - 1)/(k - 1) 个节点。
4. 具有 n 个节点的 k 叉树的最小深度为 log_k(n*(k - 1)) + 1。包含 n 个结点的二叉树的高度至少为 log_2(n) + 1。

树的基本操作

1. 建立一棵空树 T。
2. 求结点 x 所在树的根节点。或求树 T 的根节点。
3. 求树 T 中结点 x 的双亲结点。
4. 求树 T 中节点 x 的第 i 个孩子节点。
5. 求树 T 中节点 x 右边 的兄弟节点。
6. 把以 S 为根结点的树插入到 树 T 的 节点 x 的第 i 个子节点位置上。
7. 删除树 T 中 节点 x 的第 i 棵树。
8. 对一棵树进行遍历，按照某种次序遍历树所有节点并得到一个由所有节点组成的序列。

树的存储

采用链式存储方式居多。除了储存节点本身的数据信息之外，还必须做到把树中各个节点之间的连接关系反映在存储结构中。

• 多重链表表示法：分为 定长链接数目 和 不定长链接数目。

  前者：

  

  后者：

  

• 三重链表表示法：

  

二叉树

树及二叉树的基本概念_青萍之末的博客-CSDN博客。

引自：《数据结构教程》。

二叉树结构被广泛用来解决计算机领域中的各种实际问题。例如，在排序、检索、数据库管理系统以及人工智能等许多方面，二叉树都提供了强而有效的支持。

…

每一个节点最多只有两颗子树。在二叉树中严格区分节点的左、右子树，其次序不能随意颠倒。因此二叉树是有序树。

二叉树又可以分为满二叉树和完全二叉树。

二叉树的基本操作

二叉树的存储结构

• 顺序存储结构：顺序存储结构固有一些缺陷，使得二叉树的插入、删除等操作不方便，而且效率比较低（线性表的固有缺点）。

  

• 链式存储结构：更适合，更广泛。两种：二叉链表结构 和 三叉链表结构。

  二叉链表结构：链表中每一个链接点由三个域组成分，别为数据域和两个指针域，后者分别给出该节点的左、右节点的存储地址。

  

  三叉链表结构：相比于二叉链表结构，多增加一个用来指向双亲节点的指针域，这样在查找二叉树中某个节点的双亲节点时候不用遍历整个二叉树。就是空间换时间（如查找的时间等）。

二叉树与树的遍历

有关二叉树的许多操作几乎都是建立在二叉树的遍历之上。二叉树是一种非线性结构，因此需要寻找一种规律，使得二叉树中的所有节点能够排列在一个线性序列中，这就叫遍历。

若以符号 D、L 和 R 分别表示访问根节点、遍历根结点的左子树 和 遍历根结点的右子树 三个过程，并且限定先左后右的顺序，则通常采用三种遍历方式：DLR、LDR、LRD，分别称之为 前序遍历、中序遍历、后续遍历。还有 按层次 的遍历顺序。

遍历可以用递归的方式（对于很大的树容易栈溢出）。非递归方法，通常利用一个栈结构。

下面举例按照 中序遍历 顺序遍历的程序。

按照层次遍历（或叫 广度优先遍历） 即 若被遍历的二叉树非空，则依次访问二叉树的第1层、第2层……直到最后一层，对每一层的访问按照从左到右的顺序进行。 该方法通常用一个队列实现。下面举例程序。

由遍历序列恢复二叉树

三步：

线索二叉树

在二叉树的结点上加上线索的二叉树称为线索二叉树。对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

• 彻底理解线索二叉树_ Walk the horizon-CSDN博客 _线索二叉树的作用。
• 线索二叉树的理解_ huangwei18351的博客-CSDN博客 _线索二叉树。

二叉排序树

引自：《数据结构教程》。

二叉排序树用于排序、查找/检索，可以大大提高查找的时间效率（在一般情况下，查询效率比链表结构要高）。二叉排序树又叫二叉查找树。有人说，当需要完成的功能是插入、删除和检索，二叉排序树具有比迄今为止研究过的任何数据结构都有更好的性能。

引自：二叉排序树（二叉查找树）及C语言实现 (biancheng.net)。

二叉排序树要么是空二叉树，要么具有如下特点：

• 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
• 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
• 二叉排序树的左右子树也要求都是二叉排序树；

如下图所示就是一个二叉排序树。

引自：《数据结构教程》。

二叉排序树中插入数据，同样需要按照二叉排序树的原则进行。每次将一个新的元素插入到二叉排序树中，该元素对应的节点都是插在叶节点位置，插入的过程没有移动二叉树中其他节点。一个数据元素序列不一定按照值的大小进行排列，但当对其构造成为一棵二叉排序树以后，对该二叉排序树进行中序遍历得到的序列是一个按值大小排列的序列。

• 二叉排序树（二叉查找树）及C语言实现 (biancheng.net)。
• 二叉排序树_百度百科 (baidu.com)。
• 二叉查找树（BST）及二叉树的遍历_ 青萍之末的博客-CSDN博客 _二叉搜索树的遍历。
• 二分搜索树 | 菜鸟教程 (runoob.com)。

平衡二叉树（AVL树）

引自：平衡二叉树（AVL树）及C语言实现 (biancheng.net)。

平衡二叉树，又称为 AVL 树。实际上就是遵循以下两个特点的二叉树：

• 每棵子树中的左子树和右子树的深度差不能超过 1；
• 二叉树中每棵子树都要求是平衡二叉树；

其实就是在二叉树的基础上，若树中每棵子树都满足其左子树和右子树的深度差都不超过 1，则这棵二叉树就是平衡二叉树。

把二叉树中每个节点的左子树深度与右子树深度之差定义为该节点的平衡因子，因此平衡二叉树中每个节点的平衡因子只能是 1、0 或 -1。

引自：《数据结构教程》。

二叉排序树的形态，事先无法预料，随意性很大，得到的往往是一颗很不 “平衡” 的二叉树，深度差越大，其运算时间也越长，丧失了其优势。为了克服二叉排序树的这个缺陷，需要在插入和删除节点的同时对二叉树的形态结构进行必要的调整，使二叉排序树始终处于一种平衡状态。

…

理论上已经证明，具有 n 个节点的平衡树的深度在任何情况下都不会比具有相同节点数目的理想平衡数的深度高出 45% 以上。因此再平衡树上进行查找操作虽然比理想平衡树要慢一些，但通常比任意生成的二叉排序树中进行查找要快得多，其时间复杂度的数量级仍为O(Log_2(n))。

• 平衡二叉树（AVL树）及C语言实现 (biancheng.net)。
• AVL树（平衡二叉树）_ 青萍之末的博客-CSDN博客 _avl树是平衡二叉树吗。

红黑树

引自 红黑树（RB-Tree）_青萍之末的博客-CSDN博客。

红黑树是一种二叉查找树。

红黑树与AVL树的对比

• 如果插入一个节点引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除节点引起树的不平衡时，最坏情况下，AVL需要维护从被删节点到根节点这条路径上所有节点的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度；
• 但是由于红黑树没有AVL树那么高度平衡，所以红黑树的查找性能相比AVL树要差一些，查找上的这一点性能差相比数据的插入和删除时的旋转性能是值得的，这就是为什么很多场合是用的红黑树，而不是AVL树，例如STL中的map和set。因此，RB-Tree在需要大量插入和删除节点的场景下效率更高。自然，由于AVL高度平衡，因此AVL的查找效率更高。

• 红黑树和AVL树的实现与比较—–算法导论 - 希隆囚徒 - 博客园 (cnblogs.com)。
• 红黑树（RB-tree）比AVL树的优势在哪？_mmshixing的博客-CSDN博客_红黑树的优点。
• 动画红黑树，旋转的艺术 - 知乎 (zhihu.com)。

其它树种和应用介绍

• B树和B+树_青萍之末的博客-CSDN博客 B树是对二叉查找树的改进，B树大量应用在数据库和文件系统当中。
• 浅谈二叉查找树、AVL树、红黑树、B树、B+树的原理及应用_青萍之末的博客-CSDN博客。
• 还有哈夫曼树、字典树等等树种。。