精华内容
下载资源
问答
  • 什么是数据结构?什么是算法

    万次阅读 多人点赞 2018-05-04 00:35:22
    记得是大一大二的时候学习了数据结构。时间过的好快,现在实现了,现在感觉自己的...引用姥姥的例子:如果给一堆书会怎么放? 想怎么放就怎么放,哈哈。 如果书不多,我们一般是一本插着一本的放着。如下图 ...

    记得是大一大二的时候学习了数据结构。时间过的好快,现在实现了,现在感觉自己的基础好差很多都不会。欠的帐还是要还的!

    什么是数据结构?什么是算法?

    呃呃呃呃 哎….不会。

    多次参加了MOOC姥姥的数据结构,都没有坚持下来,希望这次可以坚持下来。

    引用姥姥的例子:如果给你一堆书你会怎么放?

    想怎么放就怎么放,哈哈。

    如果书不多,我们一般是一本插着一本的放着。如下图

    要是书的规模很大呢?如学校图书馆里面的书如果是按上述一本一本的插入,那么以后需要找书的时候是不是累死人了。如下图

    所以答案是看书的规模。


    什么是数据结构?

    数据是什么?结构是什么?

    参考大话数据结构,几个术语的定义

    数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合

    其实就是图书馆中所有的书。

    数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。

    就是书。

    数据项:一个数据元素可以由若干个数据项组成。

    其实就是书名、作者、出版社啥的….

    class Book {
    //书名
    private String bookName;
    //作者
    private String bookAuthor;
    //出版社
    private String bookPress;
    }
    

    其实一个Book对象就是数据元素,bookName、bookAuthor、bookPress就是数据项。

    数据对象:是性质相同的数据元素的集合,是数据的子集。

    其实就是某一类书。如图下图都是数据结构一类的书

    是不是明白了什么是数据?哈哈 还是需要结合例子理解的深入啊。

    什么是结构?

    逻辑结构、物理结构。

    逻辑结构:是指数据对象中数据元素之间的相互关系。包括集合结构、线性结构、树形结构、图形结构。

    集合结构:集合结构中的数据元素除了同属于一个集合外,它们之间没有其它关系。

    线性结构:线性结构中的数据之间是一对一的关系。

    树形结构:树形结构中的数据之间存在一种一对多的层次关系。

    图形结构:图形结构的数据元素是多对多的关系。


    物理结构:是指数据的逻辑结构在计算机中的存储形式。顺序存储和链式存储。

    顺序存储:是把数据元素存放在地址连续的存储单元里。

    链式存储:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。


    什么是数据结构?

    Sartaj Sahni在他的《数据结构、算法与应用》一书中称:“数据结构是数据对象,以及存在于该对象的实例合组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象(data object)定义为“一个数据对象是实例或值的集合”。

    Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是:“数据结构是 ADT(抽象数据类型Abstract Data Type) 的物理实现。”

    大话数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

    姥姥:数据结构包括数据对象集以及它们在计算机中的组织方式,即它们的逻辑结构和物理存储结构,同时还包括与数据对象集相关的操作集,以及实现这些操作的最高效的算法。

    个人:就是把图书馆中的书转化为一些字符数据存入电脑中,以及对这些数据对象集的操作。如找书,摆放放书等。


    什么是算法?

    还是图书馆的例子,如果一本一本找累死人,要是有个索引,先找哪一类这样会快很多。如何查找其实就是算法。

    算法是解决问题步骤的有限集合,通常用某一种计算机语言进行伪码描述。通常用时间复杂度和空间复杂度来衡量算法的优劣。

    算法的五大特征:输入、输出、有穷性、确定性、可行性。

    输入:零个或多个输入。

    输出:一个或多个输出。

    有穷性:有限步骤后在可接受时间内完成。

    确定性:每个步骤都有确定含义,无二义性。

    可行性:每一步都是可行的。

    算法设计要求:正确性、可读性、健壮性、时间效率高和存储低。

    正确性:有输入输出,无二义性,有正确答案。

    可读性:方便阅读。

    健壮性:输入不合法能处理

    时间效率高和存储低:时间空间复杂度越低越好。


    这就是数据结构和算法。

    展开全文
  • 其实树结构是平日里我们常见的一种数据结构,例如家族族谱、公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    本篇文章将开始讲解树结构。其实树结构是平日里我们常见的一种数据结构,例如家族族谱公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。

    • 家族族谱图

    在这里插入图片描述

    • 公司管理层级结构图

    在这里插入图片描述

    因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就从零开始学习一下树结构,并且也会封装一个二叉查找树,本文 3万+ 的详细教程,希望大家耐心观看,我是以一个纯小白的角度来写的这篇文章,相信大家认真看一定都能看懂的

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是树

    树在我们平日应该算是一个低头不见抬头见的东西了。这里我特地找了个比较好看的树放在这里,大家可以观察一下树的特点,如图

    在这里插入图片描述
    第一反应是不是从树根开始往上生长,分出了特别的多分叉?没错,咱们要学习的树结构就是参照着真正的树衍生过来的,只不过是一个倒着的抽象的树,如图
    在这里插入图片描述
    我们把图中第一层的圆圈看成是树根,以下的几层都是由树根延伸出去的分支,这里的每一个圆圈都可以用于存储我们的数据。

    是一种非线性数据结构,它是由一个或多个结点组成的

    二、树结构的优点

    总的来说,树结构是结合了之前我们讲过的数组、链表、哈希表等结构的优缺点,但也不能说哈希表是最好的数据结构,毕竟每种数据结构都有各自突出的优点

    树结构的优点:

    1. 空间利用率比较高
    2. 可以非常快速地查找到最大值和最小值

    三、树结构的术语

    因为本文是从零开始学习树结构,所以我们在这里有必要讲解一下,在我们封装各种树结构的过程中涉及到的术语,方便大家理解。

    术语名 含义
    结点 树中的数据元素
    结点的度 结点拥有的子树个数
    叶子结点 度为0的结点
    分支结点 度大于0的结点
    父节点 衍生出其它结点的结点为这些结点的父结点
    子结点 被某个结点衍生出来的结点为该结点的子结点
    兄弟结点 具有同一个父节点的所有结点为兄弟结点
    结点的层次 设定根结点所在层次为1,其它结点层次为其父节点层次+1
    树的深度 树的所有结点中的最大层次为该树的深度
    路径 从某个结点沿着树的层级关系到达另一个结点之间的路线
    路径长度 路径上的结点个数 -1

    我们来用图讲解一下每个术语的含义
    在这里插入图片描述
    如图,每一个圆圈就是一个结点结点A 延伸出去三个结点,因此 结点A 的度为 3结点B 延伸出去两个结点,因此 结点B 的度为 2结点C 并没有延伸出去的结点,故 结点C 的度为 0

    图中像 结点C 一样的度为 0 的结点还有 结点D结点E结点F,它们都称为叶子结点 ; 那么相对的,结点A结点B 的度都不为 0,它们就称为分支结点

    对于 父结点 、子结点 、兄弟结点,我们把图中的树结构看成族谱就很好理解了,假设 结点B爸妈,其延伸出去两个结点 结点E结点F,那么就是 B 生了 EF,所以 结点B 就是 结点E结点F父结点结点E结点F 就是 结点B子结点结点E结点F 互为兄弟结点

    树结构我们可以进行层次分级,例如统一规定根结点所在层次为 1,接着往下层级逐渐 +1。如图,结点A 所在的层次为 1;那么它的下一层层级就为 2,也就是 结点B结点C结点D 所在的层次为 2 ;再往下一层,结点E结点F 所在的层次为 3,这就是结点的层次。因为该树结构的最大层次为 3,所以该树的深度就为 3

    对于路径,假设我们要找到 结点A结点E 的路径,我们只需要沿着树的层次结构走就可以了,如图红线所标的路线就称为 结点A结点E路径
    在这里插入图片描述
    那么路径的长度为多少呢?因为该路径上经过了 3 个结点,因此,该路径的长度2

    四、什么是二叉树

    在树结构中,我们用到的最多的就是二叉树,因此它也是我们重点学习的对象,并且本文最后是要进行二叉查找树的代码封装,那么我们还是要先来了解一下二叉树的定义

    二叉树的定义: 树结构中每个结点最多只有两个子结点,即任何一个结点的度都小于等于 2

    我自己画了几个图来给大家举例哪些是二叉树,哪些不是

    首先说明,二叉树可以为空,也就是结点个数可以等于 0,此时称之为空二叉树


    在这里插入图片描述
    该树结构只有一个根节点,符合二叉树的定义,因此这一个非空二叉树


    在这里插入图片描述
    该树结构不是二叉树,因为 结点A 有三个子结点,不符合二叉树的定义


    在这里插入图片描述
    该树结构一个非空二叉树


    正是因为二叉树只有两个子结点,因此我们可以简单得把位于左侧和位于右侧的两个子结点分别称作其父节点的 左子结点右子结点

    讲到这里,我再补充个概念,叫做 左子树右子树 。因为我们整个二叉树就像是一棵树嘛,那么当我们以某个结点当作根结点,我们可以把其左边的所有结点组成的结构看成是一颗小一点的树,称之为 左子树 ;同理,其右侧所有结点组成的结构称之为 右子树 。如图

    在这里插入图片描述


    其实在二叉树中,又有两种特殊的二叉树,即 完美二叉树完全二叉树,接下来我们来简单讲解一下这两种类型的二叉树的概念

    五、完美二叉树

    完美二叉树 又叫 满二叉树,顾名思义,就是在一个二叉树中,除了最后一个层级的叶子节点外,其余每个结点都有两个子结点

    如图就是一个满二叉树
    在这里插入图片描述


    再来看一个不是满二叉树的例子,如图
    在这里插入图片描述
    该二叉树就不是一个满二叉树,因为处于倒数第二层的 结点C 只有一个子结点,不满足满二叉树的定义

    六、完全二叉树

    完全二叉树要满足以下两个条件:

    1. 除了最后一层外,其它各层的结点个数都达到最大个数
    2. 最后一层的结点集中在左侧,且结点连续,只有右侧部分可以缺失结点

    光看定义难以理解,我们来用实例了解完全二叉树
    在这里插入图片描述
    不是一个完全二叉树。其满足了完全二叉树的第一个条件,第一层最大结点个数应为 1,它有 1 个结点 ;第二层最大结点个数应为 2,它有 2 个结点 ;第三层最大结点个数应为 4,它有 4 个结点。

    但其不满足完全二叉树的第二个条件,因为最后一层的 结点H结点I结点J 没有连续集中在左侧。


    那么如何才算是连续集中在左侧呢?只需要在此图中给 结点D 添加一个右子结点即可使最后一层的结点连续集中在左侧,如图
    在这里插入图片描述
    这就一个正确的完全二叉树


    再来看一个例子,如图
    在这里插入图片描述
    这就不是一个完全二叉树了,虽然最后一层的结点连续集中在一起,但是它们集中在最后一层的右侧,这并不满足完全二叉树的定义


    其实 满二叉树 是一种特殊的 完全二叉树,不信你可以自己举个简单的例子验证一下

    七、二叉树的特性

    二叉树作为树结构中一种特殊的类型,它是有一些自己的特性的,我们来看一下

    (1)特性一

    一个二叉树第 i 层的最大结点个数为 2i1(i>=1)2^{i-1}(i>=1)

    在二叉树中,结点个数最多的情况就是满二叉树,即除了最后一层的叶子结点外,其余结点都有两个子结点,因此满二叉树每一层的结点个数都达到了最大值,其余类型的二叉树每一层结点个数只会小于或等于它

    我们可以自己来验证一下,下图时一个树的深度为 3 的满二叉树
    在这里插入图片描述
    第一层结点个数最多只有 20=12^0 = 1 个,图中有一个结点
    第二层结点个数最多只有 21=22^1 = 2 个,图中有两个结点
    第三层结点个数最多只有 22=42^2 = 4 个,图中有四个结点

    (2)特性二

    深度为 k 的二叉树拥有的最大结点数为 2k1(k>=1)2^k-1(k>=1)

    同样的,满二叉树是二叉树中结点个数最多的,因此其结点个数公式就为 2k1(k>=1)2^k-1(k>=1)

    我们可以验证一下

    在这里插入图片描述
    这是一个深度为 1 的满二叉树,最大结点个数为 201=12^0-1 = 1


    在这里插入图片描述
    这是一个深度为 2 的满二叉树,最大结点个数为 221=32^2-1 = 3


    在这里插入图片描述
    这是一个深度为 3 的满二叉树,最大结点个数为 231=72^3-1 = 7

    (3)特性三

    在非空二叉树中,n0n_0 表示叶子结点个数,n1n_1 表示分支结点个数,那么它们满足的关系有 n0=n1+1n_0=n_1 + 1

    该特性也是一个总结出来的规律,大家了解一下即可,可以自行验证一下

    八、二叉树的存储

    在使用二叉树存储数据时,我们有两种选择,一种是数组存储,另一种是链表存储

    (1)数组存储

    当使用数组存储时,如图
    在这里插入图片描述

    在按照从上到下,从左到右的顺序给二叉树标上下标以后,我们发现在使用数组存储二叉树的数据时,很难或者说几乎无法分辨结点之间的结点关系

    因此,有一种解决办法就是将二叉树补全成一个满二叉树,然后下标仍是按照从上到下,从左到右的顺序给的,如图
    在这里插入图片描述
    此时,我们就可以看到,各个结点之间就可以分辨得出来了,即父节点的下标值 index * 2 + 1,就等于其左子结点的下标值 ;同样的,父节点的下标值 index * 2 + 2,就等于其右子结点的下标值

    虽然现在结点间的关系可以辨别得出来了,但是有没有发现,这造成了很大的空间浪费,整个数组长度为 15,空着的位置就有 8

    所以我个人认为,用数组来存储二叉树的数据不太合适

    (2)链表存储

    链表存储也是二叉树最常用的一种存储方法。我们可以通过给每个结点封装一个对象,通过 leftright 分别指向其左子结点和右子结点

    来看一下,用链表存储的二叉树的样子,如图
    在这里插入图片描述
    我们只需要调用某结点的 leftright 就可以找到其子结点,这样做既避免了空间的浪费,又能把结点关系理得特别清楚

    九、什么是二叉查找树

    二叉查找树,英文名为 Binary Search Tree,简称BST,又名二叉排序树、二叉搜索树。

    二叉查找树本身就是一棵二叉树,它可以是一棵空树

    当二叉查找树不为空时,必须满足以下三个条件

    1. 非空左子树的结点的 key 小于其根结点的 key
    2. 非空右子树的结点的 key 大于其根结点的 key
    3. 左子树和右子树本身也是个二叉查找树

    我们可以先一个例子来体会一下这三个条件,如图

    在这里插入图片描述
    首先根结点的 key50 ,其左子结点为 10 小于 50,符合第一个条件 ;其右子结点为 70 大于 50,符合第二个条件

    再来看 结点10,其左子结点为 8 小于 10,符合第一个条件 ;其右子结点为 13 大于 10,符合第二个条件

    同理,结点70 也是符合的,因此就符合了第三个条件


    总结一下呢,就是以下几条结论:

    1. 左边的结点永远比根结点以及右边的结点小
    2. 右边的结点永远比根结点已经左边的结点大

    所以,接下来我们再来看几个例子,判断一下哪些时二叉查找树,哪些不是

    在这里插入图片描述
    这不是一个二叉查找树,因为 结点7 在右侧,比其根结点 8 要小,所以不符合条件。正确的位置应该是处于 结点8 的左子树位置


    在这里插入图片描述
    这是一个二叉查找树

    十、树的遍历

    以上给出的树结构的图都是我们布局好的非常美观的样子,但在程序里,树结构是非常抽象的,因此我们可以通过遍历全部结点的方式,将整个树结构展现出来

    树的遍历一共分成三种,分别是 先序遍历中序遍历后序遍历

    (1)先序遍历

    先序遍历: 访问根结点 => 访问左子树 => 访问右子树。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行先序遍历

    在这里插入图片描述


    第一步: 先访问根结点 50 ,再访问左子树,最后访问右子树,如图
    在这里插入图片描述

    此时我们记录一下访问的过程,即 50 左子树10 右子树70


    第二步: 左子树10 也需要按照先序遍历的步骤进行,所以先访问 左子树10 中的根节点 10,再遍历其左子树,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 50 10 8 13 右子树70


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先访问其根结点 70,再遍历其左子树,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 50 10 8 13 70 60 80


    好了,到此位置,一个先序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图
    在这里插入图片描述

    (2)中序遍历

    中序遍历: 访问左子树 => 访问根结点 => 访问右子树。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行中序遍历

    在这里插入图片描述


    第一步: 先遍历 左子树10,再访问根结点 50,最后遍历右子树 70,如图

    在这里插入图片描述

    此时我们记录一下访问的过程,即 左子树10 50 右子树70


    第二步: 左子树10 也需要按照中序遍历的步骤进行,所以先遍历 左子树10 中的左子树,再访问其根节点 10,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 8 10 13 50 右子树70


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先遍历 右子树70 的左子树,再访问其根结点 70,最后遍历其右子树,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 8 10 13 50 60 70 80


    好了,到此位置,一个中序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图

    在这里插入图片描述

    (3)后序遍历

    后序遍历: 访问左子树 => 访问右子树 => 访问根结点 。在访问左子树或右子树的时候,仍是按照这个规则继续访问。

    我们来看一个简单的例子,如图,对其进行后序遍历

    在这里插入图片描述


    第一步: 先遍历 左子树10,再遍历右子树 70,最后访问根结点 50,如图

    在这里插入图片描述

    此时我们记录一下访问的过程,即 左子树10 右子树70 50


    第二步: 左子树10 也需要按照后序遍历的步骤进行,所以先遍历 左子树10 中的左子树,再遍历其右子树,最后再访问其根节点 10,如图
    在这里插入图片描述

    因为 结点10 的左右子树都属于叶子结点了,即没有任何的子结点了,所需就无需对其进行遍历了

    我们接着第一步中的结果进行记录,即 8 13 10 右子树70 50


    第三步: 最后还剩个 右子树70 没有遍历了,那么同理,先遍历 右子树70 的左子树,再遍历其右子树,最后访问其根结点 70,如图
    在这里插入图片描述

    因为 结点70 的左右子树也都属于叶子结点了,所以也没有必要对其进行遍历了,直接获取该结点即可

    我们接着第二步的结果进行记录,即 8 13 10 60 80 70 50


    好了,到此位置,一个后序遍历的结果就出来了,我们来总结一下它的全部访问过程,如图
    在这里插入图片描述

    十一、二叉查找树的方法

    在封装二叉查找树之前,我们还是先来看一下二叉查找树常见的方法右哪些吧

    方法 作用
    insert() 向二叉查找树插入数据
    preOrder() 先序遍历二叉查找树,并返回结果
    inOrder() 中序遍历二叉查找树,并返回结果
    postOrder() 后序遍历二叉查找树,并返回结果
    getMax() 返回二叉查找树中的最大值
    getMin() 返回二叉查找树中的最小值
    search() 查找二叉查找树中的某个值
    remove() 移除某个值

    十二、用代码实现二叉查找树

    前提:

    1. 代码中会用到大量的递归思想,请还没了解过递归的小伙伴自行了解一下
    2. 部分方法会通过再封装一个内部函数来实现,请认真理解

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放二叉查找树的一些属性和方法。

    function BinarySearchTree() {
        // 属性
        this.root = null
    }
    

    二叉查找树的属性最主要的就是 root ,用于指向树的根节点

    (2)创建结点构造函数

    因为我们准备通过链表来实现二叉查找树,所以我们需要先在内部封装一个结点的构造函数

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    }
    

    一个结点包括的内容有 左子结点右子结点,分别对应的 keyvalueleftright

    (3)实现insert()方法

    insert()方法就是将一个数据插入到二叉查找树中合适的位置。该方法接收两个参数,即 keyvalue

    实现思路:

    1. 调用内部结点构造函数,并把参数 keyvalue 传入,生成一个结点对象 node
    2. 判断二叉查找树是否右根结点,即判断是否为空,若为空,则直接将 node 作为二叉查找树的根结点,即将 node 赋值给 root 属性
    3. 若不为空,则遍历整个二叉查找树,用 node.key 与遍历到的结点的 key 值进行比对,最终找到合适的位置进行插入

    思路看着略微复杂,我做了动图方便大家理解,如图

    • 当二叉查找树为空时

    在这里插入图片描述

    • 当二叉查找树不为空时

    在这里插入图片描述
    这里我选择用递归的方式来遍历整个二叉查找树,因此我会再额外封装一个用于递归内部调用的函数 insertNode ,给其传入两个参数,第一个参数是当前遍历到的结点 ; 第二个参数是我们要插入的结点

    先来看下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 插入数据
        BinarySearchTree.prototype.insert = function(key, value = null) {
            // 1. 创建结点
            let node = new Node(key, value)
    
            // 2. 判断根结点是否存在
            // 2.1 不存在
            if(!this.root) {
                this.root = node
                return;
            }
    
            // 2.2 存在
            this.insertNode(this.root, node)
            
        }
    
    	// 插入结点函数(内部)
        BinarySearchTree.prototype.insertNode = function(oldNode, newNode) {
            // 1. 判断我们插入的数据的 key是否大于当前遍历结点的 key
            // 1.1 插入数据的 key 大于当前遍历结点的 key
            if(newNode.key < oldNode.key) {
                // 1.1.1 判断当前遍历结点的左结点是否为空
                // 1.1.1.1 为空
                if(oldNode.left === null) {
                    oldNode.left = newNode
                } 
    			// 1.1.1.2 不为空
    			else {
                    this.insertNode(oldNode.left, newNode)
                }
            } 
    		// 1.2 插入数据的 key 小于当前遍历结点的 key
    		else {
    			// 1.2.1 判断当前遍历结点的右结点是否为空
    			// 1.2.1.1 为空
                if(oldNode.right === null) {
                    oldNode.right = newNode
                } 
    			// 1.2.1.2 不为空
    			else {
                    this.insertNode(oldNode.right, newNode)
                }
            }
        }
    }
    

    insert() 方法中,若二叉查找树不为空,我们就调用 insertNode() 内部方法进行递归调用,并先把 root 和 我们新创建的结点 node 传过去当成参数 , 即表示用需要插入的结点先和根节点进行比较,然后慢慢比对下去,找到属于自己的位置插入

    我在代码上都标注了很详细的注解,大家可以消化消化

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    console.log(bst.root)
    

    因为这里我们还没有封装遍历的函数,因此可以靠浏览器的打印来查看二叉查找树是否正确,结果如下
    在这里插入图片描述
    首先,根节点为 50,然后根节点的左子节点为 10,右子结点为 70
    在这里插入图片描述
    然后看到 结点10 的左子结点是 5,右子结点是 15
    在这里插入图片描述
    最后,结点70 没有自己的左右子结点

    总结一下,当前的二叉树如下图
    在这里插入图片描述
    判断一下,这个结果是正确的,这确实是一个二叉查找树,所以我们的 insert()方法就封装好啦

    (4)实现preOrder()方法

    preOrder()方法就是通过先序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法接收一个回调函数 handle 作为参数, 用于在遍历过程中执行某些操作

    实现思路:

    1. 从根结点开始,按照 访问根结点 => 访问左子树 => 访问右子树 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果先序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 先序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.preOrder = function(handle) {
        
    		// 从整棵二叉查找树的根节点开始遍历
            this.preOrderNodes(this.root, handle)
            
        }
    
        // 以先序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.preOrderNodes = function(node, handle) {
            if(node !== null) {
                // 将根结点的 key传给回调函数处理
                handle(node.key)
    			// 遍历左子树
                this.preOrderNodes(node.left, handle)
    			// 遍历右子树
                this.preOrderNodes(node.right, handle)
            }
            
        }
    }
    

    我们来使用一下该方法,并详细体会一下递归调用的过程是不是跟我们前面分析的先序遍历的思想一样

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)             // 50 10 5 15 70
    

    首先二叉查找树是这样的
    在这里插入图片描述

    1. 刚开始我们从整棵树的根节点 root 开始遍历,先记录 rootkey值,即 50 ;然后遍历 root 的左子树,因此把 root.left 作为下一次调用 preOrderNodes() 方法的根结点

    2. 然后记录一下 结点10,即 50 10,然后我们又要继续遍历 结点10 的左子树,所以就把 结点10.left 作为下一次调用 preOrderNodes() 方法的根结点

    3. 此时访问到了 结点5,并记录一下 50 10 5,再下一次就是遍历 结点5 的左右子树,但因为 结点5 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止, 结点10 的左子树已经全部遍历完毕,接着就要遍历其右子树,因此把 结点10.right 作为下一次调用 preOrderNodes() 方法的根结点

    4. 此时就访问到了 结点15,并记录一下 50 10 5 15,再下一次就是遍历 结点15 的左右子树,但因为 结点15 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止,结点50 的左子树已经全部遍历完毕了,接着就要遍历其右子树,因此把 结点50.right 作为下一次调用 preOrderNodes() 方法的根结点

    5. 此时就访问到了 结点70,并记录一下 50 10 5 15 70,再下一次就是遍历 结点15 的左右子树,但因为 结点15 的左右子树都为 null,所以在调用preOrderNodes() 方法时不进行任何操作。到此为止,结点50 的右子树也全部遍历完毕了。

    6. 因为整棵树的根节点的左右子树都遍历完了,所以先序遍历的操作也就完成了,最终结果就为 50 10 5 15 70

    (5)实现inOrder()方法

    inOrder()方法就是通过中序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法无需传入参数

    实现思路:

    1. 从根结点开始,按照 访问左子树 => 访问根节点 => 访问右子树 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果中序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 中序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.inOrder = function(handle) {
    
            // 从二叉查找树的根结点开始遍历
            this.inOrderNodes(this.root, handle)
            
        }
    
        // 以中序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.inOrderNodes = function(node, handle) {
            if(node !== null) {
            	// 遍历左子树
                this.inOrderNodes(node.left, handle)
                // 将根结点的 key传给回调函数处理
                handle(node.key)
                // 遍历右子树
                this.inOrderNodes(node.right, handle)
            }
        }
    }
    

    因为树结构的三种遍历方式思想都一样,只不过是遍历的顺序有所差别,这里我就不再花大篇幅来讲解整个遍历过程了,直接来使用一下代码,核对一下结果是否准确

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.inOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)                 // 5 10 15 50 70
    

    验证了一下,结果是正确的

    (6)实现postOrder()方法

    postOrder()方法就是通过后序遍历的方式遍历整个二叉查找树,并返回遍历结果。该方法无需传入参数

    实现思路:

    1. 从根结点开始,按照 访问左子树 => 访问右子树 => 访问根结点 的顺序对各个结点进行访问
    2. 访问到结点时,执行回调函数 handle ,并将访问到的结点的 key 作为参数传入

    因为上边已经详细将结果后序遍历的全过程了,因此我们直接来看代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 后序遍历并返回结果(外部函数)
        BinarySearchTree.prototype.postOrder = function(handle) {
    
            // 从二叉查找树的根结点开始遍历
            this.postOrderNodes(this.root, handle)
            
        }
    
        // 以后序遍历的方式遍历整个树(内部函数)
        BinarySearchTree.prototype.postOrderNodes = function(node, handle) {
            if(node !== null) {
            	// 访问左子树
                this.postOrderNodes(node.left, handle)
                // 访问右子树
                this.postOrderNodes(node.right, handle)
                // 将根结点的 key传给回调函数处理
                handle(node.key)
            }
        }
    }
    

    因为树结构的三种遍历方式思想都一样,只不过是遍历的顺序有所差别,这里我就不再花大篇幅来讲解整个遍历过程了,直接来使用一下代码,核对一下结果是否准确

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    
    let str = ''
    bst.postOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)               // 5 15 10 70 50
    

    验证了一下,结果是正确的

    (7)实现getMax()方法

    getMax()方法就是找到二叉查找树中 key 值最大的结点,并返回该结点对象

    实现思路: 该方法思路比较简单,因为二叉查找树越大的值都是往右走的,即 key值较大的结点都是其父结点的右子结点,因此我们可以从整个二叉查找树的根节点开始,一直向右查找,即 node.right,直到 node.right === null,该结点就为这个二叉查找树中 key值最大的结点

    我们来直接看一下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 获取二叉树中的最大值
        BinarySearchTree.prototype.getMax = function() {
        	// 从根结点开始遍历
            let node = this.root
    
    		// 一直向二叉查找树的的右边遍历,直到结点没有右子结点
            while(node.right !== null) {
                node = node.right
            }
    
    		// 返回 key值最大的结点对象
            return node
        }
    }
    

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(60)
    bst.insert(80)
    bst.insert(13)
    bst.insert(12)
    bst.insert(14)
    bst.insert(19)
    bst.insert(20)
    bst.insert(16)
    bst.insert(17)
    
    console.log(bst.getMax())
    // Node { key: 80, value: null, right: null, left: null }
    

    可以看到,最终结果确实返回了 key值最大的结点,为 结点80

    (8)实现getMin()方法

    getMin()方法就是找到二叉查找树中 key 值最小的结点,并返回该结点对象

    实现思路: 该方法思路比较简单,因为二叉查找树越小的值都是往左走的,即 key值较小的结点都是其父结点的左子结点,因此我们可以从整个二叉查找树的根节点开始,一直向左查找,即 node.left,直到 node.left === null,该结点就为这个二叉查找树中 key值最小的结点

    我们来直接看一下代码吧

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 获取二叉树中的最小值
        BinarySearchTree.prototype.getMin = function() {
        	// 从二叉查找树的根结点开始遍历
            let node = this.root
            // 一直向二叉查找树的左边遍历,直到结点没有左子结点
            while(node.left !== null) {
                node = node.left
            }
            // 返回 key值最小的结点对象
            return node
        }
    }
    

    我们来使用一下该方法

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(60)
    bst.insert(80)
    bst.insert(13)
    bst.insert(12)
    bst.insert(14)
    bst.insert(19)
    bst.insert(20)
    bst.insert(16)
    bst.insert(17)
    
    console.log(bst.getMin())
    // Node { key: 5, value: null, right: null, left: null }
    

    可以看到,最终结果确实返回了 key值最小的结点,为 结点5

    (9)实现search()方法

    search()方法就是查找二叉查找树中指定的 key对应的结点的 value 值。该方法接收一个参数,即需要查找的结点的 key

    实现思路: 从二叉查找树的根节点 root 开始遍历,用我们的参数 key1 与遍历到的结点的 key2 进行比较,若 key1 > key2,则向右继续遍历 ;若 key1 < key2,则向左继续遍历 ;若 key1 === key2,则返回该结点的 value 值 ;若遍历到最后,找不到任何结点了,则返回 false

    我们来看一下实现代码

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 查找指定的 key对应的数据
        BinarySearchTree.prototype.search = function(key) {
    		// 1. 从二叉查找树的根结点开始遍历
            let node = this.root
    		
    		// 2. 一直与遍历到的结点的 key值进行比较
            while(node !== null) {
            	// 查找的 key值大于当前结点 key值
                if(key > node.key) {
                    node = node.right
                }
                // 查找的 key值小于当前结点 key值 
                else if(key < node.key) {
                    node = node.left
                }
                // 查找到对应 key值的结点 
                else {
                    return node.value
                }
            }
    		// 未找到对应 key值的结点
            return false
        }
    }
    

    因为这个方法要返回结点的 value 值,因此这里我们就给每个结点赋值一定的 value

    let bst = new BinarySearchTree()
    
    bst.insert(50, '我是结点50')
    bst.insert(10, '我是结点10')
    bst.insert(70, '我是结点70')
    bst.insert(5, '我是结点5')
    bst.insert(15, '我是结点15')
    bst.insert(60, '我是结点60')
    bst.insert(80, '我是结点80')
    bst.insert(13, '我是结点13')
    bst.insert(12, '我是结点12')
    bst.insert(14, '我是结点14')
    bst.insert(19, '我是结点19')
    bst.insert(20, '我是结点20')
    bst.insert(16, '我是结点16')
    bst.insert(17, '我是结点17')
    
    console.log(bst.search(13))   // 我是结点13
    console.log(bst.search(50))   // 我是结点50
    console.log(bst.search(99))   // false
    

    (10)实现remove()方法

    remove()方法就是用来移除二叉查找树中指定 key 值的结点。该方法需要接收一个参数 key

    总的来说,在二叉查找树的封装中,我认为 remove() 方法应该算是需要考虑情况最最最最最多的,并且需要一定技巧的方法,因此我们先不着急封装,先来观察二叉查找树,如图

    在这里插入图片描述

    放眼望去,我们可以把结点先总的分成三种类型

    1. 叶子结点(没有子结点)
    2. 只有一个子结点(左子结点或右子结点)
    3. 有两个子结点

    同时,这三种情况就是我们在封装 remove() 方法时要考虑的三种情况,我们来分别研究一下

    • 删除的结点为叶子结点

    假设我们要删除 结点14 ,因为该结点为叶子结点,后面没有其它结点,所以直接删除它不会对后续结点造成影响,即将 结点14 的父节点 结点13 的右子结点设置为 null ,如图

    在这里插入图片描述

    • 删除的结点只有一个子结点

    假设我们要删除的结点为 结点5 ,该结点只有一个右子结点,那么我们只需要用 结点5 的右子结点来代替 结点5 原本的位置,因为 结点5 下面的所有结点肯定都小于 结点10,因此我们只需要将 结点10 的左子结点设置成 结点7 ,如图

    在这里插入图片描述
    同样的,如果我们要删除 结点15 ,也是只需要用其子结点来代替其原来的位置即可,如图
    在这里插入图片描述

    • 删除的结点有两个子结点

    假设我们要删除的结点为 结点10 ,它有两个子结点,且子结点后面还有好多结点。当 结点10 被移除以后,该位置上应该有一个比其左子结点 结点5 以及后面所有结点还要大,同时比其右子结点 结点15 以及后面所有结点还要小的结点,这样的结点怎么找呢?

    这里我给大家一个思路,此时我们有两种选择

    1. 第一种选择就是去 结点10 的左子树里找,找到左子树里 key 值最大的一个结点,在本例中,最大的结点肯定就是 结点7 了,然后我们用 结点7 代替 结点10 的位置,这样就能保证该位置上结点的 key 值大于左子树里所有结点的 key 值,又能保证小于右子树里所有结点的 key 值了。同时我们不能忘记了,结点7 也有它自己的子结点,但能保证的是它一定没有右子结点,因为如果 结点7 还有右子结点,那么 结点7 就不是最大的结点了,所以我们只需要考虑它有无左子结点即可。
      在这里插入图片描述

    2. 第二种选择自然就是去 结点10 的右子树里去找了,找到右子树里 key 值最小的一个结点,在本例中,最小的结点肯定是 结点13 了,然后我们也一样的用 结点13 代替 结点10 的位置,这样就能保证该位置上结点的 key 值大于左子树里所有结点的 key 值,又能保证小于右子树里所有结点的 key 值了。至于 结点13 的子结点如何处理,想必应该不用我再过多重复了吧
      在这里插入图片描述

    这就是 remove() 方法要考虑的三种情况了,接下来我们来讲解一下整个方法的实现思路

    实现思路:

    1. 先遍历整个二叉查找树,找到我们要删除的结点 node ,同时创建变量 parentdirection 分别记录结点 node 的父节点 以及结点node 属于其父节点的左结点还是右结点。若没有遍历到我们要删除的结点,则返回 false
    2. 若遍历到了要删除的结点 node ,则按上面提到三种情况分析结点 node 的类型,然后做出相应的处理,需要注意的是,无论分析哪种类型结点,我们还需要多做一步判断,那就是被删除结点是否为根节点 root

    好了,前面铺垫了那么多,现在我们来写一下代码吧,这里先申明一下,在面对被删除结点右两个子结点时,我选用的是我上面提到的第二种选择

    function BinarySearchTree() {
        // 属性
        this.root = null
    
    	// 结点构造函数
        function Node(key, value) {
            this.key = key
            this.value = value
            this.right = null
            this.left = null
        }
    
    	// 删除指定 key的数据
        BinarySearchTree.prototype.remove = function(key) {
            let node = this.root
            let parent = null
            let direction = ''
    
            // 1. 找到需要被删除的节点
            while(node !== null) {
                if(key < node.key) {
                    parent = node
                    direction = 'left'
                    node = node.left
                } else if(key > node.key) {
                    parent = node
                    direction = 'right'
                    node = node.right
                } else {
                    break;
                }
            }
    
            // 1.1 未找到对应节点,删除失败
            if(node === null) return false;
    
            // 1.2 找到对应节点
            // 2. 判断节点类型(叶子节点、只有一个子节点、有两个子节点)
    
            // 2.1 节点类型为叶子节点
            if(node.left === null && node.right === null) {
    
                if(node === this.root) {
                    this.root = null
                } else {
                    parent[direction] = null
                }
    
            } 
            
            // 2.2.1 节点只有一个右子节点
            else if(node.left === null) {
                if(node === this.root) {
                    this.root = this.root.right
                } else {
                    parent[direction] = node.right
                }
            } 
    
            // 2.2.2 节点只有一个左子节点
            else if(node.right === null) {
                if(node === this.root) {
                    this.root = this.root.left
                } else {
                    parent[direction] = node.left
                }
            } 
    
            // 2.3 节点有两个子节点
            else {
                let minNode = node.right
                let minNode_parent = node
                // 2.3.1 找到被删除节点右子节点的子孙节点中最小的节点
                while(minNode.left !== null) {
                    minNode_parent = minNode
                    minNode = minNode.left
                }
                
                // 2.3.2 判断 minNode是否有右子节点
                // 2.3.2.1 无右子节点
                if(minNode.right === null) {
                    if(node === this.root) {
                        this.root = minNode                 
                    } else {
                        parent[direction] = minNode      
                    }
                    minNode.left = node.left
                    minNode.right = node.right
                    minNode_parent.left = null      
                }
    
                // 2.3.2.2 有右子节点
                else {
                    if(node === this.root) {
                        this.root = minNode                
                    } else {
                        parent[direction] = minNode
                    }
                    minNode_parent.left = minNode.right
                    minNode.left = node.left
                    minNode.right = node.right      
                }
            }
            
        }    
    }
    

    这里我们仍然用上面提到的那个例子,因此先用 insert() 方法插入相应的结点

    let bst = new BinarySearchTree()
    
    bst.insert(50)
    bst.insert(10)
    bst.insert(70)
    bst.insert(5)
    bst.insert(15)
    bst.insert(7)
    bst.insert(6)
    bst.insert(13)
    bst.insert(14)
    bst.insert(60)
    bst.insert(80)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 10 5 7 6 15 13 14 70 60 80
    

    我们采用先序遍历的方式,先验证二叉查找树的初始状态,此时的二叉树查找树如下图

    在这里插入图片描述

    • 删除结点6(叶子节点)
    bst.remove(6)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 10 5 7 15 13 14 70 60 80
    

    在删除了 结点6 以后,先序遍历输出的结果为 50 10 5 7 15 13 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除结点15(只有一个子结点)
    bst.remove(15)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)        // 50 10 5 7 6 13 14 70 60 80
    

    在删除了 结点15 以后,先序遍历输出的结果为 50 10 5 7 6 13 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除结点10(有两个子结点)
    bst.remove(10)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 50 13 5 7 6 15 14 70 60 80
    

    在删除了 结点10 以后,先序遍历输出的结果为 50 13 5 7 6 15 14 70 60 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    • 删除根节点50(有两个子结点)
    bst.remove(50)
    
    let str = ''
    bst.preOrder(function(key) {
    	str += `${key} `
    })   
    
    console.log(str)         // 60 10 5 7 6 15 13 14 70 80
    

    在删除了 结点50 以后,先序遍历输出的结果为 60 10 5 7 6 15 13 14 70 80 ,还原成二叉查找树如下图

    在这里插入图片描述

    十三、结束语

    二叉查找树的讲解就到这里了,希望大家对二叉查找树有了更深一层的理解。下一篇文章我将讲解一下红黑树

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 大家好,我是 Rocky0429,一个连数据结构和算法都不会的蒟蒻… 学过数据结构和算法的都知道这玩意儿不好学,没学过的经常听到这样的说法还没学就觉得难,其实难吗?真难! 难在哪呢?当年我还是个小蒟蒻,初学数据...

    在这里插入图片描述


    大家好,我是 Rocky0429,一个连数据结构和算法都不会的蒟蒻…


    学过数据结构和算法的都知道这玩意儿不好学,没学过的经常听到这样的说法还没学就觉得难,其实难吗?真难!


    难在哪呢?当年我还是个小蒟蒻,初学数据结构和算法的时候,在忍着枯燥看完定义原理,之后想实现的时候,觉得它们的过程真的是七拐八绕,及其难受。


    在简单的链表、栈和队列这些我还能靠着在草稿上写写画画理解过程,但是到了数论、图论的时候,中间实现的过程步骤开始剧增,那个时候靠写写画画和对程序的单步调试强行理解,作为一个智商一直被压制的惨人,稍不注意就会重新来过,陷入死循环…


    后来搞 ACM 之初,我的队友给了我一个数据结构模拟器的压缩包(后来知道好像是严蔚敏数据机构那本书光盘里带的),里面是对一些数据结构的模拟操作,一步步的很形象,有些东西好像一下子就通了…


    在这里插入图片描述

    这种可视化的动画真的对我们理解数据结构和算法非常有帮助,尤其是在学习之初,堪称很好的防劝退工具,所以我对这些做了一些整理,希望能帮助到你。



    0x00 数据结构在线模拟器


    Github 网址:https://github.com/IACJ/react-datastructer
    在线网址:https://iacj.github.io/react-datastructer/#/


    这个在线的模拟器包含“栈”、“队列”、“堆”、“BST” 等数据结构,每个数据结构以图像的方式展示在我们面前,同时又有各自的帮助文档,可以用鼠标对数据节点进行拖拽,还可以实现各种数据结构的增删改查。


    还有一点好的是,这个网站还伴随着一些数据结构的教学材料、简要的复杂度分析、数据结构使用实例,对于理解各种数据结构的原理及运用可以说是相当丝滑了…


    在这里插入图片描述

    网站上还带着使用说明和产品简介,可以说是相当贴心了…


    在这里插入图片描述

    随便点开一个“堆”的,大家体验一下,是不是想赶紧用起来啦…


    在这里插入图片描述



    0x01 VisuAlgo


    英文网址:https://visualgo.net/en
    中文网址:https://visualgo.net/zh


    VisuAlgo 可以说是知名度比较高的一个通过动画学习算法和数据结构的网站了,它最初的建立就是通过可视化让学生更好的理解数据结构和算法。


    VisuAlgo 的功能更丰富,它包含了很多的数据结构和算法,从简单的到复杂的都一一包含,而且对于一些新出现的算法也有涉猎,通过可视化动画的方法,帮助我们更轻松透彻的理解算法及原理,尤其是对一些通过文字描述很难理解的算法而言,简直是生命之光。


    VisuAlgo 还支持搜索和多种语言的切换,英语不好的同学可以切换成中文,但是现在有一些算法中文翻译的并不全,所以如果能看英文的话还是建议看中文的。


    在这里插入图片描述

    我们随便点开一个排序来看,可以看到它包含之多,还带文字讲解、单步、回退、暂停等功能,真的是功能丰富且强大,当然它不止于此,还包含着更多的东西等着我们去玩儿,赶紧行动起来吧。


    在这里插入图片描述



    0x02 Data Structure Visualizations


    网址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html


    这是旧金山大学的一个数据结构和算法的可视化工具,不过它涉及的内容没有 VisuAlgo 多,不过也涉及了很多常用的数据结构和算法。


    在这里插入图片描述

    我们随便打开一个“栈”,左上角就有 Push(进站)、Pop(出栈)、Clear Stack(清空栈),下面可以设置对动画的一些参数,关于具体的使用,还需要大家多做尝试:


    在这里插入图片描述



    0x03 Algorithm Visualizer


    Github 网址:https://github.com/algorithm-visualizer/algorithm-visualizer
    网址:https://algorithm-visualizer.org/


    AV 同样包含了很多可视化的数据结构和算法,包括动态规划、加密算法、回溯算法等,这个项目在 Github 上有 25k+ 的 Star,足以见得它的受欢迎程度:


    在这里插入图片描述


    同样随便点开一个“
    二叉搜索树”,包括演示区域、过程数据记录和代码演示的部分,而且在代码演示的部分,动画执行到某步的同时代码执行处也会同步,既可以理解代码也可以理解算法原理和过程,真的是相当棒!


    在这里插入图片描述



    0x04 LeetCodeAnimation


    网址:https://github.com/MisterBooo/LeetCodeAnimation


    这个是我的好朋友程序员吴师兄(五分钟学算法)维护的项目,在 Github 上已经有了 44k+ 的 star,属于头部中的战斗机。


    这个项目致力于用动画的形式呈现解LeetCode题目的思路,我们学数据结构与算法,就是为了用,在实际具体的实操环境中往往更能加深对理解,在应用中理解,在理解中应用,才能更快的掌握。


    比如删除链表的倒数第 N 个节点:


    在这里插入图片描述


    现在项目还在继续完善,我觉得大家应该 star 一下。



    0x05 写在之后


    虽然这篇文章介绍的几种可视化动画,可以更轻松的理解数据结构和算法,但我还是建议大家把这个当成一个辅助工具来用,理解以后还是要自己动手写写画画,不要过度依赖,因为方便让人懒惰。


    总会有新的东西需要你靠自己去理解,去学习,而不是每次都有通往目的地的捷径,大家共勉。



    ❤️ 看完有所收获?希望爱学习的你不要吝啬三连击哟[点赞 + 收藏 + 评论]~


    另外本蒟蒻把公众号的高分原创文章整理成了一本电子书,取名《Python修炼之道》,一共 400 页!

    具体内容请戳:熬夜爆肝整理 400 页 《Python 修炼之道》,一本高分原创高清电子书送给你!

    目录如下:


    在这里插入图片描述

    现在免费送给大家,在我的公众号Python空间(微信搜 Devtogether) 回复 修炼之道即可获取。



    作者Info:

    【作者】:Rocky0429
    【原创公众号】:Python空间。
    【简介】:CSDN 博客专家, 985 计算机在读研究生,ACM 退役狗 & 亚洲区域赛银奖划水选手。这是一个坚持原创的技术公众号,专注Python 编程,每天坚持推送各种 Python 基础/进阶文章,数据分析,爬虫实战,数据结构与算法,不定期分享各类资源。
    【转载说明】:转载请说明出处,谢谢合作!~

    展开全文
  • 属于冯诺依曼体系结构必要组成部分是: 正确答案: B 的答案: B (正确) CPU Cache RAM ROM 添加笔记 求解答(4) 收藏 纠错 冯诺依曼 计算机 由CPU...

    不属于冯诺依曼体系结构必要组成部分是:

    正确答案: B   你的答案: B (正确)

    CPU
    Cache
    RAM
    ROM


    冯诺依曼   计算机
    由CPU处理器、
    运算器、
    存储器( RAM, ROM等 
    输入设备、
    输出设备五部分组成

    展开全文
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。
  • 01 什么是数据结构

    千次阅读 2018-08-27 15:23:47
    以后如果要想在这条路上走的远一些和深一些,那就好好打好数据结构和算法的基础。学好这门课,的编程会有一个质的飞跃。 1、什么是数据结构? 程序设计 = 数据结构+算法 所谓数据结构就是关系。什么关系呢,...
  • 【简答题】一句话说出html作用 【单选题】我们在头脑中把魁树分解为根、基、花、果实等来分别加以思考的过程是( ) (5.0分) 【单选题】(2.0分) 【单选题】以下不属于Python语言控制结构的是() (1.0分) 【资料题】根据...
  • IT行业一直流传着一句名言,“程序设计=算法+数据结构”,这是瑞士计算机科学家Niklaus Wirth于1976年出版... 如果说要修一座房子,那么数据结构就是的地基,地基不稳,如何建造高楼大厦?数据结构的一般定义是...
  • 前言 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。...其次,数据结构是计算机软考、计算机等级考试等相关考试的必考内容之一,想要顺利通过这些考...
  • 转载请标明出处:http://blog.csdn.net/lmj623565791/article/details/40212367,本文出自:【张鸿洋的博客】1、概述大家在项目中或多或少...整体是一个树形结构;遇到这样的情况,大家可能回去百度,因为层次多嘛,可
  • js中有三种结构:顺序结构,选择结构,循环结构 一、顺序结构 顺序结构表示程序中的各操作是按照它们出现的先后顺序执行的。 输入 0个或多个 输出 1个或多个 赋值 = 二、选择结构 选择结构表示...
  • 什么是数据结构

    万次阅读 2007-03-19 10:30:00
    数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上...
  • 数据结构:图结构的实现

    万次阅读 多人点赞 2018-02-07 19:44:45
    图是一种很重要的数据结构,不解释。
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    把数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...
  • Java流程控制语句-分支结构(选择结构)

    万次阅读 多人点赞 2019-09-28 22:53:49
    文章目录定义分类if分支结构第一种格式格式执行流程举例第二种格式格式执行流程举例第三种格式格式执行流程举例注意事项switch分支结构执行流程举例注意事项 定义 条件语句可根据不同的条件执行不同的语句。包括if...
  • 数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。 一、什么是数据结构 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一...
  • 我叫《数据结构与算法》,是计算机世界的四大基石之一。 想来我应该是惹人怜爱的吧(认真脸),因为我仿佛听到了无数个初入计算机世界的同学的呐喊声(????)。 我作为一门简单学科,看到有很多的在半途弃我而去,我...
  • 2022考研数据结构_1 绪论

    万次阅读 2020-12-28 16:29:19
    ​ 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。 ​ 程序设计的实质是对确定的问题选择一种好的结构,加上设计一种好的算法。数据结构在程序设计当中占据...
  • 分门别类介绍数据结构的基本概念,查漏补缺必看文章。
  • 数据结构

    千次阅读 2012-06-28 00:24:43
    数据的逻辑结构、存储结构及其数据在运算上的实现 2.下面关天算法的说法,错误的是( D ) A.为解决某问题的算法与为该问题编写的程序含义是相同的 B.算法最终必须由计算机程序实现 C.算法的可行性是指指令不能...
  • 大话数据结构 摘录 第一章 数据结构绪论

    千次阅读 多人点赞 2019-09-01 23:18:06
    文章目录启示:数据结构学习数据机构的重要性数据结构引发的案例数据结构的起源程序设计=数据结构+算法基础概念与术语数据数据元素数据项数据对象数据结构数据结构:是相互之间存在一种或多种特定关系的数据元素的集合...
  • 常用数据结构--线性结构

    万次阅读 多人点赞 2012-04-27 00:20:14
    数据结构是计算机存储、组织数据的方式。常见的数据结构分类方式如下图: 常用的线性结构有:线性表,栈,队列,循环队列,数组。线性表中包括顺序表、链表等,其中,栈和队列只是属于逻辑上的概念,实际中不...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    原创公众号:bigsai 文章已收录在 全网都在关注的数据结构与算法学习仓库 欢迎star 前言 数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在...如果还是学生,那么这门课程是必修的,考研基本也.
  • python分支结构

    万次阅读 多人点赞 2019-05-10 20:49:09
    程序结构 程序三种结构 顺序 循环 分支 ...分支结构 ...分支结构基本语法 ...注意if后面出现的语句,如果属于if语句块,则必须同一缩进等级 条件表达式结果为True执行if后面的缩进...
  • 为什么要学数据结构

    万次阅读 多人点赞 2019-11-19 09:45:23
    一、前言 在可视化化程序设计的今天,借助于...1) 能够熟练地选择和设计各种数据结构和算法 2) 至少要能够熟练地掌握一门程序设计语言 3) 熟知所涉及的相关应用领域的知识 其中,后两个条件比较容易实现,而第一个...
  • 轮廓的层次结构

    千次阅读 2020-10-23 08:23:51
    1.什么是层次结构 通常我们使用函数cv2.findContours 在图片中查找一个对象。有时对象 可能位于不同的位置。还有些情况,一个形状在另外一个形状的内部,这种 情况下我们称外部的形状为父,内部的形状为子。按照这种...
  • 数据结构与算法—前导

    千次阅读 2019-07-25 23:53:34
    前言 重要性 数据结构与算法是程序员内功体现的重要标准之一,而数据结构的也应用在各个方面,更有程序=数据结构+算法这个被人认证的等式存在。并且数据结构与算法的...数据结构是指相互之间存在一种或多种特定关...
  • 数据结构学习之概述

    千次阅读 2016-07-30 21:46:15
    什么是数据结构?... 数据结构是一门研究费数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的科学。 相信不少人看了这个解释后已经在心里对我竖起了中指,这他喵的什么鬼,看不懂。那么
  • 程序猿修仙之路--数据结构是否真的懂数组?

    千次阅读 多人点赞 2019-03-04 16:06:23
    但凡IT江湖侠士,算法与数据结构为必修之课。早有前辈已经明确指出:程序=算法+数据结构 。要想在之后的江湖历练中通关,数据结构必不可少。数据结构与算法相辅相成,亦是阴阳互补之法。...如果觉的对数组足够了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 490,780
精华内容 196,312
关键字:

属于你的结构的是