数据结构与算法

今天我们来聊一下哈希(Hashing)，有时候也被称为散列。简单来说，哈希是一个唯一标识，用于标识一个东西。例如，一个人的身份证号就可以称为一个哈希，通过一个身份证号，可以定位到某一个人的信息。一个人的名字，也可以用作哈希，不过这个可能会产生重复，因为有很多人重名，这样导致的问题就是，通过名字，可能定位到多个人的信息，这种情况叫做哈希碰撞。 哈希表(Hash Table) 哈希表是一种存储结构，也称为散列表，是一种 Key-Value 的存储结构。通过 Key 可以直接访问在内存存储位置的数据(Value)。例如 C# 中的 Dictionary 数据结构就是一种哈希表，还有一些编程语言中的 Tuple，也可以用哈希表实现。 哈希函数/散列函数 哈希函数也可以称为散列函数，是在哈希表内部，用于将我们之前提到的 Key，转为哈希表用于直接访问数据的索引。 哈希表的实现 在哈希表的内部，可以用数组来存储数据，当我们添加一个 Key-Vale 时，首先会使用哈希函数将 Key 转换成索引，然后将 Value 存储在数组中，而位置就是刚才计算出来的索引。哈希表通常有一个默认容量大小，而哈希函数计算出来的索引，通常会和当前的哈希表容量进行取模计算，然后得到最终的索引，这样能保证不管计算出来的索引有多大，永远不会超界。而当哈希表快要满时，则会进行自动扩容，通常扩为当前容量的2倍，而扩容后，当前哈希表中的所有数据，会重新计算位置。 举一个例子，假设当前哈希表的容量为 10，我们要将 jack 作为 Key 存放在哈希表中，那索引是什么呢。我们这里使用一个简单哈希函数将Jack转为数据，使用每一个字母的Ascii值之和，也就是 106 + 97 + 99 + 107，最后的结果是 409，然后用 409 % 10，也就是对当前的容量取模，最后得到的索引就是 9，所以数据最终放在数据中索引为9的位置。 而从哈希表中取数据，也是通过Key来取的，内部也是先把Key计算成索引，然后取数据。 有时，哈希表部分结构也会使用树的形式来存储数据，也有可能在不同容量时，线性存储和树形存储会互相转换 哈希碰撞 哈希函数在计算索引时，有时候同一个 Key 得到的索引是一样的，这种情况称为哈希碰撞，通常的解决方案是，哈希表内部的数组不直接存储数据，而是存储一个数据的指针，当有碰撞时，会以链表的形式将数据挂到索引所对应的数据指针上，这种处理碰撞的方法，也叫做拉链法。看一下下面的图，就会很容易明白。 总结 哈希表的实现要考虑很多情况，例如哈希函数是否均匀、处理冲突的方法、哈希表的载荷因子等等，这些细节直接决定了哈希表增删改查数据的效率。通常情况下我们直接使用编程语言已经实现好的哈希表结构即可，没有必要自己实现。 更多资料 维基百科 哈希表 Hashing data structure

今天我们来说一下二叉堆(BinaryHeap)。堆是很有用的数据结构，例如后面会学到的优先队列，堆排序等，都和堆有关。操作系统中很多调度，也和堆有关。 还记得我们之前学过的完全二叉树吗？如果不记得了，就需要先回去复习一下，因为二叉堆，首先是一棵完全二叉树，或者近似完全二叉树。 再来说一下二叉堆的特性。二叉堆分为最小堆和最大堆。如果是最小堆，那么父节点的值，总是小于或等于任何一个子节点的值，通俗点就是把一棵树从上往下看，值在变大，下面的大于等于上面的。如果是最大堆，则是反过来，父节点的值，总是大于或等于任何一个子节点的值。 如果要简单点记忆，那就是这棵树上的值按层来看，如果是从小到大，那就是最小堆，如果是从大到小，那就是最大堆。 接下来我们就开始说二叉堆的细节，插入节点，删除节点。 插入节点 插入节点，其实也就是构建二叉堆的过程，语言描述流程如下。 找到要插入的位置，这个位置就是当前这棵完全二叉树，最后一个位置 (不太好理解)。如果用代码流程来描述的话，就是按层遍历当前的树，如果遇到一个节点，左子树为空，或者又子树为空，或者左右子树都为空，那么，这个点就是要插入节点的父节点，而要插入的节点，将作为这个节点的左子树或右子树。看下面的图 假设我们要在上面的堆中插入一个节点，按照上面代码流程中描述的，可以找到要插入节点的父节点，是11。 找到了要插入节点的父节点，还要判断这个父节点是左子树为空，还是右子树为空，还是都为空，如果左子树为空，则新点作为左子树，如果左子树不为空，则新点作为右子树。插入后的图如下(假设要插入的数值为3) 节点插入后，当前的树并不满足二叉堆的规则，所以还需要将新插入的点向上浮动。如果当前节点值小于父节点的值，则交换当前节点和父节点的值。然后再次判断，直到当前值不再小于父节点值，或者父节点值为空了，则位置调整完毕，整个插入流程也就结束了。看下面的流程图 上图中，首先用 3 和 11 比较，因为 3 小于 11，所以交换两个节点的值 上图中，再次用 3 和父节点 5 比较，因为 3 小于 5，所以再次交换两个节点的值 上图中，再次用 3 和父节点 1 比较，咦，3 不小于 1，所以不交换，节点调整结束。此时的树满足二叉堆的规则。 以上就是整个插入节点的流程，下面我们用代码去实现一下。代码中的 TreeAlgo 类是我们为了方便写的一个帮助类，实现了层序打印和查找的一些方法。 // 定义节点的结构 public class Node { public int data; public Node parent = null; public Node left = null; public Node right = null; public Node(int data){ this.data = data; } } // 定义二叉堆操作类 using System; public class BinaryHeap { public Node root; public void Insert(int data){ Node lastParentNode = TreeAlgo....

