//二叉樹類定義
template<class T>
class BinaryTree {
public :
BinaryTree( ) {root=0;};
~ BinaryTree( ) { };
bool IsEmpty( ) const
{reurn ((root) ? false : true);}
bool Root(T& x) const;
void MakeTree(const T& element，BinaryTree<T>& left，BinaryTree<T>& right);
void BreakTree(T& element，BinaryTree<T>& left ，BinaryTree<T>& right);
void PreOrder(void(*Visit) (BinaryTreeNode<T> *u))
{ PreOrder( Visit，root ) ; }
void Inorder(void (*Visit) (BinaryTreeNode<T> *u))
{ Inorder(Visitroot) ; }
void PostOrder(void(*Visit ) (BinaryTreeNode<T> *u));
{Postorder Visit, root); }
void LevelOrder(void(*Visit) (BinaryTreeNode<T> *u));
private :

BinaryTree<T> *root; // 根節點指針 

void PreOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
void InOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
void PostOrder(void(*Visit) (BinaryTreeNode<T> *u)，BinaryTree<T> *t);
} ;
 





template<class T>
bool BinaryTree<T>::Root(T& x) const
{
// 取根節點的data域放入x
// 如果沒有根節點，則返回false
if (root) {x = root->data;
return true;}
else return false; // 沒有根節點
}
template<class T>
void BinaryTree< T >::MakeTree(const T& element, BinaryTree<T>& left, BinaryTree<T>& right)
{
// 將left, right和element 合并成一棵新樹
// left,right和this必須是不同的樹
// 創建新樹
root = new BinaryTreeNode< T >(element, left.root, right.root);
// 阻止訪問left和right
left.root = right.root=0;
}
template<class T>
void BinaryTree <T>:: BreakTree(T& element, BinaryTree<T>& left, BinaryTree<T>& right)
{
// left, right和t h i s必須是不同的樹
// 檢查樹是否為空
if (!root) cout<<"It's empty"; // 空樹
// 分解樹
element = root->data;
left.root = root->LeftChild;
right.root = root->RightChild;
delete root;
root = 0;
}
template<class T>
void BinaryTree< T >::PreOrder( void (*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{
// 前序遍歷
if(t){
Visit(t);
PreOrder(Visit,t->LeftChild);
PreOrder(Visit,t->RightChild);
}
}
template <class T>
void BinaryTree<T> ::InOrder ( void (* Visit)( BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{
// 中序遍歷
if (t) {
InOrder(Visit,t->LeftChild);
Visit(t) ;
InOrder(Visit,t->RightChild);
}
}
template <class T>
void BinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T> *u), BinaryTreeNode<T> *t)
{
// 后序遍歷
if(t){
PostOrder(Visit, t->LeftChild);
PostOrder(Visit,t->RightChild);
Visit(t);
}
}
//逐層遍歷
template<class T>
void BinaryTree<T>::LevelOrder(void(*Visit)(BinaryTreeNode<T> *u))
{
// 逐層遍歷
LQueue <BinaryTreeNode<T>*> Q;
BinaryTreeNode<T> *t;
t=root;
while(t)
{
Visit(t);
if(t->LeftChild) Q.Add(t->LeftChild);
if(t->RightChild) Q.Add(t->RightChild);
Q.Delete(t)
}
}