C#實現的BinaryTree

2019-11-17 03:56:01

字體：大中小

來源：轉載

供稿：網友

確切的說，該二叉樹更類似于二叉排序樹，在判斷了節點是否可以進行比較操作后，根據給定的比較操作進行節點的插入。

using  System;
using  System.Collections;

namespace  SEI.DL88250.SourceCodes.BinaryTree
{
     ///   <summary> 二叉樹節點類 </summary>
     class  TreeNode
    {
         ///   <summary> 當前節點的出現計數 </summary>
         PRivate   int  _occurs;
         ///   <summary> 當前節點值 </summary>
         private   object  _nval;
         ///   <summary> 左孩子節點 </summary>
         private  TreeNode _lchild;
         ///   <summary> 右孩子節點 </summary>
         private  TreeNode _rchild;

         ///   <value> 設置/返回右孩子節點 </value>
         ///   <remarks> 設置/返回
         ///   <see cref="_rchild"/> 字段
         ///   </remarks>
         public  TreeNode RightChild
        {
             get  {  return  _rchild; }
             set  { _rchild  =  (TreeNode)value; }
        }

         ///   <value> 設置/返回左孩子節點 </value>
         ///   <remarks> 設置返回
         ///   <see cref="_lchild"/> 字段
         ///   </remarks>
         public  TreeNode LeftChild
        {
             get  {  return  _lchild; }
             set  { _lchild  =  (TreeNode)value; }
        }

         ///   <value> 返回當前節點值 </value>
         ///   <remarks> 返回
         ///   <see cref="_nval"/> 字段
         ///   </remarks>
         public   object  Value {  get  {  return  _nval; } }

         ///   <summary> 構造一個二叉樹節點 </summary>
         ///   <param name="val"> 節點對象 </param>
         public  TreeNode( object  val)
        {
            _nval  =  val;
            _occurs  =   1 ;
            _rchild  =  _lchild  =   null ;
        }

         ///   <summary> 在二叉樹中查找指定對象 </summary>
         ///   <param name="val"> 待查對象 </param>
         ///   <remarks> 用尾遞歸方式進行查找 </remarks>
         ///   <returns>
         ///      <list>
         ///          <item> null: 說明未找到待查對象 </item>
         ///          <item> this: 待查對象 </item>
         ///          <item> _lchild.FindValue(val): 左子樹遞歸查找 </item>
         ///          <item> _rchild.FindValue(val): 右子樹遞歸查找 </item>
         ///      </list>
         ///   </returns>
         public  TreeNode FindValue( object  val)
        {
            IComparable ic  =  val  as  IComparable;

             if  ( 0   ==  ic.CompareTo(_nval))
            { //  找到！
                 return   this ;
            }

             if  (ic.CompareTo(_nval)  <   0 )
            { //  到左子樹中查找
                 if  ( null   ==  _lchild)
                {
                     return   null ;
                }
                 return  _lchild.FindValue(val);
            }
             else //  到右子樹中查找
            {
                 if  ( null   ==  _rchild)
                {
                     return   null ;
                }
                 return  _rchild.FindValue(val);
            }
        }

         ///   <summary> 插入對象到二叉樹中 </summary>
         ///   <remarks> 用尾遞歸方式進行插入 </remarks>
         ///   <param name="val"> 要插入的對象 </param>
         public   void  InsertValue( object  val)
        {
            IComparable ic  =  val  as  IComparable;

             if  ( 0   ==  ic.CompareTo(_nval))
            {
                _occurs ++ ;
                 return ;
            }

             if  (ic.CompareTo(_nval)  <   0 )
            { //  插入到左子樹
                 if  ( null   ==  _lchild)
                {
                    _lchild  =   new  TreeNode(val);
                }
                 else
                {
                    _lchild.InsertValue(val);
                }
            }
             else
            { //  插入到右子樹
                 if  ( null   ==  _rchild)
                {
                    _rchild  =   new  TreeNode(val);
                }
                 else
                {
                    _rchild.InsertValue(val);
                }
            }
        }

         ///   <summary> 設置左子樹葉子節點為指定對象值 </summary>
         ///   <remarks> 這個方法主要用于刪除節點的操作 </remarks>
         ///   <param name="leaf"> 要設置的節點值 </param>
         ///   <param name="subtree"> 左子樹根節點 </param>
         public   static   void  LchildLeaf(TreeNode leaf, TreeNode subtree)
        {
             while  (subtree._lchild  !=   null )
            {
                subtree  =  subtree._lchild;
            }
            subtree._lchild  =  leaf;
        }

         ///   <summary> 刪除指定對象 </summary>
         ///   <remarks> 用尾部遞歸方式刪除 </remarks>
         ///   <param name="val"> 要刪除的對象 </param>
         ///   <param name="prev"> 要刪除節點的前一個節點 </param>
         ///   <returns>
         ///      <list>
         ///          <item> false: 說明未找到待刪除對象 </item>
         ///          <item> _lchild.RemoveValue(val, ref _lchild): 左子樹遞歸刪除 </item>
         ///          <item> _rchild.RemoveValue(val, ref _rchild): 右子樹遞歸刪除 </item>
         ///      </list>
         ///   </returns>
         public   bool  RemoveValue( object  val,  ref  TreeNode prev)
        {
            IComparable ic  =  val  as  IComparable;
             if  ( 0   ==  ic.CompareTo(_nval))
            {
                 if  (_rchild  !=   null )
                {
                    prev  =  _rchild;
                     if  (_lchild  !=   null )
                    {
                         if  ( null   ==  prev._lchild)
                        {
                            prev._lchild  =  _lchild;
                        }
                         else
                        {
                            LchildLeaf(_lchild, prev._lchild);
                        }
                    }
                }
                 else
                {
                    prev  =  _lchild;
                }
            }

             if  (ic.CompareTo(_nval)  <   0 )
            {
                 if  ( null   ==  _lchild)
                {
                     return   false ;
                }
                 return  _lchild.RemoveValue(val,  ref  _lchild);
            }
             else
            {
                 if  ( null   ==  _rchild)
                {
                     return   false ;
                }
                 return  _rchild.RemoveValue(val,  ref  _rchild);
            }
        }
    }
}
using  System;

