javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】 本文实例讲述了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.zwyuanma.com/code/HtmlJsRun测试运行效果如下： 感兴趣的朋友可以自己测试一下看看运行效果。 更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》 希望本文所述对大家JavaScript程序设计有所帮助。