确切的说，该二叉树更类似于二叉排序树，在判断了节点是否可以进行比较操作后，根据给定的比较操作进行节点的插入。 using System; using System.Collections; namespace SEI.DL88250.SourceCodes.BinaryTree { /// 二叉树节点类 class TreeNode { /// 当前节点的出现计数 private int _occurs; /// 当前节点值 private object _nval; /// 左孩子节点 private TreeNode _lchild; /// 右孩子节点 private TreeNode _rchild; /// 设置/返回右孩子节点 /// 设置/返回 /// 字段 /// public TreeNode RightChild { get { return _rchild; } set { _rchild = (TreeNode)value; } } /// 设置/返回左孩子节点 /// 设置返回 /// 字段 /// public TreeNode LeftChild { get { return _lchild; } set { _lchild = (TreeNode)value; } } /// 返回当前节点值 /// 返回 /// 字段 /// public object Value { get { return _nval; } } /// 构造一个二叉树节点 /// 节点对象 public TreeNode( object val) { _nval = val; _occurs = 1 ; _rchild = _lchild = null ; } /// 在二叉树中查找指定对象 /// 待查对象 /// 用尾递归方式进行查找 /// ///
/// - null: 说明未找到待查对象
/// - this: 待查对象
/// - _lchild.FindValue(val): 左子树递归查找
/// - _rchild.FindValue(val): 右子树递归查找
/// /// 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); } } /// 插入对象到二叉树中 /// 用尾递归方式进行插入 /// 要插入的对象 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); } } } /// 设置左子树叶子节点为指定对象值 /// 这个方法主要用于删除节点的操作 /// 要设置的节点值 /// 左子树根节点 public static void LchildLeaf(TreeNode leaf, TreeNode subtree) { while (subtree._lchild != null ) { subtree = subtree._lchild; } subtree._lchild = leaf; } /// 删除指定对象 /// 用尾部递归方式删除 /// 要删除的对象 /// 要删除节点的前一个节点 /// ///
/// - false: 说明未找到待删除对象
/// - _lchild.RemoveValue(val, ref _lchild): 左子树递归删除
/// - _rchild.RemoveValue(val, ref _rchild): 右子树递归删除
/// /// 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 { /// 二叉树类 class BinaryTree { /// 节点类型 private Type _elemType; /// 根节点 private TreeNode _root; // private Action _nodeAction; // public delegate void Action(ref TreeNode node); /// 插入一个节点到二叉树中 /// 待插入的节点 public void Insert( object elem) { // 判断是否是根节点 if ( null == _root) { ConfirmComparable(elem); _elemType = elem.GetType(); _root = new TreeNode(elem); } else // 是叶子节点 { ConfirmType(elem); _root.InsertValue(elem); } } /// 删除根节点 /// ///
/// - false: 说明当前树为空
/// - ture: 删除根节点成功
/// /// 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 ; } /// 删除指定对象的节点 /// 给定对象 /// ///
/// - false: 说明当前树为空
/// - _root.RemoveValue(elem, ref _root): 尾部递归删除节点
/// /// 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); } /// 查找与给定对象相同的节点 /// 给定对象 /// ///
/// - null: 说明没有找到
/// - _root.FindValue(elem): 尾部递归查找方法
/// /// public TreeNode Find( object elem) { if ( null == _root) { return null ; } ConfirmType(elem); return _root.FindValue(elem); } /// 查看给定对象类型是否与二叉树节点类型相同 /// 类型不符合的话将抛出异常 /// 给定对比的对象 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); } } /// 查看给定对象类型是否可以进行比较运算 /// 如果类型不可进行比较运算的话将抛出异常 /// 给定对象 /// /// IComparable: IComparable接口 /// 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 { /// 用于测试二叉树类 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
|
