二叉搜索树的概念

二叉搜索树又称二叉排序树, 最基本形态就是一颗空树，它具有以下一个性质：
· 如果一个节点有左子树, 那么左子树上的节点值都小于该节点
· 如果一个节点有右子树, 那么右子树上的节点值都大于该节点

讯享网

#pragma once #include<iostream> using namespace std; namespace lq { 
    template <class T> class BarSortTreeN { 
    BarSortTreeN<T>* _Left; BarSortTreeN<T>* _Right; public: T _data; BarSortTreeN(const T& val = T()) :_Left(nullptr) , _Right(nullptr) , _data(val) { 
   } template <class T> friend class BinarysortTree; }; template <class T> class BinarysortTree { 
    BarSortTreeN<T>* _root; public: BinarysortTree() :_root(nullptr) { 
   } bool insert(const T& val) { 
    if (_root == nullptr) { 
    _root = new BarSortTreeN<T>(val); return true; } BarSortTreeN<T>* cur = _root; BarSortTreeN<T>* pre = nullptr; while (cur) { 
    if (val < cur->_data) { 
    pre = cur; cur = cur->_Left; } else if (val > cur->_data) { 
    pre = cur; cur = cur->_Right; } else { 
    return false; } } cur = new BarSortTreeN<T>(val); if (val < pre->_data) { 
    pre->_Left = cur; } if (val > pre->_data) { 
    pre->_Right = cur; } return true; } void Print() { 
    _Print(_root); cout << endl; } bool erase(const T& val) { 
    if (_root == nullptr) return false; BarSortTreeN<T>* pCur = _root; BarSortTreeN<T> arr; arr._Left = _root; BarSortTreeN<T>* pParent = &arr; while (pCur) { 
    if (pCur->_data == val) { 
    break; } else if (pCur->_data > val) { 
    pParent = pCur; pCur = pCur->_Left; } else { 
    pParent = pCur; pCur = pCur->_Right; } } if (pCur == nullptr) { 
    return false; } if (pCur->_Left && pCur->_Right) { 
    BarSortTreeN<T>* pCur2 = pCur->_Left; BarSortTreeN<T>* pParent2 = pCur; while (pCur2->_Right) { 
    pParent2 = pCur2; pCur2 = pCur2->_Right; } // for (; pCur2->_Right; pParent2 = pCur2, pCur2->_Right); #if 0  //交换法删除 将替换的值放在要删除的地方 然后删除替代的节点 比较简单 但是在节点比较大的时候 效率比较低 if (pParent2->_data > pCur2->_data) { 
    pParent2->_Left = pCur2->_Left; } else //一定要先链接节点 然后再换值 不然错误 { 
    pParent2->_Right = pCur2->_Left; } swap(pCur2->_data, pCur->_data); delete pCur2; #endif //代替节点交代上下文关系 if (pParent2->_data > pCur2->_data) { 
    pParent2->_Left = pCur2->_Left; } else // 这一点一定要先做 如果值换掉了之后在挂的话 那么里面的值已经变了 会发生错误 { 
    pParent2->_Right = pCur2->_Left; } pCur2->_Left = pCur->_Left; pCur2->_Right = pCur->_Right; if (pParent->_Left == _root) { 
    delete pCur; _root = pCur2; return true; } else { 
    if (pParent->_data > pCur->_data) { 
    pParent->_Left = pCur2; } else { 
    pParent->_Right = pCur2; } } //被删节点交代关系 delete pCur; return true; }else if (pCur->_Left) { 
    if (pParent->_data < pCur->_data) { 
    pParent->_Right = pCur->_Left; } else { 
    pParent->_Left = pCur->_Left; } delete pCur; }else if (pCur->_Right) { 
    if (pParent->_data < pCur->_data) { 
    pParent->_Right = pCur->_Right; } else { 
    pParent->_Left = pCur->_Right; } delete pCur; } else { 
    if (pParent->_data < pCur->_data) { 
    delete pCur; pParent->_Right = nullptr; } else { 
    delete pCur; pParent->_Left = nullptr; } } return true; } ~BinarysortTree() { 
    Destoy(_root); } BarSortTreeN<T>* Find(const T& data) { 
    if (_root == nullptr) { 
    return nullptr; } BarSortTreeN<T>* pCur = _root; while (pCur) { 
    if (pCur->_data == data) return pCur; else if (pCur->_data > data) { 
    pCur = pCur->_Left; } else { 
    pCur = pCur->_Right; } } return nullptr; } private: void _Print(BarSortTreeN<T>* root) { 
    if (root) { 
    _Print(root->_Left); std::cout << root->_data << " "; _Print(root->_Right); } } void Destoy(BarSortTreeN<T>*& root) //必须是& 不然是形参的拷贝 出错 { 
    if (root) { 
    Destoy(root->_Left); Destoy(root->_Right); delete root; root = nullptr; } } }; }; 

讯享网测试函数 void testTree() { 
    using namespace lq; BinarysortTree<int> Tree; Tree.insert(5); Tree.insert(3); Tree.insert(4); Tree.insert(1); Tree.insert(7); Tree.insert(8); Tree.insert(2); Tree.insert(6); Tree.insert(0); Tree.insert(9); Tree.insert(-1); Tree.insert(-3); Tree.insert(-1); Tree.Print(); Tree.erase(3); Tree.Print(); BarSortTreeN<int>* node; node=Tree.Find(7); //Tree.erase(7); //Tree.Print(); cout << " FIND->" << node->_data << endl; } 

树还有未完善的地方例如 没有增加迭代器 不可以一起插入多个，删除多个，完善也比较简单。