如何在 JavaScript 中查找二叉树中是否存在某个值?
javascriptweb developmentfront end technologyobject oriented programming
我们需要在 BinarySearchTree 数据类型的原型对象上编写一个 JavaScript 函数，该函数接受一个值并查找该值是否包含在 BST 中。
示例
此代码如下 -
// BST 的单个节点类
class Node {
constructor(value) {
this.value = value;
}
}
// BST 类
// 包含插入节点和搜索现有节点的函数
class BinarySearchTree {
constructor() {
this._root = null;
};
insert(value) {
let node = this, side = '_root';
while (node[side]) {
node = node[side];
if (value === node.value) {
return;
};
side = value < node.value ? 'left' : 'right';
};
node[side] = new Node(value);
};
contains(value) {
let current = this._root;
while (current) {
if (value === current.value) {
return true;
};
current = value < current.value ? current.left : current.right;
}
return false;
};
}
const tree = new BinarySearchTree();
for (let i = 0; i < 10; i++) {
tree.insert(Math.floor(Math.random() * 1000));
};
tree.insert(34);
console.log(tree.contains(34));
console.log(tree.contains(334));
输出
控制台中的输出将是 −
true false
