#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;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/07/21/1247762.html，如需转载请自行联系原作者