admin管理员组

文章数量:1296440

How would I go about creating a tree-like data structure in JS, where, I can have access to things like reference to parent node, id based node lookup, having access to length (number) of children nodes, index based lookup etc?

this is basically the API I am envisioning:

var rootNode = DataStructure.getRoot();
var child1 = rootNode.addNode('child1'); //added a node with id 'child1'
child1.addNode('innerChild1');
child1.addNode('innerChild2');
rootNode.getChildById('child1') //should be same node as var child1
rootNode.getAtIndex(0) //should be same node as var child1
child1.parent() //should be rootNode
child1.getAtIndex(0) // should be node with id 'innerChild1'
child1.getAtIndex(1) // should be node with id 'innerChild2'
child1.length() //should be 2 

etc..

I understand its a broad question, but I wonder if anyone could remend a way to approach this and/or any libraries that might be doing it already? Should i just dynamically create an XML and work with its native methods? Would that be the fastest ?

How would I go about creating a tree-like data structure in JS, where, I can have access to things like reference to parent node, id based node lookup, having access to length (number) of children nodes, index based lookup etc?

this is basically the API I am envisioning:

var rootNode = DataStructure.getRoot();
var child1 = rootNode.addNode('child1'); //added a node with id 'child1'
child1.addNode('innerChild1');
child1.addNode('innerChild2');
rootNode.getChildById('child1') //should be same node as var child1
rootNode.getAtIndex(0) //should be same node as var child1
child1.parent() //should be rootNode
child1.getAtIndex(0) // should be node with id 'innerChild1'
child1.getAtIndex(1) // should be node with id 'innerChild2'
child1.length() //should be 2 

etc..

I understand its a broad question, but I wonder if anyone could remend a way to approach this and/or any libraries that might be doing it already? Should i just dynamically create an XML and work with its native methods? Would that be the fastest ?

• javascript
• arrays
• json
• oop
• data-structures

Share Follow edited Apr 10, 2015 at 21:35 nuway asked Apr 10, 2015 at 21:10 nuwaynuway 2,38455 gold badges2929 silver badges4949 bronze badges 6

• I think you want jQuery? – KJ Price Commented Apr 10, 2015 at 21:11
• why jQuery? i want a data structure, its not DOM specific – nuway Commented Apr 10, 2015 at 21:14
• It seems like what you need is a Binary Search Tree Check This Out – nem035 Commented Apr 10, 2015 at 21:31
• Should getAtIndex correspond to the sorted order of the nodes or the order in which they were added? – Sildoreth Commented Apr 16, 2015 at 22:09
• 1 Do you want a global lookup by id or only within a single parent node? – Ja͢ck Commented Apr 17, 2015 at 3:11

 |  Show 1 more ment

2 Answers 2

Sorted by: Reset to default 5 +25

The data structure you described can be easily implemented as follows:

var Tree = defclass({
    constructor: function (parent) {
        this.parent   = parent || null; // null for root node
        this.children = {};             // for id based lookup
        this.ids      = [];             // for index based lookup
        this.length   = 0;              // for ease of access
    },
    addNode: function (id) {
        var children = this.children;
        if (children.hasOwnProperty(id)) throw new Error(id + " exists");
        return children[this.ids[this.length++] = id] = new Tree(this);
    },
    getChildById: function (id) {
        var children = this.children;
        if (children.hasOwnProperty(id)) return children[id];
        throw new Error(id + " does not exist");
    },
    getAtIndex: function (index) {
        return this.getChildById(this.ids[index]);
    }
});

function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

<script>
    setTimeout(function () {
        var rootNode    = new Tree;
        var child1      = rootNode.addNode("child1");
        var innerChild1 = child1.addNode("innerChild1");
        var innerChild2 = child1.addNode("innerChild2");

        console.assert(rootNode.getChildById("child1") === child1);
        console.assert(rootNode.getAtIndex(0)          === child1);
        console.assert(child1.parent                   === rootNode);
        console.assert(child1.getAtIndex(0)            === innerChild1);
        console.assert(child1.getAtIndex(1)            === innerChild2);
        console.assert(child1.length                   === 2);

        alert("success");
    }, 0);
</script>

Both id based lookups and index based lookups take constant (i.e. O(1)) time. Hope that helps.

I have a structure like this in an app. The API specified would make it difficult to create a structure like you want. Here are some things I noticed: DataStructure is a singleton, addChild doesn't allow you to add a node with children, and indexes are numbers. How about the following?

API

TreeNode (newable)

Members:

• children (Object, indexed on ID)
• root (TreeNode)
• parent (TreeNode)
• index (String)
• attributes (Object)
• _referenceCount (int) - useful if your tree has cycles for some reason

Methods:

• addChild(TreeNode: treeNode)
  • Register the node with the parent
  • Adds the node by ID to children
  • Increments reference count of added TreeNode
• forEach(callback(TreeNode: treeNode))
• removeChild(String: id)
  • Removes node from this Object
  • Decrement _referenceCount of the indicated child
  • Removes it from the root if _referenceCount is 0

Tree (extends TreeNode) (newable)

Members:

• _nodeMap (Object)

Methods:

• getNodeByID(String: id)
  • looks up id in _nodeMap, O(1) lookup time
• removeNode(String: id)
• addToNodeMap(TreeNode: treeNode)

treeFactory (optional)

Methods:

• createFromFormatX(Object: a tree of stuff in some specific format) The tree works fine, you should create a factory for your specific case that helps you transform a blob into your fancy data structure.
• createFromFormatY, basically another loader mechanism

Potential Immutability

Nothing here is immutable necessarily. You could however, via use of a new factory method and make more of the above methods private always force immutability of the tree. This may or may not be desirable.

本文标签： javascriptTreelike data structure in JS that allows for fastest node lookupStack Overflow