JavaScript 二叉树实现：创建、遍历、插入和删除

这是一个使用 JavaScript 实现二叉树的基本结构和操作的示例。

二叉树的基本结构

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

这里定义了一个 Node 类，每个节点包含一个值 (value) 和指向左右子树的指针 (left 和 right)。如果指针为空，则表示该节点没有左右子树。

创建二叉树

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

这里创建了一个包含 5 个节点的二叉树，根节点的值为 1，左子树包含节点 2 和 4，右子树包含节点 3 和 5。

遍历二叉树

function inorderTraversal(root) {
  if (!root) return;
  inorderTraversal(root.left);
  console.log(root.value);
  inorderTraversal(root.right);
}

inorderTraversal(root);  // 4 2 5 1 3

这里定义了一个中序遍历函数 inorderTraversal，它会先递归遍历左子树，再输出当前节点的值，最后递归遍历右子树。运行该函数会输出节点值的中序遍历。

插入节点

function insert(root, value) {
  if (!root) {
    return new Node(value);
  }
  if (value < root.value) {
    root.left = insert(root.left, value);
  } else if (value > root.value) {
    root.right = insert(root.right, value);
  }
  return root;
}

insert(root, 6);
inorderTraversal(root);  // 4 2 5 1 3 6

这里定义了一个插入节点函数 insert，它会根据节点值的大小比较递归地插入节点。运行该函数会将值为 6 的节点插入到二叉树中，并输出更新后的中序遍历。

删除节点

function deleteNode(root, value) {
  if (!root) return null;
  if (value < root.value) {
    root.left = deleteNode(root.left, value);
  } else if (value > root.value) {
    root.right = deleteNode(root.right, value);
  } else {
    if (!root.left && !root.right) {
      return null;
    } else if (!root.left || !root.right) {
      return root.left || root.right;
    } else {
      let minNode = root.right;
      while (minNode.left) {
        minNode = minNode.left;
      }
      root.value = minNode.value;
      root.right = deleteNode(root.right, minNode.value);
    }
  }
  return root;
}

deleteNode(root, 2);
inorderTraversal(root);  // 4 5 1 3 6

这里定义了一个删除节点函数 deleteNode，它会根据节点值的大小比较递归地删除节点。如果节点没有左右子树，则直接删除该节点。如果节点只有一个子树，则用该子树替换当前节点。如果节点有两个子树，则找到右子树中的最小节点，用该节点替换当前节点，并递归删除该最小节点。运行该函数会将值为 2 的节点从二叉树中删除，并输出更新后的中序遍历。

希望这些例子能够帮助您理解如何使用 JavaScript 创建和操作二叉树。