STL源码笔记（17）—二叉排序树BST（C++封装）

stl中还有一类非常重要的容器，就是关联容器，比如map啊set啊等等，这些容器说实话，在应用层上还不能完全得心应手（比如几种容器效率的考虑等等），更别说了，因此这一部分打算稳扎稳打，好好做做笔记研究一番。
说到关联容器，我们想到了什么avl树，红黑树等等，但大多时候我们仅仅局限于知道其名字，或者知道其概念，俗话说“talk is cheap，show me the code”，因此，我打算从他们的祖爷爷二叉排序树开始下手。（其实，侯老师的书上也是这么安排的哈）

1.概念

1.任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2.任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3.任意节点的左、右子树也分别为二叉查找树；
4.没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为o(logn)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

---

2.性质

1.中序遍历是一个升序的有序序列。
2.搜索、插入、删除的复杂度等于树高，期望o(logn)，最坏o(n)（数列有序，树退化成线性表）。

---

3.二叉排序树的实现

既然看到此，不如试着实现一下二叉排序树，主要需要包含这些操作：构建二叉排序树输入一个序列输出一个二叉排序树，插入、删除节点。

写代码之前考虑的问题：

1.二叉排序树的插入一定是在叶子节点处。

2.二叉排序树的删除需要考虑三种情况：
　　a）待删除节点在叶子节点处
　　　　直接另其父节点相应指针制空，并删除该节点即可。
　　b）待删除节点只含有一个孩子（左子树为空或者右子树为空）
　　　　将待删除节点父节点对应指针指向待删除节点的孩子节点。
　　c）待删除节点即包含左右孩子都不为空
　　　　找到待删除节点的右子树的最小值（右子树一路向左），并将该值替换待删除节点的值，最后删除最小值原本所在位置的节点（叶子节点）。

3.二叉排序树的中序遍历是升序。
4.摈弃以前的c语言写法，我这次想把bst封装成一个c++类，虽然困难重重，勉强实现了吧。
5.既然是c++类，在析构函数中做所有节点内存释放处理（最后一个根节点需要特殊处理）。

上述5个问题中除了对c++的熟悉程度外，涉及bst算法部分最麻烦的就是删除操作了，因为它考虑的情况比较多，这里贴出侯老师书中的示意图方便理解：

目标节点只有一个孩子节点

 

 喎? f/ware/vc/"="" target="_blank" class="keylink">vcd4ncjxoncbpzd0="目标节点有两个子节点">目标节点有两个子节点

 

 

---

代码

编译运行环境：visual studio 2013，windows 7 32 bits

（1）二叉排序树的节点数据结构

//bstnode.h
#ifndef __bstnode_h__
#define __bstnode_h__
#include
class bstnode{
public:
    bstnode();
    bstnode(int val);
    int value;
    bstnode *lchild;
    bstnode *rchild;
};
#endif

//--------------------------------------------
//--------------------------------------------
//--------------------------------------------

//bstnode.cpp
#include "bstnode.h"
bstnode::bstnode()
{
    value = 0;
    lchild = null;
    rchild = null;
}
bstnode::bstnode(int val)
{
    value = val;
    lchild = null;
    rchild = null;
}

（2）二叉排序树的c++类封装

//bst.h
#ifndef __bst_h__
#define __bst_h__
#include "bstnode.h"
#include 
#include 
class bstnode;
class bst
{
    //说明：
    //为了数据结构私有化，不为外部访问，这里提供一些私有内部函数实现真正的操作以"__"开头。
    //对于public的接口来说，只需要直接调用内部函数即可
private:
    bstnode * bstroot;//二叉排序树数据结构
    bstnode * __search(bstnode* root,const int& key);//查找关键字
    bstnode * __treemin(bstnode*const root,bstnode *&parent);//返回当前节点的最小孩子（一路向左）
    bstnode * __treemax(bstnode*const root);//查找最大值（未实现）
    bool __insert( const int &key);//插入节点
    bool __delete(const int &key);//删除删除
    bool __isleaf(bstnode* const &);//判断是否是叶子节点
    bool __isnodewithtwochild(bstnode * const &);//判断是否有两个孩子
    void __inordertraversal(bstnode *root,std::vector&result);//中序遍历
    void __deleteallnodes(bstnode *root);//删除所有节点
public:
    //构造函数
    bst();//默认构造函数
    bst(std::vectorarr);
    bst(int *arr, int len);
    //析构函数
    ~bst();
    bool isempty() const;//判断树空
    bool search(const int &key);//查找关键字是否存在的对外接口
    bool insert(const int &key);//插入节点的外部接口
    bool delete(const int &key);//删除节点的外部接口
    void inordertraversal(std::vector&);//中序遍历的外部接口
};
#endif

（3）二叉排序树c++类实现部分

//bst.cpp

#include "bst.h"

//判断树空
bool bst::isempty() const
{
    return bstroot == null;
}

//判断是否是叶子节点（删除部分用到）
bool bst::__isleaf(bstnode*const & root)
{
    if ((root->lchild == null) && (root->rchild == null))
        return true;
    else
        return false;
}

//判断节点是否有两个孩子（删除部分用到）
bool bst::__isnodewithtwochild(bstnode * const & root)
{
    if (root->lchild != null &&root->rchild != null)
        return true;
    else
        return false;
}

//找到当前节点为根的子树中的最小值（删除部分用到，因此返回其父节点和当前节点）
bstnode * bst::__treemin(bstnode*const root,bstnode *&parent)
{
    bstnode * curr = root;
    while (curr->lchild != null)
    {
        parent = curr;
        curr = curr->lchild;
    }
    return curr;
}

