二叉查找树又称二叉排序树，它要么是空树，要么是具有下列性质的二叉树：

1. 每个节点都有一个作为查找依据的关键码。所有节点的关键码互不相同；
2. 若它的左子树不为空，则左子树上所有节点的关键码均小于根节点的关键码；
3. 若它的右子树不为空，则右子树上所有节点的关键码均大于根节点的关键码；
4. 它的左、右子树也是二叉查找树。

一、查找元素

若二叉查找树的根节点的指针为空，则查找不成功；否则进行一下的操作：

1. 若给定值等于根节点的关键码，则查找成功，返回指向需要查找元素的指针；
2. 若给定值小于根节点的关键码，则继续在根节点的左子树上进行递归查找；
3. 若给定值大于根节点的关键码，则继续在根节点的右子树上进行递归查找；

二叉查找树的递归查找算法实现代码如下：

TreeNode* Search(TreeNode* root, int target)
{
    if (root == nullptr) return nullptr;
    else if (target < root->val)
    {
        return Search(root->left, target);
    }
    else if (target > root->val)
    {
        return Search(root->right, target);
    }
    else return root;
}

由于递归算法的执行效率较低，因此可以改用非递归的算法实现二叉查找树。在非递归算法中，需要增加一个引用指针parent，若查找成功，则函数返回target所在节点的地址，parent返回该节点的双亲节点的地址；若查找不成功，则函数返回nullptr，parent返回新节点应插入的节点地址，此时新节点应作为叶节点被插入parent之下。

二叉查找树的非递归查找算法，代码如下：

TreeNode* Search(TreeNode* root, int target, TreeNode* &parent)
{
    TreeNode* p = root;
    parent = nullptr;
    while (p != nullptr && p->val != target)
    {
        parent = p;
        if (target < p->val) 
        {
            p = p->left;
        }
        if (target > p->val)
        {
            p = p->right;
        }
    }
    return p;
}

二、插入元素

在二叉查找树中插入一个新元素，首先要用查找算法检查该元素是否在树中已经存在。对于一个不存在于二叉查找树中的元素，其查找操作停止的位置即为该元素的插入位置。

二叉查找树的插入算法，代码如下：

void Insert(TreeNode* root, int x)
{
    TreeNode *p, *parent;
    p = Search(root, x, parent);   //寻找插入位置
    if (p != nullptr) return;      //查找成功，不插入
    TreeNode* s = new TreeNode(x); //查找失败，创建新节点
    if (parent != nullptr)
    {
        root = s;                  //原树为空，节点为根节点
    }
    else if (x < parent->val)
    {
        parent->left = s;          //原树非空，节点小于根节点作为左节点插入
    }
    else if (x > parent->val)
    {
        parent->right = s;         //原树非空，节点大于根节点作为右节点插入
    }
}

三、删除元素

在二叉查找树中删除元素，分为以下两种情况：

1. 被删节点有一颗子树为空或者两颗子树为空。如果被删节点*p的左子树为空，那么用指针s记下它的右子节点的地址（可能为空）；如果*p的左子树不为空，那么用s记下他的左子节点的地址。然后让*p的双亲节点中原来指向*p的指针指向s所指的节点，再释放*p节点。如果原来的*p是根节点，那么*s成为新的根节点。
2. 被删节点的左、右子树都不为空。在被删节点*p的右子树中寻找中序下的第一个节点*s（其元素关键码在其右子树中最小），用它的值填补到*s所指向的节点中，再让p=s，处理新的*p节点的删除，这是一个递归处理。

二叉查找树的删除算法，代码如下：

void Delete(TreeNode* root, int x)
{
    TreeNode* s, * p, * parent;
    p = Search(root, x, parent);  //查找待删除节点，返回其指针和父节点
    if (p == nullptr) return;     //查找失败，不执行删除
    if (p->left != nullptr && p->right != nullptr)   //待删除节点左右子树都不为空
    {
        s = p->right;
        parent = p;
        while (s->left != nullptr)
        {
            parent = s;
            s = s->left;
        }
        p->val = s->val;       //将s指向的数据赋给p
        p = s;   //*p成为待删除节点
    }
    if (p->left != nullptr) s = p->left;     //单子节点，记录非空子节点
    else s = p->right;

    if (p == root) root = s;   //被删除的节点为根节点
    else if (s && s->val < parent->val) parent->left = s;
    else parent->right = s;

    free(p);   //释放被删除节点
}