我需要使用JavaScript创建

Question

我在JavaScript抬头这一基本格式树结构的自定义树数据结构：

function Tree(parent, child, data) { 
    this.parent = parent; 
    this.children = child || []; 
    this.data = data; 
    this.addNode ... 
    this.addChild ... 
} 

我正在一棵树就是“长”这个问题。我使用的数据是在步道的街道名单，这几乎是一条直线路径，但也有几个小劈叉的踪迹，该数据会看起来像：

A -> 
B -> 
C -> 
D -> E,F 
E -> 
G -> 
H  
F -> I 
I -> J 
J -> K,L 
K -> 
M -> 
N 
L -> O 
O -> P 

我会想避免代码看起来像：

tree.children[0].children[0].children[0].addNode("E"); 
tree.children[0].children[0].children[0].push("F"); 

所以我的问题之一是如何遍历树，简单地说？

node = tree; 
while(node.children != null) 
    node = node.children[0]; 

，如果你能帮助我，我会很感激，感谢，

mathacka

Answer 1

这个结构最可管理的方法是恕我直言，使用链表。

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; 
} 

要遍历的孩子，做这样的事情：

function GetChildren(node) 
{ 
    var result=new Array(); 
    var child=node.FirstChild; 
    while(child) 
    { 
     result.push(child); 
     child=child.NextSibling; 
    } 
    return result; 
} 

（编辑）的“节点” -object仅仅是一个例子，它应该有有意义的特性添加到它。使用它作为树中所有对象的基础，它可以具有任何深度而不会更复杂。您可以添加更多功能，如GetChildByName，RemoveChild等。

Answer 2

如果你想在树中的每个节点做一些计算，那么你可以添加一个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) 
} 

或者如果你正在做更具体的事情，如操纵树或查找特定那么你可能想看看Visitor Design Pattern。

Answer 3

看一看如何从SQL查询创建的树结构这种方法：

http://blog.tcs.de/creating-trees-from-sql-queries-in-javascript/

Answer 4

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