二叉搜索树查找，插入，删除

二叉排序树的查找过程通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).

查找算法:

在二叉排序树b中查找x的过程为：

若b是空树，则搜索失败，否则：

若x等于b的根结点的数据域之值，则查找成功；否则：

若x小于b的根结点的数据域之值，则搜索左子树；否则：

查找右子树。

插入算法:

向一个二叉排序树b中插入一个结点s的算法，过程为：

若b是空树，则将s所指结点作为根结点插入，否则：

若s->data等于b的根结点的数据域之值，则返回，否则：

若s->data小于b的根结点的数据域之值，则把s所指结点插入到左子树中，否则：

把s所指结点插入到右子树中。

删除算法:

在二叉排序树删去一个结点，分三种情况讨论：

（1）若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则只需直接删去接点即可

二叉搜索树查找，插入，删除

（2）若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树或右子树即可，作此修改也不破坏二叉排序树的特性。

二叉搜索树查找，插入，删除

（3）若*p结点的左子树和右子树均不空。

可分为两种类型，一种是z的后继y位于其右子树中，但没有左孩子，也就是说，右孩子y是其后继。如下：

二叉搜索树查找，插入，删除

另外一种类型是，z的后继y位于z的右子树中，但并不是z的右孩子，此时，用y的右孩子替换y，然后再用y替换z。如下：

二叉搜索树查找，插入，删除

#include <iostream>
using namespace std;


template<class K, class V>
struct BinarySearchTreeNode
{
    BinarySearchTreeNode(const K& key, const V& value)
        : _pLeft(NULL)
        , _pRight(NULL)
        , _key(key)
        , _value(value)
    {}

    BinarySearchTreeNode<K, V>* _pLeft;
    BinarySearchTreeNode<K, V>* _pRight;

    K _key;
    V _value;
};


template<class K, class V>
class BinarySearchTree
{
    typedef BinarySearchTreeNode<K, V> Node;
    typedef BinarySearchTree<K, V> Self;

public:
    BinarySearchTree()
        :_pRoot(NULL)
    {}


    BinarySearchTree(const Self& bst)
    {
        _pHead = _CopyTree(bst._pRoot);
    }

    Self& operator=(const Self& bst)
    {
        if(this != NULL)
        {
            _DestoryTree(_pRoot);
            _pRoot = _CopyTree(bst._pRoot);
            return *this;
        }
    }

    ~BinarySearchTree()
    {
        _DestoryTree(_pRoot);
    }

    // 查找递归和非递归
    bool Find_Nor(const K& key)
    {
        if(_pRoot == NULL)
            return false;

        Node* pCur = _pRoot;
        while(pCur)
        {
            if(_pRoot->_key == key)
                return true;
            else if(_pRoot->_key > key)
                pCur = pCur->_pRight;
            else
                pCur = pCur->_pLeft;
        }
        return false;
    }

    bool Find(const K& key)
    {
        return _Find(_pRoot, key);
    }

    // 插入递归和非递归
    bool Insert_Nor(const K& key, const V& value)
    {
        if (_pRoot == NULL)   
        {
            _pRoot = new Node(key, value);  
        }

        Node* pCur = _pRoot;
        Node* parent = NULL;

        //找到要插入节点的位置
        while(pCur)
        {
            if (pCur->_key > key)  
            {  
                parent = pCur;  
                pCur = pCur->_pLeft;  
            }  
            else if(pCur->_key < key)  
            {  
                parent = pCur;  
                pCur = pCur->_pRight;  
            }  
            else   //要么节点已存在，要么插入位置不合法  
                return false; 
        }
        //找到插入位置后，判断插入父亲节点是左还是右
        if(parent->_key > key)
            parent->_pLeft = new Node(key, value);
        else
            parent->_pRight = new Node(key, value);
    }

    bool Insert(const K& key, const V& value)
    {
        return _Insert(_pRoot, key, value);
    }

