数据结构TypeScript之二叉查找树实现详解

数据结构TypeScript之二叉查找树实现详解

什么是二叉查找树

二叉查找树（Binary Search Tree，简称BST）是一种基础的数据结构，也是一种常用的搜索算法。它通过以二叉树的形式表示各个结点之间的关系，实现了快速查找、添加、删除等操作。对于任何一个节点，其左子树上的节点值均小于该节点的值，右子树上的节点值均大于该节点的值。

二叉查找树的实现

下面我们将分别介绍二叉查找树的构造方法、插入、查找和删除等操作的实现。

构造方法

构造方法的主要作用是创建一棵空树。由于我们要实现的是泛型的BST，因此需要在定义中使用泛型T。在新建二叉查找树时，我们仅需设置其根节点为null即可。

class BinarySearchTree<T> {
  private root: BSTNode<T> | null;

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

插入

插入操作分为两步：查找插入节点的位置和将新节点插入到该位置。

1. 查找插入节点的位置

查找插入节点的位置需要从根节点开始递归查找。对于当前节点，如果插入节点的值小于该节点的值，则继续递归查找该节点的左子树；否则继续递归查找该节点的右子树。如果递归到最底层节点时，仍未找到合适的插入位置，则说明该节点为插入节点的位置。

private findInsertPos(val: T): BSTNode<T> {
  let current = this.root;
  let parent = null;

  while (current !== null) {
    parent = current;
    if (val < current.val) {
      current = current.left;
    } else if (val > current.val) {
      current = current.right;
    } else {
      // 已存在该节点，不需要插入
      return null;
    }
  }

  // parent为插入节点的父节点
  return parent;
}

1. 将新节点插入到该位置

找到插入位置的父节点后，我们需要将新节点插入到该位置。由于二叉查找树要求，所有左子树上的节点值均小于该节点的值，右子树上的节点值均大于该节点的值，因此需要先将新节点的值与父节点进行比较，然后决定将新节点插入到左子树或右子树。

public insert(val: T): void {
  const parent = this.findInsertPos(val);

  if (parent === null) {
    // 已存在该节点，不需要插入
    return;
  }

  const node = new BSTNode(val);
  if (parent.val > val) {
    parent.left = node;
  } else {
    parent.right = node;
  }
}

查找

查找操作的实现与插入操作相似，也需要从根节点开始递归查找，但对于查找的值与当前节点的值大小关系，我们有三种情况需要考虑：查找值等于当前节点值、查找值小于当前节点值、查找值大于当前节点值。

private find(val: T, current: BSTNode<T>): BSTNode<T> {
  if (current === null) {
    return null;
  }

  if (val === current.val) {
    // 查找值等于当前节点值
    return current;
  } else if (val < current.val) {
    // 查找值小于当前节点值，递归查找左子树
    return this.find(val, current.left);
  } else {
    // 查找值大于当前节点值，递归查找右子树
    return this.find(val, current.right);
  }
}

public search(val: T): boolean {
  return this.find(val, this.root) !== null;
}

删除

删除操作最复杂的地方在于删除节点时需要查找该节点的后继（即以当前节点为根的子树上的最小节点）或前驱（即以当前节点为根的子树上的最大节点）。

1. 查找目标节点

查找目标节点时需要从根节点开始递归查找，找到要删除的节点。

private findDeleteNode(val: T, current: BSTNode<T>, parent: BSTNode<T>): BSTNode<T> {
  if (current === null) {
    return null;
  } else if (val === current.val) {
    // 找到目标节点
    return { node: current, parent };
  } else if (val < current.val) {
    // 查找左子树
    return this.findDeleteNode(val, current.left, current);
  } else {
    // 查找右子树
    return this.findDeleteNode(val, current.right, current);
  }
}

1. 删除目标节点

当找到目标节点后，我们需要考虑以下三种情况。

• 目标节点没有子节点：直接删除目标节点即可；
• 目标节点只有一个子节点：将目标节点的父节点指向目标节点的子节点；
• 目标节点有两个子节点：找到目标节点的后继或前驱，并将其值赋给目标节点，然后删除后继或前驱节点。

public delete(val: T): void {
  let { node, parent } = this.findDeleteNode(val, this.root, null);

  if (node === null) {
    // 没有找到目标节点
    return;
  }

  if (node.left === null && node.right === null) {
    // 目标节点没有子节点
    if (parent === null) {
      // 删除根节点
      this.root = null;
    } else if (parent.left === node) {
      parent.left = null;
    } else {
      parent.right = null;
    }
  } else if (node.left === null || node.right === null) {
    // 目标节点只有一个子节点
    const child = node.left || node.right;
    if (parent === null) {
      // 删除根节点
      this.root = child;
    } else if (parent.left === node) {
      parent.left = child;
    } else {
      parent.right = child;
    }
  } else {
    // 目标节点有两个子节点，找到后继节点
    let successor = node.right;
    let successorParent = node;
    while (successor.left !== null) {
      successorParent = successor;
      successor = successor.left;
    }

    // 将后继节点的值赋给目标节点，然后删除后继节点
    node.val = successor.val;
    if (successorParent.left === successor) {
      successorParent.left = successor.right;
    } else {
      successorParent.right = successor.right;
    }
  }
}

示例

假设我们有一组整数需要插入到二叉查找树中。

const nums = [20, 5, 12, 30, 28, 15, 18, 35, 25, 40];
const bst = new BinarySearchTree<number>();

for (const num of nums) {
  bst.insert(num);
}

插入完成后，我们可以使用以下方法检查树是否构造正确，并输出中序遍历结果。

function inOrder(node: BSTNode<any>, arr: any[]): void {
  if (node !== null) {
    inOrder(node.left, arr);
    arr.push(node.val);
    inOrder(node.right, arr);
  }
}

const res: any[] = [];
inOrder(bst.root, res);
console.log(res);

输出结果为：

[5, 12, 15, 18, 20, 25, 28, 30, 35, 40]

接下来，我们可以使用以下代码测试删除操作。

bst.delete(20);  // 删除根节点
bst.delete(5);   // 删除叶子节点
bst.delete(30);  // 删除有一子节点的节点
bst.delete(15);  // 删除有两子节点的节点

const res: any[] = [];
inOrder(bst.root, res);
console.log(res);

输出结果为：

[12, 18, 25, 28, 35, 40]

从结果中可以看出，二叉查找树插入和删除操作都能够正常工作，可以使用该数据结构实现高效的查找、添加、删除等操作。