二叉查找树，也称二叉排序树，二叉搜索树。
它或者是一棵空树；或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 左、右子树也分别为二叉排序树

查找操作

步骤：

• 若根结点的关键字值等于查找的关键字，成功。
• 否则，若小于根结点的关键字值，递归查左子树；若大于根结点的关键字值，递归查右子树。
• 若子树为空，查找不成功。

插入操作

步骤：

• 首先执行查找算法，找出被插结点的父亲结点。
• 判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
• 若二叉树为空，则首先单独生成根结点。
  注意：新插入的结点总是叶子结点。

删除操作

假设被删结点是*p，其双亲是*f，不失一般性，设*p是*f的左孩子，下面分三种情况讨论：

• 若结点*p是叶子结点，则只需修改其双亲结点*f的指针即可。
• 若结点*p只有左子树PL或者只有右子树PR，则只要使PL或PR 成为其双亲结点的左子树即可。
• 若结点*p的左、右子树均非空，先找到*p的中序前趋结点*s（注意*s是*p的左子树中的最右下的结点，它的右链域为空），然后有两种做法：
  
  • 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
  • 以*p的中序前趋结点*s代替*p（即把*s的数据复制到*p中），将*s的左子树链到*s的双亲结点*q的左（或右）链上。

C++实现代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

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

TreeNode* minNode(TreeNode *root)
{
//    if (root != NULL && root->left != NULL)
//    {
//        return minNode(root->left);
//    }
    while (root != NULL && root->left != NULL)
    {
        root = root->left;
    }

    return root;
}

TreeNode* maxNode(TreeNode *root)
{
    if (root != NULL && root->right != NULL)
    {
        return maxNode(root->right);
    }

    return root;
}

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

void insertNode(TreeNode*& root, int value)
{
    if (search(root, value) != NULL)
    {
        return;
    }

    TreeNode *newnode = new TreeNode(value);
    TreeNode *temp = root;
    TreeNode *parentNode = NULL;
    if (root == NULL)
    {
        root = newnode; //新插入结点成为根结点
        return;
    }

    while (temp != NULL)
    {
        parentNode = temp;
        if (temp->val > value)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }

    if (value < parentNode->val)
    {
        parentNode->left = newnode;
    }
    else
    {
        parentNode->right = newnode;
    }
    newnode->parent = parentNode;
}

bool deleteNode(TreeNode*& root, int value)
{
    TreeNode *cur = search(root, value);
    TreeNode *temp;
    if (cur == NULL)
    {
        return false; //未找到结点
    }
    if (cur->left != NULL && cur->right != NULL)
    {
        TreeNode *max_node = maxNode(cur->left);
        cur->val = max_node->val;
        deleteNode(max_node, max_node->val);
    }
    else
    {
        if (cur->left == NULL && cur->right == NULL) //删除叶子结点
        {
            temp = NULL;
        }
        else if (cur->left == NULL) //要删除结点的左结点为空
        {
            temp = cur->right;
        }
        else if (cur->right == NULL) //要删除结点的右结点为空
        {
            temp = cur->left;
        }

        if (cur->parent == NULL)
        {
            root = temp;
            if (temp != NULL) temp->parent = NULL;
        }
        else
        {
            if (cur->parent->left == cur)
            {
                cur->parent->left = temp;
            }
            else
            {
                cur->parent->right = temp;
            }

            if (temp != NULL)
            {
                temp->parent = cur->parent;
            }

        }

        delete cur;
    }

    return true;
}

void preTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        cout<<root->val<<" ";
        preTraverse(root->left);
        preTraverse(root->right);
    }
}

void inTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        inTraverse(root->left);
        cout<<root->val<<" ";
        inTraverse(root->right);
    }
}

void postTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        postTraverse(root->left);
        postTraverse(root->right);
        cout<<root->val<<" ";
    }
}

int main()
{
    TreeNode *root = NULL;
    for (int i = 0; i < 20; i++)
    {
        insertNode(root, rand() % 100);
    }

    cout<<"先序遍历：";preTraverse(root);cout<<" END"<<endl;
    cout<<"中序遍历：";inTraverse(root);cout<<" END"<<endl;
    cout<<"后序遍历：";postTraverse(root);cout<<" END"<<endl;

    for (int  i = 0; i < 20; i++)
    {
        deleteNode(root, i);
    }
    cout<<"先序遍历：";preTraverse(root);cout<<" END"<<endl;

    TreeNode *temp = minNode(root);
    temp != NULL ? cout<<temp->val<<endl : cout<<"null"<<endl;
    temp = maxNode(root);
    temp != NULL ? cout<<temp->val<<endl : cout<<"null"<<endl;

    return 0;
}

