清泉逐流

做着努力,等待幸福到来

Binary search tree

作者:Eamonn 时间 : 2014-09-10 20:12 分类:C/C++

#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
template <typename T>
struct BNode{
    BNode *l;
    BNode *r;
    T data;
};
template <typename T>
class BSTree{
    public:
        static const int PRE_ORDER = 1;
        static const int POST_ORDER = 1;
        static const int IN_ORDER = 1;
       
        BSTree();
        ~BSTree();
           
        bool Insert(T data);
        bool Delete(T data);
        BNode<T> *Find(T data);
        void Destory(void);
        void Print(void);
        void PrintByLevel(void);
       
    private:
        BNode<T> *m_root;
        void PrintNode(BNode<T> *node);
        void DestoryNode(BNode<T> *node);
               
};
template <typename T>
BSTree<T>::BSTree()
{
    m_root = NULL;
}
template <typename T>
BSTree<T>::~BSTree()
{
    if(m_root){
        Destory();
    }
}
template <typename T>
bool BSTree<T>::Insert(T data)
{
    if( NULL == m_root ){
        m_root = new BNode<T>;
        m_root->data = data;
        m_root->l = m_root->r = NULL;
        return true;
    }
       
    BNode<T> *tmp = m_root;
    while(true){
        if( data > tmp->data ){
            if( tmp->r ){
                tmp = tmp->r;
            }else{
                break;
            }
        }else if( data < tmp->data ){
            if( tmp->l ){
                tmp = tmp->l;
            }else{
                break;
            }
        }else{
            return false;
        }
    }
       
    if(tmp){
           
        BNode<T> *t = new BNode<T>;
        t->l = t->r = NULL;
        t->data = data;
           
        if( data > tmp->data ){
            tmp->r = t;
        }else{
            tmp->l = t;
        }
           
        return true;
           
    }
    return false;
}
template <typename T>
bool BSTree<T>::Delete(T data)
{
    BNode<T> *curr = m_root;
    BNode<T> *parent = NULL;
    while(curr){
        if( data > curr->data ){
            if( curr->r ){
                parent = curr;
                curr = curr->r;
            }else{
                return false;
            }
        }else if( data < curr->data ){
            if( curr->l ){
                parent = curr;
                curr = curr->l;
            }else{
                return false;
            }
        }else if( data == curr->data ){
            break;
        }
           
    }
           
    if(curr){
           
        // 1. leaf node
        if( !curr->l && !curr->r ){
            if(parent){
                if(parent->l==curr){
                    parent->l = NULL;
                }else{
                    parent->r = NULL;
                }
                delete curr;
            }else{
                delete curr;
                m_root = NULL;
            }
            return true;
        }
           
        // 2. node with a single child
        else if( (!curr->l && curr->r) || (curr->l && !curr->r) ){
               
            if(parent){
                   
                if(parent->l==curr){
                    if(curr->l){
                        parent->l = curr->l;
                    }else{
                        parent->l = curr->r;
                    }
                }else{
                    if(curr->l){
                        parent->r = curr->l;
                    }else{
                        parent->r = curr->r;
                    }
                }
                delete curr;
                   
            }else{
                if(curr->l){
                    m_root = curr->l;
                }else{
                    m_root = curr->r;
                }
                delete curr;
            }
            return true;
               
        }
           
        // 3. node with 2 children
        else if( curr->l && curr->r){
               
            BNode<T> *successor=curr->r;
            BNode<T> *successorParent=curr;
            while(successor->l){
                successorParent = successor;
                successor = successor->l;
            }
               
            if( parent ){
                if(curr == parent->l){
                    parent->l = successor;
                }else{
                    parent->r = successor;
                }
            }else{
                m_root = successor;
            }
               
            successor->l = curr->l;
            if(curr->r!=successor){
                successorParent->l = successor->r;
                successor->r = curr->r;  
            }
               
            delete curr;
               
        }
           
    }
    return false;
}
template <typename T>
BNode<T> *BSTree<T>::Find(T data)
{
    BNode<T> *p = m_root;
    while(p){
        if( data > p->data ){
            if( p->r ){
                p = p->r;
            }else{
                return NULL;
            }
        }else if( data < p->data ){
            if( p->l ){
                p = p->l;
            }else{
                return NULL;
            }
        }else if( data == p->data ){
            return p;
        }
    }
    return NULL;
}
template <typename T>
void BSTree<T>::Destory(void)
{
    DestoryNode(m_root);
    m_root = NULL;
}
template <typename T>
void BSTree<T>::DestoryNode(BNode<T> *node)
{
    if(node){
        DestoryNode(node->l);
        DestoryNode(node->r);
        delete node;
    }
}
template <typename T>
void BSTree<T>::Print(void)
{
    cout << "PreOrder : " ;
    PrintNode(m_root);
    cout << endl;
}
// print in pre-order
template <typename T>
void BSTree<T>::PrintNode(BNode<T> *node)
{
    if(node){
        cout << node->data << " ";
        PrintNode(node->l);
        PrintNode(node->r);
    }
}
template <typename T>
void BSTree<T>::PrintByLevel(void)
{
    cout << "PrintLevel : " << endl;
    if(m_root){
        deque<BNode<T>*> dq;
        BNode<T> *curr= m_root;
        BNode<T> *end = curr;
        while(true){
            if (curr->l){
                dq.push_back(curr->l);  
            }
            if (curr->r){
                dq.push_back(curr->r);
            }
            cout << curr->data;
            if (curr != end){
                cout << " ";
            }else{
                cout << "\n";
                if (dq.empty()){
                    break; 
                }
                end = dq.back();
            }
            curr = dq.front();
            dq.pop_front();
           
        }
    }
}
int main(int argc, char *argv[])
{
       
    BSTree<int> bt;
       
       
       
    bt.Insert(10);
    bt.Insert(5);
    bt.Insert(15);
    bt.Insert(3);
    bt.Insert(6);
    bt.Insert(1);
    bt.Insert(4);
    bt.Insert(7);
    bt.Insert(12);
    bt.Insert(20);
    bt.Insert(24);
       
    if( bt.Find(4) ){
        cout << "4 was found" << endl;
    }else{
        cout << "4 not found" << endl;
    }
    if( bt.Find(14) ){
        cout << "4 was found" << endl;
    }else{
        cout << "14 not found" << endl;
    }
       
    cout << "print as pre-order: " << endl;
    bt.Print();
       
    cout << "delete 5" << endl;
    bt.Delete(5);
    bt.Print();
       
    bt.PrintByLevel();
       
    cout << "destory" << endl;
    bt.Destory();
    bt.Print();
       
    return 0;
}


转载注明: http://www.eamonning.com/note/view/38
» 笔记大类