JS二叉树

二叉树是一种树形数据结构，它的每个节点最多有两个子节点。常用于实现搜索算法和排序算法。在 JavaScript 中，可以使用对象来表示二叉树。

下面是一个简单的二叉树实现示例：

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

class BinaryTree {
  constructor() {
    this.root = null;
  }

  // 插入节点
  insert(value) {
    const node = new Node(value);

    if (!this.root) {
      this.root = node;
      return;
    }

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

  // 中序遍历
  inOrderTraversal(callback) {
    function traverse(node) {
      if (node) {
        traverse(node.left);
        callback(node.value);
        traverse(node.right);
      }
    }

    traverse(this.root);
  }

  // 先序遍历
  preOrderTraversal(callback) {
    function traverse(node) {
      if (node) {
        callback(node.value);
        traverse(node.left);
        traverse(node.right);
      }
    }

    traverse(this.root);
  }

  // 后序遍历
  postOrderTraversal(callback) {
    function traverse(node) {
      if (node) {
        traverse(node.left);
        traverse(node.right);
        callback(node.value);
      }
    }

    traverse(this.root);
  }
}

上述代码中，`Node` 类表示节点，包含一个值和左右子节点的引用。`BinaryTree` 类表示二叉树，包含一个根节点和插入、遍历节点的方法。

在 `insert` 方法中，如果当前二叉树为空，则将新节点设置为根节点；否则，从根节点开始向下遍历，根据当前节点值与新节点值的大小比较，选择左子树或右子树进行遍历，直到找到没有子节点的位置，将新节点插入。

`inOrderTraversal`、`preOrderTraversal` 和 `postOrderTraversal` 方法分别实现了中序、先序和后序遍历三种遍历方式。其中，递归遍历左子树、当前节点和右子树的顺序不同，以实现不同的遍历方式。

使用示例：

const tree = new BinaryTree();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(4);
tree.insert(6);
tree.insert(8);

tree.inOrderTraversal(console.log); // 输出：1 3 4 5 6 7 8
tree.preOrderTraversal(console.log); // 输出：5 3 1 4 7 6 8
tree.postOrderTraversal(console.log); // 输出：1 4 3 6 8 7 5

上述代码中，创建了一个二叉树并插入了七个节点，然后使用三种遍历方式输出节点值。