2

我正在创建一个程序来表示 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);

我知道这对前者来说效率较低,但它仍然更加简洁。那么有什么办法吗?

4

2 回答 2

1

是的,在这种情况下,您可以使用常量实例,因为所有空节点都是相同的并且没有不同的引用(如“父”属性)。要创建这样一个常量,您需要一个存储它的地方;可以是(私有)变量或类似的东西

BST.emptyleaf = new BST(null);

你也可以使用单例模式:

function BST(data) {
    if (data === null || data === undefined) {
        if (BST.emptyleaf)
            return BST.emptyleaf; // singleton instance if available
        this.data  = null;
        this.left  = null;
        this.right = null;
        BST.emptyleaf = this; // else create it for re-use
    } else {
        this.data  = data;
        this.left  = new BST(null);
        this.right = new BST(null);
    }
}
于 2012-04-17T18:32:40.477 回答
1

但是对于每个空节点,我必须创建一个代表相同数据的新节点。有没有办法分配给空节点的公共实例?

是的,但这会破坏你的代码。想一想:当您insert在该节点实例上调用该方法时会发生什么?...

至于第二个问题,您无法使用当前模型对其进行优化。没有就地对象替换之类的东西(在 C# 中有)。

我认为您当前的代码还可以,尽管我个人会坚持使用更简单的模型,例如

var BST = function(data) {
    this.insert(data);
};

BST.prototype.insert = function(data) {
    if (typeof this.data == 'undefined') {
        this.data = data;
    } else if (data < this.data) {
        if (!this.left) {
            this.left = new BST();
        }
        this.left.insert(data);
    } else if (data > this.data) {
        if (!this.right) {
            this.right = new BST();
        }
        this.right.insert(data);
    }
};

BST.prototype.inOrder = function(func) {
    if (typeof this.data != 'undefined') {
        this.left && this.left.inOrder(func);
        func(this.data);
        this.right && this.right.inOrder(func);
    }
};

请注意,这完全消除了对 a 的需要nullNode,因为 - 嘿!undefined- 它是 JavaScript,所以为什么不使用动态对象扩展等美妙的东西。

于 2012-04-17T20:17:27.393 回答