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);

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！