二叉搜索樹(BST樹)的簡單實現

作者: Phinecos(洞庭散人)  來源: 博客園  發布時間: 2008-08-16 22:43  閱讀: 1235 次  推薦: 0   原文鏈接   [收藏]  
#include <stdlib.h>
template<typename T>
class CBinSTree;

template <typename T>
class CTreeNode
{//樹節點類
public:
    CTreeNode(const T& item,CTreeNode<T>* lptr = NULL,CTreeNode<T>* rptr = NULL):data(item),left(lptr),right(rptr)
    {
    }
    CTreeNode<T>* Left(void)
    {
        return left;
    }
    CTreeNode<T>* Right(void)
    {
        return right;
    }
    friend class CBinSTree<T>;
public:
    T data;//數據
private:
    CTreeNode<T>* left;//左子樹
    CTreeNode<T>* right;//右子樹
};

template<typename T>
class CBinSTree  
{//二叉搜索樹類
public:
    CBinSTree();
    virtual ~CBinSTree();
    CBinSTree(const CBinSTree<T>& tree);
    CBinSTree<T>& operator = (const CBinSTree<T>& rhs);
    CTreeNode<T>* FindNode(const T& item,CTreeNode<T>* &parent)const;//尋找節點
    void PrintTree();//前序遍歷樹(非遞歸)
    void ClearTree();//清空樹
    void Insert(const T& item);//插入數據
    void Delete(const T& item);//刪除數據
    bool Contains(const T& item);//是否包含數據
    CTreeNode<T>* FindMin()const;//找最小值
    CTreeNode<T>* FindMax()const;//找最大值

protected:
    //輔助函數區
    CTreeNode<T>* GetTreeNode(const T& item,CTreeNode<T>* lptr=NULL,CTreeNode<T>* rptr=NULL);//分配樹節點
    void FreeTreeNode(CTreeNode<T>* p);//釋放樹節點
    void DeleteTree(CTreeNode<T>* t);//刪除樹
    CTreeNode<T>* CopyTree(CTreeNode<T>* t);//拷貝樹
private:
    CTreeNode<T> *root;//二叉搜索樹樹根
    int size;//樹節點個數
};

 

