C#ツリーの実装
ツリーの作成:
参照先:http://www.csharpwin.com/csharpspace/2412.shtml
http://www.cnblogs.com/ppchouyou/archive/2008/07/18/1245819.html
http://tech.sina.com.cn/s/2008-06-20/1017701850.shtml
http://www.yqdown.com/chengxukaifa/CC/28584_3.htm
namespace BinaryTree
{
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
public T Data { get; set; } // ( )
public Node<T> LeftChild { get; set; } //
public Node<T> RightChild { get; set; } //
//
public Node(T value, Node<T> lChild, Node<T> rChild)
{
this.Data = value;
this.LeftChild = lChild;
this.RightChild = rChild;
}
//
public Node(Node<T> lChild, Node<T> rChild)
{
this.Data = default(T);
this.LeftChild = lChild;
this.RightChild = rChild;
}
//
public Node(T value)
{
this.Data = value;
this.LeftChild = null;
this.RightChild = null;
}
}
/// <summary>
/// BiTree<T>
/// </summary>
/// <typeparam name="T"></typeparam>
public class BiTree<T>
{
public Node<T> Head{get;set;} //
//
public BiTree()
{
this.Head = null;
}
//
public BiTree(T value)
{
Node<T> p = new Node<T>(value);
this.Head = p;
}
//
public BiTree(T val, Node<T> lp, Node<T> rp)
{
Node<T> p = new Node<T>(val, lp, rp);
this.Head = p;
}
//
public bool IsEmpty()
{
if(this.Head ==null)
return true;
else
return false;
}
//
public Node<T> Root()
{
return this.Head;
}
/// <summary>
///
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public Node<T> GetLeftChild(Node<T> p)
{
return p.LeftChild;
}
/// <summary>
///
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public Node<T> GetRightChild(Node<T> p)
{
return p.RightChild;
}
/// <summary>
/// p val .
/// .
/// </summary>
/// <param name="value"></param>
/// <param name="p"></param>
public void InsertLeftChild(T value,Node<T> p)
{
Node<T> temp = new Node<T>(value);
temp.LeftChild = p.LeftChild;
p.LeftChild = temp;
}
// p val ,
// .
public void InsertRightChild(T value, Node<T> p)
{
Node<T> temp = new Node<T>(value);
//
temp.RightChild = p.RightChild;
//p
p.RightChild = temp;
}
/// <summary>
/// p , p
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public Node<T> DeleteLeft(Node<T> p)
{
if(p ==null || p.LeftChild ==null)
{
return null;
}
Node<T> temp = p.LeftChild;
temp.LeftChild = null;
return temp;
}
/// <summary>
/// p , p
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public Node<T> DeleteRight(Node<T> p)
{
if ((p == null) || (p.RightChild == null))
{
return null;
}
Node<T> temp = p.RightChild;
p.RightChild = null;
return temp;
}
/// <summary>
///
/// </summary>
/// <param name="p"></param>
/// <returns></returns>
public bool IsLeaf(Node<T> p)
{
if ((p != null) && (p.LeftChild == null) && (p.RightChild == null))
{
return true;
}
else
{
return false;
}
}
// : ,
//
// : A B C D E F G H I J
//( , )
//1. (DLR), : ,
// , .
// : A B D H I E J C F G
public void PreOrder(Node<T> root)
{
//
if (root == null)
{
return;
}
// :
Console.WriteLine("{0}", root.Data);
// :
PreOrder(root.LeftChild);
// :
PreOrder(root.RightChild);
}
// (LDR), : ,
// ,
// : H DI B E J E A F C G
public void InOrder(Node<T> root)
{
//
if (root == null)
{
return;
}
//
InOrder(root.LeftChild);
// , : .
Console.WriteLine("{0}", root.Data);
// .
InOrder(root.RightChild);
}
// (LRD): : ,
// ,
// : H I D J E B F G C A
public void PostOrder(Node<T> root)
{
//
if (root == null)
{
return;
}
//
PostOrder(root.LeftChild);
//
PostOrder(root.RightChild);
//
Console.WriteLine("{0}", root.Data);
}
//(4). (Level Order)
// : ,
// .
// , , , ,
// , :
//(1). , .
//(2). , ;
//(3). , ;
public void LevelOrder(Node<T> root)
{
//
if (root == null)
{
return;
}
//
//... , .
}
}
}
class Program
{
static void Main(string[] args)
{
Node<string>[] node = new Node<string>[8];
//
node[0] = new Node<string>("A");
node[1] = new Node<string>("B");
node[2] = new Node<string>("C");
node[3] = new Node<string>("D");
node[4] = new Node<string>("E");
node[5] = new Node<string>("F");
node[6] = new Node<string>("G");
node[7] = new Node<string>("H");
// ,
BiTree<string>[] biTree = new BiTree<string>[8];
biTree[0] = new BiTree<string>("R"); //
biTree[0].Head.LeftChild = node[0];
biTree[0].Head.RightChild = node[1];
biTree[1] = new BiTree<string>("r1");
biTree[1].Head.LeftChild = node[2];
biTree[1].Head.RightChild = node[3];
biTree[2] = new BiTree<string>("r2");
biTree[2].Head.LeftChild = node[4];
biTree[2].Head.RightChild = node[5];
biTree[3] = new BiTree<string>("r3");
biTree[3].Head.LeftChild = node[6];
biTree[3].Head.RightChild = node[7];
//biTree[3].Head.RightChild = biTree[6].Head;
//biTree[4].Head.RightChild = biTree[7].Head;
biTree[0].InOrder(biTree[1].Head);
Console.Read();
}
}
参照先:http://www.csharpwin.com/csharpspace/2412.shtml
http://www.cnblogs.com/ppchouyou/archive/2008/07/18/1245819.html
http://tech.sina.com.cn/s/2008-06-20/1017701850.shtml
http://www.yqdown.com/chengxukaifa/CC/28584_3.htm