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.jb51.net/code/HtmlJsRun测试运行效果如下：

感谢各位的阅读！关于“javascript数据结构之多叉树经典操作的示例分析”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！