//this is a binary tree template by C++
//It complied ok with dev-c++ and vc++6.0
//fine name is Test.cpp
#include <cstdlib>
#include <iostream>
#include <cstring>
#include "Btree.h"
using namespace std;
int main(int argc, char *argv[])
{
cout<<"Btree class template demo.../n";
//1.constrator Btree() test ok
Btree<int> b1,b3; //Btree()
b1.InsertNode(25);
b1.InsertNode(11);
b1.InsertNode(33);
b1.InsertNode(66);
b1.PreorderTrans();
b1.PreorderQuick();
cout<<endl;
Btree<char> c1;
c1.InsertNode('a');
c1.InsertNode('b');
c1.InsertNode('c');
c1.InorderTrans();
cout<<endl;
//2.copy constrator,=,destructor test ok
Btree<int> b2(b1); //copy constrator
b3=b2; //=
b2.PreorderTrans();
cout<<endl;
b3.PreorderTrans();
cout<<endl;
//3.IsEmpty(),TreeHeight() tesk ok
cout<<"b1.IsEmpty()="<<b1.IsEmpty()<<endl; //IsEmpty()
cout<<"b1.TreeHeight()="<<b1.TreeHeight()<<endl; //TreeHeight()
//4.FindNode(item),InsertNode(item),DeleteNode(item) test ok
b3.InsertNode(99); //InsertNode(item)
cout<<"FindNode(99)="<<b3.FindNode(99)<<endl; //FindNode(item)
b3.InorderTrans();
cout<<endl;
b3.DeleteNode(99); //DeleteNode(item)
b3.InorderTrans();
cout<<endl;
//5.InorderTrans(),PreorderTrans(),PostorderTrans() test ok
b3.InsertNode(88); //InorderTrans()
b3.InorderTrans();
cout<<endl;
b3.PreorderTrans(); //PreorderTrans()
cout<<endl;
b3.PostorderTrans(); //PostorderTrans()
cout<<endl;
//private: skip these private funcation
//6.Height(root),int max()
//7.CopyTree(Btree&),Destrory(),DestroyTree()
//8.Inorder(),Preorder(),Postorder();
system("Pause");
return 0;
}
//----------------------------------------------------------------------------------
/*
*Btree.h
*this is a Btree template by pointer
*Btree ADT
*writer:chinanetboy ,QQ:44633197
*blog http://chinanetboy.bokee.com
*date:07/01/2008
*/
#ifndef H_Btree
#define H_Btree
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <stack>
using namespace std;
//Btree ADT list
template <class T>
struct NodeType{
T info;
NodeType<T> * Llink;
NodeType<T> * Rlink;
};
template <class T>
class Btree
{
public:
//1.constrator Btree()
Btree();
//2.copy constrator,=,destructor
Btree(const Btree <T> & O);
const Btree<T>& operator=(const Btree<T>& O);
~Btree();
//3.IsEmpty(),TreeHeight()
bool IsEmpty();
int TreeHeight();
//4.FindNode(item),InsertNode(item),DeleteNode(item)
bool FindNode(const T& item);
void InsertNode(const T& item);
void DeleteNode(const T& item);
//5.递归的InorderTrans(),PreorderTrans(),PostorderTrans()
//非递归的InorderQuick(),PreorderQuick(),PostorderQuick();
void InorderTrans();
void PreorderTrans();
void PostorderTrans();
void InorderQuick();
void PreorderQuick();
void PostorderQuick();
private:
//6.Height(root),int max();
int Height(NodeType<T> *P);
int max(int ,int);
//7.CopyTree(Btree&),Destrory(),DestroyTree()
void CopyTree(NodeType<T>* &cpy,NodeType<T>* Other);
void Destrory(NodeType<T>* &P);
void DestroyTree();
//8.Inorder(),Preorder(),Postorder();
void Inorder(const NodeType<T> *P);
void Preorder(const NodeType<T> *P);
void Postorder(const NodeType<T> *P);
//protected:
private:
NodeType<T> *root;
};
//1.constrator Btree()
template <class T>
Btree<T>::Btree(){ root=NULL; }
//2.copy constrator,=,destructor
template <class T>
Btree<T>::Btree(const Btree<T>& Other){
if (Other.root==NULL)
root=NULL;
else
CopyTree(root,Other.root);
}
template <class T>
const Btree<T>& Btree<T>::operator=(const Btree<T>& O){
if(this!=&O){
if(root!=NULL)
Destrory(root);
else
CopyTree(root,O.root);
}
return *this;
}
template <class T>
Btree<T>::~Btree(){
Destrory(root);
}
//3.IsEmpty(),TreeHeight()
template <class T>
bool Btree<T>::IsEmpty(){
return (root==NULL);
}
template <class T>
int Btree<T>::TreeHeight(){
return Height(root);
}
//4.FindNode(item),InsertNode(item),DeleteNode(item)
template <class T>
bool Btree<T>::FindNode(const T& finditem){
NodeType<T> *current;
bool found=false;
if(root!=NULL){
current=root;
while(current!=NULL && !found){
if(current->info==finditem){
found=true;
return found;
}
else
{
if(current->info>finditem)
current=current->Llink;
else
current=current->Rlink;
}//end else
}//end while
}
return found;
}
template <class T>
void Btree<T>::InsertNode(const T& item){
NodeType<T> *current,*trailcurrent,*newnode;
newnode=new NodeType<T>;
assert(newnode!=NULL);
newnode->info=item;
newnode->Llink=NULL;
newnode->Rlink=NULL;
if(root==NULL)
root=newnode;
else
{
current=root;
while(current!=NULL){
trailcurrent=current;
if(current->info==item){
cerr<<"this item is already ,insert fail..."<<endl;
return;
}
else
{
if(current->info < item)
current=current->Rlink;
else
current=current->Llink;
}//end else
}//end while
if(trailcurrent->info < item)
trailcurrent->Rlink=newnode;
else
trailcurrent->Llink=newnode;
}
}
template <class T>
void Btree<T>::DeleteNode(const T& delitem){
NodeType<T> *current,*trailcurrent;
bool found=false;
if(root!=NULL){
current=root;
trailcurrent=root;
while(current!=NULL && !found)
{
if(current->info==delitem){
found=true;
break;
}
else
{
trailcurrent=current;
if(current->info > delitem)
current=current->Llink;
else
current=current->Rlink;
}
}//end while
if (found){
if(current==root)
Destrory(root);
else
{
if(trailcurrent->info > delitem)
Destrory(trailcurrent->Llink);
else
Destrory(trailcurrent->Rlink);
}
}//end found
}//end if
}
//5.InorderTrans(),PreorderTrans(),PostorderTrans()
template <class T>
void Btree<T>::InorderTrans(){
Inorder(root);
}
template <class T>
void Btree<T>::PreorderTrans(){
Preorder(root);
}
template <class T>
void Btree<T>::PostorderTrans(){
Postorder(root);
}
//非递归的中序遍历二叉树InorderQuick
template <class T>
void Btree<T>::InorderQuick(){
stack<NodeType<T>*> stack1;
NodeType<T> * current;
current=root;
while(current!=NULL || !stack1.empty()){
if(current!=NULL){
stack1.push(current);
current=current->Llink;
}
else{
current=stack1.top();
stack1.pop();
cout<<current->info<<" ";
current=current->Rlink;
}
}
cout<<endl;
}
template <class T>
void Btree<T>::PreorderQuick(){
stack<NodeType<T>*> stack1;
NodeType<T> * current;
current=root;
while(current!=NULL || !stack1.empty()){
if(current!=NULL){
cout<<current->info<<" ";
stack1.push(current);
current=current->Llink;
}
else{
current=stack1.top();
stack1.pop();
current=current->Rlink;
}
}
cout<<endl;
}
template <class T>
void Btree<T>::PostorderQuick(){
stack<NodeType<T>*> stack1;
NodeType<T> * current;
current=root;
while(current!=NULL || !stack1.empty()){
if(current!=NULL){
stack1.push(current);
current=current->Llink;
}
else{
current=stack1.top();
stack1.pop();
current=current->Rlink;
cout<<current->info<<" ";
}
}
cout<<endl;
}//end all
//private:
//6.Height(root),int max()
template <class T>
int Btree<T>::Height(NodeType<T> *P){
if(P==NULL)
return 0;
else
return 1 + max(Height(P->Llink),Height(P->Rlink));
}
template <class T>
int Btree<T>::max(int x,int y){
if (x>y)
return x;
else
return y;
}
//7.CopyTree(Btree&),Destrory(),DestroyTree()
template <class T>
void Btree<T>::CopyTree(NodeType<T>* &cpy,NodeType<T>* Other){
if(Other==NULL)
cpy=NULL;
else
{
cpy=new NodeType<T>;
cpy->info=Other->info;
CopyTree(cpy->Llink,Other->Llink);
CopyTree(cpy->Rlink,Other->Rlink);
}
}
template <class T>
void Btree<T>::Destrory(NodeType<T>* &P){
if (P!=NULL){
Destrory(P->Llink);
Destrory(P->Rlink);
delete P;
P=NULL;
}
}
template <class T>
void Btree<T>::DestroyTree(){
Destrory(root);
}
//8.Inorder(),Preorder(),Postorder();
template <class T>
void Btree<T>::Inorder(const NodeType<T> *P){
if(P!=NULL){
Inorder(P->Llink);
cout<<P->info<<" ";
Inorder(P->Rlink);
}
}
template <class T>
void Btree<T>::Preorder(const NodeType<T> *P){
if(P!=NULL){
cout<<P->info<<" ";
Preorder(P->Llink);
Preorder(P->Rlink);
}
}
template <class T>
void Btree<T>::Postorder(const NodeType<T> *P){
if(P!=NULL){
Postorder(P->Llink);
Postorder(P->Rlink);
cout<<P->info<<" ";
}
}
#endif