Shulou(Shulou.com)05/31 Report--

这篇文章主要讲解了"javascript数据结构之多叉树怎么实现"，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习"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); 运行效果如下：

Thank you for reading, the above is "javascript data structure of the multi-fork tree how to achieve" the content, after learning this article, I believe we have a deeper understanding of the javascript data structure of the multi-fork tree how to achieve this problem, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.