为Javascript二进制搜索树编写递归add方法
为Javascript二进制搜索树编写递归add方法
提问于 2018-06-20 03:58:20
我正在尝试为JS中的BST编写一个add/insert方法，但由于某些原因似乎无法使其工作。我的代码如下：
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
this.add = function(insertElem){
let currNode = this.root;
var recurInsert = function(elem, node){
if(node == null){
let newNode = new Node(elem);
node = newNode;
console.log("firstNode");
return undefined;
}
else if(elem == node.value){
console.log("equal val");
return null
}
else if(elem > node.value){
console.log("go right");
recurInsert(elem, node.right);
}
else{
console.log("go left");
recurInsert(elem, node.left);
}
}
recurInsert(insertElem, currNode);
}
}具体地说，node = newNode行实际上并没有将node设置为newNode。我怀疑这可能与JavaScript的按值传递特性有关，但我不能完全确定。
我哪里错了？
此外，如果可能的话，我希望现在可以保留这种递归形式。
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-06-20 04:53:03
基本上，您需要将对象引用移交给递归函数，因为如果不这样做，您将创建新节点而不链接到根节点。
这段代码将对象和方向作为键，并检查要做出的四个不同决策。如果必须分配新节点，则使用对象和键。
如果值小于或大于节点的值，则将节点与新方向一起用于检查。
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
this.add = function (value) {
function check(node, direction) {
if (node[direction] === null) {
node[direction] = new Node(value);
console.log('new node', value);
return;
}
if (node[direction].value === value) {
console.log('equal value', value);
return;
}
if (node[direction].value > value) {
console.log('go left', node[direction].value);
check(node[direction], 'left');
return;
}
if (node[direction].value < value) {
console.log('go right', node[direction].value);
check(node[direction], 'right');
}
}
check(this, 'root');
};
}
var tree = new BinarySearchTree;
tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);
console.log(tree);.as-console-wrapper { max-height: 100% !important; top: 0; }
使用默认节点的一种更短的方法。
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function BinarySearchTree() {
this.root = null;
this.add = function (value) {
function check(node) {
if (node.value === value) {
return;
}
if (node.value > value) {
check(node.left = node.left || new Node(value));
return;
}
if (node.value < value) {
check(node.right = node.right || new Node(value));
}
}
check(this.root = this.root || new Node(value));
};
}
var tree = new BinarySearchTree;
tree.add(10);
tree.add(5);
tree.add(15);
tree.add(2);
tree.add(4);
tree.add(11);
console.log(tree);.as-console-wrapper { max-height: 100% !important; top: 0; }
更改对象与属性的小示例
function assign(o) { // take object reference as value of o
o = { bar: 43 }; // assign a new value to o, object keeps it value
console.log('o', o); // the reference to object is replaced by an own object
}
function change(o) { // take object reference as value of o
o.bar = 41; // take object reference and assign a new property
console.log('o', o); // because of the object reference, o and object has changed
}
var object = { foo: 42 };
console.log('object', object);
assign(object);
console.log('object', object);
change(object);
console.log('object', object);.as-console-wrapper { max-height: 100% !important; top: 0; }
Stack Overflow用户
发布于 2018-06-20 04:13:23
问题是您需要将节点或node.left设置为节点，而不是newNode = newNode。否则，就没有引用的链接，您的root将永远不会有任何子代。
因此，如果right.next或left.next为null，那么您的插入操作实际上应该在这里完成，而不是在下一次递归时执行。
else if(elem > node.value){
console.log("go right");
if (node.right == null)
node.right = new Node(elem);
else
recurInsert(elem, node.right);
}
else{
console.log("go left");
if (node.left == null)
node.left = new Node(elem);
else
recurInsert(elem, node.left);
}您还可以删除整个if (node == null) { ... }部分，只需在启动之前检查一次根是否为null
if (root == null) {
root = new Node(insertElem);
return null;
}下面是完整的代码：
function Node(value) {
this.value = value;
this.right = null;
this.left = null;
}
function BinarySearchTree() {
this.root = null;
this.add = function(value) {
if (this.root == null) {
this.root = new Node(value);
return;
}
var recInsert = function(value, node) {
if (value == node.value) {
print("equal");
return;
}
if (value < node.value) {
if (node.left == null)
node.left = new Node(value);
else
recInsert(value, node.left);
}
else {
if (node.right == null)
node.right = new Node(value);
else
recInsert(value, node.right);
}
}
recInsert(value, this.root);
}
this.print = function() {
if (this.root != null) {
var rec = function(node) {
if (node == null)
return;
rec(node.left);
print(node.value);
rec(node.right);
}
rec(this.root);
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50936044
复制相关文章
相似问题