用C#实现数据结构--树(一)

                                          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

         }