首先我们给树下一个定义： 树是一个有限的、非空的结点集， 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);

[1] [2] 下一页  

频道声明：本频道的文章除部分特别声明禁止转载的专稿外，可以自由转载.但请务必注明出出处和原始作者 文章版权归本频道与文章作者所有.对于被频道转载文章的个人和网站,我们表示深深的谢意。 原始作者:佚名 录入时间:2006-10-26 信息来源:不详 投稿信箱:itqoo@126.com