#include<iostream.h>
#include<assert.h>

const int size=30;
class tree;

class node{
friend class cqueue;
friend class tree;
friend void wirthorder(node *);
friend node *copytree(node *);
friend int depth(node *);
friend void leaf(node *,int &);
friend void printtree(node *,int);
public:
  node():data(0),leftptr(0),rightptr(0){}
  node(int &d):data(d),leftptr(0),rightptr(0){}
  node(int &,node *,node *);
  int getdata(){ return data;}
private:
  node *leftptr;
  node *rightptr;
  int data;
};
node::node(int &value,node *lptr,node *rptr){
    data=value;
    leftptr=lptr;
    rightptr=rptr;
}
class cqueue:public node{
friend void wirthorder(node *);
 public:
   cqueue();
   void input(node *);
   node *output();
   int empty();
 private:
   int count;
   int head;
   int rear;
   node *q[size];
};
cqueue::cqueue():head(0),rear(0),count(0),node(){}
int cqueue::empty(){
  if(count==0) return 1;
    else return 0;
}
void cqueue::input(node *ptr){
  if(count<size){
     q[rear]=ptr;
     rear=(rear+1)%size;
     count++;
  }
    else
      cout<<endl<<"the circular queue is full!";
}
node *cqueue::output(){
  node *temp;
  if(count>0){
    temp=q[head];
    head=(head+1)%size;
    count--;
    return temp;
  }
    else{
	 cout<<endl<<"the circular queue is empty!";
     }
}
class tree{
friend class cqueue;
friend node *copytree(node *);
friend void wirthorder(node *);
public:
  tree(){ cout<<endl<<"tree is builted!"; rootptr=0;}
  ~tree(){ cout<<endl<<"tree is destrcuted!";}
  void insert(int &);
  void preorder();
  void inorder();
  void postorder();
  void findtiem(int &,node *);
  void insertnode(int &);
  void deletenode(int &);
  node *getroot();
private:
  void insertnode(node **,int &);
  void preorder1(node *);
  void inorder1(node *);
  void postorder1(node *);
  node *rootptr;
  node *find(int &,node *&);
};
void tree::deletenode(int &key){
  node *dptr,*pptr=0,*rptr,*prptr;
  dptr=find(key,pptr);
  if(dptr==0) cout<<endl<<"the item not exist!"<<endl;
    else{
      if(pptr==0){
	 cout<<endl<<"Sorry! can't delete root!"<<endl;
	 return;
      }
	else{
	  if((dptr->leftptr==0)&&(dptr->rightptr==0)){
	     if(dptr->data<pptr->data) { pptr->leftptr=0; delete dptr; }
		 else{ pptr->rightptr=0;
		       delete dptr;
		       }
	 }
	 else{
	      if(dptr==pptr->leftptr){
		  if((dptr->leftptr!=0)&&(dptr->rightptr==0)){
		     pptr->leftptr=dptr->leftptr;
		     delete dptr;
		  }
		     else{
		       if((dptr->leftptr==0)&&(dptr->rightptr!=0)){
			    pptr->leftptr=dptr->rightptr;
			    delete dptr;
		       }
			  else{
			    rptr=dptr->leftptr;
			    prptr=dptr;
			    while(rptr->rightptr!=0){
			       prptr=rptr;
			       rptr=rptr->rightptr;
			    }
			    if(prptr==dptr){
				rptr->rightptr=dptr->rightptr;
				pptr->leftptr=rptr;
				}
				else{
				  prptr->rightptr=rptr->leftptr;
				  rptr->leftptr=dptr->leftptr;
				  rptr->rightptr=dptr->rightptr;
				  pptr->leftptr=rptr;
				  delete dptr;
				}
			  }
		     }
	      }
	      else{
		if((dptr->leftptr!=0)&&(dptr->rightptr==0)){
		   pptr->rightptr=dptr->leftptr;
		   delete dptr;
		}
		   else{
		      if((dptr->leftptr==0)&&(dptr->rightptr!=0)){
			 pptr->rightptr=dptr->rightptr;
			 delete dptr;
		      }
			else{
			     prptr=dptr;
			     rptr=dptr->leftptr;
			     while(rptr->rightptr!=0){
				prptr=rptr;
				rptr=rptr->rightptr;
			     }
			     if(prptr==dptr){
				rptr->rightptr=dptr->rightptr;
				pptr->rightptr=rptr;
				delete dptr;
			     }
				else{
				  prptr->rightptr=rptr->leftptr;
				  rptr->leftptr=dptr->leftptr;
				  rptr->rightptr=dptr->rightptr;
				  pptr->rightptr=rptr;
				  delete dptr;
			     }
			}
		   }
	       }
	   }
       }
   }
}
void tree::insertnode(int &value){
    node *iptr=rootptr,*newnode,*piptr=0;
    while(iptr!=0){
       piptr=iptr;
       if(iptr->data<value) iptr=iptr->rightptr;
	  else{
	     if(iptr->data>value) iptr=iptr->leftptr;
		else{
		   cout<<"Oh! duplicate! can't insert!"<<endl;
		   return;
		   }
	  }
    }
    newnode=new node(value);
    if(piptr->data>value) piptr->leftptr=newnode;
       else piptr->rightptr=newnode;
}
void tree::findtiem(int &key,node *parent){
    node *p;
    p=find(key,parent);
    if(p!=0){
	cout<<"find! currptr->data: "<<p->data;
	if(parent!=0)
	     cout<<" and parent item: "<<parent->data;
		 else
		    cout<<" this is root node no parent node!";
	}
	else  cout<<endl<<"Sorry! no find!";
}
node *tree::getroot(){ return rootptr;}
node *tree::find(int &key,node *&parent){
     node *currptr=rootptr;
     parent=0;
     while(currptr!=0){
       if(currptr->data==key) break;
	 else{
	    if(currptr->data>key){
		 parent=currptr;
		 currptr=currptr->leftptr; }
	       else{
		    parent=currptr;
		    currptr=currptr->rightptr;
		   }
	    }
     }
     return currptr;
}
void tree::insert(int &value){ insertnode(&rootptr,value);}
void tree::insertnode(node **ptr,int &value){
   if(*ptr==0){
     *ptr=new node(value);
     assert(*ptr!=0);
   }
   else
     if(value<((*ptr)->data))  insertnode(&((*ptr)->leftptr),value);
	else
	  if(value>((*ptr)->data))  insertnode(&((*ptr)->rightptr),value);
	    else
	      cout<<value<<"  dup!"<<endl;
}