//删除节点内部实现
bool bst::__delete(const int &key)
{
    bool found = false;//找到待删除的元素
    if (isempty())
    {
        std::cerr << "binary search tree is empty" << std::endl;//bst为空
        return false;
    }
    bstnode * curr = bstroot;
    bstnode *parent = null;
    while (curr != null)//查找待删除节点
    {

        if (key == curr->value)
        {
            found = true;
            break;
        }
        else 
        {
            parent = curr;
            if (key < curr->value)
                curr = curr->lchild;
            else
                curr = curr->rchild;
        }
    }
    if (!found)
    {
        std::cerr << "keyvalue not found" << std::endl;
        return false;
    }
    if (null == parent)//删除最后一个节点(根节点需要特殊处理)
    {
        bstroot = null;
        delete curr;
        return true;
    }
    //对于待删除的节点有三种可能：
    //1.叶子节点
    //2.只包含左子树或者右子树（单个孩子）
    //3.既包含左子树又包含右子树
    //删除节点的时候需要分3种情况进行考虑

    if (__isleaf(curr))//叶子节点
    {
        if (parent->lchild == curr)
            parent->lchild = null;
        else
            parent->rchild = null;
        delete curr;
        return true;
    }//end if
    else if (__isnodewithtwochild(curr))//有两个孩子的节点
    {
        //以当前节点的右子树中的最小值取代它
        bstnode*parent=curr;
        bstnode *tmp = __treemin(curr->rchild,parent);
        curr->value = tmp->value;
        if (parent->rchild == tmp)
            parent->rchild = null;
        else
            parent->lchild = null;
        delete tmp;
        return true;
    }//end else-if
    else//只有一个孩子的节点
    {
        if (curr->lchild != null)//只有左孩子
        {
            if (parent->lchild == curr)
            {
                parent->lchild = curr->lchild;
                delete curr;
                return true;
            }
            else
            {
                parent->rchild = curr->lchild;
                delete  curr;
                return true;
            }
        }
        if (curr->rchild != null)//只有右孩子
        {
            if (parent->lchild == curr)
            {
                parent->lchild = curr->rchild;
                delete curr;
                return true;
            }
            else
            {
                parent->rchild = curr->rchild;
                delete  curr;
                return true;
            }
        }
    }//end else
    return false;
}
//删除操作的外部接口
bool bst::delete(const int &key)
{
    return __delete(key);
}

//插入节点的内部实现，插入操作一定都在叶子节点处。
bool bst::__insert(const int & key)
{
    bstnode* t = new bstnode(key);//临时节点
    bstnode*parent = null;
    if (isempty())//新树
    {
        bstroot = t;
        return true;
    }
    else
    {
        bstnode* curr;
        curr = bstroot;
        while (curr)
        {
            //插入位置都位于叶子节点处
            parent = curr;
            if (t->value > curr->value)
                curr = curr->rchild;
            else
                curr = curr->lchild;
        }
        if (t->value < parent->value)
        {
            parent->lchild = t;
            return true;
        }
        else
        {
            parent->rchild = t;
            return true;
        }
    }
    return false;
}
//插入节点的外部接口
bool bst::insert(const int &key)
{
    return __insert(key);
}

//构造函数
bst::bst()//默认构造函数
{
    bstroot = null;
}
bst::bst(int*arr, int len)//数组构造
{
    bstroot = null;
    for (int i = 0; i < len; i++)
    {
        __insert(*(arr + i));
    }
}

bst::bst(std::vectorarr)//容器构造
{
    bstroot = null;
    for (int i = 0; i < (int)arr.size(); i++)
    {
        __insert(arr[i]);
    }
}

//内部查找函数
//递归调用
bstnode* bst::__search(bstnode*root,const int& key)
{
    if (null == root)
        return null;
    if (key == root->value)
        return root;
    else if (key < root->value)
        return __search(root->lchild, key);
    else
        return __search(root->rchild, key);
}
//查找函数接口
bool bst::search(const int& key)
{
    bstnode*t = __search(bstroot, key);
    return t == null ? false : true; 
}

//中序遍历内部实现
void bst::__inordertraversal(bstnode *root,std::vector&result)
{
    if (null == root)
        return;
    __inordertraversal(root->lchild, result);
    std::cout << root->value << " ";
    result.push_back(root->value);
    __inordertraversal(root->rchild, result);
}
//中序遍历接口，vector保存遍历结果
void bst::inordertraversal(std::vector&result)
{
    __inordertraversal(bstroot, result);
}

//删除所有节点（析构用）
void bst::__deleteallnodes(bstnode *root)
{
    if (root == null)
    {
        return;
    }
    __deleteallnodes(root->lchild);
    __deleteallnodes(root->rchild);
    __delete(root->value);
}

//析构函数
bst::~bst()
{
    bstnode*curr = bstroot;
    __deleteallnodes(curr);
}

（4）二叉排序树的测试代码

//main.cpp
#include "bst.h"
int main()
{
    std::vectorvec = { 8,6,2,5,1,3,7 };
    bst bst(vec);
    bst.delete(9);//not found

    bst.insert(4);
    bool found=bst.search(4);
    if (!found)
        std::cout << "not found" << std::endl;
    else
        std::cout << "found!" << std::endl;
    std::vectorresult;
    bst.inordertraversal(result);
    std::cout << std::endl;
    for (int i = 0; i < result.size(); i++)
    {
        std::cout << result[i] << " ";
    }
    std::cout << std::endl;
    system("pause");
    return 0;
}

 

喎?>