我正在创建一个程序来表示 javascript 中的二叉搜索树。我想要的是一种创建公共树节点的方法,其中 ptrs(left, right) 都为空。这是我写的代码:
var BST = function(data) {
if (data === null || data === undefined){
this.data = null;
this.left = null;
this.right = null;
}
else{
this.data = data;
this.left = new BST(null);
this.right = new BST(null);
}
};
BST.prototype.insert = function(data) {
if (this.data === null){
this.data = data;
this.left = new BST(null);
this.right = new BST(null);
}
else if (data < this.data)
this.left.insert(data);
else if (data > this.data)
this.right.insert(data);
};
BST.prototype.inOrder = function(func) {
if (this.data !== null) {
this.left.inOrder(func);
func(this.data);
this.right.inOrder(func);
}
};
在这里,我想为所有空指针分配一个空节点(如if(data === null || data === undefined)
条件中所定义)。但是对于每个空节点,我必须创建一个代表相同数据的新节点。有没有办法分配给空节点的公共实例?
我使用空节点而不是仅仅使用的原因
else{
this.data = data;
this.left = null;
this.right = null;
}
是在调用该inOrder
方法时,在到达带有 的节点时left or right = null
,它会给出 aTypeError
因为它试图运行 null.inOrder(func);
,因为它this.left
转换为null
。
解决这个问题的方法是修改inOrder
函数,这将导致每个语句周围出现许多条件,即不是一个非常优雅的实现。
我也可以inOrder
在对象的原型之外定义,并使其以树作为参数,即inOder(tree,func)
,但我不想这样做。
此外,作为对代码的第二个改进,请考虑该insert
方法;在这种 null
情况下:
if (this.data === null){
this.data = data;
this.left = new BST(null);
this.right = new BST(null);
}
因为无论如何我都必须覆盖每个条目,所以我想通过执行以下操作来将此节点完全重新分配给一个新树:
if (this.data === null)
this = new BST(data);
我知道这对前者来说效率较低,但它仍然更加简洁。那么有什么办法吗?