#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，如需轉載請自行聯系原作者
