首先我們給樹下一個定義： 樹是一個有限的、非空的結點集， t={r} or t1 or t2 or…or tn 
   
　　它具有下列性質： 
   
　　1．集合指定的結點r叫做樹的根結點 
   
　　2．其余的結點可以劃分成n個子集，t1,t2,…tn(n>=0),其中每一個子集都是一棵樹。 
       
　　樹的其它定義如度，葉子，高等就請大家查閱別的資料吧，到處都有的。 
   
　　樹的主要性質一個就是遍歷，分為深度遍歷和廣度遍歷 
   
　　在這里分別實現為depthfirsttravesal()和widthfirsttravesal() 
   
　　其中深度遍歷又分為前序遍歷、中序遍歷、和后序遍歷 ，這是是采用適配器技術實現的。 
    
  using system;
  
  using system.collections;
  
  
  
  namespace datastructure
  
  {
  
   /// <summary>
  
   /// tree 的摘要說明。
  
   /// when traverse, traversaltype can't be changed,or throw a exception
  
   /// 支持枚舉、比較、深度復制
  
   /// </summary>
  
   public abstract class tree:ienumerable,icomparable
  
   {
  
   public tree()
  
   {
  
   //
  
   // todo: 在此處添加構造函數邏輯
  
   //
  
   }
  
   protected queue keyqueue=new queue();//僅僅用于枚舉時存放數據，不參與equals實現中的比較
  
   protected traversaltype traversaltype=traversaltype.breadth;// choose a traversal type,and depthfirst is default
  
   //protected uint degree=0;//degree of the tree, init it as 0
  
   //protected uint height=0;//height of the tree, init it as 0
  
  
  
   //枚舉不同的遍歷類型
  
   public enum traversaltype
  
   {
  
   breadth=1,//廣度遍歷
  
   predepth=2,//前序遍歷
  
   indepth=3,//中序遍歷
  
   postdepth=4//后序遍歷
  
  
  
   };
  
   //public virtual abstract object key{}
  
  
  
   public abstract tree this[uint _index]{get;set;}//if i only use get, can i change it later?
  
  
  
   public abstract object key{get;}
  
   public abstract uint degree{get;}
  
   //public abstract uint height{get;}
  
   public void settraversaltype(traversaltype _type){traversaltype=_type;}//set a traversal a type, if it's not set manually, depthfirst will be chosen in default
  
  
  
   public abstract bool isempty();// property takes the place of isempty()
  
   public abstract bool isleaf();
  
  
  
   //only visit, needn't queue
  
   public virtual void depthfirsttraversal(iprepostvisitor _vis)//middle depthfirst traversal
  
   {
  
   //通過_vis使用不同的訪問者來進行前序、后序、中序遍歷 
    
   if(!isempty())
  
   {
  
   _vis.previsit(this.key);
  
  
  
   if( this.degree>=1 )
  
   {
  
   if( this.degree>=2)
  
   {
  
   for(uint i=0;i<(this.degree-1);i++)//
  
   {
  
   this[i].depthfirsttraversal(_vis);//recursive call
  
   //_vis.visit(this.key);
  
   }
  
   }
  
   this[this.degree-1].depthfirsttraversal(_vis);
  
   }
  
  
  
   _vis.postvisit(this.key);
  
   } 
    
   
   } 
   
     
   public virtual void breadthfirsttraversal(ivisitor _vis)//breadth first traversal
  
   {
  
   queue tmpqueue=new queue();//used to help breadthfirsttraversal
  
   //this.keyqueue=new queue();//store keys
  
  
  
   if(!this.isempty())
  
   tmpqueue.enqueue(this);//enqueue the root node at first
  
   while(tmpqueue.count!=0)//until the number of the queue is zero
  
   {
  
   tree headtree=(tree)tmpqueue.dequeue();
  
   //this.keyqueue.enqueue(headtree.key);
  
   _vis.visit(headtree.key);
  
  
  
   for(uint i=0;i<headtree.degree;i++)
  
   {
  
   tree childtree=headtree[i];
  
   if(!childtree.isempty())
  
   tmpqueue.enqueue(childtree);
  
   }
  
   }
  
  
  
   }

public class inorder:iprepostvisitor
  
   {
  
   private ivisitor visitor;
  
   public inorder(ivisitor _vis){visitor=_vis;}
  
   #region iprepostvisitor 成員
  
  
  
   public void previsit(object _obj)
  
   {
  
   // todo: 添加 inorder.previsit 實現
  
   }
  
  
  
   public void visit(object _obj)
  
   {
  
   // todo: 添加 inorder.visit 實現
  
   this.visitor.visit(_obj);
  
   }
  
  
  
   public void postvisit(object _obj)
  
   {
  
   // todo: 添加 inorder.postvisitor 實現
  
   }
  
  
  
   #endregion
  
  
  
   }
  
   public class postorder:iprepostvisitor
  
   {
  
   private ivisitor visitor;
  
   public postorder(ivisitor _vis){visitor=_vis;}
  
   #region iprepostvisitor 成員
  
  
  
   public void previsit(object _obj)
  
   {
  
   // todo: 添加 postorder.previsit 實現
  
   }
  
  
  
   public void visit(object _obj)
  
   {
  
   // todo: 添加 postorder.visit 實現
  
   }
  
  
  
   public void postvisit(object _obj)
  
   {
  
   // todo: 添加 postorder.postvisitor 實現
  
   this.visitor.visit(_obj);
  
   }
  
  
  
   #endregion
  
  
  
   }
  
   protected class enumvisitor:ivisitor
  
   {
  
   queue thisqueue;
  
   public enumvisitor(queue _que)
  
   {
  
   this.thisqueue=_que;
  
   }
  
   #region ivisitor 成員
  
  
  
   public void visit(object _obj)
  
   {
  
   // todo: 添加 enumvisitor.visit 實現
  
   this.thisqueue.enqueue(_obj);
  
   }
  
  
  
   #endregion
  
   }   
   
   #region ienumerable 成員
  
  
  
   public ienumerator getenumerator()
  
   {
  
   // todo: 添加 tree.getenumerator 實現
  
   enumvisitor vis=new enumvisitor(this.keyqueue);
  
   switch (this.traversaltype)
  
   {
  
   case traversaltype.breadth:
  
   breadthfirsttraversal(vis);
  
   break;
  
   case traversaltype.predepth:
  
   preorder previs=new preorder(vis);
  
   depthfirsttraversal(previs);
  
   break;
  
   case traversaltype.indepth:
  
   inorder invis=new inorder(vis);
  
   depthfirsttraversal(invis);
  
   break;
  
   case traversaltype.postdepth:
  
   postorder postvis=new postorder(vis);
  
   depthfirsttraversal(postvis);
  
   break;
  
  
  
   default:
  
   console.writeline("warning:please set a travel type first!--void settraversaltype(traversaltype _type) ");
  
   //throw new exception("warning:please set a travel type first!");//if not set a type, a exception will happen
  
   break;
  
   }
  
   return this.keyqueue.getenumerator();
  
   } 

   #endregion

//overwrite object.equals() --- reference type realization
  
   public override bool equals(object _obj)
  
   {
  
   if( _obj==null )
  
   return false;//因為this不可能為null
  
   if( ! (this.gettype()==_obj.gettype()) )
  
   return false;//類型不相等也不相等
  
   tree tmpobj=(tree)_obj;
  
   //比較引用成員
  
   if( !object.equals(this.key,tmpobj.key) )
  
   return false;
  
  
  
   //比較值類型成員
  
   if( !this.degree.equals(tmpobj.degree) )
  
   return false;
  
   //if( !this.height.equals(tmpobj.height) )
  
   //return false;
  
  
  
   return true;
  
   }
  
   //在此重載 ==,!= 后， 在以后繼承的類中不必實現了
  
   public static bool operator==(tree _treea,tree _treeb)
  
   {
  
   return object.equals(_treea,_treeb);
  
   }
  
   public static bool operator!=(tree _treea,tree _treeb)
  
   {
  
   return !(_treea==_treeb);
  
   }   
   
    
   #region icomparable 成員
  
  
  
   public virtual int compareto(object obj)
  
   {
  
   // todo: 添加 tree.compareto 實現
  
   return 0;
  
   }
  
  
  
   #endregion
  
  
  
   }
  
  }