C#的確是一個(gè)很好的面向?qū)ο笳Z(yǔ)言，我看《數(shù)據(jù)結(jié)構(gòu)(第二版)》那本書應(yīng)該出本用C#描述的版本。下面是我用C#寫的一棵樹。先用接口把節(jié)點(diǎn)做了抽象定義，這樣在實(shí)現(xiàn)遍歷，插入等操作的時(shí)候只對(duì)接口進(jìn)行操作。在程序中，我盡量使用C#的特性，如接口，屬性，玫舉，這樣代碼雖然看起來(lái)比較冗長(zhǎng)，但是，當(dāng)代碼越來(lái)越長(zhǎng)的時(shí)候，你就會(huì)從中看到優(yōu)點(diǎn)，因?yàn)楹侠淼慕Y(jié)構(gòu)讓你永遠(yuǎn)思路清晰。這課樹我只能算寫了一個(gè)開頭，因?yàn)槿绻�要把所有類型的樹和加在他們之上的算法都寫出�?lái)，我看沒(méi)有1~2k 行程序是絕對(duì)不行的，不過(guò)，只要有時(shí)間，我一定會(huì)繼續(xù)寫的，同時(shí)希望大家也寫，把這個(gè)代碼庫(kù)完善起來(lái)。
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>
/// 二叉樹節(jié)點(diǎn)的抽象定義
/// </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; //指向最近訪問(wèn)過(guò)的前驅(qū)節(jié)點(diǎn)
public TravelBinTree()
{
 tree = new BinNodePtr();
}
public TravelBinTree(IBinNode INode)
{
 tree = INode;
}
/// <summary>
/// 先序遍歷樹,用非遞歸算法實(shí)現(xiàn)
/// </summary>
/// <remarks>非遞歸實(shí)現(xiàn)</remarks>
public void PreOrderTravel()
{
 IBinNode temptree;
 Stack stk = new Stack(INIT_TREE_SIZE);
 if(tree == null)
throw(new InvalidOperationException("訪問(wèn)的樹為空"));
 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("不能將空節(jié)點(diǎn)插入樹"));
 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>
/// 中序線索化的遞歸實(shí)現(xiàn)
/// </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>
/// 測(cè)試控制臺(tái)
/// </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 )