分享
 
 
 

一棵C#写的树(1)

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

C#的确是一个很好的面向对象语言,我看《数据结构(第二版)》那本书应该出本用C#描述的版本。下面是我用C#写的一棵树。先用接口把节点做了抽象定义,这样在实现遍历,插入等操作的时候只对接口进行操作。在程序中,我尽量使用C#的特性,如接口,属性,玫举,这样代码虽然看起来比较冗长,但是,当代码越来越长的时候,你就会从中看到优点,因为合理的结构让你永远思路清晰。这课树我只能算写了一个开头,因为如果要把所有类型的树和加在他们之上的算法都写出来,我看没有1~2k 行程序是绝对不行的,不过,只要有时间,我一定会继续写的,同时希望大家也写,把这个代码库完善起来。

using System;

using System.Collections;

///

/// author 何潇(sailer)( he_x@263.net )

///

namespace Tree

{

/// <summary>

/// LEFT左子树,RIGHT右子树

/// </summary>

enum Position{LEFT,RIGHT};

/// <summary>

/// LINK指向孩子,THREAD指向后继

/// </summary>

enum Tag{LINK,THREAD};

/// <summary>

/// 二叉树节点的抽象定义

/// </summary>

interface IBinNode

{

bool isLeaf();

object Element{get;set;}

IBinNode Left{get;set;}

IBinNode Right{get;set;}

}

/// <summary>

/// 遍历,线索化等操作的接口

/// </summary>

interface ITravelBinTree

{

void PreOrderTravel();

void InOrderTravel();

void RevOrderTravel();

void Print(IBinNode t);

}

interface IInsertBinTree

{

void Insert(IBinNode node,Position pos);

}

/// <summary>

/// Normal actualize of bintree

/// </summary>

class BinNodePtr : IBinNode

{

protected object element;

protected IBinNode lchild;

protected IBinNode rchild;

public BinNodePtr(object e,IBinNode left,IBinNode right)

{

element = e;

lchild = left;

rchild = right;

}

public BinNodePtr(object e)

{

element = e;

lchild = rchild = null;

}

public BinNodePtr()

{

element = null;

lchild = rchild =null;

}

public bool isLeaf()

{

if(lchild==null && rchild==null)

return true;

return false;

}

public object Element

{

get{return element;}

set{element = value;}

}

public IBinNode Left

{

get

{

return lchild;

}

set

{

lchild = value;

}

}

public IBinNode Right

{

get

{

return rchild;

}

set

{

rchild = value;

}

}

}

class BinNodeLine : BinNodePtr,IBinNode

{

private Tag ltag,rtag;

public BinNodeLine(object e,IBinNode left,IBinNode right) :base(e,left,right)

{ltag = rtag = Tag.LINK;}

public BinNodeLine(object e) : base(e)

{ltag = rtag = Tag.LINK;}

public Tag LTag

{

get{return ltag;}

set{ltag = value;}

}

public Tag RTag

{

get{return rtag;}

set{rtag = value;}

}

}

class TravelBinTree : ITravelBinTree,IInsertBinTree

{

const int INIT_TREE_SIZE=20;

private IBinNode tree;

private BinNodeLine head; //线索化后的头指针

private IBinNode prenode; //指向最近访问过的前驱节点

public TravelBinTree()

{

tree = new BinNodePtr();

}

public TravelBinTree(IBinNode INode)

{

tree = INode;

}

/// <summary>

/// 先序遍历树,用非递归算法实现

/// </summary>

/// <remarks>非递归实现</remarks>

public void PreOrderTravel()

{

IBinNode temptree;

Stack stk = new Stack(INIT_TREE_SIZE);

if(tree == null)

throw(new InvalidOperationException("访问的树为空"));

temptree = tree;

stk.Push(tree);

while(stk.Count!=0)

{

while(temptree!=null)

{

Print(temptree);

stk.Push(temptree.Left);

temptree = temptree.Left;

}

stk.Pop(); // 空指针退栈

if(stk.Count != 0)

{

temptree=(IBinNode)stk.Pop();

stk.Push(temptree.Right);

temptree = temptree.Right;

}

}

}

public void InOrderTravel()

{

InOrderTravel(tree);

}

private void InOrderTravel(IBinNode t)

{

if(t==null) return;

InOrderTravel(t.Left);

Print(t);

InOrderTravel(t.Right);

}

public void RevOrderTravel()

{

RevOrderTravel(tree);

}

private void RevOrderTravel(IBinNode t)

{

if(t==null) return;

RevOrderTravel(t.Left);

RevOrderTravel(t.Right);

Print(t);

}

public void Print(IBinNode t)

{

Console.Write(t.Element + ",");

}

public void Insert(IBinNode node,Position pos)

{

if(node == null)

throw(new InvalidOperationException("不能将空节点插入树"));

switch(pos)

{

case Position.LEFT : tree.Left = node;break;

case Position.RIGHT: tree.Right = node;break;

}

}

/// <summary>

/// 按照先序遍历顺序遍历树

/// </summary>

public void TreeBuilder()

{

Stack stk = new Stack(INIT_TREE_SIZE);

stk.Push(tree);

Position pos;

string para;

pos = Position.LEFT;

IBinNode baby,temp;

while(true)

{

para = Console.ReadLine();

if(para == "")

{

if(pos == Position.RIGHT)

{

stk.Pop();

while(stk.Count!=0 && ((IBinNode)stk.Peek()).Right!=null)

stk.Pop();

if(stk.Count ==0) break;

}

else

pos = Position.RIGHT;

}

else

{

if(tree.GetType().Equals()==true)

baby = new BinNodePtr(para);

temp = (IBinNode)stk.Peek();

if(pos == Position.LEFT)

temp.Left = baby;

else

temp.Right = baby;

pos = Position.LEFT;

stk.Push(baby);

}

}

}

/// <summary>

/// 中序线索化

/// </summary>

public void InOrderThreading()

{

head = new BinNodeLine("");

head.RTag = Tag.THREAD;

head.Right = head;

if(tree == null) head.Left = head;

else

{

head.Left = tree; prenode = head;

}

}

/// <summary>

/// 中序线索化的递归实现

/// </summary>

/// <param name="t"></param>

private void InThreading(IBinNode t)

{

if(t==null)

return;

else

{

InThreading(t.Left);

// if(left

}

}

}

/// <summary>

/// Summary description for Class1.

/// </summary>

class Class1

{

/// <summary>

/// 测试控制台

/// </summary>

/// <param name="args"></param>

static void Main(string[] args)

{

string para = null;

para = Console.ReadLine();

BinNodePtr root = new BinNodePtr(para);

TravelBinTree t = new TravelBinTree(root);

t.TreeBuilder();

t.PreOrderTravel();

Console.WriteLine("");

t.InOrderTravel();

Console.WriteLine("");

t.RevOrderTravel();

}

}

}

非常希望和大家交流( he_x@263.net )

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
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- 王朝網路 版權所有