哈希

今天我们来聊一下哈希(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

January 8, 2020 · 1 min · fred

二叉堆

今天我们来说一下二叉堆(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....

December 30, 2019 · 4 min · fred

一个公平的洗牌算法 | Knuth-Shuffle

洗牌(随机)算法有很多应用,例如我们平时用的音乐播放器随机播放,棋牌游戏中的洗牌,扫雷游戏中雷的位置随机等等,都会用到洗牌算法。 今天来介绍一个简单,公平,时间复杂度为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....

December 30, 2019 · 1 min · fred

二叉查找树

二叉查找树(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....

December 26, 2019 · 5 min · fred

二叉树

这篇博客来聊一下二叉树。呆萌数据结构系列,终于开始了树型结构的部分。这篇文章你能够学到的内容有 树,有哪些应用,二叉树的结构,什么是满二叉树,什么是完全二叉树,二叉树的遍历方式,二叉树的构建。二叉树是很基本的结构,在此基本上,会有很多很多变种,变成各种各样的树,理解了二叉树,对于后面学习其他更复杂的树型结构,会有很大的帮助。 这篇文章首先理解文字上的内容,不要管代码,对二叉树的结构,操作,理解原理,最后再看代码。 好了,下面开始吧。 树,有哪些应用 现在学习的目的,已经不是为了考试,而是为了能够用来做一些事情。对于我们来说,知识只有用起来,才是有意义的,所以,我们先说一下树型结构的一些应用。咦?为什么不是二叉树的应用呢,因为很多应用,都不是单纯地使用二叉树来实现的,而是在此基础上,使用了它的变种,所以我们这里直接说一下树型结构的一些应用。 我们使用各种各样的数据结构,本质上似乎就是为了更方便或更高效地去组织数据,操作数据。我们平时用的搜索引擎,当你输入要搜索的内容时,可能在输入了前几个字,下面就已经出现了我们想要的结果,其实背后,就是用了树型结构,才能在这样庞大的数据中,找到与我们输入内容匹配的结构。 我们手机中常用的电话薄,也是这个原理。当你找一个联系人时,输入第一个字,例如李,可能下面的结构是李四,李五,李六,但是输入第二个字时,结果就会更精确。 我们平时用的压缩软件,其数据压缩算法,也离不开树型结构。 操作系统中的文件系统,以及我们使用的数据库软件,也是树型结构的应用。 二叉树的结构 二叉树是由一个一个节点组成,每个节点,有数据部分,以及两个节点指针,一个指向左子树,一个指向右子树。二叉树每一个节点,最多拥有两个子树。就像下面中的图(图中的数字可以理解为要存储的数据)。另外,二叉树的分支,也就是左右子树,是具有左右次序的,不能随意颠倒。 什么是满二叉树 满二叉树就除了最后一层,每一个节点,都拥有左右两个子树,没有空缺。 什么是完全二叉树 在理解了满二叉树的基础上,才能理解完全二叉树。完全二叉树要满足两个条件。首先,如果不看最后一层,那这棵树是满二叉树。其次,最后一层,要尽可能的往左靠,中间不能有空缺。什么意思呢?我们看一张图。 上图中,左边的图是一个完全二叉树。如果去掉最后一层,那这棵树是满二叉树,满足。最后一层,即使缺少了一个节点,但是所有的节点都是尽可能地往左靠了,所以,也满足第二个条件。 而第二个图,不是完全二叉树。首先第一个条件就不满足。其实,最后一层的节点也不是尽可能地往左靠。什么叫尽可能得往左靠呢,如果 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....

December 21, 2019 · 2 min · fred

队列

生活中的一些排队行为,基本上都是队列的形式。这篇博客涉及的概念有 队列,循环队列,优先队列,双端队列。 很多编程语言已经内置了队列结构,在实际项目中可以直接使用。这篇文章里的代码实现,主要用做原理理解。 拿超市买单为例,买完东西,一般会找一个结账台排队,等待结账。如果前面已经有人在排队,那你肯定是排在当前队伍的最后面,如果再来人,肯定是排在你的后面,依次往后排。每当有一个顾客买完单,那后面的顾客就会往前走,直到整个买单队伍没有人排队。这就是队列结构。是不是很简单~ 队列 队列,是一种先进先出的结构(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....

December 18, 2019 · 2 min · fred

堆栈

有一堆书,一本叠一本地放入箱子里,最后放入的,一定是在最上面,对不对。取书的时候,规定只能从上面一本一本地取,如果要拿最先放入箱子里的那本书,也就是最下面的那本书,只能先把上面的拿出来。 什么是堆栈(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 (!...

December 12, 2019 · 1 min · fred

链表

什么是链表 链表和数组一样,是一种线性的数据结构,由一个一个节点构成,节点中存放着数据,以及指向下一个或上一个节点的指针,通过指针,将节点链接在一起,构成整个链表结构。不同于数组,链表在内存中并不是连续的存储空间。 为什么要用链表?或者说链表有哪些优点 我们知道,数组是很方便的数据结构,但是数组有一些局限性。必须事先知道要分配多少内存空间。插入和移除是很耗费性能的操作,因为需要移动不止一个元素。 而链表,正好弥补了数组的缺点,链表是动态内存,不需要事先分配固定大小的空间,添加和删除元素,也只需要改变指针即可,不需要移动很多元素。 链表的缺点 当然,链表也有弊端。无法像数组一样随机访问,例如要访问第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....

December 11, 2019 · 2 min · fred

数组

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

December 10, 2019 · 1 min · fred

数据结构概述

经常有小伙伴想系统地学习一下数据结构,但很难找到适合自己的教程。好吧,其实说的是我自己。那今天就来聊一聊这个问题。 我们先把一些常用的数据结构列表出,大概讲一下他们的结构及应用,后面分篇细细讲解。在分篇讲解时,我们的关注点是某个数据结构是什么,怎样用代码描述出来。而更多涉及到这个数据结构的一些算法,将在后面的算法系列中详细讲解。 这个系列的博客,是面向那些和我差不多,大概了解数一些数据结构(知道一些名字,不太了解内部详细实现),又想系统地巩固一下,深入一下的小朋友们~ 快来一起学习吧 ^_^ 数组 [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,是在二叉树的基础上,增加了额外的规则。首先,我们给每一个节点赋予一个权重,这个权重,可以用任何东西代替,例如小朋友的分数,例如冰激凌的价格等等。然后,每一个节点,满足下面的规则 如果一个节点左子树不为空,则整个左子树上的所有节点,权重都要小于当前节点 如果一个节点右子树不为空,则整个右子树上的所有节点,权重都要大于当前节点 左右子树,也都是二叉查找树,也就是说,子树,也要满足上面也条规则 应用: 二叉查找树常常应用一些需要数据保持有序状态,但是又经常需要插入和删除某些数据的场景。例如电商平台中的商品数据组织,可能就经常用到二叉查找树。...

November 17, 2019 · 1 min · fred