6

JavaScript の一般的なツリー (ノードには複数の子がある場合があります) の実装を知っている人はいますか?

少なくともこれらのことができるはずです。

  1. 親ノードを取得します。
  2. 子ノードを取得します。
  3. すべての子孫を取得します。
  4. すべての子孫を削除します。
  5. 子ノードを削除します。

Adjacency List Model に似た実装。

背景: Web ページに JavaScript ベースの階層データを保存する必要がありましたが、一般的なツリーの適切な JavaScript 実装が見つからなかったため、隣接リスト モデルと php を使用して階層データをデータベースに保存するために ajax を使用しました。この問題は、ユーザーが同じページを同じブラウザの 2 つのタブで開いているか、2 つの異なるブラウザでページを開いたときに発生します。これは、両方のインスタンスが同じテーブルから読み取って同じテーブルに書き込みを行っているためです。私の質問に答えます。

編集: パフォーマンスは、いつでも私の制約ではありません.50を超えるエントリはありません.

4

2 に答える 2

9

これを試すことができます: https://github.com/afiore/arboreal

またはこれ: https://github.com/mauriciosantos/buckets/ (Binary Searched Trees のみですが、他のデータ構造も同様です)

より洗練されたものが必要な場合は、独自のライブラリ (または記述したすべてのメソッドを含む少なくとも 1 つのオブジェクト) を作成する必要があります。

編集：

これは、ツリー機能を実現するための私の簡単なコードです。すべての子孫を削除し、すべての子を削除することは、実際には同じです...だから：

function Node(value) {

    this.value = value;
    this.children = [];
    this.parent = null;

    this.setParentNode = function(node) {
        this.parent = node;
    }

    this.getParentNode = function() {
        return this.parent;
    }

    this.addChild = function(node) {
        node.setParentNode(this);
        this.children[this.children.length] = node;
    }

    this.getChildren = function() {
        return this.children;
    }

    this.removeChildren = function() {
        this.children = [];
    }
}

var root = new Node('root');
root.addChild(new Node('child 0'));
root.addChild(new Node('child 1'));
var children = root.getChildren();
for(var i = 0; i < children.length; i++) {
    for(var j = 0; j < 5; j++) {
        children[i].addChild(new Node('second level child ' + j));
    }
}
console.log(root);
children[0].removeChildren();
console.log(root);
console.log(root.getParentNode());
console.log(children[1].getParentNode());

Chrome (またはコンソールをサポートする他のブラウザー) で実行します。

于 2012-08-20T12:42:25.453 に答える
3

あなたは「ジェネリックツリー」と言いましたが、あなたの特定の要件は、すでに組み込まれてDOMParserいる.

私は他のプログラマーの意見を尊重しますが、それでもDOM、試してみて、自分に合っているかどうかを確認できると思います。

これがどのように機能するかについての簡単な図は次のとおりです。

var tXML="<root><fruit><name>apple</name><color>red</color></fruit><fruit><name>pear</name><color>yellow</color></fruit></root>";
var tree=(new DOMParser).parseFromString(tXML,"text/xml");
//get descendants
var childs=tree.documentElement.childNodes;
for(var i=0;i<childs.length;i++)
{
 if(childs[i].nodeName=="fruit")
 {
  document.write(childs[i].getElementsByTagName("name")[0].textContent);
  document.write(": ");
  document.write(childs[i].getElementsByTagName("color")[0].textContent);
  document.write("<br />");
 }
}
//get child node
var appl=tree.documentElement.getElementsByTagName("fruit")[0];
document.write(appl.getElementsByTagName("name")[0].textContent+"<br />");
//get parent node
document.write(appl.parentNode.nodeName);
document.write("<br />");
//remove child node
if(tree.documentElement.getElementsByTagName("color").length>1)
{
 var clr=tree.documentElement.getElementsByTagName("color")[1];
 clr.parentNode.removeChild(clr);
}
document.write("<textarea>"+(new XMLSerializer).serializeToString(tree)+"</textarea><br />");
//remove descendants
while(tree.documentElement.childNodes.length>0)
{
 tree.documentElement.removeChild(tree.documentElement.childNodes[0]);
}
document.write("<textarea>"+(new XMLSerializer).serializeToString(tree)+"</textarea>");

これらの長い関数名を「簡略化」していないので、より良いアイデアが得られるかもしれません。

于 2012-08-21T05:18:06.683 に答える