当前页面位置: » 丰搜网 » 文档中心 » 详细内容
数据结构与算法(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
}
