二叉搜索树引入

概念

  • 一种树状数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
  • 左子树上的所有节点的值都小于等于根节点的值。
  • 右子树上的所有节点的值都大于等于根节点的值。
  • 它的左右子树也分别为二叉搜索树。
  • 这个性质使得在二叉搜索树中可以高效地进行搜索、插入和删除操作。
1
2
3
4
5
6
7
8
          8
         / \
        3   10
       / \    \
      1   6    14
         / \   /
        4   7  13
// 二叉搜索树示例

别称

  1. 排序二叉树（Sorted Binary Tree）：
    • 类似于“有序二叉树”，强调了树中元素的排序。
  2. 二叉查找树（Binary Search Tree，BST）：
    • 使用“查找”这个词语，强调了BST在搜索操作上的高效性。
  3. 二叉排序树（Binary Sort Tree）：
    • 强调了BST作为一种排序数据的树形结构。

二叉搜索树操作

节点定义

1
2
3
4
5
6
7
8
// 节点结构定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

1. 搜索操作：

  • 思路：
    • 从根节点开始比较目标值与当前节点的值。
    • 如果目标值等于当前节点值，则找到目标节点。
    • 如果目标值小于当前节点值，递归在左子树中搜索。
    • 如果目标值大于当前节点值，递归在右子树中搜索。
    • 重复以上步骤，直到找到目标节点或到达叶子节点。

2. 插入操作：

  • 思路：
    • 从根节点开始比较要插入的值与当前节点的值。
    • 如果要插入的值小于当前节点值，递归地插入到左子树。
    • 如果要插入的值大于当前节点值，递归地插入到右子树。
    • 如果当前节点为空，表示找到插入位置，创建一个新节点插入。

3. 删除操作：

  • 思路：
    • 删除节点分为三种情况：
      1. 节点没有子节点： 直接删除节点。
      2. 节点有一个子节点： 将子节点替换为当前节点。
      3. 节点有两个子节点： 找到右子树的最小节点（或左子树的最大节点），用它替换当前节点，然后在右子树中递归删除这个最小节点。

4. 中序遍历：

  • 思路：

    • 采用递归方式，按照左子树-根节点-右子树的顺序遍历。
    • 递归遍历左子树，访问当前节点，然后递归遍历右子树。
    • 得到的节点序列是有序的。

    函数解析

    插入辅助函数 insertHelper

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    BSTNode* insertHelper(BSTNode* root, int val) {
        // 如果根节点为空，创建新节点并返回
        if (!root) {
            return new BSTNode(val);
        }

        // 根据值的大小关系递归插入节点
        if (val < root->_val) {
            root->_left = insertHelper(root->_left, val);
        } else {
            root->_right = insertHelper(root->_right, val);
        }

        return root;
    }

    1. 基本情况： 如果当前节点 (root) 为空，表示到达树的底部，创建一个新节点，并将其作为叶子节点插入。

      1
      2
      3
      if (!root) {
          return new BSTNode(val);
      }

    2. 递归调用： 根据值的大小关系，递归调用插入函数来在左子树或右子树中插入新节点。

      1
      2
      3
      4
      5
      if (val < root->_val) {
          root->_left = insertHelper(root->_left, val);
      } else {
          root->_right = insertHelper(root->_right, val);
      }

    3. 返回根节点： 返回当前子树的根节点。

      1
      return root;

    查找辅助函数 findHelper

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    BSTNode* findHelper(BSTNode* root, int val) {
        // 如果根节点为空或找到了目标值，返回当前节点
        if (!root || root->_val == val) {
            return root;
        }

        // 根据值的大小关系递归查找节点
        if (val < root->_val) {
            return findHelper(root->_left, val);
        } else {
            return findHelper(root->_right, val);
        }
    }

    1. 基本情况： 如果当前节点 (root) 为空或找到了目标值，表示查找成功，返回当前节点。

      1
      2
      3
      if (!root || root->_val == val) {
          return root;
      }

    2. 递归调用： 根据值的大小关系，递归调用查找函数在左子树或右子树中查找目标值。

      1
      2
      3
      4
      5
      if (val < root->_val) {
          return findHelper(root->_left, val);
      } else {
          return findHelper(root->_right, val);
      }

    删除辅助函数 deleteHelper

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    BSTNode* deleteHelper(BSTNode* root, int val) {
        // 如果根节点为空，返回空
        if (!root) {
            return root;
        }

        // 根据值的大小关系递归删除节点
        if (val < root->_val) {
            root->_left = deleteHelper(root->_left, val);
        } else if (val > root->_val) {
            root->_right = deleteHelper(root->_right, val);
        } else {
            // 找到要删除的节点

            // 情况1：节点没有子节点或只有一个子节点
            if (!root->_left) {
                BSTNode* temp = root->_right;
                delete root;
                return temp;
            } else if (!root->_right) {
                BSTNode* temp = root->_left;
                delete root;
                return temp;
            }

            // 情况3：节点有两个子节点
            BSTNode* temp = findMin(root->_right);
            root->_val = temp->_val;
            root->_right = deleteHelper(root->_right, temp->_val);
        }

        return root;
    }

    1. 基本情况： 如果当前节点 (root) 为空，表示到达树的底部，返回空。

      1
      2
      3
      if (!root) {
          return root;
      }

    2. 递归调用： 根据值的大小关系，递归调用删除函数在左子树或右子树中删除节点。

      1
      2
      3
      4
      5
      if (val < root->_val) {
          root->_left = deleteHelper(root->_left, val);
      } else if (val > root->_val) {
          root->_right = deleteHelper(root->_right, val);
      }

    3. 节点删除：

      • 情况1： 如果要删除的节点没有左子节点或只有一个左子节点，用右子节点（如果存在）替换该节点，然后删除该节点。
      1
      2
      3
      4
      5
      if (!root->_left) {
          BSTNode* temp = root->_right;
          delete root;
          return temp;
      }
      • 情况2： 如果要删除的节点没有右子节点或只有一个右子节点，用左子节点（如果存在）替换该节点，然后删除该节点。
      1
      2
      3
      4
      5
      else if (!root->_right) {
          BSTNode* temp = root->_left;
          delete root;
          return temp;
      }
      • 情况3：

    如果要删除的节点有左右两个子节点，找到右子树中的最小值节点，用其值替换当前节点的值，然后递归地在右子树中删除这个最小值节点。

    1
    2
    3
    4
    5
    else {
        BSTNode* temp = findMin(root->_right);
        root->_val = temp->_val;
        root->_right = deleteHelper(root->_right, temp->_val);
    }

    1. 返回根节点： 返回当前子树的根节点。

      1
      return root;

    查找右子树的最小值节点辅助函数 findMin

    1
    2
    3
    4
    5
    6
    7
    BSTNode* findMin(BSTNode* node) {
        // 遍历左子树找到最小值节点
        while (node->_left) {
            node = node->_left;
        }
        return node;
    }

    这个辅助函数用于在右子树中找到最小值的节点，确保在删除操作中正确处理有两个子节点的情况。

    这些辅助函数共同协作，确保二叉搜索树的插入、查找和删除操作能够正确地维护树的有序性质。