JavaScript树的深度优先遍历和广度优先遍历算法示

本文深入了JavaScript树的优先遍历和广度优先遍历算法，结合实例详细分析了递归与非递归的实现技巧。

一、优先遍历

优先遍历是一种用于遍历或搜索树或图的算法。在树中，此算法会优先最深的节点。以下是优先遍历的递归与非递归实现方式。

1. 递归实现

在递归实现中，我们从根节点开始，将其加入结果数组，然后对其每个子节点递归调用优先遍历函数。当节点为空时，递归停止。

```javascript

function deepTraversalRecursive(node) {

var nodes = [];

if (node != null) {

nodes.push(node);

var children = node.children;

for (var i = 0; i < children.length; i++)

deepTraversalRecursive(children[i]);

}

return nodes;

}

```

2. 非递归实现

非递归实现通常使用栈来模拟递归过程。我们从根节点开始，将其压入栈，然后循环从栈顶取节点，将其加入结果数组，并将其子节点逆序压入栈。当栈为空时，遍历结束。

```javascript

function deepTraversalNonRecursive(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;

}

```

二、广度优先遍历

广度优先遍历则是一种先最近的节点，然后再更远的节点的算法。以下是广度优先遍历的非递归实现方式。由于递归实现可能导致堆栈溢出，因此在实际应用中通常使用非递归方式。

非递归实现使用队列来保存待处理的节点。我们将根节点加入队列，然后在循环中取出队列中的节点，将其加入结果数组，并将其子节点压入队列。当队列为空时，遍历结束。

```javascript

function wideTraversalNonRecursive(selectNode) {

var nodes = [];

if (selectNode != null) {

var queue = [];

queue.unshift(selectNode);

while (queue.length > 0) {