在JavaScript中实现基本的二进制搜索树

作者 : IT 大叔 本文共1887个字,预计阅读时间需要5分钟 发布时间: 2020-10-15

什么是二叉搜索树?

二进制搜索树是常规二进制树的一种变体,后者是一种数据结构,其中每个节点最多具有两个节点。二叉搜索树与常规二叉树的区别在于,每个节点的值均小于其父节点,而每个节点的值均大于其父节点。

这是一个可视化的示例:

        10
      /    \
     8     12
    / \   /  \
   4   9 11  15

如您所见,这是一个有效的Binary Search Tree,因为它在适当的位置满足了较小和较大值的规则。

我们如何建立一个?

我很高兴你问!让我们一起完成构建现代JavaScript的步骤。

我们将使用ES6类语法构建BST,实际上它可以在类中完成!

让我们先声明它,然后同时构建我们的构造函数:

class Node {
  constructor(data) {
   this.data = data;
   this.left = null;
   this.right = null;
  }
}

我们放入构造函数中的是树中每个节点的实际数据所需的一切。该节点具有自己的数据(作为参数传入),并且具有左节点和右节点,默认情况下两者都设置为null。简单!

现在,让我们构建一个类方法,将新节点插入树中。请记住,我们需要确保此方法将给定数据与当前节点的左值和右值进行比较,并正确地从该节点沿现有树向下进行。

我们可以分为两个部分,例如:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }
}

本质上,这在左右两侧都做相同的事情。

我们正在检查传入的数据是否小于或大于当前节点的数据,然后检查当前节点是否已存在左节点或右节点。

如果不是,那么我们将该数据作为新节点插入适当的位置。如果已经有一个节点,则根据我们向哪个方向移动,再次在左侧或右侧节点上调用insert方法。这将在该子节点中重复下面的过程。

构建二进制搜索树而言,我们现在基本上已经完成。好极了!

但是,让我们更进一步,并实现另一种方法来查看BST是否包含某个值:

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  insert(data) {
    if (data < this.data && this.left) {
      this.left.insert(data);
    } else if (data < this.data) {
      this.left = new Node(data);
    }

    if (data > this.data && this.right) {
      this.right.insert(data);
    } else if (data > this.data) {
      this.right = new Node(data);
    }
  }

  contains(data) {
    if (this.data === data) {
      return this;
    }

    if (data < this.data && this.left) {
      return this.left.contains(data);
    } else if (data > this.data && this.right) {
      return this.right.contains(data);
    } else {
      return null;
    }
  }
}

实际上,我们在这里所做的与在上面使用insert方法所做的相同。

我们将给定数据与当前节点的数据进行比较,看其是否小于或大于,以及是否存在左节点或右节点,然后在其上调用相同的contains方法来检查数据和子节点。

如果该值小于或大于当前数据,并且分别不存在左或右子节点,那么我们知道该值在树中不存在,并返回null。

此方法的关键方面是我们的“基本情况”或函数的前三行。这将检查当前节点的数据是否等于我们正在搜索的值,如果是,则找到匹配项!我们可以返回该节点或我们选择用来确认匹配的任何其他值。


在那里,您拥有了!我们已经在JavaScript中正式构建了一个简单的功能二进制搜索树。在稍后的博客文章中,我将探讨BST的其他功能,对您可能遇到的其他采访问题进行更深入的介绍。

如果您已读完本文,非常感谢您抽出宝贵的时间。希望对您有所帮助!:)

免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 在JavaScript中实现基本的二进制搜索树

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论