首先我们给树下一个定义： 树是一个有限的、非空的结点集， 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
}
}
新闻热点
疑难解答
