C#的BinaryTree实现

C#的BinaryTree实现

- 中国WEB开发者网络 (http://www.webasp.net)
-- 技术教程 (http://www.webasp.net/article/)
--- C#的BinaryTree实现 (http://www.webasp.net/article/5/4182.htm)

-- 作者：未知
-- 发布日期： 2003-07-12

由于在一个程序中需要二叉树，所以在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;
        }
}

webasp.net