C#编程

开发平台：
Others

ercha2.cs：源码内容
							using System;
	public class TreeNode
	{
		public int data;//节点数据
		public TreeNode LeftNode;//左子女
		public TreeNode RightNode;//右子女
		/// 
		/// 构造函数，初始化左右子女为空
		/// 
		public TreeNode()
		{
			LeftNode = RightNode = null;
		}
	}
	public class Node
	{
		private TreeNode root;//根节点
		bool temp = false;//默认查找不存在
		/// 
		/// 构造函数
		/// 
		public Node()
		{
			root = null;
		}
		// 获得该节点最小左子女，用于删除元素使用
		// 
		// 
		// 
		TreeNode Min(TreeNode parent)
		{
			TreeNode temp = parent;
			while(temp != null)
			{
				if(temp.LeftNode == null)
					return temp;
				else
					temp = temp.LeftNode;
			}
			return null;
		}
		/// 
		/// 删除元素
		/// 
		/// 
		public void Remove(int data)
		{
			if (root == null)
				return;
			if(root.data == data)
			{
				TreeNode tmp = Min(root.RightNode);
				if(tmp == null)
				{
					root = root.LeftNode;
				}
				else
				{
					root.data = tmp.data;
					Remove(root,root.RightNode,1,tmp.data);
				}
			}
			else if(root.data!=data) 
			{
				Remove(root,root.RightNode,1,data);
			}
			else
				Remove(root,root.LeftNode,0,data);
		}
		//在二叉排序树中删除值为data的结点
		public TreeNode Remove2(int data)
		{
			TreeNode p,f,s,q;
			p=root;f=null;
			//如果p不空就一直找下去
			while(p!=null)
			{
				//找到了 就跳出循环
				if(p.data==data) 
					break;
				f=p;
				if(p.data>data) 
					p=p.LeftNode;
				else
					p=p.RightNode;
			}
			
			//找不到 返回原根节点
			if(p==null) return root;
			//如果p无左子树
			if(p.LeftNode==null)
			{
				//p是原二叉排序树的根
				if(f==null)
					root=p.RightNode;
				//如果p是f的左孩子
				else if(f.LeftNode==p)
					f.LeftNode=p.RightNode;
				else
				//如果p是f的右孩子	
					f.RightNode=p.RightNode;
				//free(p);
			}
			//p有左子树
			else
			{
				q=p;s=p.LeftNode;
				//寻找p左子树的最右下节点
				while(s.RightNode!=null)
				{q=s;s=s.RightNode;}
				if(q==p)
					//将s的左子树链到q上
					q.LeftNode=s.LeftNode;
				else
					q.RightNode=s.LeftNode;
				//将s的值赋给p
				p.data=s.data;
				//free(s);
			}
			return root;
		}
		/// 
		/// 删除元素递归
		/// 
		/// 
		/// 
		/// 
		/// 
		private void Remove(TreeNode parent,TreeNode cur,int direction,int data)
		{
			if(cur.data == data)
			{
				if(cur.LeftNode == null)
				{
					if(direction == 0)
						parent.LeftNode = cur.RightNode;
					else
						parent.RightNode = cur.RightNode;
				}
				else if(cur.RightNode == null)
				{
					if(direction == 0)
						parent.LeftNode = cur.LeftNode;
					else
						parent.RightNode = cur.LeftNode;
				}
				else
				{
					TreeNode tmp =Min(cur.LeftNode);
					cur.data = tmp.data;
					Remove(cur,cur.LeftNode,1,tmp.data);
				}
			}
			else if(cur.data > data)
			{
				Remove(cur,cur.LeftNode,0,data);
			}
			else
			{
				Remove(cur,cur.RightNode,1,data);
			}
		}
		/// 
		/// 查找是否存在该元素
		/// 
		/// 
		/// 
		public bool Search(int data)
		{
			bool temp = false;
			if(root.data == data)
			{
				temp = true;
			}
			else
			{
				temp = Search(root,data);
			}
			return temp;
		}
		/// 
		///查找是否存在该元素，递归
		/// 
		/// 
		/// 
		/// 
		public bool Search(TreeNode node,int data)
		{
			if(node.data == data)
			{
				temp = true;
				Console.WriteLine("find");
			}
			else
			{
				if(node.data > data)
				{
					if(node.LeftNode != null)
					{
						Search(node.LeftNode,data);
					}
				}
				else
				{
					if(node.RightNode != null)
					{
						Search(node.RightNode,data);
					}
				}
			}
			return temp;
		}
		public void Search2(int data)
		{
			if(root==null)
				return;
			else
			  Search(root,data);
		}
		/// 
		/// 插入元素
		/// 
		/// 
		public  void Insert(int data)
		{
			if( root == null)
			{
				root = new TreeNode();
				root.data = data;
			}
			else
			{
				Insert(root,data);
			}
		}
		/// 
		///插入元素，递归
		/// 
		/// 
		/// 
		public  void Insert(TreeNode node,int data)
		{
			if(node.data>data)
			{
				if(node.LeftNode == null)
				{
					TreeNode temp = new TreeNode();
					temp.data = data;
					node.LeftNode = temp;
				}
				else
				{
					Insert(node.LeftNode,data);
				}
			}
			else
			{
				if(node.RightNode== null)
				{
					TreeNode temp = new TreeNode();
					temp.data = data;
					node.RightNode = temp;
				}
				else
				{
					Insert(node.RightNode,data);
				}
			}
		}
		public  void PrintTree(TreeNode node,int layer)
		{
			if(node==null)
			  return;
			PrintTree(node.RightNode, layer+3);
			for(int i=0; i<layer; i++)
				Console.Write(" ");
			Console.Write("{0}",node.data);
			Console.WriteLine();
            PrintTree(node.LeftNode, layer+3);
		
		}
        
		public  void PrintTree2()
		{
			if(root==null)
				return;
			else
				PrintTree(root,9);
			
		}
	}
class myApp
{
	public static void Main()
	{
		int z=0;
		string buff;
		TreeNode first = new TreeNode();
		Node Tfirst = new Node();
		for(;;)
		{
		  Console.WriteLine("please intput a int");
		  Console.WriteLine("if input -1 then break");
		  buff= Console.ReadLine();
		  z= Convert.ToInt32(buff);
          if(z==-1)
			  break;
		  Tfirst.Insert(z);
	    }
		Tfirst.PrintTree2();
        Console.WriteLine("please intput a int which you want to search");
        buff= Console.ReadLine();
		z= Convert.ToInt32(buff);
        Tfirst.Search2(z);
		Console.WriteLine("please intput a int which you want to remove");
		buff= Console.ReadLine();
		z= Convert.ToInt32(buff);
		Tfirst.Remove2(z);
        Tfirst.PrintTree2();
		Console.ReadLine();
	   
	}
}

						