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来实现了。