C++ 二叉搜索树 模板的代码
将写内容过程重要的一些内容备份一次，下面内容内容是关于C++ 二叉搜索树 模板的内容，希望能对大家也有帮助。
#pragma once
#include <iostream>
#include <cstdlib>
#include <queue>
using namespace std;
template <class T> class STree;
template <class T>
class TNode{
friend class STree_iterator<T>;
friend class STree_const_iterator<T>;
protected:
T data;
void copy(const TNode<T> &rhs) {
left=rhs.left;
right=rhs.right;
parent=rhs.parent;
data=rhs.data;
}
public:
TNode() {left=NULL, right=NULL, parent=NULL;}
:data(item), left(lptr), right(rptr), parent(pptr) {}
TNode( const TNode<T> &rhs) { copy(rhs); }
~TNode() {}
};
template <class T>
class STree {
friend class STree_iterator<T>;
friend class STree_const_iterator<T>;
protected:
int size;
public:
typedef T value_type;
STree(void);
STree(const STree<T> &rhs);
~STree(void);
connect the right subtree of R to its parent as the left sub tree
connect the left subtree of the deleted node to R as the left subtree link the right
subtree of the deleted node to R as its right sub tree, and the substitute the
void erase(iterator first, iterator last);
void LevelorderPrint();
bool empty() const {return root==NULL;}
int Size() const {return size;}
template <class T>
STree<T>::STree(void){
root=NULL;
size=0;
}
template <class T>
root=NULL;
size=0;
while(first!=last) {
++first;
}
}
template <class T>
STree<T>::STree(const STree<T> &rhs) {
root=copy( rhs.Root() );
size=rhs.Size();
}
template <class T>
STree<T> &STree<T>::operator=(const STree<T> &rhs){
if(this==rhs) return this;
DelTree(root);
root=copy(rhs.Root());
size=rhs.Size();
return this;
}
template <class T>
STree<T>::~STree(void){
DelTree(root);
}
template <class T>
if(newnode==NULL) {cerr<<"allocate storage for new node failed!"<<endl; exit(0);}
return newnode;
}
template <class T>
if(rhs==NULL) return NULL;
lptr=copy(rhs->left);
newnode=GetNode(rhs->data, lptr, rptr, NULL);
if(lptr!=NULL) lptr->parent=newnode;
if(rptr!=NULL) rptr->parent=newnode;
}
template <class T>
if(_root!=NULL){
DelTree(_root->left);
DelTree(_root->right);
delete _root;
}
}
template <class T>
while(cur!=NULL) {
if(item==cur->data) return cur;
else if(item<cur->data) cur=cur->left;
else cur=cur->right;
}
return cur;
}
template <class T>
int r_depth, l_depth, depth;
if(cur==NULL) depth=-1;
else {
r_depth=height(cur->right);
l_depth=height(cur->left);
depth=1+(r_depth>l_depth?r_depth:l_depth);
}
return depth;
}
template <class T>
typename STree<T>::iterator STree<T>::find(const T& item){
cur=findNode(item);
if(cur!=NULL) return STree<T>::iterator(cur, this);
else return this->end();
}
template <class T>
typename STree<T>::iterator STree<T>::insert(const T& item) {
while(cur!=NULL) {
par=cur;
if(item==cur->data) return STree<T>::iterator(cur, this);
else if(item<cur->data) cur=cur->left;
else cur=cur->right;
}
newnode=GetNode(item, NULL, NULL, par);
if(par==NULL) root=newnode;
else if(item<par->data) par->left=newnode;
else par->right=newnode;
++size;
return STree<T>::iterator(newnode, this);
}
template <class T>
bool STree<T>::erase(const T& item) {
STree<T>::iterator pos=find(item);
if( pos!=end() ) erase(pos);
return pos!= end();
}
template <class T>
void STree<T>::erase(typename STree<T>::iterator pos) {
if(del==NULL) return;
if(del->left==NULL || del->right==NULL) {
if(del->left==NULL) subs=del->right;
else subs=del->left;
if(subs != NULL) subs->parent=par;
}
else {
subs=del->right;
while(subs->left!=NULL) {
temp=subs;
subs=subs->left;
}
if(temp==del) {
subs->left=del->left;
subs->parent=par;
subs->left->parent=subs;
}
else {
if(subs->right!=NULL) subs->right->parent=temp;
subs->left->parent=subs;
subs->right->parent=subs;
}
}
if(par==NULL) root=subs;
else if(par->left==del) par->left=subs;
else par->right=subs;
delete del;
--size;
}
template <class T>
void STree<T>::erase(typename STree<T>::iterator first, typename STree<T>::iterator last){
STree<T>::iterator iter=first;
while(iter!=last) {
erase(iter);
++iter;
}
}
template <class T>
void STree<T>::LevelorderPrint() {
queue< TNode<T> > parQ;
queue< TNode<T> > chdQ;
while(!parQ.empty()) {
do{
parQ.pop();
cout<<cur->data<<ends;
} while(!parQ.empty());
cout<<endl;
parQ=chdQ;
queue< TNode<T> > empty;
swap(chdQ, empty);
}
delete cur;
cur=NULL;
}
template <class T>
typename STree<T>::iterator STree<T>::begin(){
if(cur!=NULL)
while(cur->left!=NULL)
cur=cur->left;
}
template <class T>
return STree<T>::iterator(NULL, this);
}
template<class T, class Ref, class Ptr>
friend class STree<T>;
public:
typedef STree_iterator<T, Ref, Ptr> self;
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef ptrdiff_t difference_type;
public:
STree_iterator(){
pn=NULL;
tree=NULL;
}
pn=rhs.pn;
tree=rhs.tree;
}
bool operator==(const STree_iterator &rhs) const {return pn == rhs.pn;}
bool operator!=(const STree_iterator &rhs) const {return pn != rhs.pn;}
if(pn==NULL) {cerr<<"allocate storage for new node failed!"<<endl; exit(0);}
return pn->data;
}
pn=tree->root;
if(pn==NULL) { cerr<<"move on a empty tree!"<<endl; exit(0);}
while(pn->left!=NULL) pn=pn->left;
}
pn=pn->right;
while(pn->left!=NULL) pn=pn->left;
}
p=pn->parent;
while(p!=NULL && pn==p->right) {
pn=p;
p=p->parent;
}
pn=p;
}
}
self temp(pn, tree);
}
pn=tree->root;
if(pn==NULL) {cerr<<"move on a empty tree!"<<endl; exit(0);}
while(pn->right!=NULL) pn=pn->right;
}
pn=pn->left;
while(pn->right!=NULL) pn=pn->right;
}
p=pn->parent;
while(p!=NULL && pn==p->left) {
pn=p;
p=p->parent;
}
pn=p;
}
}
self operator--(int) {
self temp(pn, tree);
}
private:
};
template<class T, class Ref, class Ptr>
class STree_const_iterator{
friend class STree<T>;
public:
typedef STree_const_iterator<T, Ref, Ptr> self;
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef ptrdiff_t difference_type;
public:
STree_const_iterator(){
pn=NULL;
tree=NULL;
}
pn=rhs.pn;
tree=rhs.tree;
}
pn=rhs.pn;
tree=rhs.tree;
}
bool operator==(const STree_const_iterator &rhs) const {return pn == rhs.pn;}
bool operator!=(const STree_const_iterator &rhs) const {return pn != rhs.pn;}
return pn->data;
}
pn=tree->root;
if(pn==NULL) { cerr<<"STree STree_const_iterator operator++(): tree empty"<<endl; exit(0); }
while(pn->left!=NULL) pn=pn->left;
}
pn=pn->right;
while(pn->left!=NULL) pn=pn->left;
}
p=pn->parent;
while(p!=NULL && pn==p->right) {
pn=p;
p=p->parent;
}
pn=p;
}
}
STree<T>::STree_const_iterator temp(pn, tree);
}
pn=tree->root;
if(pn==NULL)
throw underflowError
("STree STree_const_iterator operator++(): tree empty");
while(pn->right!=NULL) pn=pn->right;
}
pn=pn->left;
while(pn->right!=NULL) pn=pn->right;
}
p=pn->parent;
while(p!=NULL && pn==p->left) {
pn=p;
p=p->parent;
}
pn=p;
}
}
STree_const_iterator operator--(int) {
STree_const_iterator temp(pn, tree);
}
private:
};
