二叉查找树又称二叉排序树，它要么是空树，要么是具有下列性质的二叉树：
- 每个节点都有一个作为查找依据的关键码。所有节点的关键码互不相同；
- 若它的左子树不为空，则左子树上所有节点的关键码均小于根节点的关键码；
- 若它的右子树不为空，则右子树上所有节点的关键码均大于根节点的关键码；
- 它的左、右子树也是二叉查找树。
一、查找元素
若二叉查找树的根节点的指针为空，则查找不成功；否则进行一下的操作：
- 若给定值等于根节点的关键码，则查找成功，返回指向需要查找元素的指针；
- 若给定值小于根节点的关键码，则继续在根节点的左子树上进行递归查找；
- 若给定值大于根节点的关键码，则继续在根节点的右子树上进行递归查找；
二叉查找树的递归查找算法实现代码如下：
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; //原树非空，节点大于根节点作为右节点插入 } }
三、删除元素
在二叉查找树中删除元素，分为以下两种情况：
- 被删节点有一颗子树为空或者两颗子树为空。如果被删节点*p的左子树为空，那么用指针s记下它的右子节点的地址（可能为空）；如果*p的左子树不为空，那么用s记下他的左子节点的地址。然后让*p的双亲节点中原来指向*p的指针指向s所指的节点，再释放*p节点。如果原来的*p是根节点，那么*s成为新的根节点。
- 被删节点的左、右子树都不为空。在被删节点*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); //释放被删除节点 }