Posted on 2007-04-02 17:29
dennis 閱讀(1628)
評論(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來實現了。