JavaScript implements tree structure

使用JavaScript 实现树结构

1.定义节点

function Node(data) {
 	this.data = data
 	this.parent = null
 	this.children = []
}

2.声明树

function Tree(data) {
		var node = new Node(data)
 	this._root = node
}

3.给树添加广度优先的遍历方法

Tree.prototype.traverseBF = function (callback) {
    var queue = [];
    queue.push(this._root);
    currentTree = queue.shift();
    while (currentTree) {
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.push(currentTree.children[i]);
        }
        callback(currentTree);
        currentTree = queue.shift();
    }
};

4.深度优先的遍历方法

Tree.prototype.traverseDF = function (callback) {
    (function recurse(currentNode) {
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        } 
        callback(currentNode);
    })(this._root);
};

5.测试

var tree

let data0 = 1

tree = new Tree(data0)
for (let i = 0; i < 3; i++) {
let data1 = 'r_i_'+i
let node = new Node(data1)
tree._root.children[i] = node
node.parent = tree
for (let j = 0; j < Math.floor(Math.random() *4 + 1); j++) {
let data2 ='r_i_j_'+j
let cnode = new Node(data2)
node.children[j] = cnode
cnode.parent = node
for (let k = 0; k < Math.floor(Math.random() *4 + 1); k++) {
let data3 = 'r_i_j_k_'+k
let sNode = new Node(data3)
cnode.children[k] = sNode
sNode.parent = cnode
}
}
}
tree.traverseDF(function(node){
console.log(node.data)
})

console.log('-----------------------------------') tree.traverseBF(function(node){ console.log(node.data) })