void tree::preorder(){ preorder1(rootptr);}
void tree::inorder(){ inorder1(rootptr);}
void tree::postorder(){ postorder1(rootptr);}

void tree::preorder1(node *ptr){
   if(ptr!=0){
   cout<<ptr->data<<" ";
   preorder1(ptr->leftptr);
   preorder1(ptr->rightptr);
   }
}
void tree::inorder1(node *ptr){
   if(ptr!=0){
   inorder1(ptr->leftptr);
   cout<<ptr->data<<" ";
   inorder1(ptr->rightptr);
   }
}
void tree::postorder1(node *ptr){
   if(ptr!=0){
   postorder1(ptr->leftptr);
   postorder1(ptr->rightptr);
   cout<<ptr->data<<" ";
   }
}
node *copytree(node *ptr){
  node *newlptr,*newrptr,*newnode;
      if(ptr==0) return 0;
	else{
	  if(ptr->leftptr!=0)
	      newlptr=copytree(ptr->leftptr);
		 else
		    newlptr=0;
	  if(ptr->rightptr!=0)
	      newrptr=copytree(ptr->rightptr);
		 else
		    newrptr=0;

	  newnode=new node(ptr->data,newlptr,newrptr);
	  return newnode;
      }
}
int depth(node *ptr){
  if(ptr==0) return 0;
    else
      return 1+(depth(ptr->leftptr)>depth(ptr->rightptr)?depth(ptr->leftptr):depth(ptr->rightptr));
}
void leaf(node *ptr,int &count){
   if(ptr!=0){
	leaf(ptr->leftptr,count);
	leaf(ptr->rightptr,count);
	if((ptr->leftptr==0)&&(ptr->rightptr==0)) count++;
   }
}
void blank(int n){
  for(int i=0;i<n;i++)
    cout<<" ";
}
void printtree(node *ptr,int lever){
  if(ptr!=0){
     printtree(ptr->leftptr,lever+1);
     blank(6*lever);
     cout<<ptr->data<<endl;
     printtree(ptr->rightptr,lever+1);

  }       
}
void wirthorder(node *root){
    node *ptr=root;
    cqueue a;
    if(root==0) cout<<endl<<"the tree empty!";
    else{
    a.input(root);
    while(a.empty()==0){
      ptr=a.output();
      cout<<ptr->data<<" ";
      if(ptr->leftptr!=0) a.input(ptr->leftptr);
      if(ptr->rightptr!=0) a.input(ptr->rightptr);
    }
  }
}
main(){
tree inttree;
node *parent,*copynode;
int intval=0,deep,lever=0,leafcount=0;
cout<<endl<<"enter num to built tree(999 to exit)."<<endl;
while(intval!=999){
  cout<<"enter(999 to exit):";
  cin>>intval;
  if(intval==999) break;
   else
     inttree.insert(intval);
}
cout<<"preorder:";
inttree.preorder();
cout<<endl<<"inorder:";
inttree.inorder();
cout<<endl<<"postorder:";
inttree.postorder();
cout<<endl<<"wirthorder:";
wirthorder(inttree.getroot());
cout<<endl<<"the deep: ";
cout<<depth(inttree.getroot());
cout<<endl<<"the number of leaf:";
leaf(inttree.getroot(),leafcount);
cout<<leafcount;
cout<<endl<<"--------the graph of tree-------"<<endl;
printtree(inttree.getroot(),lever);
intval=0;
cout<<endl<<"enter key to find(999 to exit)."<<endl;
while(intval!=999){
   cout<<"enter key to find(999 to exit):";
   cin>>intval;
   if(intval==999) break;
      else
	inttree.findtiem(intval,parent);
}
intval=0;
cout<<endl<<"--enter item to insert in the tree(999 to exit)."<<endl;
while(intval!=999){
   cout<<"--enter to insert(999 to exit):";
   cin>>intval;
   if(intval==999) break;
      else{
       inttree.insertnode(intval);
       printtree(inttree.getroot(),lever);
       cout<<endl<<"inorder:"<<endl;
       inttree.inorder();
       }
}
cout<<endl<<"--------the graph of tree-------"<<endl;
printtree(inttree.getroot(),lever);
cout<<"preorder:";
inttree.preorder();
cout<<endl<<"inorder:";
inttree.inorder();
cout<<endl<<"postorder:";
inttree.postorder();
cout<<endl<<"wirthorder:";
wirthorder(inttree.getroot());
cout<<endl<<"the deep: ";
cout<<depth(inttree.getroot());
cout<<endl<<"the number of leaf:";
leafcount=0;
leaf(inttree.getroot(),leafcount);
cout<<leafcount;
intval=0;
cout<<endl<<"--enter item to delete(999 to exit)."<<endl;
while(intval!=999){
  cout<<"--enter to delete(999 to exit):";
  cin>>intval;
  if(intval==999) break;
    else{
      inttree.deletenode(intval);
      printtree(inttree.getroot(),lever);
      cout<<endl<<"inorder:"<<endl;
      inttree.inorder();
      }
}
cout<<endl<<"--------the graph of tree-------"<<endl;
printtree(inttree.getroot(),lever);
cout<<"preorder:";
inttree.preorder();
cout<<endl<<"inorder:";
inttree.inorder();
cout<<endl<<"postorder";
inttree.postorder();
cout<<endl<<"wirthorder:";
wirthorder(inttree.getroot());
cout<<endl<<"the deep: ";
cout<<depth(inttree.getroot());
leafcount=0;
cout<<endl<<"the number of leaf:";
leaf(inttree.getroot(),leafcount);
cout<<leafcount;
cout<<endl<<"the copy tree:";
cout<<endl<<"--------the graph of the copy tree-------"<<endl;
copynode=copytree(inttree.getroot());
lever=0;
printtree(copynode,lever);
return 0;
}