template <class  T>
BiTreeNode <T> *GetTreeNode (const T item, BiTreeNode <T> *left=NULL, 
BiTreeNode <T> *right=NULL)  
{
	BiTreeNode <T>  *p;
	p = new  BiTreeNode <T> ( item, left, right);
	return  p;
}

//template <class  T>
//void Visit( T  item)
//{
//	cout << item << "  ";
//}

//3. 前序遍歷二叉樹
template <class  T>
void  PreOrder ( BiTreeNode <T> *t,  void  Visit( T  item ))
{
	if (t != NULL)
	{
	Visit( t->data);
	PreOrder ( t->left( ), Visit );
	PreOrder ( t->right( ), Visit );
}
}

//4. 中序遍歷二叉樹
template <class  T>
void  InOrder ( BiTreeNode <T> *t,  void  Visit( T  item ))
{
	if (t != NULL)
	{	
	InOrder ( t->left( ), Visit );
    Visit( t->data);
	InOrder ( t->right( ), Visit );
}
}

//4. 后序遍歷二叉樹
template <class  T>
void  PostOrder ( BiTreeNode <T> *t,  void  Visit( T  item ))
{
	if (t != NULL)
	{	
	PostOrder ( t->left( ), Visit ); 
PostOrder ( t->right( ), Visit );
Visit( t->data);	
}
}

//5. 二叉樹的撤銷操作
template <class  T>
void  Destory( BiTreeNode <T> * &root )
{
	if ( (root) != NULL && (root)->left( ) != NULL)
		Destory (root->left( ));

	if ( (root) != NULL && (root)->right( ) != NULL)
		Destory (root->right( ));

	cout << root->data <<"  ";
	delete  root;
}

//6. 打印二叉樹  //　　
template <class  T>
void  PrintBiTree( BiTreeNode <T> * &root ,  int level)
{
	if ( (root) != NULL )
	{
		PrintBiTree(root->right( ) , level+1);

		if ( level !=0)
		{
		for ( int i=0;i<6*(level-1);i++)						
			cout << "  ";								
		cout <<"----"; 							
		}											
		cout << root->data <<endl;
		PrintBiTree(root->left( ) , level+1);
	}
}   													

//7. 查找數據元素
template <class  T>
BiTreeNode <T>  *Search ( BiTreeNode <T> * t ,  T  x)
{
	BiTreeNode <T>  *p;
if ( t==NULL )    return  NULL;
if ( t->data==x)   return  t;

	if ( t ->left( ) != NULL ) 
	{
	p = Search ( t-> left( ), x);	
	if ( p != NULL)   return  p;
}
	
	if ( t ->right()!= NULL ) 
	{
	p = Search ( t->right( ), x);	
	if ( p != NULL)   return  p;
}
	return   NULL;
}



//求二叉樹的葉節點
int leave=0,mleave=1;
template <class  T>
void  TreeLeave(BiTreeNode<T> *&root)
{
	
	if(root!=NULL&&root->left()!=NULL)
		TreeLeave(root->left());
	if(root->right()!=NULL)
		TreeLeave(root->right());
	if(root->left()==NULL&&root->right()==NULL)
	{
		leave++;
		mleave=leave;
	    cout<<"該樹有"<<leave<<"個葉節點"<<endl;
	}
}


//求二叉樹高度
int j=0,jmax;
template <class T>
void TreeHigh(BiTreeNode<T> *&root)
{
	if(root!=NULL&&root->left()!=NULL)
	{
		j++;
		TreeHigh(root->left());
	}
	if(root!=NULL&&root->right()!=NULL)
	{
		j++;
		TreeHigh(root->right());
	}
	if(root->left()==NULL&&root->right()==NULL&&j>jmax)
	{
		jmax=j;
	    cout<<"該樹有"<<jmax+1<<"層"<<endl;
	}
		j--;
}

//判斷是否是完全二叉樹
int i,jmin=100,k=0,l=0;
template <class T>
void FullBiTree(BiTreeNode<T> *&root)
{
	if(root!=NULL&&root->left!=NULL)
	{
		FullBiTree(root->left());
		l++;i++;
	}
	else
	if(root!=NULL&&root->right()!=NULL)
	{
		FullBiTree(root->right());
		l++;i++;
	}
	else
	if(root!=NULL&&root->left()==NULL&&root->right()!=NULL&&k<=1)
		k++;
	else
	if(root!=NULL&&root->left()==NULL&&root->right()==NULL&&l<jmin)
		jmin=l;
	l--;
	else
	if(i<pow(2,jmax)||i>=pow(2,jmax+1))
		cout<<"該樹不是完全二叉樹"<<endl;
	else if(k>=2)
		cout<<"該樹不是完全二叉樹"<<endl;
	else if(jmax-jmin>1)
		cout<<"該樹不是完全二叉樹"<<jmin<<endl;
	else
		cout<<"該樹是完全二叉樹"<<endl;
	
}