我需要使用 JavaScript 创建自定义树数据结构
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17750650/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
I need to create a custom tree data-structure using JavaScript
提问by mathacka
I looked up this basic format for a tree structure in javascript:
我在 javascript 中查找了树结构的基本格式：
function Tree(parent, child, data) {
this.parent = parent;
this.children = child || [];
this.data = data;
this.addNode ...
this.addChild ...
}
the problem I have is making a tree that is "long" with this. The data I'm using is a list of streets on a trail that is almost one straight path, but there are a couple of small splits in the trail, the data would look something like:
我的问题是制作一棵“长”的树。我使用的数据是一条几乎是一条直线的小径上的街道列表，但小径中有几个小裂缝，数据看起来像：
A ->
B ->
C ->
D -> E,F
E ->
G ->
H
F -> I
I -> J
J -> K,L
K ->
M ->
N
L -> O
O -> P
I'd like to avoid code that looks like:
我想避免看起来像这样的代码：
tree.children[0].children[0].children[0].addNode("E");
tree.children[0].children[0].children[0].push("F");
so one of my questions is how to traverse the tree, simply by saying?
所以我的问题之一是如何遍历树，简单地说？
node = tree;
while(node.children != null)
node = node.children[0];
if you could help me out, I'd appreciate it, thanks,
如果你能帮助我，我将不胜感激，谢谢
mathacka
马塔卡
回答by Mongolojdo
The most managable approach for this structure is IMHO to use linked lists.
这种结构最易于管理的方法是恕我直言，使用链表。
function Node(parentNode)
{
this.Parent=parentNode;
this.FirstChild=null;
this.LastChild=null;
this.PreviousSibling=null;
this.NextSibling=null;
}
Node.prototype.AddChild=function(child)
{
child.Parent = this;
child.PreviousSibling = this.LastChild;
if (this.LastChild != null)
this.LastChild.NextSibling = child;
this.LastChild = child;
if (this.FirstChild == null)
this.FirstChild = child;
}
To loop through children, do something like this:
要循环遍历子项，请执行以下操作：
function GetChildren(node)
{
var result=new Array();
var child=node.FirstChild;
while(child)
{
result.push(child);
child=child.NextSibling;
}
return result;
}
(edit) The "Node"-object is just an example and it should have meaningful properties added to it. Using this as a base for all objects in your tree, it may have any depth without making it more complex. You can add more functions, like GetChildByName, RemoveChild, and so on.
（编辑）“节点”对象只是一个例子，它应该添加有意义的属性。使用它作为树中所有对象的基础，它可以具有任何深度而不会使其更复杂。您可以添加更多函数，例如 GetChildByName、RemoveChild 等。
回答by Vivex
var Tree = function () {
Tree.obj = {};
return Tree;
};
// Parent Will be object
Tree.AddChild = function (parent, child) {
if (parent === null) {
if (Tree.obj.hasOwnProperty(child)) {
return Tree.obj[child];
} else {
Tree.obj[child] = {};
return Tree.obj[child];
}
} else {
parent[child] = {};
return parent[child];
}
};
// Uses
// Inserting -
var t = Tree();
var twoDoor = t.AddChild(null, "2 Door");
var fdoor = t.AddChild(null, "4 Door");
t.AddChild(fdoor, "manual");
t.AddChild(twoDoor, "automatic");
var man = t.AddChild(twoDoor, "manual");
t.AddChild(man, "Extended Cab");
console.log(t.obj);回答by Smrchy
Have a look at this approach on how to create tree structures from SQL queries:
看看这个关于如何从 SQL 查询创建树结构的方法：
http://blog.tcs.de/creating-trees-from-sql-queries-in-javascript/
http://blog.tcs.de/creating-trees-from-sql-queries-in-javascript/
回答by Splendiferous
If you want to do some calculation at every node in the tree then you could add a traversefunction to your tree nodes, something like:
如果您想对树中的每个节点进行一些计算，那么您可以traverse向树节点添加一个函数，例如：
Tree.prototype.traverse = function( operation ){
// call the operation function and pass in the current node
operation( this )
// call traverse on every child of this node
for( var i=0; i<this.children.length; i++ )
this.children[i].traverse( operation )
}
// an example operation that finds all the leaf nodes
var leaves = []
myTree.traverse( function( node ){
if( !node.children.length )
leaves.push(node)
}
Alternatively if you're doing something more specific such as manipulating the tree or finding a particular node then you may want to look at the Visitor Design Pattern.
或者，如果您正在做一些更具体的事情，例如操作树或查找特定节点，那么您可能需要查看访问者设计模式。
