Javascript 中的通用树实现

Generic tree implementation in Javascript

提问by wh0

Is anyone aware of a generic tree (nodes may have multiple children) implementation for JavaScript?

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

It should be able to do atleast these things,

至少应该可以做这些事情，

1. get parent node.
2. get children nodes.
3. get all the descendants.
4. remove all the descendants.
5. remove children nodes.

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

Some implementation similar to Adjacency List Model.

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

Background:I needed JavaScript based hierarchical data storing for my webpage i could not find a good JavaScript implementation of generic trees so what i did is i used ajax to store hierarchical data into database using Adjacency List Model and php. The problem comes when the user is opening the same page in two tabs of same browser or opened the page in two different browsers because both the instances are writing to same table reading from same table which is causing me problems any possible work around for this also answers my question.

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

Edit:Performanceis really not my constraint at any point of time i will not have more than 50 entries.

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

回答by Karol

You can try this: https://github.com/afiore/arboreal

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

Or this: https://github.com/mauriciosantos/buckets/(only Binary Searched Trees, but olso other data structures)

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

If you need anything more sophisticated, you will need to write your own library (or at least one object with all methods you desribed).

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

EDIT:

编辑：

This is my simple code to achieve tree functionality. Remove all descendants and remove all children is in fact the same... so:

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

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

Run it in Chrome (or other browser which supports console).

在 Chrome（或其他支持控制台的浏览器）中运行它。

回答by Passerby

Although you did say "generic tree", what your specific requirementsounds simple enough for an already built-in DOMParser.

尽管您确实说过“通用树”，但您的具体要求对于已经内置的DOMParser.

I respect other programmers' opinions, but still I think you can give DOMa try and see if it fits you.

我尊重其他程序员的意见，但我仍然认为你可以DOM尝试一下，看看它是否适合你。

Here's an simple illustration on how it works:

这是有关其工作原理的简单说明：

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

I didn't "simplified" those long function names, so you may get a better idea.

我没有“简化”那些长函数名，所以你可能会得到一个更好的主意。