开发学院WEB开发ASP C#实现的BinaryTree 阅读

C#实现的BinaryTree

 2009-12-23 10:43:50 来源:WEB开发网   
核心提示:确切的说,该二叉树更类似于二叉排序树,C#实现的BinaryTree,在判断了节点是否可以进行比较操作后,根据给定的比较操作进行节点的插入
确切的说,该二叉树更类似于二叉排序树,在判断了节点是否可以进行比较操作后,根据给定的比较操作进行节点的插入。

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

Tags:实现 BinaryTree

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接