數據結構與算法(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 cant 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 its 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, neednt 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);
}
