可视化讲解 深度优先遍历(DFT)

2018-09-16 admin

深度优先遍历, 刷过题的朋友应该都很熟悉了,难是不难,但是理解起来还是要费一些功夫的. 深度优先遍历的实现方法有递归非递归两种, 这里我们用可视化的角度,讲解前一种: 递归的深度优先遍历.

为什么要以可视化的方式来讲解呢? 因为人是视觉的动物, 如果和你说 二叉树 , 相信大家脑中出现的都是下面的图形:

binary tree

stack

而不是下面的代码:

// binary tree
class Node {
  constructor(value, leftChild, rightChild) {
    this.value = value
    this.leftChild = leftChild
    this.rightChild = rightChild
  }
}

// stack
const stack = new Array()
stack.push(1)
var topItem = stack.pop()

所以说, 人是_视觉动物_, 以图形可视化的方式来讲解问题往往能讲解的更清楚, 这也就是我写本文的缘由.

效果展示

为了可视化的讲解 深度优先遍历算法, 笔者写了一个简单的网页, 实现的功能有:

  • 用户可编辑进行深度遍历的二叉树
  • 网页上给出了 JavaScript 版本的实现
  • 点击 Start DFT 按钮, 用户将看到算法中用到的 二叉树 都将动态 的展示在页面中,可以直观的看到代码运行过程中数据的变化

页面目前还在继续优化中, 让我们看看目前的效果:

stack

可以看到,网页模拟了深度搜索时二叉树的动态变化过程:

  • 二叉树中当前遍历到的节点会变成_红色_;
  • 栈中压入 (push)的节点为_灰色_;
  • 栈中弹出 (pop) 的节点会变为_红色_, 然后消失;

其中页面左上角为初始遍历的二叉树数据, 用户可以修改二叉树数据后再次启动可视化深度优先遍历过程.

页面左下角为深度优先遍历的 javascript 实现版本,作为参考.

深度优先遍历简介

可视化分析之前,让我们先来简单看看实现深度优先搜索的代码:

export class Dft {
  constructor(rootNode, stepCallback) {
    this.rootNode = rootNode
    this.stepCallback = stepCallback
  }

  start() {
    if (!this.rootNode || !this.stepCallback) {
      return
    }
    const stack = [this.rootNode]
    while (stack.length !== 0) {
      const curNode = stack.pop()
      console.log(`current node: ${curNode.value}`)
      curNode.childrenNodes.forEach(element => {
        stack.push(element)
      })
    }
  }
}

export class Node {
  constructor(value, childrenNodes = []) {
    this.value = value
    this.childrenNodes = childrenNodes
  }
}

代码不长,让我们一步步看.

首先我们创建了一个栈 const stack = [this.rootNode] , 并将根节点放入栈中.

接下来是一个_while_语句, 跳出循环的条件是 栈为空, 也就是代表我们遍历完了整棵树.

在循环中, 我们先将栈顶的节点弹出, 并打印出来, 表示我们已经遍历过了该节点. 然后将该节点的所有子节点压入栈中, 这就保障了我们下一个遍历到的点就是该节点的子节点. 重复该循环, 最后我们就可以看到, 二叉树的每个节点都按照深度搜索的顺序被打印了出来:

current node: 1
current node: 4
current node: 7
current node: 6
current node: 2
current node: 5
current node: 3

如果是对栈的使用比较熟悉的同学, 可能看到这里就已经明白原理了.

但是, 如果是对栈使用不是很熟悉的同学, 估计对代码的执行过程还是没有一个直观的认识, 那么让我们以更直观的方式看看这段代码是怎么运行的.

可视化讲解

第一步, 将根节点压入栈中:

step1

接下来进入 while 循环, 每个循环都会将栈顶的节点弹出, 将其子节点压入栈中:

step2

可以看出, 深度优先遍历利用了栈先进后出的特性, 使得对于每个节点, 都将在遍历该节点后,下一步遍历他的子节点, 由此完成深度优先的遍历:

stack

最后

本文中的二叉树, 的可视化是笔者自己封装的 UI 组件, 只需简单的调用就可以将代码中数据结构以可视化的方式显示在页面中.

个人觉得这样的数据结构可视化可能会对代码的讲解有些帮助, 如果你也有这方面的需求的话, 不妨在下面留言告诉我, 我可以将这些 UI 组件封装一下方便有需要的人使用.

想继续了解 D3.js || 数据可视化 ?

这里是我的 D3.js数据可视化 的 github 地址, 欢迎 start & fork

D3-blog

如果觉得不错的话, 不妨点击下面的链接关注一下 : )

github 主页

知乎专栏

掘金

原文链接:https://segmentfault.com/a/1190000016414730

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-40403.html

文章标题:可视化讲解 深度优先遍历(DFT)

相关文章
举例讲解AngularJS中的模块
AngularJS支持模块化的方法。模块用于单独的逻辑表示服务,控制器,应用程序等,并保持代码的整洁。我们在单独的js文件中定义的模块,并将其命名为按照module.js文件形式。在这个例子中,我们要创建两个模块。 Application...
2017-03-24
IoT实时数据可视化方案:Grafana+InfluxDB+Telegraf+MQTT协议+Windows 10
为什么写这篇博客? 最近被论文折磨的死去活来,实时数据可视化方案是我论文的题目。 每天都被这些技术玩弄于股掌之间,靠看文档延续生命和出成果。不得不说,做完这个论文可能以后不敢乱写readme了。 由此大胆推测大家的发量问题有都是看文档时产...
2017-12-24
举例讲解Node.js中的Writable对象
只要有玩过 nodejs,那就一定接触过 Writable。http 模块的请求回调参数中的 res 参数就是一个 Writable 对象。我们经常会往上面 write 一堆东西,最后调用个 end 方法吧?这些都属于 Writable 的...
2017-03-27
js遍历json的key和value的实例
原生js遍历json对象 遍历json对象: 无规律: <script> var json = [{dd:'SB',AA:'东东',re1:123},{cccc:'dd&#x27...
2017-02-23
javascript事件的传播基础实例讲解(35)
本文实例为大家分享了js事件的传播,供大家参考,具体内容如下 <html> <head> <meta charset="UTF-8"> <title>&lt...
2017-03-17
NodeJS遍历文件生产文件列表功能示例
本文实例讲述了NodeJS遍历文件生产文件列表功能。分享给大家供大家参考,具体如下: 功能需求:在工作中我们可能经常需要知道项目中静态文件列表发布,一个一个去检索写,那就太苦逼了。 要想知道里面的文件列表是不是很蛋疼,可能我们也会有dos...
2017-02-23
JavaScript遍历json对象所有key及根据动态key获取值的方法(必看)
实例如下: var obj = {}; for(var k in obj) { //遍历对象,k即为key,obj[k]为当前k对应的值 console.log(obj[k]); } 以上这篇js遍历json...
2017-03-13
javascript事件的绑定基础实例讲解(34)
本文实例为大家分享了js事件绑定的具体代码,供大家参考,具体内容如下 <html> <head> <meta charset="UTF-8"> <title&gt...
2017-03-17
javascript基础知识之html5轮播图实例讲解(44)
本文实例为大家分享了html5轮播图的具体代码,供大家参考,具体内容如下 1.轮播图的布局: <!DOCTYPE html> <html> <head> <meta charset...
2017-03-16
JavaScript 实现获取name 相同的页面元素并循环遍历的方法
实例如下: <input type="hidden" name="blues" value="蓝色浏阳河之最"> <input type="hidde...
2017-03-17
回到顶部