    // 删除递归和非递归
    bool Remove_Nor(const K& key)
    {
        //二叉搜索树中没有节点
        if(_pRoot == NULL)
            return false;

        //二叉搜索树中只有根节点
        if(_pRoot->_pLeft == NULL && _pRoot->_pRight == NULL)
        {
            if(_pRoot->_key == key)
            {
                delete _pRoot;
                _pRoot = NULL;
                return true;
            }
            return false;
        }

        Node* pCur = _pRoot;
        Node* parent = NULL;

        //遍历查找要删除节点的位置
        while(pCur)
        {
            Node* pDel = NULL; 
            if(pCur->_key < key)
            {
                parent = pCur;
                pCur = pCur->_pRight;
            }
            else if(pCur->_key > key)
            {
                parent = pCur;
                pCur = pCur->_pLeft;
            }
            else
            {
                //要删除节点的左子树为空
                if(pCur->_pLeft == NULL)
                {
                    //判断父节点是否为空，若为空，则要删除的节点为根节点
                    if (parent == NULL)  
                    {  
                        _pRoot = pCur->_pRight;  
                        delete pCur;  
                        pCur = NULL;  
                        return true;  
                    } 

                    else if(parent->_key < key)  //右子树
                    {
                        pDel = pCur;
                        parent->_pRight = pCur->_pRight;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                    else  //左子树
                    {
                        pDel = pCur;
                        parent->_pLeft = pCur->_pRight;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                }
                //要删除节点的右子树为空
                else if(pCur->_pRight == NULL)
                {
                    //判断父节点是否为空，若为空，则要删除的节点为根节点
                    if (parent == NULL)  
                    {  
                        _pRoot = pCur->_pLeft;  
                        delete pCur;  
                        pCur = NULL;  
                        return true;  
                    } 
                    else if(parent->_key > key)  //左子树
                    {
                        pDel = pCur;
                        parent->_pLeft = pCur->_pLeft;
                        delete pCur;
                        pCur = NULL;
                        return true;
                    }
                    else   //右子树
                    {
                        pDel = pCur;
                        parent->_pRight = pCur->_pLeft;
                        delete pDel;
                        pDel = NULL;
                        return true;
                    }
                }
                //左右子树都不为空
                //右子树中序遍历第一个节点，用它的值替换被删除节点的值，在进行删除
                else
                {
                    Node* pDel = pCur;  
                    Node* parent = NULL;  
                    Node* RightFirst = pCur->_pRight; 

                    //右边第一个节点的左子树为空 
                    if (RightFirst->_pLeft == NULL)  
                    {  
                        swap(RightFirst->_key, pCur->_key);  
                        swap(RightFirst->_value, pCur->_value);
                        //交换删除节点与中序遍历第一个节点的值,即就是最左边节点 
                        pDel = RightFirst;  
                        pCur->_pRight = RightFirst->_pRight;  
                        delete pDel;  
                        return true;  
                    } 

                    //右边第一个节点的左子树不为空  
                    while (RightFirst->_pLeft)  
                    {  
                        parent = RightFirst;  
                        RightFirst = RightFirst->_pLeft;  
                    }  
                    swap(RightFirst->_key, pCur->_key);  
                    swap(RightFirst->_value, pCur->_value);  
                    pDel = RightFirst;  
                    parent->_pLeft = RightFirst->_pRight;  
                    delete pDel;  
                    return true;    
                }
            }
        }
    }

    bool Remove(const K& key)
    {
        return _Remove(_pRoot, key);
    }

    void InOrder()
    {
        cout<<"中序遍历结果为:";
        _InOrder(_pRoot);
        cout<<endl;
    }

private:
    Node* _CopyTree(Node* pRoot)
    {
        if(pRoot)
        {
            Node* pNewNode = new Node(pRoot->_key, pRoot->_value);
            pNewNode->_pLeft = _CopyTree(pRoot->_pLeft);
            pNewNode->_pRight = _CopyTree(pRoot->_pRight);

            return pNewNode;
        }
        return NULL;
    }

    void _DestoryTree(Node*& pRoot)
    {
        if(pRoot)
        {
            _DestoryTree(pRoot->_pLeft);
            _DestoryTree(pRoot->_pRight);
            delete pRoot;
            pRoot = NULL;
        }
    }

    bool _Find(Node* pRoot, const K& key)
    {
        if(pRoot == NULL)
            return false;

        if(pRoot->_key == key)
            return true;

        if(pRoot->_key > key)
            _Find(pRoot->_pRight, key);

        if(pRoot->_key < key)
            _Find(pRoot->_pLeft, key);
    }

    bool _Insert(Node* &pRoot, const K& key, const V& value)
    {
        if(pRoot == NULL)
            pRoot = new Node(key, value);

        if(pRoot->_key > key)
            _Insert(pRoot->_pLeft, key, value);

        else if (pRoot->_key < key)
            _Insert(pRoot->_pRight, key, value);

        else 
            return false;
    }

    bool _Remove(Node*& pRoot, const K& key)
    {
        if(pRoot == NULL) //空树
            return false;

        //只有根节点
        if(pRoot->_pLeft == NULL && pRoot->_pRight == NULL)
        {
            if(pRoot->_key == key)
            {
                delete pRoot;
                pRoot = NULL;
                return true;
            }
            else
                return false;
        }

        //递归查找要删除节点的位置
        if(pRoot->_key >  key)
            _Remove(pRoot->_pLeft, key);
        else if(pRoot->_key < key)
            _Remove(pRoot->_pRight, key);
        else
        {
            Node* pDel = NULL;

            //要删除的节点只有右孩子
            if(pRoot->_pLeft == NULL)
            {
                pDel = pRoot;
                pRoot = pRoot->_pRight;
                delete pDel;
                pDel = NULL;
                return true;
            }

            //要删除的节点只有左孩子
            else if(pRoot->_pRight == NULL)
            {
                pDel = pRoot;
                pRoot = pRoot->_pLeft;
                delete pDel;
                pDel = NULL;
                return true;
            }

            //要删除的节点有左右孩子
            else
            {
                Node* RightFirst = pRoot->_pRight;
                while(RightFirst->_pLeft)
                    RightFirst = RightFirst->_pLeft;

                swap(pRoot->_key, RightFirst->_key);  
                swap(pRoot->_value, RightFirst->_value);  

                _Remove(pRoot->_pRight, key);  
                return true; 
            }
        }
        return false;
    }

    void _InOrder(Node* pRoot)
    {
        if(pRoot)
        {
            _InOrder(pRoot->_pLeft);
            cout<<pRoot->_key<<" ";
            _InOrder(pRoot->_pRight);
        }
    }
private:
    Node* _pRoot;
};

// 测试非递归的三种情况
void Test1()
{
    BinarySearchTree<int, int> bst;
    int a [] = {5,3,4,1,7,8,2,6,0,9,};
    int len = sizeof(a)/sizeof(a[]);

    for(size_t idx=0; idx<len; ++idx)
    {
        bst.Insert_Nor(a[idx], a[idx]);
    }

    bst.InOrder();
    bst.Find_Nor(2);
    bst.InOrder();
    bst.Find_Nor(0);
    bst.InOrder();
    bst.Find_Nor(5);
    bst.InOrder();
    bst.Find_Nor(10);
    bst.InOrder();

    //要删除节点左右子树都为空
    bst.Remove_Nor(4);
    bst.InOrder();

    //要删除节点右子树为空
    bst.Remove_Nor(9);
    bst.InOrder();

    bst.Remove_Nor(0);
    bst.InOrder();

    //要删除节点左子树为空
    bst.Remove_Nor(4);
    bst.InOrder();

    //要删除节点左右子树都不为空
    bst.Remove_Nor(5);
    bst.InOrder();
}


// 测试递归的三种情况
void Test2()
{
    BinarySearchTree<int, int> bst;
    int a [] = {5,3,4,1,7,8,2,6,0,9,};
    int len = sizeof(a)/sizeof(a[]);

    for(size_t idx=0; idx<len; ++idx)
    {
        bst.Insert(a[idx], a[idx]);
    }

    bst.InOrder();
    bst.Find(2);
    bst.InOrder();
    bst.Find(0);
    bst.InOrder();
    bst.Find(5);
    bst.InOrder();
    bst.Find(10);
    bst.InOrder();

    //要删除节点左右子树都为空
    bst.Remove(4);
    bst.InOrder();

    //要删除节点右子树为空
    bst.Remove(9);
    bst.InOrder();

    bst.Remove(0);
    bst.InOrder();

    //要删除节点左子树为空
    bst.Remove(4);
    bst.InOrder();

    //要删除节点左右子树都不为空
    bst.Remove(5);
    bst.InOrder();
}

int main()
{
    //Test1();
    Test2();

    system("pause");
    return 0;
}

二叉搜索树查找，插入，删除

查找算法:

插入算法:

删除算法:

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器