C#ツリーの実装


ツリーの作成:
namespace BinaryTree
{
    /// <summary>
    ///          
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class Node<T> 
    {
        public T Data { get; set; } //   (    )
        public Node<T> LeftChild { get; set; } //   
        public Node<T> RightChild { get; set; } //   

        //   
        public Node(T value, Node<T> lChild, Node<T> rChild)
        {
            this.Data = value;
            this.LeftChild = lChild;
            this.RightChild = rChild;
        }

        //   
        public Node(Node<T> lChild, Node<T> rChild)
        {
            this.Data = default(T);
            this.LeftChild = lChild;
            this.RightChild = rChild;
        }

        //   
        public Node(T value)
        {
            this.Data = value;
            this.LeftChild = null;
            this.RightChild = null;
        }
    }

    /// <summary>
    ///                  BiTree<T>
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BiTree<T>
    {
        public Node<T> Head{get;set;}  //   

        //   
        public BiTree()
        {
            this.Head = null;
        }

        //   
        public BiTree(T value)
        {
            Node<T> p = new Node<T>(value);
            this.Head = p;
        }

        //   
        public BiTree(T val, Node<T> lp, Node<T> rp)
        {
            Node<T> p = new Node<T>(val, lp, rp);
            this.Head = p;
        }

         //         
        public bool IsEmpty()
        {
            if(this.Head ==null)
                return true;
            else
                return false;
        }

          //     
        public Node<T> Root()
        {
            return this.Head;
        }

        /// <summary>
        ///           
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> GetLeftChild(Node<T> p)
        {
            return p.LeftChild;
        }

        /// <summary>
        ///           
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> GetRightChild(Node<T> p)
        {
            return p.RightChild;
        }

        /// <summary>
        ///    p         val    .
        ///                .
        /// </summary>
        /// <param name="value"></param>
        /// <param name="p"></param>
        public void InsertLeftChild(T value,Node<T> p)
        {
            Node<T> temp = new Node<T>(value);
            temp.LeftChild = p.LeftChild;
            p.LeftChild = temp;

        }

        
        //   p         val    ,
        //               .
        public void InsertRightChild(T value, Node<T> p)
        {
            Node<T> temp = new Node<T>(value);
            //               
            temp.RightChild = p.RightChild;
            //p        
            p.RightChild = temp; 
        }

        /// <summary>
        ///   p   ,    p     
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> DeleteLeft(Node<T> p)
        {
            if(p ==null || p.LeftChild ==null)
            {
                return null;
            }
            Node<T> temp = p.LeftChild;
            temp.LeftChild = null;
            return temp;
        }

        /// <summary>
        ///   p   ,    p     
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public Node<T> DeleteRight(Node<T> p)
        {
            if ((p == null) || (p.RightChild == null))
            {
                return null;
            }
 
            Node<T> temp = p.RightChild;
            p.RightChild = null;
            return temp;
        }

        /// <summary>
        ///          
        /// </summary>
        /// <param name="p"></param>
        /// <returns></returns>
        public bool IsLeaf(Node<T> p)
        {
            if ((p != null) && (p.LeftChild == null) && (p.RightChild == null))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
 
        //    :           ,
        //            
        //     : A B C D E F G H I J
        //(        ,     )
        //1.    (DLR),    :        ,
        //          ,          .
        //   : A B D H I E J C F G
        public void PreOrder(Node<T> root)
        {
            //     
            if (root == null)
            {
                return;
            }
 
            //   :      
            Console.WriteLine("{0}", root.Data);
            //   :      
            PreOrder(root.LeftChild);
            //   :      
            PreOrder(root.RightChild);
        }

          //    (LDR),    :             ,
        //       ,           
        //   : H DI B E J E A F C G
        public void InOrder(Node<T> root)
        {
            //     
            if (root == null)
            {
                return;
            }
            //       
            InOrder(root.LeftChild);
            //     , :                     .
            Console.WriteLine("{0}", root.Data);
            //       .
            InOrder(root.RightChild);
        }

         //    (LRD):      :            ,
        //              ,        
        //   :  H I D J E B F G C A
        public void PostOrder(Node<T> root)
        {
            //     
            if (root == null)
            {
                return;
            }
            //       
            PostOrder(root.LeftChild);
            //       
            PostOrder(root.RightChild);
            //     
            Console.WriteLine("{0}", root.Data);
 
        }

        //(4).    (Level Order)
        //  :                      ,
        //          .
        //  ,         ,       ,         ,
        //      ,         :
        //(1).            ,       .
        //(2).          ,             ;
        //(3).          ,             ;
        public void LevelOrder(Node<T> root)
        {
            //     
            if (root == null)
            {
                return;
            }
 
            //               
            //...                 ,   .
        }

    }

}
    class Program
    {
        static void Main(string[] args)
        {
            Node<string>[] node = new Node<string>[8];
            //    
            node[0] = new Node<string>("A");
            node[1] = new Node<string>("B");
            node[2] = new Node<string>("C");
            node[3] = new Node<string>("D");
            node[4] = new Node<string>("E");
            node[5] = new Node<string>("F");
            node[6] = new Node<string>("G");
            node[7] = new Node<string>("H");
            //            ,           

            BiTree<string>[] biTree = new BiTree<string>[8];
            biTree[0] = new BiTree<string>("R");  //   
            biTree[0].Head.LeftChild = node[0];
            biTree[0].Head.RightChild = node[1];
            biTree[1] = new BiTree<string>("r1");
            biTree[1].Head.LeftChild = node[2];
            biTree[1].Head.RightChild = node[3];
            biTree[2] = new BiTree<string>("r2");
            biTree[2].Head.LeftChild = node[4];
            biTree[2].Head.RightChild = node[5];
            biTree[3] = new BiTree<string>("r3");
            biTree[3].Head.LeftChild = node[6];
            biTree[3].Head.RightChild = node[7];
            //biTree[3].Head.RightChild = biTree[6].Head;
            //biTree[4].Head.RightChild = biTree[7].Head;
            biTree[0].InOrder(biTree[1].Head);

            Console.Read();
        }
    }

参照先:http://www.csharpwin.com/csharpspace/2412.shtml
http://www.cnblogs.com/ppchouyou/archive/2008/07/18/1245819.html
http://tech.sina.com.cn/s/2008-06-20/1017701850.shtml
http://www.yqdown.com/chengxukaifa/CC/28584_3.htm