排序二叉树js实现

排序二叉树（BST）的 JavaScript 实现

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

节点类定义

每个节点包含值、左子节点和右子节点的引用：

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;
    } else {
      this._insertNode(this.root, newNode);
    }
  }

  _insertNode(node, newNode) {
    if (newNode.value < node.value) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this._insertNode(node.left, newNode);
      }
    } else {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this._insertNode(node.right, newNode);
      }
    }
  }

  // 查找节点
  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    if (node === null) return false;
    if (value < node.value) {
      return this._searchNode(node.left, value);
    } else if (value > node.value) {
      return this._searchNode(node.right, value);
    } else {
      return true;
    }
  }

  // 删除节点
  remove(value) {
    this.root = this._removeNode(this.root, value);
  }

  _removeNode(node, value) {
    if (node === null) return null;
    if (value < node.value) {
      node.left = this._removeNode(node.left, value);
      return node;
    } else if (value > node.value) {
      node.right = this._removeNode(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：有两个子节点
      const minRight = this._findMinNode(node.right);
      node.value = minRight.value;
      node.right = this._removeNode(node.right, minRight.value);
      return node;
    }
  }

  _findMinNode(node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  }
}

遍历方法

实现前序、中序、后序遍历：

// 中序遍历（升序）
inOrderTraverse(callback) {
  this._inOrderTraverseNode(this.root, callback);
}

_inOrderTraverseNode(node, callback) {
  if (node !== null) {
    this._inOrderTraverseNode(node.left, callback);
    callback(node.value);
    this._inOrderTraverseNode(node.right, callback);
  }
}

// 前序遍历
preOrderTraverse(callback) {
  this._preOrderTraverseNode(this.root, callback);
}

_preOrderTraverseNode(node, callback) {
  if (node !== null) {
    callback(node.value);
    this._preOrderTraverseNode(node.left, callback);
    this._preOrderTraverseNode(node.right, callback);
  }
}

// 后序遍历
postOrderTraverse(callback) {
  this._postOrderTraverseNode(this.root, callback);
}

_postOrderTraverseNode(node, callback) {
  if (node !== null) {
    this._postOrderTraverseNode(node.left, callback);
    this._postOrderTraverseNode(node.right, callback);
    callback(node.value);
  }
}

使用示例

const bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);

bst.inOrderTraverse(value => console.log(value)); // 输出：3,5,7,11,15
console.log(bst.search(7)); // true
bst.remove(5);

注意事项

• 插入重复值的处理需根据需求决定（示例中默认插入右子树）
• 删除操作需处理三种情况：叶子节点、单子节点、双子节点
• 时间复杂度：平均情况下插入/查找/删除为 O(log n)，最坏情况（退化为链表）为 O(n)