二叉搜索树(BST树)的简单实现

#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>;

    T data;//数据

private:

    CTreeNode<T>* left;//左子树

    CTreeNode<T>* right;//右子树

};

class CBinSTree  

{//二叉搜索树类

    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);//拷贝树

    CTreeNode<T> *root;//二叉搜索树树根

    int size;//树节点个数

#include "stdafx.h"

#include "BinSTree.h"

#include <iostream>

#include <stack>

using namespace std;

/**///////////////////////////////////////////////////////////////////////

// Construction/Destruction

CBinSTree<T>::CBinSTree()

    this->root = NULL;

    this->size = 0;

}

CBinSTree<T>::CBinSTree(const CBinSTree<T>& tree)

    root = this->CopyTree(tree.root);

    this->size = tree.size;

CBinSTree<T>::~CBinSTree()

    this->ClearTree();

CBinSTree<T>& CBinSTree<T>::operator = (const CBinSTree<T>& rhs)

    if(this==&rhs)

        return *this;

    root = this->CopyTree(rhs.root);

    size = rhs.size;

    return *this;

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;

CTreeNode<T>* CBinSTree<T>::FindMin()const

    CTreeNode<T> *t = root;

    while(t->left!=NULL)

        t = t->left;

    return t;

CTreeNode<T>* CBinSTree<T>::FindMax()const

    while(t->right!=NULL)

        t = t->right;

bool CBinSTree<T>::Contains(const T& item)

    CTreeNode<T> *p;

    return (this->FindNode(item,p)!=NULL);

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());

        newrptr = NULL;

    newnode = GetTreeNode(t->data,newlptr,newrptr);

    return newnode;

void CBinSTree<T>::FreeTreeNode(CTreeNode<T>* p)

    delete p;

    p = NULL;

void CBinSTree<T>::DeleteTree(CTreeNode<T>* t)

    if(t!=NULL)

        DeleteTree(t->Left());

        DeleteTree(t->Right());

        FreeTreeNode(t);

void CBinSTree<T>::ClearTree()

    DeleteTree(root);

    root = NULL;

CTreeNode<T>* CBinSTree<T>::FindNode(const T& item,CTreeNode<T>* &parent)const

    parent = NULL;

    while(t!=NULL)

        if(item==t->data)

            break;

        else

            parent = t;

            if(item<t->data)

                t = t->Left();

            else 

                t = t->Right();

        }

void CBinSTree<T>::Insert(const T& item)

    CTreeNode<T>* t = root,*parent = NULL,*newnode;

        parent = t;

        if(item<t->data)

            t = t->Left();

            t = t->Right();

    newnode = this->GetTreeNode(item);

    if(parent==NULL)

        root = newnode;

    else if(item<parent->data)

        parent->left = newnode;

        parent->right = newnode;

    size++;

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;

        CTreeNode<T> *pParOfRNode = pDNode;

        while(pRNode->right!=NULL)

            pParOfRNode = pRNode;

            pRNode = pRNode->right;

        if(pParOfRNode==pDNode)

            pRNode->right = pDNode->right;

            pParOfRNode->right = pRNode->left;

            pRNode->left = pDNode->left;

    if(pParNode==NULL)

        root = pRNode;

    else if(pDNode->data<pParNode->data)

        pParNode->left = pRNode;

        pParNode->right = pRNode;

    this->FreeTreeNode(pDNode);

    this->size--;

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 "BinSTree.cpp"

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);

    cout<<tree1->Contains(40)<<endl;

    CTreeNode<int> *p = tree1->FindMin();

    cout<<p->data<<endl;

    return 0;