JavaScript树的深度优先遍历和广度优先遍历算法示例
网络 2018-09-18 2727
本文实例讲述了JavaScript树的深度优先遍历和广度优先遍历算法。分享给大家供大家参考，具体如下：
1、深度优先遍历的递归写法
1 2 3 4 5 6 7 8 9 10 | function deepTraversal(node) { var nodes = []; if (node != null) { nodes.push(node); var children = node.children; for (var i = 0; i < children.length; i++) deepTraversal(children[i]); } return nodes; } |
2、深度优先遍历的非递归写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function deepTraversal(node) { var nodes = []; if (node != null) { var stack = []; stack.push(node); while (stack.length != 0) { var item = stack.pop(); nodes.push(item); var children = item.children; for (var i = children.length - 1; i >= 0; i--) stack.push(children[i]); } } return nodes; } |
3、广度优先遍历的递归写法：
报错：Maximum call stack size exceeded(…)
1 2 3 4 5 6 7 8 9 10 11 | function wideTraversal(node) { var nodes = []; var i = 0; if (!(node == null)) { nodes.push(node); wideTraversal(node.nextElementSibling); node = nodes[i++]; wideTraversal(node.firstElementChild); } return nodes; } |
4、广度优先遍历的非递归写法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | function wideTraversal(selectNode) { var nodes = []; if (selectNode != null) { var queue = []; queue.unshift(selectNode); while (queue.length != 0) { var item = queue.shift(); nodes.push(item); var children = item.children; for (var i = 0; i < children.length; i++) queue.push(children[i]); } } return nodes; } |
