程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 數據結構與算法(C#實現)系列---樹

數據結構與算法(C#實現)系列---樹

編輯：關於C語言

　首先我們給樹下一個定義：樹是一個有限的、非空的結點集， 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



   }

  }