洗牌(随机)算法有很多应用，例如我们平时用的音乐播放器随机播放，棋牌游戏中的洗牌，扫雷游戏中雷的位置随机等等，都会用到洗牌算法。 今天来介绍一个简单，公平，时间复杂度为O(n)的洗牌算法。什么是洗牌算法呢？其实就是将一些数据以公平随机的方式打乱顺序。这个算法，是由Knuth(高纳德)，也就是计算机程序设计艺术的作者发明的。下面我们直接进入正题。 假设有这样一个数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，我们使用Knuth-Shuffle算法将数据打乱。基本流程是这样的，从最后一个数开始，往前遍历，每一次，从当前数和第1个数之间，随机选择一个数，与当前数字进行交换（这里的随机选择就直接使用程序语言中的Random随机一个索引即可）。 例如上面的数组，第一次循环，当前数字为10，我们从1~10之间，随机选择一个数，与10交换，这样第9个索引位就算洗完了，接下来就是第8个索引位，也就是数字为9，我们从第1个索引位与第8个索引位之间，选择一个数，第9交换，这样第8个索引位也就洗完了…。这个算法之所以公平，是因为保证了每一个元素出现在每一个位置上的概率，都是一样的。 代码实现 using System; using System.Collections.Generic; class Program { static void Main(string[] args) { List<int> songList = new List<int>(); songList.Add(1); songList.Add(2); songList.Add(3); songList.Add(4); songList.Add(5); songList.Add(6); songList.Add(7); songList.Add(8); songList.Add(9); songList.Add(10); Random rand = new Random(); // 开始洗牌算法 int last = songList.Count - 1; for (int i = last; i >= 0; --i) { // 从当0~当前索引位之间，选择一个数 int selection = rand....

二叉查找树（Binary Search Tree），简写BST，是满足某些条件的特殊二叉树。任何一个节点的左子树上的点，都必须小于当前节点。任何一个节点的右子树上的点，都必须大于当前节点。任何一棵子树，也都满足上面两个条件。另外二叉查找树中，是不存在重复节点的。 上图中的二叉查找树，我们从Root节点3开始看，它的左子树（1，2） 和右子树（6，4，9，7）分别满足条件，左子树上的点，都小于当前节点，右子树上的点，都大于当前节点。 继续，我们以6作为起点，来看一下这棵子树，6的左子树（4），右子树（9，7）也满足上面两条规则。 整棵树中，任何一个点下面的子树，都满足上面提到的两条规则。你现在是不是对Binary Search Tree已经有一个大概的形象概念了。 为什么叫做 Binary Search Tree呢？ 因为在BST中搜索一个值是非常简单和高效的。 看上面的树，假设要搜索7这个节点。首先从Root节点出发，我们知道7大于3，所以会走到右子树6，然后因为7也大于6，所以会继续往右子树走，到了9，因为7小于9，所以会向左子树走，走到7，发现7等于7，所以找到要搜索的节点。 二叉树的一些性质 将任何一个点看作Root节点，则这个点的左子树也是 Binary Search Tree 将任何一个点看作Root节点，则这个点的右子树也是 Binary Search Tree Binary Search Tree中的最小节点，一定是整棵树中最左下的叶子节点(从Root开始一直顺着左子树往下走，直到某一个点没有左子节点，则这个点就是最小的) Binary Search Tree中的最大节点，一定是整棵树中最右下的叶子节点(从Root开始一直顺着右子树往下走，直到某一个点没有右子节点，则这个点就是最大的) 怎样构建和插入节点 向BST中插入一个节点，也是一个构建的过程，和上面的搜索思路基本一样。首先从Root开始，如果Root点为空，则直接构建Root点。如果Root点不为空，则要判断要插入的值，比Root点的值大还是小，如果小，则往左子树走，如果大，则往右子树走。直到走到某一个点，我们称为点X，发现要插入的值，小于那个点X的值，并且点X没有左子树，则要插入的点作为X的左子节点。或者，要插入的点大于X，并且X没有右子树，则要插入的点作为X的右子节点。 下面是代码实现（为了方便后面的删除逻辑，我们每一个点，包含了指向左子树，右子树，以及父节点的引用） // 这里先定义出节点的结构 class Node { public int data; public Node parent; public Node left; public Node right; public Node(int _data) { this.data = _data; } } // 定义二叉搜索树结构 class BST { private Node root; // 这个函数是 private 的，递归调用，插入节点 private Node RecursionInsert(Node node, int data) { if (node == null) { return new Node(data); } if (data < node....

这篇博客来聊一下二叉树。呆萌数据结构系列，终于开始了树型结构的部分。这篇文章你能够学到的内容有 树，有哪些应用，二叉树的结构，什么是满二叉树，什么是完全二叉树，二叉树的遍历方式，二叉树的构建。二叉树是很基本的结构，在此基本上，会有很多很多变种，变成各种各样的树，理解了二叉树，对于后面学习其他更复杂的树型结构，会有很大的帮助。 这篇文章首先理解文字上的内容，不要管代码，对二叉树的结构，操作，理解原理，最后再看代码。 好了，下面开始吧。 树，有哪些应用 现在学习的目的，已经不是为了考试，而是为了能够用来做一些事情。对于我们来说，知识只有用起来，才是有意义的，所以，我们先说一下树型结构的一些应用。咦？为什么不是二叉树的应用呢，因为很多应用，都不是单纯地使用二叉树来实现的，而是在此基础上，使用了它的变种，所以我们这里直接说一下树型结构的一些应用。 我们使用各种各样的数据结构，本质上似乎就是为了更方便或更高效地去组织数据，操作数据。我们平时用的搜索引擎，当你输入要搜索的内容时，可能在输入了前几个字，下面就已经出现了我们想要的结果，其实背后，就是用了树型结构，才能在这样庞大的数据中，找到与我们输入内容匹配的结构。 我们手机中常用的电话薄，也是这个原理。当你找一个联系人时，输入第一个字，例如李，可能下面的结构是李四，李五，李六，但是输入第二个字时，结果就会更精确。 我们平时用的压缩软件，其数据压缩算法，也离不开树型结构。 操作系统中的文件系统，以及我们使用的数据库软件，也是树型结构的应用。 二叉树的结构 二叉树是由一个一个节点组成，每个节点，有数据部分，以及两个节点指针，一个指向左子树，一个指向右子树。二叉树每一个节点，最多拥有两个子树。就像下面中的图（图中的数字可以理解为要存储的数据）。另外，二叉树的分支，也就是左右子树，是具有左右次序的，不能随意颠倒。 什么是满二叉树 满二叉树就除了最后一层，每一个节点，都拥有左右两个子树，没有空缺。 什么是完全二叉树 在理解了满二叉树的基础上，才能理解完全二叉树。完全二叉树要满足两个条件。首先，如果不看最后一层，那这棵树是满二叉树。其次，最后一层，要尽可能的往左靠，中间不能有空缺。什么意思呢？我们看一张图。 上图中，左边的图是一个完全二叉树。如果去掉最后一层，那这棵树是满二叉树，满足。最后一层，即使缺少了一个节点，但是所有的节点都是尽可能地往左靠了，所以，也满足第二个条件。 而第二个图，不是完全二叉树。首先第一个条件就不满足。其实，最后一层的节点也不是尽可能地往左靠。什么叫尽可能得往左靠呢，如果 B 节点作为 A 节点的左子树，那就叫做尽可能地往左靠了。 二叉树的遍历方式 树的遍历(不限于二叉树)，有广度优先遍历，和深度优先遍历。而深度优先遍历，分为前序遍历，中序遍历，后序遍历。 我们以下面这张图为例子，分别说一下这几种遍历方式。 广度优先遍历： 广度优先遍历，其实就是一层一层地遍历，所以又可以称为层次遍历，会先访问离根节点最近的节点。按照广度优先遍历，上面的树中节点访问顺序是这样的。 8，4，12，2，6，10，14，1，3，5，7，9，11，13，15 深度优先索索 深度优先搜索，通常采用递归的形式来进行。这里我们用简单的代码去描述，会比文字描述更直观。 前序遍历 前序遍历的顺序是先访问根节点，然后再访问子树。 void pre_order_traversal(Node root) { // TODO：操作当前节点 // 如果左子树不为空，则递归处理左子树 if(root.left != null){ pre_order_traversal(root.left); } // 如果右子树不为空，则递归处理右子树 if(root.right != null){ pre_order_traversal(root.right); } } 中序遍历 中序遍历的顺序是先访问左（右）子树，然后访问根，然后访问右（左）子树。 void in_order_traversal(Node root) { // 如果左子树不为空，则递归处理左子树 if(root.left != null){ in_order_traversal(root.left); } // TODO: 处理当前节点 // 如果右子树不为空，则递归处理右子树 if(root....

生活中的一些排队行为，基本上都是队列的形式。这篇博客涉及的概念有 队列，循环队列，优先队列，双端队列。 很多编程语言已经内置了队列结构，在实际项目中可以直接使用。这篇文章里的代码实现，主要用做原理理解。 拿超市买单为例，买完东西，一般会找一个结账台排队，等待结账。如果前面已经有人在排队，那你肯定是排在当前队伍的最后面，如果再来人，肯定是排在你的后面，依次往后排。每当有一个顾客买完单，那后面的顾客就会往前走，直到整个买单队伍没有人排队。这就是队列结构。是不是很简单~ 队列 队列，是一种先进先出的结构(First in first out)，也就是在队尾进行插入操作，在队头进行删除操作。队列可以用链表来实现，也可以用数组来实现，要根据实际需求来决定。 队列的操作有入列、出列、判断是否为空、判断是否已满等操作。下面将用C#来实现列表结构，看代码 public class Node { public int data; public Node next; public Node(int data) { this.data = data; } } public class LinkedListQueue { public Node head; public Node tail; // 插入一个元素 public void Enqueue(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } } // 删除一个元素 public int Dequeue() { if (IsEmpty()) { Debug....

有一堆书，一本叠一本地放入箱子里，最后放入的，一定是在最上面，对不对。取书的时候，规定只能从上面一本一本地取，如果要拿最先放入箱子里的那本书，也就是最下面的那本书，只能先把上面的拿出来。 什么是堆栈(Stack) 上面说的就是我们今天要讲的堆栈，也可以简单叫做栈。堆栈是很常用很基础的数据结构。堆栈涉及到的概念如果下。 栈顶，就是最上面的一个元素。 压栈(Push)，就是将一个元素放入栈中。 弹出(Pop)，就是将栈顶的元素从堆栈中拿出来。 就像上面往箱子里放书一样，最先放入堆栈的元素，在最下面，最后放入的元素，在最上面，而取元素，只能从上面一个一个取，不能从中间抽取元素。 堆栈有什么用呢 那栈有什么用呢，举几个简单的例子。我们用的很多软件，都有撤销功能对不对，其实，那个就可以用堆栈来实现。将每一步操作时的状态，保存到堆栈中，当用户要撤销时，就从堆栈中拿出最近的一个状态进行恢复，也就是最后放入堆栈中 (栈顶) 的状态数据。是不是很熟悉？ 后面要学到的树的遍历，深度优先搜索，也是用堆栈来实现的。 总之呢，记住一句话，先进后出(Fist in last out) 或者 后进先出(Last in first out) 就可以完美诠释堆栈这种数据结构。 自己动手实现一下 很多编程语言已经实现了堆栈(Stack)结构，但是呢，我们这里自己实现一下，加深理解。代码使用 C#，以链表的形式来实现。(C# 语言本身已经拥有了Stack，在实际使用中，不需要自己实现) class Node { public int data; public Node next; public Node(int data){ this.data = data; } } class Stack { public Node topNode = null; // 将一个数据压入堆栈中 public void Push(int data){ Node newNode = new Node(data); newNode.next = topNode; topNode = newNode; } // 将一个栈顶数据从堆栈中弹出 public int Pop() { if (!...

什么是链表 链表和数组一样，是一种线性的数据结构，由一个一个节点构成，节点中存放着数据，以及指向下一个或上一个节点的指针，通过指针，将节点链接在一起，构成整个链表结构。不同于数组，链表在内存中并不是连续的存储空间。 为什么要用链表？或者说链表有哪些优点 我们知道，数组是很方便的数据结构，但是数组有一些局限性。必须事先知道要分配多少内存空间。插入和移除是很耗费性能的操作，因为需要移动不止一个元素。 而链表，正好弥补了数组的缺点，链表是动态内存，不需要事先分配固定大小的空间，添加和删除元素，也只需要改变指针即可，不需要移动很多元素。 链表的缺点 当然，链表也有弊端。无法像数组一样随机访问，例如要访问第5个元素，是没办法直接访问的，只能遍历。每一个节点，需要额外的内存空间用来存储指向下一节点的指针。对缓存不友好，因为链表的内存空间并不一定是连续的。 链表怎样用代码表示，以及插入、删除、遍历操作 下面我们使用C#来描述一下链表 /// <summary> /// 链表中的节点结构 /// </summary> public class Node { public int data; public Node next; public Node (int data) { this.data = data; } } public class Linkedlist { public Node head; public Node tail; /// <summary> /// 插入一个节点 /// </summary> /// <param name="data"></param> public void InsertNode(int data) { Node newNode = new Node(data); if(head == null) { head = newNode; tail = newNode; } else { tail....

数组，在数据结构中，是很基础，也很常用的一个，在很多很多业务中，都能看到它的身影。数组很简单，在不同的编程语言中，操作方式，也几乎都是类似的。 那数组是什么呢？简单来说，就是在内存中分配一块连续的空间，用来存储相同类型的元素。使用索引，可以直接访问某一个元素的数据。大多数编程语言，数组的索引是从0开始的。 数组也分为一维数组，和多维数组。就像excel中的表格，一行数据，就可以看做是一个一维数组，而多行数据，就可以看做是一个多维数组。 这个是一维数组结构 这个是多维数组结构 关于性能方面，因为数组是固定大小，连续的内存结构，所以访问元素的速度是很快的，时间复杂度是O(1)，也就是说，不用遍历，能直接找到要访问的元素，几乎不消耗什么时间。 但是插入和删除某一个元素，就不一样了，假设一个数组有10个元素，删除了第4号元素，那么，4号后面的元素，都要往前移。而插入，也需要将插入位置后面的元素，往后移动。这是数组的一个弊端。 当要插入一个元素，而原本分配的数组空间已经不够时，有些编程语言会产生数组溢出。这时，我们就需要自己写逻辑，当数组空间不足时，分配一个新的更大的数组，先将原来数组的元素复制进去，然后将新元素插入。就像你要将100个桃子放进一个盒子里，但是装着装着发现盒子不够大，这时，就需要找一个更大的盒子，将原来盒子里那些拿出来放到新盒子里，然后继续新盒子里放桃子。 对于数组的操作，有很多，例如删除头部元素、删除尾部元素、在头部添加元素、在尾部添加元素、数组切片、多个数组链接等等。有一些编程语言已经内部实现了这些方法，例如Javascript，Python等，但有一些编程语言，我们就需要在用到时自己实现，例如C语言等。 好了，数组就先介绍到这里，如果有什么问题，或者有解释不准确的地方，欢迎在下面留言，谢谢~

经常有小伙伴想系统地学习一下数据结构，但很难找到适合自己的教程。好吧，其实说的是我自己。那今天就来聊一聊这个问题。 我们先把一些常用的数据结构列表出，大概讲一下他们的结构及应用，后面分篇细细讲解。在分篇讲解时，我们的关注点是某个数据结构是什么，怎样用代码描述出来。而更多涉及到这个数据结构的一些算法，将在后面的算法系列中详细讲解。 这个系列的博客，是面向那些和我差不多，大概了解数一些数据结构(知道一些名字，不太了解内部详细实现)，又想系统地巩固一下，深入一下的小朋友们~ 快来一起学习吧 ^_^ 数组 [Array] 数组用于存储同种类型的数据，数据与数据之间在内存中是连续的(相邻的)，在使用数组前，要预先分配好指定的内存大小。 应用: 例如我们想存储幼儿员小班所有小朋友有的名字，就可以用数组。 [第一个小朋友名字, 第二个小朋友名字, 第三个小朋友名字, …] 链表 [Linked List] 链表，是由一个个节点，相连而成。每一个节点，都是独立的元素，它们在内存中的位置也不一定是连续的。每一个节点，都拥有两个部分，数据部分，和一个指向下一个节点的引用。刚刚说的是单向链表。 还有一种叫做双向链表，区别就是一个节点有三个部分，数据部分，一个指向下一个节点的引用，一个指向上一个节点的引用。 还有一种叫做循环链表，区别就是尾部和头部会连起来。 应用: 链表常应用于存储不能事先确认数据个数的情况，对于这种情况，使用链表不需像数组一样预先分配内存，当有新的数据要存储时，只需要新申请一个节点的内存空间，然后将这个节点添加到链表即可。 堆栈 [Stack] 想象这样一个场景，往一个箱子里放书，先放进一本漫画书，再放进一本故事书，再放进一本数学书。现在最上面的是数学书，如果要把里面的书一本一本都拿出来，就要先拿出数学书，再拿出故事书，再拿出漫画书，正好与放下的顺序相反。这就叫先进后出，FILO (First in last out)。 而堆栈就是这一种结构，堆栈通常拥有两个方法，Push 和 Pop，分别就是放入数据，和拿出数据。后放入的数据，总是在最上面，往外拿数据时，也像从箱子里拿书一样，要从最上面开始拿。是不是很形象~ 应用: 堆栈是一个很有用的东西，我们平常用的很多软件中，都能找到它的应用，例如文本编辑器的撤销功能，其实就是在特定时间将用户的操作Push入栈，然后撤销时，从栈中Pop出最近的一个操作。再例如浏览器的后退功能，也是依次将用户浏览的网址Push入栈，然后后退时，依次Pop出最近的浏览网址。 队列 [Queue] 大家排队买冰激凌，就是一种队列结构，这个人买完冰激凌，然后下一个。在这个过程中，后面不断的有人在排队，队伍越来越长，服务员从前面一个一个处理顾客的需求。 队列也是这样，先入列的，也会先出列，就像排队。先排队的，先拿到冰激凌，然后走人。所以队列通常有两个操作，入列(Enqueue) 和 出列 (Dequeue)。队列是先进先出，FIFO (First in first out)。 还有一种队列叫做环形队列，会循环利用已经分配好的内存空间，而不是入列和出列时执行分配和销毁内存操作。 应用: 需要依次处理的事情，都可以使用队列，例如网络通信数据包，当客户端收到消息时，就可以放入队列，而消息处理器，不断地尝试从队列中取消息，如果有，则处理。 咦？刚才好像说到冰激凌了~ 二叉树 [Binary Tree] 树，就像我们平时在公园里看到的那种树的结构，分叉。而二叉树呢，就是只能分两叉，一分为二，每一个分叉，又可以最多一分为二。就像下面的这种形状。 二叉树的结构，也可以理解为由 “节点” 组成，就像链表那样的节点。对于二叉树来说，每一个节点有三个部分，数据部分，指向左边分叉节点的引用，指向右边分叉节点的引用。 二叉树，每一个节点，最多能分两叉，也就是，每一个节点，最多拥有两个直接子节点，也可能有一个，也可能没有。其实，二叉树的实现，很多也是用链表来做的。这个后面的博客再详细介绍，嘿嘿~ 应用: 树型结构在计算机中也有很多应用，例如我们很熟悉的文件浏览器。一个目录下，可以有多个目录，子目录下，又可以有多个文件，然后还可以再分叉继续往下深入。不过，真正的文件系统并不一定用的是二叉树，也可能是n叉树，具体的我还不是很清楚，尴尬ing… 二叉查找树 [Binary Search Tree] 二叉查找树，简称 BST，是在二叉树的基础上，增加了额外的规则。首先，我们给每一个节点赋予一个权重，这个权重，可以用任何东西代替，例如小朋友的分数，例如冰激凌的价格等等。然后，每一个节点，满足下面的规则 如果一个节点左子树不为空，则整个左子树上的所有节点，权重都要小于当前节点 如果一个节点右子树不为空，则整个右子树上的所有节点，权重都要大于当前节点 左右子树，也都是二叉查找树，也就是说，子树，也要满足上面也条规则 应用: 二叉查找树常常应用一些需要数据保持有序状态，但是又经常需要插入和删除某些数据的场景。例如电商平台中的商品数据组织，可能就经常用到二叉查找树。...