二叉查找树的理解

二叉查找树是一种特殊的二叉树，它支持动态的数据集合的快速插入、删除和查找操作。二叉查找树的一般结构如下图所示：

从上图可以观察到二叉查找树的一个重要特性树中的任意一个节点，其左子树中的每个节点的值都小于该节点的值，右子树中的每个节点的值都大于该节点的值。

二叉查找树的查找操作

对于二叉查找树的查找操作主要步骤如下：

• 先获取根节点，如果根节点的值等于需要查找的值，则返回；
• 如果根节点的值小于需要查找的值，则在右子树中递归查找；
• 如果根节点的值大于需要查找的值，则在左子树中递归查找。

查找的代码如下所示：

public class BinarySearchTree {
  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if(p.data < data)
        p = p.right;
      else if(p.data > data)
        p = p.left;
      else
        return p;
    }
    return null;
  }
}

二叉查找树的插入操作

对于二叉查找树的插入操作时，新插入节点一般都是插入到叶子节点，从根节点开始依次比较新插入节点的值与当前节点值的大小关系，具体步骤如下：

• 如果新插入节点的值大于当前节点的值，并且当前节点的右子树为空，则将新插入的节点插入到右子节点的位置；如果当前节点的右子树不可空，则递归遍历右子树，查找插入的位置；
• 如果新插入节点的值小于当前节点的值，并且当前节点的左子树为空，则将新插入的节点插入到左子节点的位置；如果当前节点的左子树不为空，则递归遍历左子树，查找插入的位置。

插入的代码如下所示：

public class BinarySearchTree {

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node tree;

  public void insert(int data) {
    if (tree == null) {
      tree = new Node(data);
      return;
    }

    Node p = tree;
    while (p != null) {
      if (data > p.data) {
        if (p.right == null) {
          p.right = new Node(data);
          return;
        }
        p = p.right;
      } else {                     // data < p.data
        if (p.left == null) {
          p.left = new Node(data);
          return;
        }
        p = p.left;
      }
    }
  }
}

二叉查找树的删除操作

对于二叉查找树的删除操作主要分为三种情况，下面分别讨论：

• 当删除的节点中没有子节点，只需要将父节点中指向该节点的指针设为空即可；
  

• 当删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中指向删除节点的指针，让该指针指向删除节点的子节点即可；
  

• 当删除的节点有两个节点时，需要找到该节点右子树中值最小的节点，把它替换到删除节点上，然后删除找到的右子树中值最小的节点。
  

删除的代码如下所示：

public class BinarySearchTree {

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }

  private Node tree;

  public void delete(int data) {
    Node p = tree;             // p 指向要删除的节点，初始化指向根节点
    Node pp = null;         // pp 记录的是 p 的父节点
    while (p != null && p.data != data) {
      pp = p;
      if (data > p.data) 
          p = p.right;
      else p = p.left;
      }
    if (p == null) return; // 没有找到

    // 要删除的节点有两个子节点
    if (p.left != null && p.right != null) { // 查找右子树中最小节点
      Node minP = p.right;
      Node minPP = p;             // minPP 表示 minP 的父节点
      while (minP.left != null) {
        minPP = minP;
        minP = minP.left;
      }
      p.data = minP.data; // 将 minP 的数据替换到 p 中
      p = minP; // 下面就变成了删除 minP 了
      pp = minPP;
    }

    // 删除节点是叶子节点或者仅有一个子节点
    Node child; // p 的子节点
    if (p.left != null) 
      child = p.left;
    else if (p.right != null) 
      child = p.right;
    else 
      child = null;

    // 删除的是根节点
    if (pp == null) 
      tree = child; 
    else if (pp.left == p) 
      pp.left = child;
    else 
      pp.right = child;
  }
}

更多秋招资料和秋招面试题，请关注公众号[算法半岛]