引言上一篇文章《精通二叉树的“独门忍术”——线索二叉树（上）》提到了线索二叉树的改良，并给出了改良后的“中序遍历”“前序遍历”线索二叉树的定义。本文就来谈谈改良后的“前序遍历”的线索二叉树的转换与遍历算法。非递归型算法既然《精通二叉树的“独门忍术”——线索二叉树（上）》中已经给出了“中序遍历”的线索二叉树的转换与遍历算法，那么朴素的想法就是：将“前序遍历”线索二叉树与“中序遍历”线索二叉树进行对比，基于后者来推导出前者的算法。我们先来对比一下“中序遍历”线索二叉树与“前序遍历”线索二叉树的图示：图1“中序遍历”的线索二叉树图2“前序遍历”的线索二叉树对比图2与图1可以看出：“中序遍历”线索二叉
引言二叉树的叶子节点的孩子都是空节点（Null），如果展开显示，如下图：图1原始二叉树二叉树的遍历方法，有“前序遍历”“中序遍历”和“后序遍历”三种。“前序遍历”的规则：先访问当前节点，再访问其左子树，最后访问右子树；访问子树时，按照规则1递归执行。“中序遍历”的规则：先访问左子树，再访问当前节点，最后访问右子树；访问子树时，按照规则1递归执行。“后序遍历”的规则：先访问左子树、再访问右子树，最后访问当前节点；访问子树时，按照规则1递归执行。如果要写出非递归的遍历算法，无论用哪种遍历方法，根据《再不会“降维打击”你就Out了！》《神力加身！动态编程》三篇文章中讲到的知识和技巧，都要借助堆栈来记
引言在上一篇《无死角“盘”它！二分查找树》中提到了：平衡二叉树的目的就是使得平均查找长度最短。那么这里就引出两个问题：什么是平衡二叉树？为什么平衡二叉树的平均查找长度最短？如何将非平衡二叉树调整成平衡二叉树？1.平衡二叉树是什么鬼？满足如下两个条件的二叉树称为“平衡二叉树”：首先它得是二分查找树然后它的左右子树的高度相差不超过1图1平衡二叉树图2非平衡二叉树图1就是一棵平衡二叉树，而图2不是平衡二叉树。在图2中，对于值为9的节点，它的左子树为空，高度为0，右子树高度为3，两者相差3，不满足平衡二叉树定义的第二条规则。2.如何证明平衡二叉树的平均查找长度最短？首先研究一下平衡二叉树与非平衡二叉树
引言《菜鸟也能“种”好二叉树！》一文中提到了：为了方便查找，需要进行分层分类整理。而满足这种目标的数据结构之一就是树。树的叶子节点可以看作是最终要搜寻的目标物；叶子节点以上的每一层，都可以看作是一个大类别、层中的每个节点都可以看作是一个小类别。从上图可以看出，要定位目标物，就需要从最上面的大类依次向下定位目标物所属的小类。定位的效率（时间复杂度）取决于两个因素：非叶子节点的分岔数：分岔数越多，表示大类包含的小类数目也就越多，那么为了定位到底属于哪个小类，比较次数也就越多，从而时间开销也就越大。树的高度（或称为深度）：树越深（高），从根节点（最大类）到叶子节点（目标物）的路径也就越长，也就意味着
引言上一篇文章《菜鸟也能“种”好二叉树！》提到：树是一种分层分类的数据结构，用途是查找和排序。而与查找和排序密切相关的就是求最值（最大值或者最小值）。今天我们就来介绍一个与最值相关的数据结构——二叉堆。尽管网上或者相关的算法书均有对二叉堆算法的介绍，但大部分只停留在how的阶段，并未对一些关键细节进行why的深究。比如：为什么二叉堆的算法都使用数组作为数据结构，而不是链表？为什么要引入二叉堆的调整算法来构造堆？相对于插入法构造堆，为什么更优？为什么不论是调整法还是插入法来构造堆，都是自底向上进行遍历，而不是自顶向下？采用调整法来构造堆，为什么时间复杂度是O(N)？本文旨在填补这个空白，“授人鱼
>引言在本系列第5篇《小白也能玩转数组和链表啦！》中，给出了常用数据结构的全貌图：本文就来讲讲“树”这个数据结构。1.树的本质是什么？本系列第2篇《扫雷还可以这样玩》中提到了算法问题的基本类型——搜索、排序、规划、计算。其中，搜索和排序与生活中朴素的体验息息相关。我们每个人都有如下体验：如果房间乱七八糟，那么找一样东西相当棘手。收拾好房间之后，找东西就容易多了。收拾的过程就是分类、整理的过程。当东西特别多时，往往一个分类还不够——这会导致该分类下的东西太多，找起来仍然很花时间。但是直接简单增加分类的话，当分类增加到一定程度，我们查找分类的时间就会变长。那么怎么解决这个矛盾呢？方法就是给分
本系列的第6篇《再不会“降维打击”你就Out了!》讲述了递归算法的意义、套路，第7篇《神力加身！动态编程》讲述了递归算法的优化，但是在大量的实际项目、工程和大家关心的求职面试中，却会碰到大量消除递归的需求。于是产生了两个问题：1.为什么会有消除递归的需求？2.如果都采用非递归的方式，那么递归算法的独特价值又是什么呢？本文以此为引子，将以你在任何其他算法书中都不会看到的方式，向你揭示递归的高阶技巧，让你彻底掌握递归与非递归的左右互搏之术。今天的小汽车会逐步加速，各位乘客要系好安全带：）1.从哪里来、回到哪里去递归算法在运行的时候，是不断重入同一函数的，既然是重入，就必然要搞清楚一个基本的问题——
引言在上篇文章《再不会"降维打击"你就Out了!》中，提到了递归算法的两个局限性。本文给出解决方案——动态编程。如果说"递归算法"是圣剑的话，那么"动态编程"就是圣衣。两者加持，你便可以爆发究极小宇宙：）递归算法局限性详细分析局限性1（适用性问题）：如果“降维”前的状态集合并不方便用“降维”后的状态集合表示，即状态转移函数不好求，那么该场景使用递归不一定恰当。下面举个例子来说明：有两个集合A和B，A中有n个元素，B中也有n个相同元素，将A中的元素通过映射f，映射到B中的元素，映射f满足：f(f(x))=f(x)，求这样的不同映射有多少
引言刘慈欣的《三体》不仅让中国的硬科幻登上了世界的舞台，更是给广大读者普及了诸如“降维打击”之类的热门概念。“降维打击”之所以给人如此之震撼，在于它以极简的方式，从更高的、全新的技术视角有效解决了当前困局。那么在算法的世界中，是否存在这样的利器呢？答案是肯定的——那就是大名鼎鼎的“递归”。递归思想与传统算法思想的区别传统算法思想是正向演绎逻辑，即：根据已知条件，进行联想、寻找经验库，逐步推导，直到问题解决。而递归思想是逆向归纳逻辑，即：当前问题的求解是否可以由规模小一点的问题求解叠加而来，后者是否可以再由更小一点的问题求解叠加而来……依此类推，直到收敛为一个极简的出口问题的求解。由上可知，递归
引言在本系列第一篇文章[《走下神坛吧！算法》中提到了：算法的作用对象是数据结构数据结构的来源既有硬件维度也有软件维度把项目或者工程看作是大楼的话，那么算法就是建造大楼的具体施工流程和方法，数据结构就是砖块等原材料。常言道：“工欲善其事必先利其器”，既然要研究算法，那么首先就要把它操作的“原材料”一一搞清楚。从本篇文章起，将逐一来讲解各“原材料”的历史来源、使用方法与应用场景。1.数组就是带电梯的小高层数组的形式：<数据类型>数组名[数组长度]形象地讲，数组就是带电梯的小高层。每一个楼层就是数组的一个元素。数组元素的下标，就相当于楼层号然后按电梯楼层号。1.1访问数组元素你按下楼层号
在本系列第1篇《走下神坛吧！算法》中提到了：计算复杂度分为时间复杂度与空间复杂度，第3篇《KO！大O——时间复杂度》详细介绍了时间复杂度，本篇文章来讲讲空间复杂度。空间复杂度和硬件资源开销是一回事情吗？CPU资源开销分析：CPU的资源的设计初衷更多的是用于提升计算性能；对CPU资源的利用，基本原则都是“多多（占用、发挥）益善；加之CPU的资源空间大小与内存、外存和外设比较，非常有限。内存资源开销分析：静态视角：程序要装进内存才能运行动态视角：程序在运行时，动态申请内存外存资源开销分析：静态视角：程序本身，以二进制可执行映像形态，存放在外存上的大小动态视角：程序在运行时，对外存的需求大小（比如，
引言在本系列第1篇《走下神坛吧！算法》中提到了：计算复杂度分为时间复杂度与空间复杂度。本篇文章来讲讲时间复杂度。如何度量时间复杂度时间复杂度由所消耗的时间决定。所消耗的时间由硬件与软件共同决定。在同一硬件条件下，所消耗的时间由软件决定。通常意义上的算法指的是软件算法，所以在谈论时间复杂度时，聚焦软件的时间开销。软件的时间开销=软件各组成部分的时间开销之和。软件最基本的组成部分是语句（或者微观意义下的指令）。注：因为在同一硬件条件、特定的编程语言环境下，基本语句由多少条指令构成、运行的模式都是固定的，所以直接以语句作为基本考察单位即可。整体等于各部分之和对大部分编程语言而言，基本语句无外乎以下两
引言上篇文章介绍了算法的本质和基本概念《算法+数据结构（第01篇）走下神坛吧！算法》，这次我们用实际的问题来做算法实战。假设如下场景：公司新年晚会进行夺宝游戏，奖品是最新款的智能手机、VR游戏机、便携电脑三件套。游戏规则如下：当主持人宣布游戏开始的时候，每位员工的手机上会同时收到两组数字（数组中的每个数字都是正整数且两两不等）和一个目标正整数。员工需要在两组数字中分别取两个数字相加，使得相加的结果与目标正整数最接近。哪位员工先做出结果，那么奖品就归谁。为了使赢率最高，请问应该采用什么样的策略或者方法？显然，这是在对一个特定问题找方法。那么根据上篇文章所讲到的，这就是在求算法。那么如何算法求解呢
引言在互联网、大数据、人工智能火爆的今天，“算法”这个词几乎妇孺皆知，业已成为“高薪”“牛X”的代名词。应不少朋友的邀请，特连载本系列，旨在用最通俗的方式——“”讲人话、无废话、看得懂、用得上“”——将位于神龛之上的算法送进寻常百姓家。本篇作为系列的第一篇，采用“What、Why、How”文章结构，来给大家普及一下算法的基本概念（也纠正一些朋友的错误概念）。WhatisAlgorithm？（算法是个什么鬼）为了不落入俗套，本文不会重复wiki上“算法”的官方定义，而采用启发式结构来阐述算法的本质，试想平时在遇到问题的时候，我们是如何解决的。朴素而广泛的过程方法论如下：重新定义问题，结构化描述根
引入随着信息爆炸时代的来临，互联网上充斥着着大量的近重复信息，有效地识别它们是一个很有意义的课题。例如，对于搜索引擎的爬虫系统来说，收录重复的网页是毫无意义的，只会造成存储和计算资源的浪费；同时，展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括：镜像网站内容复制嵌入广告计数改变少量修改一个简化的爬虫系统架构如下图所示：事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数
引入什么情况下需要布隆过滤器？我们先来看几个比较常见的例子：字处理软件中，需要检查一个英语单词是否拼写正确在FBI，一个嫌疑人的名字是否已经在嫌疑名单上在网络爬虫里，一个网址是否被访问过yahoo,gmail等邮箱垃圾邮件过滤功能这几个例子有一个共同的特点：如何判断一个元素是否存在一个集合中？常规思路与局限如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hashtable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。数组链表树、平衡二叉树、TrieMap(红黑
Trie，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，RadixTree/Trie，PATRICIAtree，以及bitwise版本的crit-bittree。当然很多名字的意义其实有交叉。Trie树是一种非常重要的数据结构，它在信息检索，字符串匹配等领域有广泛的应用，同时，它也是很多算法和复杂数据结构的基础，如后缀树，AC自动机等。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hotspot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。Hash算法一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓
排序排序是日常工作和软件设计中常用的运算之一。为了提高查询速度需要将无序序列按照一定的顺序组织成有序序列。排序的主要目的就是实现快速查找。排序分类增排序和减排序：如果排序的结果是按关键字从小到大的次序排列的，就是增排序，否则就是减排序。稳定排序和不稳定排序：具有相同关键字的记录，经过排序后它们的相对次序仍然保持不变，则称这种排序方法是稳定的；反之是不稳定的。内部排序和外部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之成为外部排序。本文目录冒泡排序一、冒泡排序（BubbleSort）1.1思想冒泡排序(bubblesort)：每个回合都从第一个元素开始和它后面的元素
哈希表的概念哈希表（HashTable）是一种特殊的数据结构，它最大的特点就是可以快速实现查找、插入和删除。我们知道，数组的最大特点就是：寻址容易，插入和删除困难；而链表正好相反，寻址困难，而插入和删除操作容易。那么如果能够结合两者的优点，做出一种寻址、插入和删除操作同样快速容易的数据结构，那该有多好。这就是哈希表创建的基本思想，而实际上哈希表也实现了这样的一个“夙愿”，哈希表就是这样一个集查找、插入和删除操作于一身的数据结构。哈希表（HashTable）：也叫散列表，是根据关键码值（key-value）而直接进行访问的数据结构，也就是我们常用到的map。哈希函数：也称为是散列函数，是Hash
B树B-树，就是B树，B树的原英文名是B-tree,所以很多翻译为B-树,就会很多人误以为B-树是一种树、B树是另外一种树。其实，B-tree就是B树。B-树的定义B树（B-tree）是一种树状数据结构，是一种平衡的多路查找树，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。一棵m阶的B-树,或为空
我们知道，对于一般的二叉搜索树（BinarySearchTree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。平衡二叉树
目录1、二叉排序树的定义2、二叉排序树的查找3、二叉排序树的插入与删除4、二叉排序树的构造5、二叉排序树的删除定义二叉排序树（BinarySortTree）又称为二叉查找树（BinarySearchTree）、二叉搜索树。它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y]<=key[x]；如果y是x的右子树的一个结点，则key[y]>=key[x]。那么，这棵树就是二叉查找树。二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后再就行和每个节
查找基本概念查找就是在数据集中找出一个“特定元素”。查找表是由同一类型的数据元素(或记录)构成的集合。查找表是一种以集合为逻辑结构、以查找为核心的数据结构。关键字有时候我们需要指定某数据项的值来查找，这就用到了关键字。关键字是数据元素中某个数据项的值，用以标识一个数据元素。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”；若此关键字能识别若干记录，则称之谓“次关键字”。例：对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。查找表可分为两类:静态查找：仅作查询和检索
最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小，例：公交查询系统。问题解法：求从某个源点到其余各点的最短路径—Dijkstra算法每一对顶点之间的最短路径—Floyd算法例如：从某点到其他各顶点的最短路径最短路径不一定是经过边最少的路径，但在这些最短路径中，长度最短的那一条路径上只有一条边，且它的权值在从源点出发的所有边的权值最小。路径长度最短的最短路径的特点：在这条路径上，必定只含一条弧，并且这条弧的权值最小
有向无环图及其应用一个无环的有向图称做有向无环图,简称DAG图。DAG图是一类较有向树更一般的特殊有向图。拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。例，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动。顶点表示活动，有向边表示活动的先后关系的网简称为AOV网。AOV网中不能有环，否则工程无法顺利进行。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological
最小生成树问题提出：要在n个城市间建立通信联络网，城市间的通信线路造价不同，希望找到一种方案使得建立该通信网所需花费的总代价最小。问题分析：n个城市间，最多可设置n(n-1)/2条线路；n个城市间建立通信网，至少需n-1条线路；问题转化为：如何在可能的线路中选择n-1条，能把所有城市（顶点）连起来，且总耗费（各边权值之和）最小。定义：生成树中边的权值（代价）之和最小的树。构造最小生成树的准则：必须只使用该网中的边来构造最小生成树；必须使用且仅使用n-1条边来联结网络中的n个顶点；不能使用产生回路的边。实例：普里姆(Prim)算法普里姆方法的思想：1）在图中任取一个顶点K作为开始点，令U={k}
图的遍历在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访问过，未访问的值为0，访问过的值为1。图的遍历有两种方法：深度优先搜索遍历（DFS）、广度优先搜索遍历（BFS）。深度优先搜索深度优先搜索思想首先访问顶点i，并将其访问标记置为访问过，即visited[i]=1；然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visited[j]=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；若与i有边相连的顶点都被
图的基本概念图是由一个顶点集V和一个边集E构成的数据结构。Graph=(V，E)图中代表一条边的顶点的偶对如果无方向性，即无序，则称此图为无向图。例：V={V1,V2,V3,V4,V5}；E={(V1,V2),(V1,V4),(V2,V3),(V3,V4),(V2,V5)}在无向图中，(x,y)与(y,x)表示同一条边。图中代表一条边的顶点的偶对如果有序的，则称此图为有向图。在有向图中，用<x,y>表示一条有向边，在有向图中也称边为“弧”，x称为边的弧尾或始点，称此边为顶点x的一条出边；y称为边的弧头或终点，称此边为顶点y的一条入边。例：V={V1,V2,V3,V4}；E={<
二叉树遍历的几种方法存储结构：typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode;遍历树的遍历顺序是相对父结点来说的。先序遍历：先访问根结点,然后分别先序遍历左子树、右子树。递归先序：voidPreOrderTraverse(BiTreebt){/*最简单的Visit函数：Visit(ElemTypee){printf(e);}*/if(bt){Visit(bt->data);PreOrderTraverse(bt->lchild);PreOrderT