数据结构和算法(c#实现)系列---树(一)_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 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);

}

}

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------------------------------------

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有