//樹類的實現Tree.cpp
template<class T>
void Tree<T>::DeleteSubTree(TreeNode<T> *&t)
{if(t==NULL) return;
 TreeNode<T> *q=t->firstChild,*p;
 while(q!=NULL)
 {p=q->nextSibling;
  DeleteSubTree(q);
  q=p;}
  printf("釋放:%2c",t->data);
  delete t;
}
template<class T>
int Tree<T>::Current(TreeNode<T> *&t)
{if(t==NULL) return 0;
 curr=t;
 return 1;
}
template<class T>
int Tree<T>::Root()
{if(root==NULL)
  {curr=NULL;
   return 0;}
 return Current(root);
}
template<class T>
int Tree<T>::FirstChild()
{if(curr!=NULL&&curr->firstChild!=NULL)
  return Current(curr->firstChild);
 else return 0;
}
template<class T>
int Tree<T>::NextSibling()
{if(curr!=NULL&&curr->nextSibling!=NULL)
  return Current(curr->nextSibling);
 else return 0;
}
template<class T>
int Tree<T>::Parent()
{if(curr==NULL)
  {curr=root;
   return 0;}
 TreeNode<T> *p=SearchParent(root,curr);
 if(p==NULL) return 0;
 else return Current(p);
}
template<class T>
TreeNode<T> *Tree<T>::SearchParent(TreeNode<T> *&root,TreeNode<T> *&s)
{if(root==NULL) return NULL;
 if(root->FirstChild()==s||root->NextSibling()==s)
  return root;
 TreeNode<T> *p;
 if((p=SearchParent(root->FirstChild(),s))!=NULL) return p;
 if((p=SearchParent(root->NextSibling(),s))!=NULL) return p;
 return NULL;
}
template<class T>
void Tree<T>::InsertChild(T value)
{TreeNode<T> *newNode=new TreeNode<T> (value);
 if(root==NULL)  //當為空樹時
  {root=curr=newNode;
   return;}
 if(curr->firstChild==NULL)//當當前結點無孩子時
  curr->firstChild=newNode;
 else                     //當當前結點有孩子時
  {TreeNode<T> *p=curr->firstChild;
   while(p->nextSibling!=NULL) p=p->nextSibling;
   p->nextSibling=newNode;
  }
  Current(newNode);//使新建立的結點成為當前結點
}      
template<class T>
int Tree<T>::DeleteChild(int i)
{TreeNode<T> *r=NULL;
 if(i==1)         //當刪除當前結點的第一棵子樹時
 {r=curr->firstChild;
  if(r==NULL) return 0;//要刪除子樹為空時返回
  curr->firstChild=r->nextSibling;//脫鏈要刪除的子樹
 }
 else {          //當刪除當前結點的其他子樹時
  int k=1;
  TreeNode<T> *p=curr->firstChild;
  while(p!=NULL&&k<=i-1)//尋找要刪除子樹的指針
  {p=p->nextSibling;
   k++;}
  if(p!=NULL)//尋找到要刪除的子樹的指針
  {r=p->nextSibling;
   if(r!=NULL)
    p->nextSibling=r->nextSibling;
   else return 0;
  }
  else return 0;
 }
 DeleteSubTree(r);
 return 1;
}
template<class T>
int Tree<T>::DeleteChild1(int i)
{if(root==NULL) return 0;//當為空樹時
 TreeNode<T> *r=NULL,*q=root->firstChild;
 if(i==1&&q!=NULL) //當第一結點有孩子時
  {r=root->firstChild;
   root->firstChild=r->nextSibling;//脫鏈要刪除的子樹
  }
 else             //要刪除第一結點外的其他子樹時
  {int k=1;
   TreeNode<T> *p=root->firstChild;
   while(p!=NULL&&k<=i-1)//尋找要刪除子樹的指針
   {p=p->nextSibling;
    k++;
   }
  if(p!=NULL)    //尋找到要刪除的子樹的指針
   {r=p->nextSibling;
    if(r!=NULL)
     p->nextSibling=r->nextSibling;//脫鏈要刪除的子樹
    else return 0;}
  else return 0;
 }
 DeleteSubTree(r);//調用函數執行刪除
 return 1;    
}
template<class T>
void Tree<T>::PreOrderTree(TreeNode<T> *&t)
{if(t==NULL) return;
 cout<<setw(2)<<t->data;//顯示根結點數據
 if(t->firstChild!=NULL)//先根遍歷子樹
  PreOrderTree(t->firstChild);
 if(t->nextSibling!=NULL)
  PreOrderTree(t->nextSibling);
}
template<class T>
void Tree<T>::DisplayTree()
{PreOrderTree(root);}

template<class T>
void Tree<T>::DisplayTree1()
{PosOrderTree(root);}

template<class T>
void Tree<T>::PosOrderTree(TreeNode<T> *&t)
{if(t==NULL) return;
 if(t->firstChild!=NULL)//后根遍歷子樹
  PosOrderTree(t->firstChild);
 printf("%2c",t->data);//顯示根結點數據
 if(t->nextSibling!=NULL)
  PosOrderTree(t->nextSibling);
}