Java实现代码：

package test;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    TreeNode(int x){
        this.val = x;
    }
}

public class BinarySearchTree {
    TreeNode root;
    TreeNode maxElem(TreeNode node){
        while (node != null && node.right != null){
            node = node.right;
        }

        return node;
    }

    TreeNode minElem(TreeNode node){
        while (node != null && node.left != null){
            node = node.left;
        }

        return node;
    }

    TreeNode search(int key){
        TreeNode temp = root;
        while (temp != null && temp.val != key){
            if (temp.val > key){
                temp = temp.left;
            }else{
                temp = temp.right;
            }
        }

        return temp;
    }

    boolean insert(int key){
        if (search(key) != null){
            return false;
        }

        TreeNode newnode = new TreeNode(key);
        TreeNode temp = root;
        if (temp == null){
            this.root = newnode;
            return true;
        }

        TreeNode parentNode = null;
        while (temp != null){
            parentNode = temp;
            if (temp.val > key){
                temp = temp.left;
            }else{
                temp = temp.right;
            }
        }
        if (parentNode.val > key){
            parentNode.left = newnode;
        }else{
            parentNode.right = newnode;
        }
        newnode.parent = parentNode;

        return true;
    }

    boolean delete(int key){
        TreeNode cur = search(key);
        if (cur == null){
            return false;
        }

        TreeNode temp = null;
        if (cur.left != null && cur.right != null){
            TreeNode leftMax = maxElem(cur.left);
            cur.val = leftMax.val;
            delete(leftMax.val);
        }else if (cur.left == null && cur.right == null){
            temp = null;
        }else if (cur.left != null && cur.right == null){
            temp = cur.left;
        }else if (cur.left == null && cur.right != null){
            temp = cur.right;
        }

        if (cur.parent == null){
            this.root = temp;
            if (temp != null){
                temp.parent = null;
            }
        }
        else{
            if (cur.parent.left == cur){
                cur.parent.left = temp;
            }else{
                cur.parent.right = temp;
            }

            if (temp != null){
                temp.parent = cur.parent;
            }
        }

        return true;
    }

    void preTraverse(TreeNode node){
        if (node != null){
            System.out.print(node.val + " ");
            preTraverse(node.left);
            preTraverse(node.right);
        }
    }

    void inTraverse(TreeNode node){
        if (node != null){
            inTraverse(node.left);
            System.out.print(node.val + " ");
            inTraverse(node.right);
        }
    }

    void postTraverse(TreeNode node){
        if (node != null){
            postTraverse(node.left);
            postTraverse(node.right);
            System.out.print(node.val + " ");
        }
    }

    public static void main(String[] args){
        BinarySearchTree bst = new BinarySearchTree();
        for (int i = 0; i < 20; i++){
            bst.insert((int)(Math.random() * 100));
            //bst.insert(i);
        }
        System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();
        System.out.print("中序遍历："); bst.inTraverse(bst.root); System.out.println();
        System.out.print("后序遍历："); bst.postTraverse(bst.root); System.out.println();

        for (int i = 0; i < 20; i++){
            bst.delete(i);
        }
        System.out.print("前序遍历："); bst.preTraverse(bst.root); System.out.println();
        System.out.println("Max:" + bst.maxElem(bst.root).val);
        System.out.println("Min:" + bst.minElem(bst.root).val);
    }
}

Python实现代码：

from random import random
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.parent = None

