#include "iostream.h"
# define N 100
int n=0,w=1;
template<class type>
struct node
{
	type data;
	node <type> *lchild;
	node <type> *rchild;
	int no;
	node()
	{
		rchild=NULL;
		lchild=NULL;
	}
	node(type x,int y)
	{
		rchild=NULL;
		lchild=NULL;
		data=x;
		no=y;
	}
};


template<class type>
class btree
{
	public:
		btree();
		btree(type x);
		~btree();
		bool empty();
		int size();
		node<type>* get_root();
		node<type>* get_lchild(node<type> *t);
		node<type>* get_rchild(node<type> *t);
        void r_size(node<type> *t);
		void clear();
		void r_clear(node<type> *t);
		int height();
		int r_height(node<type> *sub_root);
		void pre_print(node<type> *sub_root,int h);
		void print();
		//void nodecopy(node<type> *sub_root,node<type> *original);
	    //btree(const btree<type>&original);
		void input();
		node<type>* search(node<type> *sub_root,int &z);
		void inorder(type &,void (*visit)(type &));
		void recursive_inorder(node<type> *sub_root,void (*visit)(type &));
		void preorder(void (*visit)(type &));
		void recursive_preorder(node<type> *sub_root,void (*visit)(type &));
		void postorder(void (*visit)(type &));
		void recursive_postorder(node<type> *sub_root,void (*visit)(type &));

	protected:
		node<type> *root;
};


//以下是函數(shù)的實現(xiàn)算法：
template<class type>
btree<type>::btree()                             //構(gòu)造函數(shù)1
{
	root=NULL;
}

template<class type>                             //構(gòu)造函數(shù)2
btree<type>::btree(type x)
{
	root=new node<type>(x);
	root->no=1;
	root->rchild=NULL;
	root->lchild=NULL;
}


template<class type>                             //析構(gòu)函數(shù)
btree<type>::~btree()
{
	r_clear(root);
}


template<class type>                                //判斷二叉樹是否為空
bool btree<type>::empty()
{
	return (root==NULL);
}


template<class type>                               //返回二叉樹的根結(jié)點
node<type>* btree<type>::get_root()
{
	return root;
}

template<class type>                               //返回結(jié)點t的左孩子結(jié)點
node<type>* btree<type>::get_lchild(node<type> *t)
{
	return t->lchild;
}


template<class type>                               //返回結(jié)點t的左孩子結(jié)點
node<type>* btree<type>::get_rchild(node<type> *t)
{
	return t->rchild;
}


template<class type>                               //打印二叉樹的所有結(jié)點
void btree<type>::print()
{  
	if(root!=NULL)
		pre_print(root,1);
	else
		cout<<"The tree is empty!"<<endl;;
}
template<class type>                            
void btree<type>::pre_print(node<type> *sub_root,int h)
{   
	if(sub_root!=NULL)
	{
		cout<<" "<<sub_root->no<<"->"<<sub_root->data<<"->"<<h<<" ";
		pre_print(sub_root->lchild,h+1);
		pre_print(sub_root->rchild,h+1);
	}
}


template<class type>                                 //求二叉樹的高度
int btree<type>::height()
{
	return r_height(root);
}
template<class type>                          
int btree<type>::r_height(node<type> *sub_root)
{
	node<type> *temp=sub_root;
	if(temp==NULL)
		return 0;
	else
	{
		 int hl=0,hr=0;
		 hl=r_height(temp->lchild);
		 hr=r_height(temp->rchild);
		 return hl>hr? hl+1:hr+1;	 
	}
}

template<class type>                                   //求樹的結(jié)點數(shù)目
int btree<type>::size()
{
	r_size(root);
	return n;
}
template<class type>                         
void btree<type>::r_size(node<type> *t)
{
	if(t==NULL)
		return ;
	else
	{
		n++;
		r_size(t->lchild);
		r_size(t->rchild);
	}
}

template<class type>                                     //把樹清空
void btree<type>::clear()
{   if(root!=NULL)

	r_clear(root);
else 
   cout<<"clear"<<endl;
root=NULL;
}
template<class type>
void btree<type>::r_clear(node<type> *t)              
{   
	if(t!=NULL)
	{   node<type> *tmp=t;
		//delete t;
		r_clear(t->lchild);
		r_clear(t->rchild);
		delete tmp;
	}//delete t;
	else
		return;
}
/*
template<class type>                                    //用一棵數(shù)初始化新樹
btree<type>::btree(const btree<type> &original)
{
	root=new node<type>;//(original.root->data);
	root->data=original.root->data;

	node<type> *t=root;
	/*while(t!=NULL)
	{
		t=t->lchild;
		t->lchild=original.t->lchild;
		t->rchild=original.t->rchild;
		t=t->rchild;
		t->lchild=original.t->lchild;
		t->rchild=original.t->rchild;
	}
}*/

