tree.cs

使用C#写的数据结构库(从链表到图)

using System;


namespace DataTypeDemo
{
	/// <summary>
	/// tree 的摘要说明。
	/// </summary>
	public class tree : dataType
	{
		private treeNode tcurrent;
		private object sData;
		public treeNode TCurrent
		{
			get{return tcurrent;}
		}
		public int Length
		{
			get{return base.length;}
		}
		public treeNode Root
		{
			get{return base.root;}
		}
		public tree()
		{
			//
			// TODO: 在此处添加构造函数逻辑
			//
			base.root = null;
			this.tcurrent = null;
			this.sData = null;
			base.length = 0;
		}

		/**
		*CreateTree
		* 
		* <PARAM> 
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/21 by LiJun
		*/
		public void CreateTree()
		{
			base.root = new treeNode();
		}

		/**
		*CreateTree
		* 
		* <PARAM> object[] data
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void CreateTree(object[] data)
		{
			this.length = data.Length;
			object[] nData = this.getData(data); //whit 1 for down-tag's arrays
			int deep = (int)Math.Log((nData.Length-1),2);//get tree deep

			treeNode tempNode = null;		//tempNode will when create tree 
			bool lor = true;				//check that is not right
			treeNode[] parNode = new treeNode[nData.Length]; //save all parent Node
			//if only one node,then create tree with only rootNode
			if(data.Length == 1)
			{
				base.root = new treeNode(data[0],null,null,null);
			}
			else
			{
				for(int i=1,j=1;i<nData.Length;i++)
				{
					if(i>1)
					{
						tempNode = new treeNode(nData[i],null,null,parNode[j]);
						if(lor == true) //set left node
						{
							parNode[j].Left = tempNode;
							lor = false;
						}
						else	//set right node
						{
							parNode[j].Right = tempNode;
							lor = true;
							j ++;	//while leftNode and rightNode all the create,
									// do save the next parent node, 
									//because leftNode and rightNode -> same parent 
						}
						parNode[i] = tempNode;
					}
					else
					{
						tempNode = new treeNode(nData[i],null,null,null);
						base.root = tempNode;	//set root
						parNode[i] = base.root; //save the parent node
					}
				}
			}
		}

		/**
		*getData
		* 
		* <PARAM> object[] d
		* <RETURN> object[]
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected object[] getData(object[] d)
		{
			object[] newd = new object[d.Length+1];
			for(int i=1; i<newd.Length;i++)
			{
				newd[i] = d[i-1];
			}
			return newd;
		}

		/**
		*searchNode
		* 
		* <PARAM> treeNode n
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected void searchNode(treeNode n)
		{	
			if(n != null)
			{
				searchNode(n.Left);
				if(n.Data == this.sData)
				{
					this.tcurrent = n;
				}
				searchNode(n.Right);
			}
		}

		/**
		*getNode
		* checked The stuct was empty
		* <PARAM> object d
		* <RETURN> treeNode
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected treeNode getNode(object d)
		{
			this.sData = d;
			if(base.root.Data == this.sData)
			{
				this.tcurrent = base.root;
			}
			else
			{
				this.searchNode(base.root);
			}
			return this.tcurrent;
		}

		/**
		*insertNode
		* 
		* <PARAM> object pardata,object insdata,bool b
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected void insertNode(treeNode parNode,object insdata,bool b)
		{
			treeNode temp = parNode;
			treeNode newnode = new treeNode(insdata,null,null,null);
			if(b == true)
			{
				if(temp.Left != null)
				{
					newnode.Left = temp.Left;
					newnode.Left.Parent = newnode;
				}
				temp.Left = newnode;
					
			}
			else
			{
				if(temp.Right != null)
				{
					newnode.Right = temp.Right;
					newnode.Right.Parent = newnode;
				}
				temp.Right = newnode;
			}
			newnode.Parent = temp;
			base.length ++;
		}

		/**
		*insertNode
		* 
		* <PARAM> object pardata,object insdata,bool b
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected void insertNode(object pardata,object insdata,bool b)
		{
			treeNode temp = this.getNode(pardata);
			if(temp != null)
			{
				this.insertNode(temp,insdata,b);
			}
		}

		/**
		*deleteNode
		* 
		* <PARAM> treeNode d, bool b
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected void deleteNode(treeNode parNode,bool b)
		{
			treeNode temp = parNode;
			if(base.root != null && temp != base.root)
			{
				if(b == true)
				{
					if(temp.Left != null)
					{
						treeNode nll = temp.Left;
						if(nll.Left != null)
						{
							temp.Left = nll.Left;
							nll.Left.Parent = temp.Left;
						}
						else if(nll.Right != null)
						{
							temp.Right = nll.Right;
							nll.Right.Parent = temp.Right;
						}
					}
				}
				else
				{
					if(temp.Right != null)
					{
						treeNode nrr = temp.Right;
						if(nrr.Right != null)
						{
							temp.Right = nrr.Right;
							nrr.Right.Parent = temp.Right;
						}
						else if(nrr.Left != null)
						{
							temp.Right = nrr.Left;
							nrr.Left.Parent = temp.Right;
						}
					}
				}
			}
			base.length --;
		}

		/**
		*deleteNode
		* 
		* <PARAM> object d, bool b
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		protected void deleteNode(object d, bool b)
		{
			treeNode temp = this.getNode(d);
			if(temp != null)
			this.deleteNode(temp,b);
		}

		/**
		*InsertLeft
		* 
		* <PARAM> object pardata,object insdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void InsertLeft(object pardata,object insdata)
		{
			this.insertNode(pardata,insdata,true);
		}

		/**
		*InsertLeft
		* 
		* <PARAM> treeNode pardata,object insdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void InsertLeft(treeNode parNode,object insdata)
		{
			this.insertNode(parNode,insdata,true);
		}

		/**
		*InsertRight
		* 
		* <PARAM> object pardata,object insdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void InsertRight(object pardata,object insdata)
		{
			this.insertNode(pardata,insdata,false);
		}

		/**
		*InsertRight
		* 
		* <PARAM> object pardata,object insdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void InsertRight(treeNode parNode,object insdata)
		{
			this.insertNode(parNode,insdata,false);
		}
		
		/**
		*GetCurrentData
		* 
		* <PARAM> object data
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public treeNode GetCurrentNode(object data)
		{
			return this.getNode(data);
		}

		/**
		*GetLeft
		* 
		* <PARAM> object pdata
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetLeft(object pdata)
		{
			treeNode temp = this.getNode(pdata);
			return temp.Left.Data;
		}

		/**
		*GetLeft
		* 
		* <PARAM> treeNode pNode
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetLeft(treeNode pNode)
		{
			//treeNode temp = this.getNode(pdata);
			return pNode.Left.Data;
		}

		/**
		*	GetRight
		* 
		* <PARAM> object pdata
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetRight(object pdata)
		{
			treeNode temp = this.getNode(pdata);
			return temp.Right.Data;
		}

		
		/**
		*	GetRight
		* 
		* <PARAM> treeNode pdata
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetRight(treeNode pNode)
		{
			//treeNode temp = this.getNode(pdata);
			return pNode.Right.Data;
		}

		/**
		*	GetParent
		* 
		* <PARAM> object pdata
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetParent(object pdata)
		{
			treeNode temp = this.getNode(pdata);
			if(temp != this.root)
			{
				return temp.Parent.Data;
			}
			return this.root;
		}

		/**
		*	GetParent
		* 
		* <PARAM> object pdata
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public object GetParent(treeNode pNode)
		{
			//treeNode temp = this.getNode(pdata);
			if(pNode != this.root)
			{
				return pNode.Parent.Data;
			}
			return this.root;
		}

		/**
		*DeleteLeft
		* 
		* <PARAM> object pdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void DeleteLeft(object pdata)
		{
			this.deleteNode(pdata,true);
		}

		/**
		*DeleteLeft
		* 
		* <PARAM> treeNode pdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/23 by LiJun
		*/
		public void DeleteLeft(treeNode pNode)
		{
			this.deleteNode(pNode,true);
		}

		/**
		*DeleteRight
		* 
		* <PARAM> object pdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/22 by LiJun
		*/
		public void DeleteRight(object pdata)
		{
			this.deleteNode(pdata, false);
		}

		/**
		*DeleteRight
		* 
		* <PARAM> treeNode pdata
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/22 by LiJun
		*/
		public void DeleteRight(treeNode pNode)
		{
			this.deleteNode(pNode, false);
		}


		/**
		*GetFindData
		* 
		* <PARAM> int index
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/22 by LiJun
		*/
		public override object GetFindData(int index)
		{
			return null;
		}

		/**
		*SetEmpty
		* 
		* <PARAM> 
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/21 by LiJun
		*/
		public override void SetEmpty()
		{
			this.tcurrent = null;
			base.root = null;
			this.CreateTree();
			
			base.length = 0;
		}
	}
}