使用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

- jaysonpowers

---

你试过你的代码了吗？ - Evan Davis

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

（编辑）“Node”对象只是一个示例，应该添加有意义的属性。使用此作为树中所有对象的基础，它可以具有任何深度，而不会增加复杂性。您可以添加更多函数，例如GetChildByName，RemoveChild等。

- Mongolojdo

---

我意识到可以将2个子节点放入链表中，你有关于如何遍历多个子节点列表的建议吗？ - jaysonpowers

上面的代码可以让您遍历无限数量的子元素。每个子元素可以有无限数量的孙元素，依此类推。试试看吧。这种代码模式称为链表。 - Mongolojdo

Answer 2

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

- vivex

Answer 3

请看这种方法，如何从SQL查询创建树形结构：

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

- Smrchy

---

你能否添加一份描述，说明链接方法如何解决这个问题？ - Steve Westbrook

Answer 4

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

如果你正在进行更具体的操作，比如操纵树或查找特定节点，那么你可能需要查看访问者设计模式。

- Splendiferous

---

谢谢，我也找到了这个链接：http://www.drdobbs.com/database/ternary-search-trees/184410528 - jaysonpowers