heavenkiller(原創)

首先我們給樹下一個定義：

樹是一個有限的、非空的結點集，

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);

                   }

              }

         }

         //------------------------------------------------end------------------------------------

         //內部成員類 用于提供不同遍歷類型的訪問者

         public class preorder:iprepostvisitor

         {

              private ivisitor visitor;

              public preorder(ivisitor _vis){visitor=_vis;}

              #region iprepostvisitor 成員

              public void previsit(object _obj)

              {

                   // todo:  添加 preorder.previsit 實現

                   this.visitor.visit(_obj);

              }

              public void visit(object _obj)

              {

                   // todo:  添加 preorder.visit 實現

              }

              public void postvisit(object _obj)

              {

                   // todo:  添加 preorder.postvisitor 實現

              }

              #endregion

         }