C#实现的BinaryTree

核心提示：确切的说，该二叉树更类似于二叉排序树，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