数据结构与算法(C#实现)系列－－-树(一)

　 数据结构与算法(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

　　 }