.net教程：c#线索二叉树
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)max=w;
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();
}
}
}
