利用JS实现二叉树遍历算法实例代码

下面是详细的攻略：

编写二叉树遍历算法

1. 创建二叉树

首先需要创建一个二叉树，在本例中，我们将使用以下节点来创建一个二叉树：

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

以上代码创建了一个Node类用于表示二叉树的节点。

接下来，我们将创建一个BinaryTree类来表示整个二叉树。在此之前，我们需要了解一个术语 - 前序遍历。前序遍历的顺序是：根节点 -> 左子树 -> 右子树。这意味着在遍历时，我们需要首先访问根节点，然后遍历左子树，接着遍历右子树。

以下是关于BinaryTree类的完整代码：

class BinaryTree {
  constructor(value) {
    this.root = new Node(value);
  }

  // 向二叉树中插入节点
  insert(value) {
    const node = new Node(value);

    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (!current.left) {
          current.left = node;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          break;
        }
        current = current.right;
      }
    }
    return this;
  }

  // 前序遍历
  preorderTraversal(node, result = []) {
    if (node) {
      result.push(node.value);
      this.preorderTraversal(node.left, result);
      this.preorderTraversal(node.right, result);
    }
    return result;
  }
}

以上代码创建了BinaryTree类，并提供了插入节点和前序遍历的方法。insert()方法用于向二叉树中插入节点。preorderTraversal()方法用于进行前序遍历。preorderTraversal()方法的参数node表示遍历的节点，result参数用于存储遍历的结果。在遍历时，每遇到一个节点，我们将它的值加入到result数组中，然后继续遍历它的左子树和右子树，直到整个二叉树被遍历完。

2. 遍历二叉树

现在我们已经有了一个二叉树和前序遍历的方法，下一步是实现一个函数来遍历二叉树。以下是遍历函数的完整代码：

function traversal(binaryTree) {
  const result = [];

  const stack = [];
  let current = binaryTree.root;

  while (stack.length || current) {
    if (current) {
      stack.push(current);
      result.push(current.value);
      current = current.left; // 遍历左子树
    } else {
      current = stack.pop();
      current = current.right; // 遍历右子树
    }
  }

  return result;
}

以上代码创建了一个名为traversal()的函数，它使用前序遍历的方式遍历二叉树。

该函数使用栈来存储要遍历的节点。它首先将二叉树的根节点压入栈中，并将其值加入到结果数组中。然后，它遍历根节点的左子树，并将遍历的节点依次压入栈中。当左子树已经构建完毕后，它开始弹出栈中的节点，遍历对应节点的右子树，并将遍历的节点压入栈中。直到整个二叉树遍历完成。

3. 示例

现在，我们已经完成了二叉树遍历算法的实现。下面，我们将通过两个示例来演示它的使用。

示例 1

假设我们有一个二叉树，根节点为5，左子树为3和2，右子树为7和9。我们可以使用以下代码创建并遍历它：

const binaryTree = new BinaryTree(5);
binaryTree.insert(3);
binaryTree.insert(2);
binaryTree.insert(7);
binaryTree.insert(9);

console.log(traversal(binaryTree)); // [5, 3, 2, 7, 9]

输出结果应该是：[5, 3, 2, 7, 9]

示例 2

假设我们有一个二叉树，根节点为10，左子树为8和9，右子树为12和11。我们可以使用以下代码创建并遍历它：

const binaryTree = new BinaryTree(10);
binaryTree.insert(8);
binaryTree.insert(9);
binaryTree.insert(12);
binaryTree.insert(11);

console.log(traversal(binaryTree)); // [10, 8, 9, 12, 11]

输出结果应该是：[10, 8, 9, 12, 11]

总结

以上就是利用JS实现二叉树遍历算法的实现攻略。我们首先创建了一个二叉树，并通过前序遍历的方式遍历它。接着，我们将遍历函数封装成一个函数，使用栈来存储要遍历的节点，最终完成了算法的实现。