namespace  SEI.DL88250.SourceCodes.BinaryTree
{
     ///   <summary> 二叉樹類 </summary>
     class  BinaryTree
    {
         ///   <summary> 節點類型 </summary>
         private  Type _elemType;
         ///   <summary> 根節點 </summary>
         private  TreeNode _root;

         // private Action _nodeAction;
         // public delegate void Action(ref TreeNode node);

         ///   <summary> 插入一個節點到二叉樹中 </summary>
         ///   <param name="elem"> 待插入的節點 </param>
         public   void  Insert( object  elem)
        {
             //  判斷是否是根節點
             if  ( null   ==  _root)
            {
                ConfirmComparable(elem);
                _elemType  =  elem.GetType();
                _root  =   new  TreeNode(elem);
            }
             else //  是葉子節點
            {
                ConfirmType(elem);
                _root.InsertValue(elem);
            }
        }

         ///   <summary> 刪除根節點 </summary>
         ///   <returns>
         ///      <list>
         ///          <item> false: 說明當前樹為空 </item>
         ///          <item> ture: 刪除根節點成功 </item>
         ///      </list>
         ///   </returns>
         private   bool  RemoveRoot()
        {
             if  ( null   ==  _root)
            {
                 return   false ;
            }

            TreeNode tmp  =  _root;
             if  (_root.RightChild  !=   null )
            {
                _root  =  _root.RightChild;
                TreeNode lc  =  tmp.LeftChild;
                TreeNode newlc  =  _root.LeftChild;

                 if  (lc  !=   null )
                {
                     if  ( null   ==  newlc)
                    {
                        _root.LeftChild  =  lc;
                    }
                     else
                    {
                        TreeNode.LchildLeaf(lc, newlc);
                    }
                }
            }
             else
            {
                _root  =  _root.LeftChild;
            }
             return   true ;
        }

         ///   <summary> 刪除指定對象的節點 </summary>
         ///   <param name="elem"> 給定對象 </param>
         ///   <returns>
         ///      <list>
         ///          <item> false: 說明當前樹為空 </item>
         ///          <item> _root.RemoveValue(elem, ref _root): 尾部遞歸刪除節點 </item>
         ///      </list>
         ///   </returns>
         public   bool  Remove( object  elem)
        {
             if  (_root  ==   null )
            {
                 return   false ;
            }
            IComparable ic  =  ConfirmComparable(elem);
            ConfirmType(elem);

             if  ( 0   ==  ic.CompareTo(_root.Value))
            {
                 return  RemoveRoot();
            }
             return  _root.RemoveValue(elem,  ref  _root);
        }

         ///   <summary> 查找與給定對象相同的節點 </summary>
         ///   <param name="elem"> 給定對象 </param>
         ///   <returns>
         ///      <list>
         ///          <item> null: 說明沒有找到 </item>
         ///          <item> _root.FindValue(elem): 尾部遞歸查找方法 </item>
         ///      </list>
         ///   </returns>
         public  TreeNode Find( object  elem)
        {
             if  ( null   ==  _root)
            {
                 return   null ;
            }
            ConfirmType(elem);
             return  _root.FindValue(elem);
        }

         ///   <summary> 查看給定對象類型是否與二叉樹節點類型相同 </summary>
         ///   <remarks> 類型不符合的話將拋出異常 </remarks>
         ///   <param name="elem"> 給定對比的對象 </param>
         private   void  ConfirmType( object  elem)
        {
             if  (_elemType  !=  elem.GetType())
            {
                 string  msg  =   " Element's type not match with the root's:  "
                     +  _elemType.ToString();
                 throw   new  ArgumentException(msg);
            }
        }

         ///   <summary> 查看給定對象類型是否可以進行比較運算 </summary>
         ///   <remarks> 如果類型不可進行比較運算的話將拋出異常 </remarks>
         ///   <param name="elem"> 給定對象 </param>
         ///   <returns>
         ///   <para> IComparable: IComparable接口 </para>
         ///   </returns>
         private  IComparable ConfirmComparable( object  elem)
        {
            IComparable ic  =  elem  as  IComparable;
             if  ( null   ==  ic)
            {
                 string  msg  =   " Element type must support IComparable --  "
                        +  elem.GetType().Name
                        +   "  does not currently do so! " ;
                 throw   new  ArgumentException(msg);
            }
             return  ic;
        }
    }
}

using  System;

namespace  SEI.DL88250.SourceCodes.BinaryTree
{
     ///   <summary> 用于測試二叉樹類 </summary>
     class  TestBinTree
    {
         public   static   void  Main( string [] arga)
        {
            BinaryTree bt  =   new  BinaryTree();

            bt.Insert( " d " );
            bt.Insert( " ab " );
            bt.Insert( " a " );
            bt.Insert( " e " );
            TreeNode tn  =  bt.Find( " ab " );
            Console.Write(tn.Value);
            bt.Remove( " ab " );
            TreeNode tnn  =  bt.Find( " ab " );
            Console.Write(tnn.Value);
        }
    }
}

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/dz45693/archive/2009/12/22/5057753.aspx

上一篇：C#全角和半角轉換

下一篇：ASP.NET MVC 框架