C#的BinaryTree实现
发表于:2007-06-30来源:作者:点击数:
标签:
由于在一个程序中需要二叉树,所以在C#中作了一个。 程序中共三个类:BinaryTreeNode、BinaryTree、Visitor。 Visitor是一个delegate。 public class BinaryTreeNode { internal object _data; internal BinaryTreeNode _leftChild; internal BinaryTreeNode
由于在一个程序中需要二叉树,所以在C#中作了一个。
程序中共三个类:BinaryTreeNode、BinaryTree、Visitor。
Visitor是一个delegate。
public class BinaryTreeNode
{
internal object _data;
internal BinaryTreeNode _leftChild;
internal BinaryTreeNode _rightChild;
public BinaryTreeNode()
{
}
public BinaryTreeNode(object e)
{
_data = e;
}
public BinaryTreeNode(object e,
BinaryTreeNode left,
BinaryTreeNode right
)
{
_data = e;
_leftChild = left;
_rightChild = right;
}
}
public delegate void Visitor(BinaryTreeNode u);
public class BinaryTree
{
private BinaryTreeNode _root;
public BinaryTree()
{
}
public bool IsEmpty
{
get
{
return _root == null;
}
}
public bool Root(object x)
{
if(_root != null)
{
x = _root._data;
return true;
}
return false;
}
public void MakeTree(
object element,
BinaryTree left,
BinaryTree right
)
{
_root = new BinaryTreeNode(element, left._root, right._root);
left._root = null;
right._root = null;
}
public void BreakTree(
object element,
BinaryTree left,
BinaryTree right
)
{
element = _root._data;
left._root = _root._leftChild;
right._root = _root._rightChild;
_root = null;
}
/// <summary>
/// 前序遍历
/// </summary>
/// <param name="v"></param>
/// <param name="t"></param>
public void PreOrder(Visitor v, BinaryTreeNode t)
{
if(t != null)
{
v(t);
PreOrder(v, t._leftChild);
PreOrder(v, t._rightChild);
}
}
/// <summary>
/// 中序遍历
/// </summary>
/// <param name="v"></param>
/// <param name="t"></param>
public void InOrder(Visitor v, BinaryTreeNode t)
{
if(t != null)
{
InOrder(v, t._leftChild);
v(t);
InOrder(v, t._rightChild);
}
}
/// <summary>
/// 后序遍历
/// </summary>
/// <param name="v"></param>
/// <param name="t"></param>
public void PostOrder(Visitor v, BinaryTreeNode t)
{
if(t != null)
{
PostOrder(v, t._leftChild);
PostOrder(v, t._rightChild);
v(t);
}
}
/// <summary>
/// 逐层遍历
/// </summary>
/// <param name="v"></param>
public void LevelOrder(Visitor v)
{
Queue __q;
BinaryTreeNode __t;
__t = _root;
__q = new Queue();
while(__t != null)
{
v(__t);
if(__t._leftChild != null)
{
__q.Enqueue(__t._leftChild);
}
if(__t._rightChild != null)
{
__q.Enqueue(__t._rightChild);
}
try
{
__q.Dequeue();
}
catch
{
return;
}
}
}
public int Height(BinaryTreeNode t)
{
int __leftHeight, __rightHeight;
if(t == null)
{
return 0;
}
__leftHeight = Height(t._leftChild);
__rightHeight = Height(t._rightChild);
if(__leftHeight > __rightHeight)
{
return ++__leftHeight;
}
return ++__rightHeight;
}
public int Size
{
get
{
_count = 0;
PreOrder(new Visitor(Add1), _root);
return _count;
}
}
public void Delete()
{
PostOrder(new Visitor(Free), _root);
_root = null;
}
private static int _count;
private static void Add1(BinaryTreeNode t)
{
_count ++;
}
private static void Free(BinaryTreeNode t)
{
t = null;
}
}
原文转自:http://www.ltesting.net