JavaScript实现二叉树的先序、中序及后序遍历方法详解

JavaScript实现二叉树的先序、中序及后序遍历方法详解

一、二叉树的定义

二叉树是一个每个节点最多有两个子树的树结构，通常分为左子树、右子树。二叉树有多种遍历方式，包括先序遍历、中序遍历和后序遍历。

其中，

• 先序遍历：按照“根结点-左子树-右子树”的方式遍历二叉树；
• 中序遍历：按照“左子树-根结点-右子树”的方式遍历二叉树；
• 后序遍历：按照“左子树-右子树-根结点”的方式遍历二叉树。

在 JavaScript 中，我们可以用基本的数据结构来表示一棵二叉树。二叉树节点的结构通常包含一个值、左子树和右子树三个属性。

下面是一个基本的二叉树节点结构的 JavaScript 代码表示：

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

下面是一个生成二叉树的函数，通过数组 inputArr 生成一棵二叉树：

const buildBinaryTree = (inputArr) => {
  const root = new TreeNode(inputArr[0]);
  const queue = [root];
  let index = 1;

  while (index < inputArr.length) {
    const currNode = queue.shift();

    if (inputArr[index] !== null) {
      currNode.left = new TreeNode(inputArr[index]);
      queue.push(currNode.left);
    }

    index++;

    if (index >= inputArr.length) break;

    if (inputArr[index] !== null) {
      currNode.right = new TreeNode(inputArr[index]);
      queue.push(currNode.right);
    }

    index++;
  }

  return root;
};

二、先序遍历实现

先序遍历按照“根结点-左子树-右子树”的方式遍历二叉树。步骤如下:

1. 如果节点为空，则返回
2. 访问根节点
3. 遍历左子树
4. 遍历右子树

以下是先序遍历的 JavaScript 实现：

const preorderTraversal = (root, result = []) => {
  if (!root) return result;

  result.push(root.val);

  root.left && preorderTraversal(root.left, result);
  root.right && preorderTraversal(root.right, result);

  return result;
};

以下是一个简单的示例：

const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(preorderTraversal(root)); // [1, 2, 4, 5, 3, 6, 7]

三、中序遍历实现

中序遍历按照“左子树-根结点-右子树”的方式遍历二叉树。步骤如下：

1. 如果节点为空，则返回
2. 遍历左子树
3. 访问根节点
4. 遍历右子树

以下是中序遍历的 JavaScript 实现：

const inorderTraversal = (root, result = []) => {
  if (!root) return result;

  root.left && inorderTraversal(root.left, result);
  result.push(root.val);
  root.right && inorderTraversal(root.right, result);

  return result;
};

以下是一个简单的示例：

const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(inorderTraversal(root)); // [4, 2, 5, 1, 6, 3, 7]

四、后序遍历实现

后序遍历按照“左子树-右子树-根结点”的方式遍历二叉树。步骤如下：

1. 如果节点为空，则返回
2. 遍历左子树
3. 遍历右子树
4. 访问根节点

以下是后序遍历的 JavaScript 实现：

const postorderTraversal = (root, result = []) => {
  if (!root) return result;

  root.left && postorderTraversal(root.left, result);
  root.right && postorderTraversal(root.right, result);
  result.push(root.val);

  return result;
};

以下是一个简单的示例：

const inputArr = [1, 2, 3, 4, 5, 6, 7];
const root = buildBinaryTree(inputArr);
console.log(postorderTraversal(root)); // [4, 5, 2, 6, 7, 3, 1]

以上是 JavaScript 实现二叉树的先序、中序及后序遍历方法的详细攻略。