6

有人知道 JavaScript 的通用树（节点可能有多个子节点）实现吗？

它至少应该能够做这些事情，

  1. 获取父节点。
  2. 获取子节点。
  3. 得到所有的后代。
  4. 删除所有后代。
  5. 删除子节点。

一些类似于邻接列表模型的实现。

背景：我需要为我的网页存储基于 JavaScript 的分层数据我找不到通用树的良好 JavaScript 实现所以我所做的是我使用 ajax 使用邻接列表模型和 php 将分层数据存储到数据库中。当用户在同一浏览器的两个选项卡中打开同一页面或在两个不同的浏览器中打开该页面时，问题就出现了，因为这两个实例都在写入从同一个表读取的同一个表，这导致我遇到任何可能的解决方法回答我的问题。

编辑： 性能在任何时候都不是我的限制，我不会有超过 50 个条目。

4

2 回答 2

9

你可以试试这个：https ://github.com/afiore/arboreal

或者这个：https ://github.com/mauriciosantos/buckets/ （只有二叉搜索树，但还有其他数据结构）

如果您需要更复杂的东西，您将需要编写自己的库（或至少一个包含您所描述的所有方法的对象）。

编辑：

这是我实现树功能的简单代码。删除所有后代并删除所有孩子实际上是相同的......所以：

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 回答