javascript数据结构之多叉树经典操作的示例分析
短信预约 -IT技能 免费直播动态提醒
这篇文章给大家分享的是有关javascript数据结构之多叉树经典操作的示例分析的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
多叉树可以实现复杂的数据结构的存储，通过遍历方法可以方便高效的查找数据，提高查找的效率，同时方便管理节点数据。javascript的DOM其实就是以多叉树的形式存储的。下面用javascript来实现多叉树的数据结构
1、创造一个节点
数据是以节点的形式存储的：
class Node {
constructor(data) {
this.data = data;
this.parent = null;
this.children = [];
}
}2、创造树
树用来连接节点，就像真实世界树的主干一样，延伸着很多分支
class MultiwayTree {
constructor() {
this._root = null;
}
}3、添加一个节点
function add(data, toData, traversal) {
let node = new Node(data)
// 第一次添加到根节点
// 返回值为this，便于链式添加节点
if (this._root === null) {
this._root = node;
return this;
}
let parent = null,
callback = function(node) {
if (node.data === toData) {
parent = node;
return true;
}
};
// 根据遍历方法查找父节点（遍历方法后面会讲到），然后把节点添加到父节点
// 的children数组里
// 查找方法contains后面会讲到
this.contains(callback, traversal);
if (parent) {
parent.children.push(node);
node.parent = parent;
return this;
} else {
throw new Error('Cannot add node to a non-existent parent.');
}
}4、深度优先遍历
深度优先会尽量先从子节点查找，子节点查找完再从兄弟节点查找，适合数据深度比较大的情况，如文件目录
function traverseDF(callback) {
let stack = [], found = false;
stack.unshift(this._root);
let currentNode = stack.shift();
while(!found && currentNode) {
// 根据回调函数返回值决定是否在找到第一个后继续查找
found = callback(currentNode) === true ? true : false;
if (!found) {
// 每次把子节点置于堆栈最前头，下次查找就会先查找子节点
stack.unshift(...currentNode.children);
currentNode = stack.shift();
}
}
}5、广度优先遍历
广度优先遍历会优先查找兄弟节点，一层层往下找，适合子项较多情况，如公司岗位级别
function traverseBF(callback) {
let queue = [], found = false;
queue.push(this._root);
let currentNode = queue.shift();
while(!found && currentNode) {
// 根据回调函数返回值决定是否在找到第一个后继续查找
found = callback(currentNode) === true ? true : false;
if (!found) {
// 每次把子节点置于队列最后，下次查找就会先查找兄弟节点
queue.push(...currentNode.children)
currentNode = queue.shift();
}
}
}6、包含节点
function contains(callback, traversal) {
traversal.call(this, callback);
}回调函数算法可自己根据情况实现，灵活度较高
7、移除节点
// 返回被移除的节点
function remove(data, fromData, traversal) {
let parent = null,
childToRemove = null,
callback = function(node) {
if (node.data === fromData) {
parent = node;
return true;
}
};
this.contains(callback, traversal);
if (parent) {
let index = this._findIndex(parent.children, data);
if (index < 0) {
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实现:
function _findIndex(arr, data) {
let index = -1;
for (let i = 0, len = arr.length; i < len; i++) {
if (arr[i].data === data) {
index = i;
break;
}
}
return index;
}完整算法
class Node {
constructor(data) {
this.data = data;
this.parent = null;
this.children = [];
}
}
class MultiwayTree {
constructor() {
this._root = null;
}
//深度优先遍历
traverseDF(callback) {
let stack = [], found = false;
stack.unshift(this._root);
let currentNode = stack.shift();
while(!found && currentNode) {
found = callback(currentNode) === true ? true : false;
if (!found) {
stack.unshift(...currentNode.children);
currentNode = stack.shift();
}
}
}
//广度优先遍历
traverseBF(callback) {
let queue = [], found = false;
queue.push(this._root);
let currentNode = queue.shift();
while(!found && currentNode) {
found = callback(currentNode) === true ? true : false;
if (!found) {
queue.push(...currentNode.children)
currentNode = queue.shift();
}
}
}
contains(callback, traversal) {
traversal.call(this, callback);
}
add(data, toData, traversal) {
let node = new Node(data)
if (this._root === null) {
this._root = node;
return this;
}
let parent = null,
callback = function(node) {
if (node.data === toData) {
parent = node;
return true;
}
};
this.contains(callback, traversal);
if (parent) {
parent.children.push(node);
node.parent = parent;
return this;
} else {
throw new Error('Cannot add node to a non-existent parent.');
}
}
remove(data, fromData, traversal) {
let parent = null,
childToRemove = null,
callback = function(node) {
if (node.data === fromData) {
parent = node;
return true;
}
};
this.contains(callback, traversal);
if (parent) {
let index = this._findIndex(parent.children, data);
if (index < 0) {
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) {
let index = -1;
for (let i = 0, len = arr.length; i < len; i++) {
if (arr[i].data === data) {
index = i;
break;
}
}
return index;
}
}控制台测试代码
var tree = new MultiwayTree();
tree.add('a')
.add('b', 'a', tree.traverseBF)
.add('c', 'a', tree.traverseBF)
.add('d', 'a', tree.traverseBF)
.add('e', 'b', tree.traverseBF)
.add('f', 'b', tree.traverseBF)
.add('g', 'c', tree.traverseBF)
.add('h', 'c', tree.traverseBF)
.add('i', 'd', tree.traverseBF);
console.group('traverseDF');
tree.traverseDF(function(node) {
console.log(node.data);
});
console.groupEnd('traverseDF');
console.group('traverseBF');
tree.traverseBF(function(node) {
console.log(node.data);
});
console.groupEnd('traverseBF');
// 深度优先查找
console.group('contains1');
tree.contains(function(node) {
console.log(node.data);
if (node.data === 'f') {
return true;
}
}, tree.traverseDF);
console.groupEnd('contains1')
// 广度优先查找
console.group('contains2');
tree.contains(function(node) {
console.log(node.data);
if (node.data === 'f') {
return true;
}
}, tree.traverseBF);
console.groupEnd('contains2');
tree.remove('g', 'c', tree.traverseBF);这里使用在线HTML/CSS/JavaScript代码运行工具：http://tools.jb51.net/code/HtmlJsRun测试运行效果如下：
感谢各位的阅读！关于“javascript数据结构之多叉树经典操作的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
