排序二叉树js实现

排序二叉树（二叉搜索树）的 JavaScript 实现

排序二叉树（Binary Search Tree, BST）是一种特殊的二叉树，其中每个节点的左子树节点值小于当前节点值，右子树节点值大于当前节点值。以下是完整的实现方法：

节点类定义

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

二叉搜索树类框架

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

插入节点

insert(value) {
  const newNode = new TreeNode(value);
  if (this.root === null) {
    this.root = newNode;
    return this;
  }

  let current = this.root;
  while (true) {
    if (value === current.value) return undefined;

    if (value < current.value) {
      if (current.left === null) {
        current.left = newNode;
        return this;
      }
      current = current.left;
    } else {
      if (current.right === null) {
        current.right = newNode;
        return this;
      }
      current = current.right;
    }
  }
}

查找节点

find(value) {
  if (this.root === null) return false;

  let current = this.root;
  while (current) {
    if (value === current.value) return current;

    if (value < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return false;
}

删除节点

delete(value) {
  const deleteNode = (node, value) => {
    if (node === null) return null;

    if (value < node.value) {
      node.left = deleteNode(node.left, value);
      return node;
    } else if (value > node.value) {
      node.right = deleteNode(node.right, value);
      return node;
    } else {
      if (node.left === null) return node.right;
      if (node.right === null) return node.left;

      let tempNode = node.right;
      while (tempNode.left !== null) {
        tempNode = tempNode.left;
      }
      node.value = tempNode.value;
      node.right = deleteNode(node.right, tempNode.value);
      return node;
    }
  };

  this.root = deleteNode(this.root, value);
}

遍历方法

// 中序遍历（升序）
inOrder() {
  const result = [];
  const traverse = (node) => {
    if (node.left) traverse(node.left);
    result.push(node.value);
    if (node.right) traverse(node.right);
  };
  traverse(this.root);
  return result;
}

// 前序遍历
preOrder() {
  const result = [];
  const traverse = (node) => {
    result.push(node.value);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  };
  traverse(this.root);
  return result;
}

// 后序遍历
postOrder() {
  const result = [];
  const traverse = (node) => {
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
    result.push(node.value);
  };
  traverse(this.root);
  return result;
}

使用示例

const bst = new BinarySearchTree();
bst.insert(10).insert(5).insert(15).insert(2).insert(7);

console.log(bst.inOrder()); // [2, 5, 7, 10, 15]
bst.delete(5);
console.log(bst.inOrder()); // [2, 7, 10, 15]

复杂度分析

• 插入/查找/删除操作的平均时间复杂度为 O(log n)
• 最坏情况（树退化为链表）时间复杂度为 O(n)
• 空间复杂度为 O(n)