数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 JavaScript 中实现二叉搜索树
树形数据结构
树是由一些边连接起来的节点集合。按照惯例，树的每个节点都包含一些数据及其子节点的引用。
二叉搜索树
二叉搜索树是一种二叉树，其中值较小的节点存储在左边，而值较大的节点存储在右边。
例如，有效 BST 的可视化表示为：
25 / \ 20 36 / \ / \ 10 22 30 40
现在让我们用 JavaScript 语言实现我们自己的二叉搜索树。
步骤 1：节点类
此类将表示 BST 中各个点处单个节点。BST 不过是根据上述规则放置的数据和子节点引用的节点集合。
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};要创建一个新的 Node 实例，我们可以像这样使用一些数据调用此类：
const newNode = new Node(23);
这将创建一个新的 Node 实例，其中数据设置为 23，左右引用均为 null。
步骤 2：二叉搜索树类
class BinarySearchTree{
constructor(){
this.root = null;
};
};这将创建二叉搜索树类，我们可以使用 new 关键字调用它来创建一个树实例。
现在我们完成了基本工作，让我们继续在正确的位置插入一个新节点（根据定义中描述的 BST 规则）。
步骤 3：在 BST 中插入节点
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};示例
完整的二叉搜索树代码
class Node{
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
};
};
class BinarySearchTree{
constructor(){
this.root = null;
}
insert(data){
var newNode = new Node(data);
if(this.root === null){
this.root = newNode;
}else{
this.insertNode(this.root, newNode);
};
};
insertNode(node, newNode){
if(newNode.data < node.data){
if(node.left === null){
node.left = newNode;
}else{
this.insertNode(node.left, newNode);
};
} else {
if(node.right === null){
node.right = newNode;
}else{
this.insertNode(node.right,newNode);
};
};
};
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);
更新于：2021年3月3日
4K+ 次浏览
广告