在Javascript中实现通用树结构

Question

在Javascript中实现通用树结构

javascripttree

7

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

它应该能够至少实现以下功能：

获取父节点。
获取子节点。
获取所有后代。
删除所有后代。
删除子节点。

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

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

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

- wh0

你是否在寻找类似于这个的东西.. http://www.jstree.com/ - Ruwantha

@RJ45与外观无关，它与分层数据存储有关。 - wh0

听起来像是一个简单的XML结构......你考虑过使用window.DOMParser() W3School吗？ - Passerby

@路人甲谢谢您之前提出的建议，这是我以前不知道的。我正在查看那些页面，但并没有太多信息，即使谷歌搜索几分钟也没有找到太多信息......请问您能否指导我一些实际上展示如何添加删除XML字符串条目的页面？ - wh0

1

请不要建议使用DOM。从API的角度来看，DOM对于访问普通树结构来说相当丑陋。 - Joachim Sauer

显示剩余3条评论

2个回答

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

我没有“简化”这些冗长的函数名称，这样你可能会更好地理解。

- Passerby

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Karol · Accepted Answer

您可以尝试这个：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（或其他支持控制台的浏览器）中运行它。