Posted on 2007-04-02 17:29
dennis 阅读(1595)
评论(1) 编辑 收藏 所属分类:
C#历程 、
数据结构与算法
二叉查找树（binary search tree)
1）概念：对于树中的每个节点n，其左子节点中保存的所有数值都小于n保存的数值，右子节点保存的数值都大于n保存的数值。
2）二叉查找树可以实现更为优越的查找性能，主要实现方式有数组和链表结构，相比较而言，链表实现更为容易，因为数组实现删除和添加功能需要移动数组元素（如填补删除空位等）
今天下午在打印问题搞定后用C#实现了一下，比java版本比较有趣的使用C#的delegate来代替遍历二叉树时的visit方法，这样一来可以在遍历时对节点进行你所想要的任何操作。我们知道C#的delegate是类型化的函数指针，而C++的函数指针可以模仿动态语言的闭包或者匿名函数。这里也有这样的味道。
代码如下，只实现了整数型的，节点定义：
public class BSTIntNode
{
public int value;
public BSTIntNode left;
public BSTIntNode right;
public BSTIntNode(int value, BSTIntNode left, BSTIntNode right)
{
this.value = value;
this.left = left;
this.right = right;
}
public BSTIntNode(int value)
{
this.value = value;
this.left = null;
this.right = null;
}
}
然后定义一个Delegate，作为遍历时的访问方法：
public delegate void Visit(BSTIntNode node);
然后就是二叉树的实现，删除算法只实现了复制删除法：
public class BSTIntTree
{
protected BSTIntNode root;
public Visit visit;
public BSTIntTree()
{
this.root = null;
}
private BSTIntNode Search(BSTIntNode node, int el)
{
while (node != null)
{
if (el == node.value)
return node;
else if (el < node.value)
node = node.left;
else
node = node.right;
}
return null;
}
//查找
public BSTIntNode Search(int el)
{
return Search(root, el);
}
//广度优先遍历,利用队列实现,至上而下，至左而右
public void BreadthFirst()
{
BSTIntNode p = root;
Queue queue = new ListQueue();
if (p != null)
{
queue.Enqueue(p);
while (!queue.IsEmpty())
{
p = (BSTIntNode)queue.Dequeue();
visit(p);
if (p.left != null)
queue.Enqueue(p.left);
if (p.right != null)
queue.Enqueue(p.right);
}
}
}
//深度优先遍历，递归实现线序，中序和后序
//先序
protected void PreOrder(BSTIntNode p)
{
if (p != null)
{
visit(p);
PreOrder(p.left);
PreOrder(p.right);
}
}
public void PreOrder()
{
PreOrder(root);
}
//中序
protected void InOrder(BSTIntNode p)
{
if (p != null)
{
InOrder(p.left);
visit(p);
InOrder(p.right);
}
}
public void InOrder()
{
InOrder(root);
}
//后序
protected void PostOrder(BSTIntNode p)
{
if (p != null)
{
PostOrder(p.left);
PostOrder(p.right);
visit(p);
}
}
public void PostOrder()
{
PostOrder(root);
}
//插入节点操作
public void Insert(int el)
{
BSTIntNode p = root, prev = null;
//查找节点位置
while (p != null)
{
prev = p;
if (p.value < el)
p = p.right;
else
p = p.left;
}
if (root == null) //空树
root = new BSTIntNode(el);
else if (prev.value < el) //大于节点，插入右子树
prev.right = new BSTIntNode(el);
else
prev.left = new BSTIntNode(el);
}
//复制删除法的实现，归并删除法可能改变树的高度
public void Delete(int el)
{
BSTIntNode node, p = root, prev = null;
//查找节点位置
while (p != null&&p.value!=el)
{
prev = p;
if (p.value < el)
p = p.right;
else
p = p.left;
}
node = p;
if (p != null && p.value == el)
{
if (node.right == null)
node = node.left;
else if (node.left == null)
node = node.right;
else
{
BSTIntNode temp = node.left;
BSTIntNode previous = node;
while (temp.right != null) //查找左字节数的最右子节点
{
previous = temp;
temp = temp.right;
}
node.value = temp.value;
if (previous == node)
previous.left = temp.left;
else
previous.right = temp.left;
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else
prev.right = node;
}
else if (root != null)
{
Console.WriteLine("没有找到节点：{0}", el);
}
else
Console.WriteLine("树为空！");
}
}
注意，在树中我们维持了一个Visit的delegate，看看使用方法：
public static void Main(string[] args)
{
BSTIntTree tree=new BSTIntTree();
int []num={10,20,6,12,23,15,8};
for (int i = 0; i < num.Length; i++)
tree.Insert(num[i]);
//添加遍历处理函数，可以有多个
tree.visit += new Visit(printNode);
Console.WriteLine("广度优先遍历");
tree.BreadthFirst();
Console.WriteLine("先序");
tree.PreOrder();
Console.WriteLine("中序");
tree.InOrder();
Console.WriteLine("后序");
tree.PostOrder();
tree.Delete(8);
tree.Delete(15);
Console.WriteLine("删除后广度优先遍历");
tree.BreadthFirst();
}
public static void printNode(BSTIntNode node)
{
Console.WriteLine("访问节点:{0}", node.value);
}
可以看到，C#的delegate机制非常有趣，如果在java中恐怕需要用inner class来实现了。