文章关键点
1. 树的建立
2. 深度遍历和广度遍历
3.callback回调函数
4. 遍历方式查找添加删除等接口
1.树的建立
一个节点有三个部分组成
-
data存储数据 -
parent指向的父节点 -
children孩子节点
function Node(data){
this.data = data;
this.parent = null;
this.children = [ ];
}
function Tree(node){
var node = new Node(data);
this._root = node;
}
var tree = new Tree('CEO');
// {data: 'CEO', parent: null, children: []}
tree._root;
2.(a) 深度遍历（DSF）
Tree.prototype.traverseDF = function (callback) {
(function recurse(currentNode) {
for(let i=0;i<currentNode.children.length;i++){
recurse(currentNode.children[i]);
}
callback(currentNode);
})(this._root);
}
eg:
var tree = new Tree('one');
tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;
tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;
tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;
tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];
tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];
tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];
/*
creates this tree
one
├── two
│ ├── five
│ └── six
├── three
└── four
└── seven
*/
2.(b)广度遍历（利用queue）
Tree.prototype.traverseBF = function (callback) {
var queue = new Queue();
queue.enqueue(this._root);
var currentTree = queue.dequeue();
while(currentTree){
for(let i =0;i<currentTree.children.length;i++){
queue.enqueue(currentTree.children[i]);
}
callback(currentTree);
currentTree = queue.dequeue();
}
}
callback
默认为一个函数，使得在函数内能调用其它函数
tree.traverseDF(function(node) {
console.log(node.data)
});
/*
logs the following strings to the console
'five'
'six'
'two'
'three'
'seven'
'four'
'one'
*/
- 遍历方式查找添加删除等接口
a.遍历方式
Tree.prototype.contains = function (callback,traversal) {
traversal.call(this,callback);
}
eg:
//tree is an example of a root node
tree.contains(function(node){
if (node.data === 'two') {
console.log(node);
}
}, tree.traverseBF);
b.查找
// tree is an example of a root node
tree.contains(function(node){
if (node.data === 'two') {
console.log(node);
}
}, tree.traverseBF);
c.添加
Tree.prototype.add = function(data, toData, traversal) {
var child = new Node(data),
parent = null,
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.');
}
};
eg:
var tree = new Tree('CEO');
tree.add('VP of Happiness', 'CEO', tree.traverseBF);
/*
our tree
'CEO'
└── 'VP of Happiness'
*/
d.删除
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;
};