前端学习数据结构 二分排序树(BST)

栏目: 数据库 · 发布时间: 5年前

内容简介:二分搜索树也是二叉树,和二叉树长的一样,就是有个特点,每个节点的值比他的左子树的值大,比他的右子树的值小。如下图所示:运行结果如下:左节点值是8 右节点值12 中间节点值是10。
前端学习数据结构 二分 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 树(BST)
对于我这样一个毕业了一年半左右的前端来说,很摸着良心的讲,平时工作中,没有遇到过写什么树。但是有大块时间的时候,觉得这些还是得好好复习一下,或者说预习。今天的主角是二分搜索树。

二分搜索树

二分搜索树也是二叉树,和二叉树长的一样,就是有个特点,每个节点的值比他的左子树的值大,比他的右子树的值小。如下图所示:

前端学习数据结构 二分排序树(BST)
那么接下来就来实现一下这个树:
// 声明节点构造函数 当前节点的值,左节点,右节点
class Node {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}
// 二分搜索树构造函数
class BST {
  constructor() {
    this.root = null
    this.size = 0
  }
  getSize() {
    return this.size
  }
  isEmpty() {
    return this.size === 0
  }
  addNode(v) {
    // 每次添加子节点后,更新树
    this.root = this._addChild(this.root, v)
  }
  _addChild(node, v) {
    if (!node) {
      this.size++
      return new Node(v)
    }
    if (node.value > v) {
      console.log(`在${node.value}节点,添加左节点${v}`)
      node.left = this._addChild(node.left, v)
    } else if (node.value < v) {
      console.log(`在${node.value}节点,添加右节点${v}`)
      node.right = this._addChild(node.right, v)
    }
    return node
  }    
}

let bst = new BST()
// 第一个节点
bst.addNode(10)
// 后续节点
bst.addNode(8)
bst.addNode(6)
bst.addNode(3)
bst.addNode(7)
bst.addNode(9)
bst.addNode(12)
bst.addNode(11)
bst.addNode(15)
bst.addNode(14)

console.log(bst)
复制代码

运行结果如下:

前端学习数据结构 二分排序树(BST)

左节点值是8 右节点值12 中间节点值是10。

再展开左节点看一下

前端学习数据结构 二分排序树(BST)

右边就不再展开赘述了

二分搜索树--遍历

二叉树遍历 分为深度遍历(先序遍历、中序遍历、后序遍历,三种遍历的区别在于何时访问节点), 广度遍历(一层层地遍历)

先序遍历

绕不开的递归又出现了,想起有一天右边同事妹子很开心的和我说她知道了递归的终极奥义: “递归的终极奥义就是:不要想递归是怎么具体一步步实现的”

那我先来实现一下先序遍历

class BST { 
    ...
    // 添加先序遍历实现,其实就是很简单的几行代码
    preTraversal() {
      this._pre(this.root)
    }
    _pre(node) {
      if (node) {
        // 访问节点的值
        console.log(node.value)
        // 递归左右子树
        this._pre(node.left)
        this._pre(node.right)
      }
    }
}
// 用上面生成的bst实例执行一下,结果如下图
bst.preTraversal()
复制代码
前端学习数据结构 二分排序树(BST)

那么这个结果是如何生成的呢?

  1. 先是打印10,这个毫无争议 然后 this._pre(node.left),this._pre(node.right)这两个方法看似两行,其实左子树没有遍历完结的话是不会去遍历右子树的
  2. 此时this._pre(node.left)中参数是如下图部分,同样,会对这部分执行那3行代码,首先会打印8 , 然后以8那个节点作为根节点,去遍历左右子树
前端学习数据结构 二分排序树(BST)
3. 打印8之后,遍历左子树的参数如下图部分,同样,会对这部分执行那3行代码,首先会打印6 , 然后以6那个节点作为根节点,去遍历左右子树
前端学习数据结构 二分排序树(BST)
4. 这个时候遍历左子树时候 this_pre(node.left)的参数只是3节点,3节点没有子树,那么在执行上面那3行代码只是打印3 ,this._pre(node.left)和this._pre(node.right)执行不下去了。
  1. 上面第三步骤时候,打印6之后,先遍历左子树,后遍历右子树。而此时的遍历左子树只是打印3。于是要去遍历6的右子树,也就是打印7。
  2. 打印7之后,本例中,作为节点8的左节点已经遍历完毕。遍历8的右节点,也就是打印9,之后8的右节点也遍历完毕。
  3. 再往回退,打印9之后,也就是10节点的左节点已经全部遍历完毕。 所以打印的结果是 10 8 6 3 7 9
  4. 同样的逻辑此时该去遍历10节点的右节点了。依次打印12 11 15 14 ,所以最终结果就是 10 8 6 3 7 9 12 11 15 14

一步步的推导递归的具体实现后,还真的觉的上面所说递归的奥义那句话总结的是很有意思的。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HTML & CSS设计与构建网站

HTML & CSS设计与构建网站

[美] Jon Duckett / 刘涛、陈学敏 / 清华大学出版社 / 2013-1 / 59.80元

欢迎您选择一种更高效的学习HTML和CSS的方式。不管您设计和建立新网站,还是想更好地控制现有网站,都可以在《HTML & CSS 设计与构建网站》一书的指导下创建出用户友好、令用户赏心悦目的Web内容。我们知道,编码是一项令人望而生畏的工作,而本书却采用有别于许多传统编程书籍的新颖编排方式,将使您收到事半功倍的学习效果。 每一页都在短小精悍的示例代码的引导下,简明直观、直截了当地阐述一个新......一起来看看 《HTML & CSS设计与构建网站》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

URL 编码/解码
URL 编码/解码

URL 编码/解码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具