C#的BinaryTree实现

发表于:2007-06-30来源:作者:点击数: 标签:
由于在一个程序中需要二叉树,所以在C#中作了一个。 程序中共三个类:BinaryTreeNode、BinaryTree、Visitor。 Visitor是一个delegate。 public class BinaryTreeNode { internal object _data; internal BinaryTreeNode _leftChild; internal BinaryTreeNode
由于在一个程序中需要二叉树,所以在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;
        }

原文转自:http://www.ltesting.net