javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】

前端之家收集整理的这篇文章主要介绍了javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

本文实例讲述了javascript数据结构之多叉树经典操作。分享给大家供大家参考,具体如下:

多叉树可以实现复杂的数据结构的存储,通过遍历方法可以方便高效的查找数据,提高查找的效率,同时方便管理节点数据。javascript的DOM其实就是以多叉树的形式存储的。下面用javascript来实现多叉树的数据结构

1、创造一个节点

数据是以节点的形式存储的:

2、创造树

树用来连接节点,就像真实世界树的主干一样,延伸着很多分支

3、添加一个节点

添加到根节点 // 返回值为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、深度优先遍历

深度优先会尽量先从子节点查找,子节点查找完再从兄弟节点查找,适合数据深度比较大的情况,如文件目录

函数返回值决定是否在找到第一个后继续查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子节点置于堆栈最前头,下次查找就会先查找子节点 stack.unshift(...currentNode.children); currentNode = stack.shift(); } } }

5、广度优先遍历

广度优先遍历会优先查找兄弟节点,一层层往下找,适合子项较多情况,如公司岗位级别

函数返回值决定是否在找到第一个后继续查找 found = callback(currentNode) === true ? true : false; if (!found) { // 每次把子节点置于队列最后,下次查找就会先查找兄弟节点 queue.push(...currentNode.children) currentNode = queue.shift(); } } }

6、包含节点

回调函数算法可自己根据情况实现,灵活度较高

7、移除节点

_findIndex实现:

完整算法

控制台测试代码

这里使用在线HTML/CSS/JavaScript代码运行工具:测试运行效果如下:

感兴趣的朋友可以自己测试一下看看运行效果。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《》、《》、《》、《》、《》及《错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

猜你在找的JavaScript相关文章