2

私はjavascriptで二分探索木を表すプログラムを作成しています。私が欲しいのは、両方のptrs（左、右）をnullとして持つ共通のツリーノードを作成する方法です。これは私が書いたコードです： 

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);
    }
};

ここでは、すべてのnullポインターにnullノード（条件で定義されている）を割り当てたいと思いますif(data === null || data === undefined)。ただし、nullノードごとに、同じデータを表す新しいノードを作成する必要があります。nullノードの共通インスタンスに割り当てる方法はありますか？
単に使用する代わりにnullノードを使用する理由

else{
    this.data = data;
    this.left = null;
    this.right = null;
}

メソッドを呼び出すと、inOrderでノードに到達するとleft or right = null、それ以降TypeErrorに実行しようとするため、がに変換されます。 それを回避する方法は、関数を変更することです。これにより、各ステートメントの周りに多くの条件が発生します。つまり、あまり洗練された実装ではありません。オブジェクトのプロトタイプの外部で 定義し、引数としてツリーを使用するようにすることもできますが、それはしたくありません。 null.inOrder(func);this.leftnull
inOrder
inOrderinOder(tree,func)

また、コードの2番目の改善点として、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

はい。この場合、すべてのnullノードが同じであり、異なる参照（「親」プロパティなど）がないため、定数インスタンスを使用できます。このような定数を作成するには、それを保存する場所が必要になります。これは、（プライベート）変数または次のようなもののいずれかです。

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

ただし、nullノードごとに、同じデータを表す新しいノードを作成する必要があります。nullノードの共通インスタンスに割り当てる方法はありますか？

はい、しかしこれはあなたのコードを壊すでしょう。考えてみてくださいinsert。そのノードインスタンスでメソッドを呼び出すとどうなりますか？..。

2番目の問題については、現在のモデルでは最適化できません。インプレースオブジェクト置換などはありません（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);
    }
};

これにより、の必要性が完全になくなることに注意してくださいnullNode。--JavaScriptなのでundefined、動的オブジェクト拡張などのすばらしいものを使用してみませんか。

于 2012-04-17T20:17:27.393 に答える