//樹的孩子兄弟表示法為存儲(chǔ)結(jié)構(gòu)的結(jié)構(gòu)體Tree.h
template<class T> class Tree;
template<class T> struct TreeNode
{friend class Tree<T>;//樹類為友元
 private:
  TreeNode<T> *firstChild;//第一個(gè)孩子結(jié)點(diǎn)指針域
  TreeNode<T> *nextSibling;//下一個(gè)兄弟結(jié)點(diǎn)指針域
 public:
  T data;//數(shù)據(jù)域
//構(gòu)造函數(shù)
  TreeNode(T value,TreeNode<T> *fc=NULL,
    TreeNode<T> *ns=NULL):data(value),
     firstChild(fc),nextSibling(ns){}
//訪問(wèn)指針域的成員函數(shù)
  TreeNode<T>* &FirstChild()
   {return firstChild;}
  TreeNode<T>* &NextSibling()
   {return nextSibling;}
};
//樹類
template<class T> class Tree
{private:
  TreeNode<T> *root;//根結(jié)點(diǎn)指針
  TreeNode<T> *curr;//當(dāng)前結(jié)點(diǎn)指針
  //顯示以t為先根結(jié)點(diǎn)的樹的數(shù)據(jù)域
  void PreOrderTree(TreeNode<T> *&t);
  //顯示以t為后根結(jié)點(diǎn)的樹的數(shù)據(jù)域
  void PosOrderTree(TreeNode<T> *&t);
  //使當(dāng)前結(jié)點(diǎn)為t所指結(jié)點(diǎn)
  int Current(TreeNode<T> *&t);
  //在樹root中回溯查找結(jié)點(diǎn)s的雙親結(jié)點(diǎn)
  TreeNode<T> *SearchParent(TreeNode<T> *&root,TreeNode<T> *&s);
 public:
  //構(gòu)造函數(shù)與析構(gòu)函數(shù)
  Tree(){root=curr=NULL;}
  ~Tree(){DeleteSubTree(root);}
  //使根結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
  int Root();
  //使當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
  int Parent();
  //使當(dāng)前結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
  int FirstChild();
  //使當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
  int NextSibling();
  //把valve插入到當(dāng)前結(jié)點(diǎn)的最后一個(gè)結(jié)點(diǎn)
  void InsertChild(T value);
  //刪除以t為根結(jié)點(diǎn)的子樹
  void DeleteSubTree(TreeNode<T> *&t);
  //刪除當(dāng)前結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)
  int DeleteChild(int i);
  //刪除以root為根結(jié)點(diǎn)的子樹的第i個(gè)孩子結(jié)點(diǎn)
  int DeleteChild1(int i);
  //按先根遍歷次序顯示樹的數(shù)據(jù)域值
  void DisplayTree();
  //按后根遍歷次序顯示樹的數(shù)據(jù)域值
  void DisplayTree1();
};