class BinarySearchTree:   
    def __init__(self, root = None):
        self.root = root

    def minElem(self, node):
        temp = node
        while temp and temp.left:
            temp = temp.left
        return temp;

    def maxElem(self, node):
        temp = node
        while temp and temp.right:
            temp = temp.right
        return temp;

    def search(self, node, key):
        if not node:
            return None
        if node.val == key:
            return node
        elif node.val > key:
            return self.search(node.left, key)
        else:
            return self.search(node.right, key)

    def insert(self, key):
        if self.search(self.root, key):
            return
        newnode = TreeNode(key)
        if not self.root:
            self.root = newnode
            return
        parentNode = None
        temp = self.root
        while temp:
            parentNode = temp
            if temp.val > key:
                temp = temp.left
            else:
                temp = temp.right
        if parentNode.val > key:
            parentNode.left = newnode
        else:
            parentNode.right = newnode
        newnode.parent = parentNode

    def delete(self, key):
        cur = self.search(self.root, key)
        if not cur:
            return
        if cur.left and cur.right:
            leftMax = self.maxElem(cur.left)
            n = leftMax.val
            self.delete(leftMax)
            cur.val = n
        else:
            temp = None
            if cur.left:
                temp = cur.left
            elif cur.left:
                temp = cur.right

            if not cur.parent:
                self.root = temp
                temp.parent = None
            else:
                if cur.parent.left == cur:
                    cur.parent.left = temp
                else:
                    cur.parent.right = temp
                if temp:
                    temp.parent = cur.parent

    def preorderTraverse(self, node):
        if node:
            print(node.val,end = ' ')
            self.preorderTraverse(node.left)
            self.preorderTraverse(node.right)

bst = BinarySearchTree();
for i in range(0, 20):
    bst.insert(int(random()*100))
bst.preorderTraverse(bst.root)   
print()
for i in range(0, 20):
    bst.delete(i);
bst.preorderTraverse(bst.root)   
print('\nThe smallest element is %d.' % bst.minElem(bst.root).val)
print('The largest element is %d.' % bst.maxElem(bst.root).val)

没有父亲指针的C++实现代码：

#include <iostream>
#include <algorithm>
using namespace std;

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

TreeNode* search(TreeNode *root, int key)
{
    while (root != NULL)
    {
        if (root->val > key)
        {
            root = root->left;
        }
        else if (root->val < key)
        {
            root = root->right;
        }
        else
        {
            break;
        }
    }

    return root;
}

void insertNode(TreeNode*& root, int key)
{
    TreeNode *p = root;
    TreeNode *q;
    while (p != NULL)
    {
        if (p->val > key)
        {
            q = p;
            p = p->left;
        }
        else if (p->val < key)
        {
            q = p;
            p = p->right;
        }
        else
        {
            break;
        }
    }

    if (p != NULL)
    {
        return;
    }

    TreeNode *newnode = new TreeNode(key);
    if (root == NULL)
    {
        root = newnode;
        return;
    }

    if (q->val > key)
    {
        q->left = newnode;
    }
    else
    {
        q->right = newnode;
    }
}

void deleteNode(TreeNode*& root, int key)
{
    TreeNode *p = root;
    TreeNode *q;
    while (p != NULL)
    {
        if (p->val > key)
        {
            q = p;
            p = p->left;
        }
        else if (p->val < key)
        {
            q = p;
            p = p->right;
        }
        else
        {
            break;
        }
    }

    if (p == NULL)
    {
        return;
    }

    if (p->left != NULL && p->right != NULL)
    {
        TreeNode *s = p->left;
        TreeNode *t = p;
        while (s->right != NULL)
        {
            t = s;
            s = s->right;
        }

        p->val = s->val;
        if (t == p)
        {
            p->left = s->left;
        }
        else
        {
            t->right = s->left;
        }

        delete s;
    }
    else
    {
        TreeNode *temp;
        if (p->left == NULL && p->right == NULL)
        {
            temp = NULL;
        }
        else if (p->left == NULL)
        {
            temp = p->right;
        }
        else
        {
            temp = p->left;
        }

        if (p == root)
        {
            root = temp;
        }
        else
        {
            if (q->left == p)
            {
                q->left = temp;
            }
            else
            {
                q->right = temp;
            }
        }

        delete p;
    }
}

void preorderTraverse(TreeNode *root)
{
    if (root != NULL)
    {
        cout<<root->val<<" ";
        preorderTraverse(root->left);
        preorderTraverse(root->right);
    }
}

int main()
{
    TreeNode *root = NULL;
    for (int i = 0; i < 20; i++)
    {
        insertNode(root, rand() % 50);
    }
    preorderTraverse(root); cout<<endl;

    for (int i = 0; i < 20; i++)
    {
        deleteNode(root, i);
    }
    preorderTraverse(root); cout<<endl;
}