排序二叉树js实现

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

排序二叉树（Binary Search Tree, BST）是一种数据结构，满足以下性质：

• 左子树所有节点的值小于根节点的值
• 右子树所有节点的值大于根节点的值
• 左右子树也分别是排序二叉树

节点类实现

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

二叉搜索树类框架

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

插入节点方法

insert(value) {
  const newNode = new Node(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;
  let found = false;
  while (current && !found) {
    if (value < current.value) {
      current = current.left;
    } else if (value > current.value) {
      current = current.right;
    } else {
      found = true;
    }
  }

  return found ? current : undefined;
}

删除节点方法

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 {
      // 情况1：叶子节点
      if (node.left === null && node.right === null) {
        return null;
      }
      // 情况2：只有一个子节点
      if (node.left === null) return node.right;
      if (node.right === null) return node.left;

      // 情况3：有两个子节点
      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);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.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)。