JavaScript实现多叉树的递归遍历和非递归遍历算法操作示例

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' }]
        }]
    }]
};

该树的结构如下图所示：

    A
   / \
  B   C
 / \   \
D   E   F
        \
         G
        / \
       I   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' }]
        }]
    }]
};

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

preOrder(tree1, console.log);

得到结果：

A
B
D
E
C
F
G
I
J

• 示例二

我们还可以尝试使用非递归算法来遍历树。为了得到中序遍历的结果，我们可以这样调用：

inOrder2(tree1, console.log);

得到结果：

D
B
E
A
F
C
I
G
J

从以上两个例子中，我们可以看出使用递归算法和非递归算法来遍历多叉树都是非常方便和实用的。