C++高级数据结构之二叉查找树

什么是二叉查找树

二叉查找树，也称二叉搜索树（BST，Binary Search Tree），是一种常见的基于二叉树的数据结构，主要用于快速查找与排序。在二叉查找树上，左子树的每个节点都比其根节点小，右子树的每个节点都比其根节点大，同时整棵树也满足二叉树的性质。

二叉查找树的实现

我们可以通过C++语言实现二叉查找树的基本操作，包括元素的插入、删除、查找等。

二叉查找树的结构体定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉查找树的插入操作

void insert(TreeNode* root, int val) {
    if (root == NULL) {
        root = new TreeNode(val);
        return;
    }
    if (root->val > val) {
        if (root->left == NULL) {
            root->left = new TreeNode(val);
            return;
        }
        insert(root->left, val);
    } else {
        if (root->right == NULL) {
            root->right = new TreeNode(val);
            return;
        }
        insert(root->right, val);
    }
}

二叉查找树的删除操作

二叉查找树的删除操作需要分几种情况考虑，可以分为以下两种情况：

• 被删除结点没有左子树或右子树，这种情况直接删除结点即可。
• 被删除结点有左子树与右子树，这种情况需要寻找该结点的后继（即右子树中最小的元素），将后继的值取代该结点的值，再删除后继节点。

以下为二叉查找树的删除操作的实现：

void deleteNode(TreeNode* root, int val) {
    if (root == NULL) {
        return;
    }
    if (root->val > val) {
        deleteNode(root->left, val);
    } else if (root->val < val) {
        deleteNode(root->right, val);
    } else {
        if (root->left == NULL) {
            root = root->right;
        } else if (root->right == NULL) {
            root = root->left;
        } else {
            TreeNode* tmp = root->right;
            while (tmp->left != NULL) {
                tmp = tmp->left;
            }
            root->val = tmp->val;
            deleteNode(root->right, root->val);
        }
    }
}

二叉查找树的查找操作

TreeNode* search(TreeNode* root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (root->val == val) {
        return root;
    } else if (root->val > val) {
        return search(root->left, val);
    } else {
        return search(root->right, val);
    }
}

示例说明

我们可以使用以下二叉查找树：

       5
      / \
     3   7
    / \   \
   1   4   8

对其进行一系列操作，例如：

TreeNode* root = new TreeNode(5);
insert(root, 3);
insert(root, 7);
insert(root, 1);
insert(root, 8);
insert(root, 4);

/*
  结果为：
       5
      / \
     3   7
    / \   \
   1   4   8
*/

TreeNode* node = search(root, 4);
// 结果为：root->left->right

deleteNode(root, 5);

/*
  结果为：
       7
      / \
     3   8
    /   
   1   
    \  
     4
*/

总结

二叉查找树是一种高效的数据结构，其实现具有一定的难度，但如果掌握了基本操作，可以非常方便地进行二叉查找树的插入、删除、查找等操作。同时，二叉查找树的优化和扩展也是值得学习的一点，例如平衡二叉树AVL树、红黑树等。