确切的说，该二叉树更类似于二叉排序树，在判断了节点是否可以进行比较操作后，根据给定的比较操作进行节点的插入。
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);
}
}
}