数据结构树

文章来源
*https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393 *

节点

• data存储一个值
• parent指向节点的父节点
• children只想列表中的下一个节点

树

• _root指向树的根节点
• traverseDF(callback)用DFS遍历树的节点
• traverseBF(callback)用BFS遍历树的节点
• contains(date,traversal)搜索树中的节点
• add(date,toData,traverse)将一个节点添加到树中
• remove（child,parent）删除树中的一个节点

节点的属性

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

树的属性

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

树的方法

traverseDF(callback)

Tree.prototype.traverseDF = function(callback){ //下面是一个立即执行函数表达式IIFE (function recurse(currentNode) { for (var i=0,length=currentNode.children,length;i<length;i++) { recurse(currentNode.children[i] } callback(currentNode); })(this._root); }

traverseBF(callback)

Tree.prototype.traverseBF = fucntion(callback) { var queue = new Queue(); queue.enqueue(this._root); currentTree = queue.dequeue(); while(currentTree) { for (var i = 0,length = currentTree.children.length;i<length;i++) { queue.enqueue(currentTree.children[i]); } callback(currentTree); currentTree = queue.dequeue(); } }

contains(callback,traversal)

Tree.prototype.contains = function(callback,traversal) { traversal.call(this,callback); }

tree.contains(function(node) { if (node.data == "two") { console.log(node); } }

add(data,toData,traversal)

Tree.prototype.add = function(data,toData,traversal) { var child = neew Node(data), parent = nul, callback = function(node){ if (node.data === toData) { parent = node; } } this.contains(callback,traversal); if (parent) { parent.children.push(child); child.parent = parent; } else { throw new Error("Cannot add node to a non-existent parent.'); } }

var tree = new Tree("CEO");
tree.add('Vp of Happiness','CEO',tree.traverseBF);

remove(data,formData,traversal)

Tree.prototype.remove = function(data,fromData,traversal) { var tree = this, parent = null, childToRemove = null, index; var callback = function(node) { if (node.data === fromData) { parent = node; } }; this.contains(callback,traversal); if (parent) { index = findIndex(parent.children,data); if (index === undefined) { throw new Error("Node to remove does not exist.") } else { childToRemove = parent.children.splice(index,1); } } else { throw new Error ("Parent does not exist.") } return childToRemove; }

辅助函数findIndex(arr,data)

function findIndex(arr,data) { var index; for (var i = 0 ;i<arr.length;i++) { if (arr[i].data === data) { index = i; } } }