数据结构与算法 (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
{
///
1<summary>
2
3/// Tree 的摘要说明。
4
5/// when traverse, traversaltype can't be changed,or throw a exception
6
7/// 支持枚举、比较、深度复制
8
9/// </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
}