二叉查找樹(shù)（binary search tree)
1）概念：對(duì)于樹(shù)中的每個(gè)節(jié)點(diǎn)n，其左子節(jié)點(diǎn)中保存的所有數(shù)值都小于n保存的數(shù)值，右子節(jié)點(diǎn)保存的數(shù)值都大于n保存的數(shù)值。
2）二叉查找樹(shù)可以實(shí)現(xiàn)更為優(yōu)越的查找性能，主要實(shí)現(xiàn)方式有數(shù)組和鏈表結(jié)構(gòu)，相比較而言，鏈表實(shí)現(xiàn)更為容易，因?yàn)閿?shù)組實(shí)現(xiàn)刪除和添加功能需要移動(dòng)數(shù)組元素（如填補(bǔ)刪除空位等）
今天下午在打印問(wèn)題搞定后用C#實(shí)現(xiàn)了一下，比java版本比較有趣的使用C#的delegate來(lái)代替遍歷二叉樹(shù)時(shí)的visit方法，這樣一來(lái)可以在遍歷時(shí)對(duì)節(jié)點(diǎn)進(jìn)行你所想要的任何操作。我們知道C#的delegate是類型化的函數(shù)指針，而C++的函數(shù)指針可以模仿動(dòng)態(tài)語(yǔ)言的閉包或者匿名函數(shù)。這里也有這樣的味道。
代碼如下，只實(shí)現(xiàn)了整數(shù)型的，節(jié)點(diǎn)定義：
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;
}
}
然后定義一個(gè)Delegate，作為遍歷時(shí)的訪問(wèn)方法：
public delegate void Visit(BSTIntNode node);
然后就是二叉樹(shù)的實(shí)現(xiàn)，刪除算法只實(shí)現(xiàn)了復(fù)制刪除法：
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);
}
//廣度優(yōu)先遍歷,利用隊(duì)列實(shí)現(xiàn),至上而下，至左而右
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);
}
}
}
//深度優(yōu)先遍歷，遞歸實(shí)現(xiàn)線序，中序和后序
//先序
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);
}
//插入節(jié)點(diǎn)操作
public void Insert(int el)
{
BSTIntNode p = root, prev = null;
//查找節(jié)點(diǎn)位置
while (p != null)
{
prev = p;
if (p.value < el)
p = p.right;
else
p = p.left;
}
if (root == null) //空樹(shù)
root = new BSTIntNode(el);
else if (prev.value < el) //大于節(jié)點(diǎn)，插入右子樹(shù)
prev.right = new BSTIntNode(el);
else
prev.left = new BSTIntNode(el);
}
//復(fù)制刪除法的實(shí)現(xiàn)，歸并刪除法可能改變樹(shù)的高度
public void Delete(int el)
{
BSTIntNode node, p = root, prev = null;
//查找節(jié)點(diǎn)位置
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) //查找左字節(jié)數(shù)的最右子節(jié)點(diǎn)
{
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("沒(méi)有找到節(jié)點(diǎn)：{0}", el);
}
else
Console.WriteLine("樹(shù)為空！");
}
}
注意，在樹(shù)中我們維持了一個(gè)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]);
//添加遍歷處理函數(shù)，可以有多個(gè)
tree.visit += new Visit(printNode);
Console.WriteLine("廣度優(yōu)先遍歷");
tree.BreadthFirst();
Console.WriteLine("先序");
tree.PreOrder();
Console.WriteLine("中序");
tree.InOrder();
Console.WriteLine("后序");
tree.PostOrder();
tree.Delete(8);
tree.Delete(15);
Console.WriteLine("刪除后廣度優(yōu)先遍歷");
tree.BreadthFirst();
}
public static void printNode(BSTIntNode node)
{
Console.WriteLine("訪問(wèn)節(jié)點(diǎn):{0}", node.value);
}
可以看到，C#的delegate機(jī)制非常有趣，如果在java中恐怕需要用inner class來(lái)實(shí)現(xiàn)了。