我需要使用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);