JavaScript实现多叉树的递归遍历和非递归遍历

在JavaScript中，通过对象的嵌套可以实现构造多叉树结构。对多叉树进行遍历，递归算法是最简单和最常用的方法，尤其方便实现先序遍历、中序遍历和后序遍历。非递归算法需要使用栈数据结构，借助栈来模拟递归操作会稍微复杂一些。本文将详细讲解如何在JavaScript中实现多叉树的递归遍历和非递归遍历算法。

创建多叉树

首先，我们需要了解如何在JavaScript中创建多叉树。一个多叉树可以表示为一个对象，每个节点包含子节点数组和其他节点属性。下面是一个例子：

var tree = {
  value: 'A',
  children: [
    { value: 'B',
      children: [
        { value: 'D' },
        { value: 'E' }]
    },
    { value: 'C',
      children: [
        { value: 'F' },
        { value: 'G',
          children: [
            { value: 'I' },
            { value: 'J' }]
        }]
    }]
};

该树的结构如下图所示：

递归遍历算法

递归遍历算法是最简单的实现方式，它使用函数递归遍历每个节点。递归遍历一个多叉树，我们需要针对每个节点执行一个操作，然后递归操作其所有子节点。下面是一个具体的实现：

// 先序遍历：根节点 -> 左子树 -> 右子树
function preOrder(node, callback) {
  if (node) {
    callback(node.value);
    if (node.children) {
      for (var i = 0, len = node.children.length; i < len; i++) {
        preOrder(node.children[i], callback);
      }
    }
  }
}

// 中序遍历：左子树 -> 根节点 -> 右子树
function inOrder(node, callback) {
  if (node) {
    if (node.children) {
      for (var i = 0, len = node.children.length; i < len; i++) {
        inOrder(node.children[i], callback);
      }
    }
    callback(node.value);
  }
}

// 后序遍历：左子树 -> 右子树 -> 根节点
function postOrder(node, callback) {
  if (node) {
    if (node.children) {
      for (var i = 0, len = node.children.length; i < len; i++) {
        postOrder(node.children[i], callback);
      }
    }
    callback(node.value);
  }
}

以上是实现了三种不同遍历顺序的递归算法。这些算法都接受两个参数：要遍历的树节点和一个回调函数，回调函数将在每个节点上被调用。具体怎么使用这些算法呢？下面是对这些算法进行调用的示例：

console.log('先序遍历: ');
preOrder(tree, console.log);

console.log('中序遍历: ');
inOrder(tree, console.log);

console.log('后序遍历: ');
postOrder(tree, console.log);

非递归遍历算法

非递归遍历算法可以节省空间和运行时间。非递归算法使用栈数据结构，将待访问节点压栈，然后逐一弹出访问。由于JavaScript中没有专用的栈数据结构，我们可以使用数组来实现，模拟栈的操作。以下是三种非递归遍历算法的具体实现：

/**
 * 先序遍历 - 非递归版
 */
function preOrder2(node, callback) {
  var stack = [],  // 数据栈
      cur;         // 当前节点
  if (node) {
    stack.push(node);
    while (stack.length > 0) {
      cur = stack.pop();
      callback(cur.value);
      if (cur.children) {
        for (var i = cur.children.length - 1; i >= 0; i--) {
          stack.push(cur.children[i]);
        }
      }
    }
  }
}

/**
 * 中序遍历 - 非递归版
 */
function inOrder2(node, callback) {
  var stack = [],  // 数据栈
      cur = node;  // 当前节点
  while (cur || stack.length > 0) {
    if (cur) {
      stack.push(cur);
      cur = cur.children && cur.children[0];
    } else {
      cur = stack.pop();
      callback(cur.value);
      cur = cur.children && cur.children[1];
    }
  }
}

/**
 * 后序遍历 - 非递归版
 */
function postOrder2(node, callback) {
  var stack = [],  // 数据栈
      cur = node,  // 当前节点
      lastVisit;   // 上次访问节点
  while (cur || stack.length > 0) {
    if (cur) {
      stack.push(cur);
      cur = cur.children && cur.children[0];
    } else {
      cur = stack.pop();
      // 如果当前节点的右子树为空或者已访问，则直接访问该节点
      if (!cur.children || cur.children[1] == lastVisit) {
        callback(cur.value);
        lastVisit = cur;
        cur = null;
      } else {
        stack.push(cur);
        cur = cur.children[1];
      }
    }
  }
}

以上是实现了三种不同遍历顺序的非递归算法，这三个算法使用栈来模拟递归操作，以达到节省内存和运行时间的目的。下面是对这些算法进行调用的示例：

console.log('先序遍历: ');
preOrder2(tree, console.log);

console.log('中序遍历: ');
inOrder2(tree, console.log);

console.log('后序遍历: ');
postOrder2(tree, console.log);

示例说明

示例一

假设现在有如下的多叉树：

var tree1 = {
  value: 'A',
  children: [
    { value: 'B',
      children: [
        { value: 'D' },
        { value: 'E' }]
    },
    { value: 'C',
      children: [
        { value: 'F' },
        { value: 'G',
          children: [
            { value: 'I' },
            { value: 'J' }]
        }]
    }]
};

我们想要得到先序遍历的结果，我们可以这样调用：