分享
 
 
 

数据结构与算法(C#实现)系列---树

王朝c#·作者佚名  2006-11-24
窄屏简体版  字體: |||超大  

首先我们给树下一个定义: 树是一个有限的、非空的结点集, 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 实现

}

&

[1] [2] 下一页

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有