//樹的孩子兄弟表示法為存儲(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){}
//訪問指針域的成員函數(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();
};
//樹類的實(shí)現(xiàn)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;}
  cout<<"釋放:"<<setw(2)<<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)  //當(dāng)為空樹時(shí)
  {root=curr=newNode;
   return;}
 if(curr->firstChild==NULL)//當(dāng)當(dāng)前結(jié)點(diǎn)無(wú)孩子時(shí)
  curr->firstChild=newNode;
 else                     //當(dāng)當(dāng)前結(jié)點(diǎn)有孩子時(shí)
  {TreeNode<T> *p=curr->firstChild;
   while(p->nextSibling!=NULL) p=p->nextSibling;
   p->nextSibling=newNode;
  }
  Current(newNode);//使新建立的結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn)
}      
template<class T>
int Tree<T>::DeleteChild(int i)
{TreeNode<T> *r=NULL;
 if(i==1)         //當(dāng)刪除當(dāng)前結(jié)點(diǎn)的第一棵子樹時(shí)
 {r=curr->firstChild;
  if(r==NULL) return 0;//要?jiǎng)h除子樹為空時(shí)返回
  curr->firstChild=r->nextSibling;//脫鏈要?jiǎng)h除的子樹
 }
 else {          //當(dāng)刪除當(dāng)前結(jié)點(diǎn)的其他子樹時(shí)
  int k=1;
  TreeNode<T> *p=curr->firstChild;
  while(p!=NULL&&k<=i-1)//尋找要?jiǎng)h除子樹的指針
  {p=p->nextSibling;
   k++;}
  if(p!=NULL)//尋找到要?jiǎng)h除的子樹的指針
  {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;//當(dāng)為空樹時(shí)
 TreeNode<T> *r=NULL,*q=root->firstChild;
 if(i==1&&q!=NULL) //當(dāng)?shù)谝唤Y(jié)點(diǎn)有孩子時(shí)
  {r=root->firstChild;
   root->firstChild=r->nextSibling;//脫鏈要?jiǎng)h除的子樹
  }
 else             //要?jiǎng)h除第一結(jié)點(diǎn)外的其他子樹時(shí)
  {int k=1;
   TreeNode<T> *p=root->firstChild;
   while(p!=NULL&&k<=i-1)//尋找要?jiǎng)h除子樹的指針
   {p=p->nextSibling;
    k++;
   }
  if(p!=NULL)    //尋找到要?jiǎng)h除的子樹的指針
   {r=p->nextSibling;
    if(r!=NULL)
     p->nextSibling=r->nextSibling;//脫鏈要?jiǎng)h除的子樹
    else return 0;}
  else return 0;
 }
 DeleteSubTree(r);//調(diào)用函數(shù)執(zhí)行刪除
 return 1;    
}
template<class T>
void Tree<T>::PreOrderTree(TreeNode<T> *&t)
{if(t==NULL) return;
 cout<<setw(2)<<t->data;//顯示根結(jié)點(diǎn)數(shù)據(jù)
 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);
 cout<<setw(2)<<t->data;//顯示根結(jié)點(diǎn)數(shù)據(jù)
 if(t->nextSibling!=NULL)
  PosOrderTree(t->nextSibling);
}
//樹類相關(guān)操作的測(cè)試TreeM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<conio.h>
#include "Tree.h"
#include "Tree.cpp"
void main()
{cout<<"TreeM.cpp運(yùn)行結(jié)果:\n";
 int i;
 Tree<char> t;
 t.InsertChild('A');
 for(i=0;i<7;i++)
 {t.Root();
  if(i>=3&&i<5) t.FirstChild();
  t.InsertChild('B'+i);
 }
 cout<<"按后根遍歷顯示的結(jié)點(diǎn)次序?yàn)?\n";
 t.DisplayTree1();
 int k;
 cout<<"\n輸入欲刪除第幾個(gè)結(jié)點(diǎn)(k):";cin>>k;
 if(t.DeleteChild1(k))
   cout<<"\n第"<<k<<"個(gè)孩子結(jié)點(diǎn),刪除成功!\n";
 else cout<<"\n第"<<k<<"個(gè)孩子結(jié)點(diǎn),刪除失敗!\n";
 cout<<"按先根遍歷顯示的結(jié)點(diǎn)次序?yàn)?\n";
 t.DisplayTree();
 getch();
 cout<<endl<<"析構(gòu)函數(shù)按后根遍歷釋放結(jié)點(diǎn)的次序?yàn)?\n";}
TreeM.cpp運(yùn)行結(jié)果:
按后根遍歷顯示的結(jié)點(diǎn)次序?yàn)?
 E F B C D G H A
輸入欲刪除第幾個(gè)結(jié)點(diǎn)(k):1
釋放: E釋放: F釋放: B
第1個(gè)孩子結(jié)點(diǎn),刪除成功!
按先根遍歷顯示的結(jié)點(diǎn)次序?yàn)?
 A C D G H
析構(gòu)函數(shù)按后根遍歷釋放結(jié)點(diǎn)的次序?yàn)?
釋放: C釋放: D釋放: G釋放: H釋放: A

TreeM.cpp運(yùn)行結(jié)果:
按后根遍歷顯示的結(jié)點(diǎn)次序?yàn)?
 E F B C D G H A
輸入欲刪除第幾個(gè)結(jié)點(diǎn)(k):3
釋放: G
第3個(gè)孩子結(jié)點(diǎn),刪除成功!
按先根遍歷顯示的結(jié)點(diǎn)次序?yàn)?
 A B E F C D H
析構(gòu)函數(shù)按后根遍歷釋放結(jié)點(diǎn)的次序?yàn)?
釋放: E釋放: F釋放: B釋放: C釋放: D釋放: H釋放: A