#include "stdafx.h"
#include "BinSTree.h"
#include <iostream>
#include <stack>
using namespace std;

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template<typename T>
CBinSTree<T>::CBinSTree()
{
    this->root = NULL;
    this->size = 0;
}
template<typename T>
CBinSTree<T>::CBinSTree(const CBinSTree<T>& tree)
{
    root = this->CopyTree(tree.root);
    this->size = tree.size;
}
template<typename T>
CBinSTree<T>::~CBinSTree()
{
    this->ClearTree();
}
template<typename T>
CBinSTree<T>& CBinSTree<T>::operator = (const CBinSTree<T>& rhs)
{
    if(this==&rhs)
        return *this;
    this->ClearTree();
    root = this->CopyTree(rhs.root);
    size = rhs.size;
    return *this;
}
template<typename T>
CTreeNode<T>* CBinSTree<T>::GetTreeNode(const T& item,CTreeNode<T>* lptr,CTreeNode<T>* rptr)
{
    CTreeNode<T>* p;
    p = new CTreeNode<T>(item,lptr,rptr);
    if(p==NULL)
    {
        cerr<<"分配內存失敗!"<<endl;
        exit(1);
    }
    return p;
}
template<typename T>
CTreeNode<T>* CBinSTree<T>::FindMin()const
{
    CTreeNode<T> *t = root;
    while(t->left!=NULL)
    {
        t = t->left;
    }
    return t;
}
template<typename T>
CTreeNode<T>* CBinSTree<T>::FindMax()const
{
    CTreeNode<T> *t = root;
    while(t->right!=NULL)
    {
        t = t->right;
    }
    return t;
}
template<typename T>
bool CBinSTree<T>::Contains(const T& item)
{
    CTreeNode<T> *p;
    return (this->FindNode(item,p)!=NULL);
}
template<typename T>
CTreeNode<T>* CBinSTree<T>::CopyTree(CTreeNode<T>* t)
{
    CTreeNode<T> *newnode,*newlptr,*newrptr;
    if(t==NULL)
        return NULL;
    if(t->Left()!=NULL)
        newlptr = CopyTree(t->Left());
    else
        newlptr = NULL;
    if(t->Right()!=NULL)
        newrptr = CopyTree(t->Right());
    else
        newrptr = NULL;
    newnode = GetTreeNode(t->data,newlptr,newrptr);
    return newnode;
}
template<typename T>
void CBinSTree<T>::FreeTreeNode(CTreeNode<T>* p)
{
    delete p;
    p = NULL;
}
template<typename T>
void CBinSTree<T>::DeleteTree(CTreeNode<T>* t)
{
    if(t!=NULL)
    {
        DeleteTree(t->Left());
        DeleteTree(t->Right());
        FreeTreeNode(t);
    }
}
template<typename T>
void CBinSTree<T>::ClearTree()
{
    DeleteTree(root);
    root = NULL;
}
template<typename T>
CTreeNode<T>* CBinSTree<T>::FindNode(const T& item,CTreeNode<T>* &parent)const
{
    CTreeNode<T> *t = root;
    parent = NULL;
    while(t!=NULL)
    {
        if(item==t->data)
            break;
        else
        {
            parent = t;
            if(item<t->data)
                t = t->Left();
            else 
                t = t->Right();
        }
    }
    return t;
}
template<typename T>
void CBinSTree<T>::Insert(const T& item)
{
    CTreeNode<T>* t = root,*parent = NULL,*newnode;
    while(t!=NULL)
    {
        parent = t;
        if(item<t->data)
            t = t->Left();
        else
            t = t->Right();
    }
    newnode = this->GetTreeNode(item);
    if(parent==NULL)
        root = newnode;
    else if(item<parent->data)
        parent->left = newnode;
    else
        parent->right = newnode;
    size++;
}
template<typename T>
void CBinSTree<T>::Delete(const T& item)
{
    CTreeNode<T> *pDNode,*pRNode,*pParNode;
    if((pDNode = this->FindNode(item,pParNode))==NULL)
        return;
    if(pDNode->left==NULL)
        pRNode = pDNode->right;
    else if(pDNode->right==NULL)
        pRNode = pDNode->left;
    else
    {
        CTreeNode<T> *pParOfRNode = pDNode;
        pRNode = pDNode->left;
        while(pRNode->right!=NULL)
        {
            pParOfRNode = pRNode;
            pRNode = pRNode->right;
        }
        if(pParOfRNode==pDNode)
        {
            pRNode->right = pDNode->right;
        }
        else
        {
            pParOfRNode->right = pRNode->left;
            pRNode->left = pDNode->left;
            pRNode->right = pDNode->right;
        }
    }
    if(pParNode==NULL)
        root = pRNode;
    else if(pDNode->data<pParNode->data)
        pParNode->left = pRNode;
    else
        pParNode->right = pRNode;
    this->FreeTreeNode(pDNode);
    this->size--;

}
template<typename T>
void CBinSTree<T>::PrintTree()
{
    stack<CTreeNode<T>* > s;
    CTreeNode<T>* p = root;
    while (p!=NULL || !s.empty())
    {
        while (p!=NULL)             //遍歷左子樹
        {
            cout<<p->data<<endl;
            s.push(p);
            p=p->Left();
        }//endwhile
        
        if (!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->Right();            //通過下一次循環實現右子樹遍歷
        }//endif   
    }
}

 

// test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "BinSTree.cpp"
#include <iostream>
using namespace std;

CBinSTree<int>* MakeSampleTree()
{//示例BST樹
    CBinSTree<int> *tree1 = new CBinSTree<int>();
    int a = 5;
    tree1->Insert(a);
    tree1->Insert(30);
    tree1->Insert(65);
    tree1->Insert(25);
    tree1->Insert(35);
    tree1->Insert(50);
    tree1->Insert(10);
    tree1->Insert(28);
    tree1->Insert(26);
    tree1->Insert(33);
    return tree1;
}

int main(int argc, char* argv[])
{
    CBinSTree<int> *tree1 = MakeSampleTree();
    tree1->PrintTree();
    std::cout<<"刪除節點30:"<<endl;
    tree1->Delete(30);
    tree1->PrintTree();
    cout<<tree1->Contains(40)<<endl;
    CTreeNode<int> *p = tree1->FindMin();
    cout<<p->data<<endl;
    return 0;
}
0
0
 
 
 

文章列表

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