bitree.cs

开始学C＃的一点知识希望可以借鉴！文件在修改中！

using System;

namespace Bitree
{
	/// <summary>
	/// Bitree 的摘要说明。
	/// </summary>
	public class biTree
	{
		biTree l;
		biTree r;
		int d;
		public biTree( int d, biTree l, biTree r )
		{
			this.d = d;
			this.l = l;
			this.r = r;
		}

		public biTree( int d )
		{
			this.l = this.r = null;
			this.d = d;
		}

		//向树中添加结点
		public static void BTInsert( ref biTree r, int e )		
		{
			if( r == null ) r = new biTree( e );
			else if( e <= r.d ) BTInsert( ref r.l, e );
			else BTInsert( ref r.r, e );
		}


		//查询指定值，并返回指定值的根结点
//		public static biTree BTSelect( ref biTree r, int e )		
//		{
//			if( r != null )
//			{
//				if( r.d == e )
//					return r;
//				else
//				{
//					BTSelect( ref r.l, e );
//					BTSelect( ref r.l, e );
//				}
//			}
//			else
//				return null;
//		}


		//查询根结点的是否有左子树
		public static biTree BTSelect_l( ref biTree r )		
		{
			if( r.l != null )
				return r.l;
			else
				return null;
		}


		//查询根结点的是否有右子树
		public static biTree BTSelect_r( ref biTree r )		
		{
			if( r.r != null )
				return r.r;
			else
				return null;
		}


		//删除树中指定值
//		public static void BTDelete( ref biTree r, int e )		
//		{
//			biTree tr = null;		//标记
//			if( biTree.BTSelect( ref r, e ) != null )		//所删除的值在树中存在
//			{
//				tr = biTree.BTSelect( ref r, e );		//要删除的值的根结点赋给标记
//			}
//			if( tr == r )		//删除根结点
//			{
//				if( biTree.BTSelect_l( ref r ) == null && biTree.BTSelect_r( ref r ) == null )		//根结点左右子树都为空
//					r = null;
//				else if( biTree.BTSelect_l( ref r ) != null && biTree.BTSelect_r( ref r ) == null )		//根结点左子树不空，右子树空
//					r = r.l;
//				else if( biTree.BTSelect_l( ref r ) == null && biTree.BTSelect_r( ref r ) != null )		//根结点右子树不空，左子树空
//					r = r.r;
//				else		//根结点左、右子树都不空
//				{
//					if( biTree.BTSelect_l( ref r.r ) != null )
//						r.r.l.l = r.l;
//				}
//
//			}
//		}
		public static void BTDelete(ref biTree T,int e)
		{
			biTree p;
			if(T==null) return;
			else if(e==T.d)
			{
				if (T.l==null) T=T.r;
				else  
				{
						p=T.l;while(p.r!=null) p=p.r;
					p.r=T.r;T=T.l;;
				}
			}
			else if(e<T.d) BTDelete(ref T.l,e);
			else BTDelete(ref T.r,e);										  

		}


		//中序遍历
		public static string LNR( biTree r )		
		{
			if( r == null ) return "";

			string sl = LNR( r.l );
			string sr = LNR( r.r );
			return sl + " " + r.d + " " + sr;
//			return LNR( r.l ) + " " + r.d + " " + LNR( r.r );


//			if ( r == null) return "";
//			if( r.l != null )
//			{
//				return r.d.ToString();
//				LNR( biTree r.l );
//			}
//			else if( r.r != null ) return r;
        }


		//先序遍历
		public static string NLR( biTree r )
		{
			if( r == null ) return "";
			else return r.d + " " + NLR( r.l ) + " " + NLR( r.r );
		}


		//计算树叶个数
		public static int LeafageCount( biTree r )		
		{
			if( r != null )
			{
				if( r.l == null && r.r == null )
					return 1;
				else
					return ( LeafageCount( r.l ) + LeafageCount( r.r ) );
			}
			else
				return 0;
		}
	}
}