C#线索二叉树

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

using System;

namespace BiThrTree

{

/// <summary>

/// 定义结点类:

/// </summary>

class BTNode

{

public char data;

public int ltag,rtag;//0表示线索,1表示结点

public BTNode lchild,rchild;

}

class BiThrTree

{

/// <summary>

/// 建立一棵新二叉树:

/// </summary>

/// <param name="T"></param>

static public void CreateBiThrTree(ref BTNode T)

{

char ch;

ch=(char)Console.Read();

if(ch=='#')

{

T=null;

}

else

{

T=new BTNode();

T.data=ch;

CreateBiThrTree(ref T.lchild);

CreateBiThrTree(ref T.rchild);

}

}

/// <summary>

/// 线索化二叉树:

/// </summary>

/// <param name="T"></param>

static BTNode pre,H;

static public void Threading(ref BTNode T)

{

H=pre=new BTNode();

pre.rchild=pre.lchild=null;

pre.rtag=pre.ltag=0;

Thread(ref T);

}

static public void Thread(ref BTNode T)

{

if(T!=null)

{

if(T.lchild==null){T.lchild=pre;T.ltag=0;}

else{T.ltag=1;}

if(T.rchild==null){T.rtag=0;}

else{T.rtag=1;}

if(pre.rchild==null&&pre.rtag==0)pre.rchild=T;

pre=T;

if(T.ltag==1)Thread(ref T.lchild);

if(T.rtag==1)Thread(ref T.rchild);

}

}

/// <summary>

/// 先序输出:

/// </summary>

static public void PrePrint(BTNode T)

{

if(T!=null)

{

Console.Write(T.data+"\t");

if(T.ltag==1)PrePrint(T.lchild);

if(T.rtag==1)PrePrint(T.rchild);

}

}

/// <summary>

/// 先序线索遍历输出:

/// </summary>

static public void PreThrPrint(BTNode T)

{

T=H.rchild;

//Console.WriteLine("H.rchild.date::"+H.rchild.data);

while(T!=null)

{

Console.Write(T.data+"\t");

if(T.rtag==0)T=T.rchild;

else{

if(T.ltag==1)T=T.lchild;

else{

T=T.rchild;

}

}

}

}

/// <summary>

/// Deepth of a BiThrTree:

/// </summary>

static public int Deepth(BTNode T)

{

int a,b;

if(T!=null)

{

if(T.ltag==1)a=Deepth(T.lchild);else a=0;

if(T.rtag==1)b=Deepth(T.rchild);else b=0;

return (1+max(a,b));

}

else

{

return 0;

}

}

static public int max(params int[] w)

{

int max;

max=w[0];

for(int i=0;i<w.Length;i++)

if(max<w[i])max=w[i];

return max;

}

/// <summary>

/// 复制线索二叉树:

/// </summary>

static public void DulplicateBiThrTree(BTNode T1,ref BTNode T2)

{

if(T1!=null)

{

T2=new BTNode();

T2.data=T1.data;

T2.ltag=T1.ltag;T2.rtag=T1.rtag;

if(T2.ltag==1)DulplicateBiThrTree(T1.lchild,ref T2.lchild);else T2.lchild=T1.lchild;

if(T2.rtag==1)DulplicateBiThrTree(T1.rchild,ref T2.rchild);else T2.rchild=T1.rchild;

}

}

static void Main()

{

BTNode mytree=null;

Console.WriteLine("Please input a tree(for example:abc##d##ed###):");

CreateBiThrTree(ref mytree);

Threading(ref mytree);

PrePrint(mytree);

Console.WriteLine("\n按先序输出:\n");

PreThrPrint(mytree);

Console.WriteLine("\n该树的深度为:{0}",Deepth(mytree));

BTNode mytree2=null;

Console.WriteLine("调用复制函数得到的新树为:");

DulplicateBiThrTree(mytree,ref mytree2);

PrePrint(mytree2);

Console.ReadLine();

Console.ReadLine();

}

}

}

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