template<class type>                                      //利用后序遍歷查找結(jié)點，用于初始化
node<type>* btree<type>::search(node<type> *sub_root,int &z)      
{   
	node<type> *temp=NULL;
	if(sub_root!=NULL)
	{    
		temp=search(sub_root->lchild,z); 
		if(temp==NULL)
			temp=search(sub_root->rchild,z);
		if(temp==NULL)
		{
     	    if(sub_root->no==z)
		    temp=sub_root;
		}
	}
	return temp;
}
	    

template<class type>                                       //二叉樹的初始化
void btree<type>::input()
{   

	int a[N]={0},s,h,j;
	type b[N],r;
	cout<<"輸入二叉樹的結(jié)點個數(shù)："<<endl;
	cin>>h;
	if(h==0)   return;
	cout<<"請輸入與完全二叉樹相對應(yīng)的序號以及樹的權(quán)值："<<endl;
	for(int i=0;i<h;i++)
	{
		cin>>s; a[i]=s;
		cin>>r; b[i]=r;
	}
	if(a[0]!=1)
	{
		cout<<"Error"<<endl;
		return;
	}
	node<type> *p=new node<type>(b[0],1);
	root=p;   i=1;
	node<type> *t=NULL;
	while(a[i]!=0)
	{
		for(j=0;j<h;j++)
		{
			if(a[i]==2*a[j]||a[i]==2*a[j]+1)          
				break;
		}
		if(j==h)
		{
			cout<<"Input error"<<endl;
			return;
		}
        else
		{
			if(a[i]==2*a[j]) 
			{
				node<type> *p=new node<type>(b[i],a[i]);
				t=search(root,a[j]);
				if(t==NULL)
					return;
				t->lchild=p;
				t=NULL;
			}
			if(a[i]==2*a[j]+1)
			{
				node<type> *p=new node<type>(b[i],a[i]);
				t=search(root,a[j]);
				if(t==NULL)					
					return;
				t->rchild=p;
				t=NULL;	
			}
		}
		i++;
	}
}

        
                                                              //以下為二叉樹的三種遍歷，利用函數(shù)指針的方法

template <class type>
void btree<type>::inorder(type &,void (*visit)(type &))
{
   recursive_inorder(root, visit);
}


template <class type>
void btree<type>::recursive_inorder(node<type> *sub_root,void (*visit)(type &))
{
   if (sub_root != NULL) {
      recursive_inorder(sub_root->lchild, visit);
      (*visit)(sub_root->data);
      recursive_inorder(sub_root->rchild, visit);
   }
}


template <class type>
void btree<type>::preorder(void (*visit)(type &))
{
   recursive_preorder(root, visit);
}


template <class type>
void btree<type>::recursive_preorder(node<type> *sub_root,void (*visit)(type &))
{
   if (sub_root != NULL) {
      (*visit)(sub_root->data);
      recursive_preorder(sub_root->lchild, visit);
      recursive_preorder(sub_root->rchild, visit);
   }
}


template <class type>
void btree<type>::postorder(void (*visit)(type &))
{
   recursive_postorder(root, visit);
}


template <class type>
void btree<type>::recursive_postorder(node<type> *sub_root,void (*visit)(type &))
{
   if (sub_root != NULL) {
      recursive_postorder(sub_root->lchild, visit);
      recursive_postorder(sub_root->rchild, visit);
      (*visit)(sub_root->data);
   }
}






//派生一個森林類
template<class type>
class forest:public btree<type>
{
	public:
		void fs_print();
		void r_fs_print(node<type> *sub_root);
};


template<class type>                                      //輸出用二叉鏈表表示的森林的所有的父子對。
void forest<type>::fs_print()
{
	r_fs_print(root);
}
template<class type>
void forest<type>::r_fs_print(node<type> *sub_root)
{
	node<type> *r=sub_root->rchild,*l=sub_root->lchild;
	if(sub_root!=NULL&&sub_root->lchild!=NULL)
	{
		cout<<sub_root->data<<"<-->"<<l->data<<"  ";
		while(l!=NULL&&l->rchild!=NULL)
		{
			cout<<sub_root->data<<"<-->"<<l->rchild->data<<"  ";
			l=l->rchild;
		}
	}
	if(sub_root->lchild!=NULL)
		r_fs_print(sub_root->lchild);
	if(sub_root->rchild!=NULL)
		r_fs_print(sub_root->rchild);
}