tree2.cs

树的简单使用方法和基本操作,这是一个CS程序.

		public bool IsTop
		{
			get
			{
				//if ( IsRoot ) throw new InvalidOperationException( "This is a Root" );
				if ( IsRoot ) return false;
				return Parent.Parent == null;
			}
		}

		//-----------------------------------------------------------------------------

		public virtual INode<T> this[ T item ]
		{
			get
			{
				if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

				IEqualityComparer<T> comparer = DataComparer;

				foreach ( INode<T> n in All.Nodes )
					if ( comparer.Equals( n.Data, item ) )
						return n;

				return null;
			}
		}

		public virtual bool Contains( INode<T> item )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			return All.Nodes.Contains( item );
		}

		public virtual bool Contains( T item )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			return All.Values.Contains( item );
		}

		//-----------------------------------------------------------------------------

		public INode<T> InsertPrevious( T o )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertPreviousCore( newNode );

			return newNode;
		}

		public INode<T> InsertNext( T o )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertNextCore( newNode );

			return newNode;
		}

		public INode<T> InsertChild( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newNode = CreateNode();
			newNode._Data = o;

			this.InsertChildCore( newNode );

			return newNode;
		}

		public INode<T> Add( T o )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			return this.Last.InsertNext( o );
		}

		public INode<T> AddChild( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			if ( Child == null )
				return InsertChild( o );
			else
				return Child.Add( o );
		}

		//-----------------------------------------------------------------------------

		public void InsertPrevious( ITree<T> tree )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newTree = GetNodeTree( tree );

			if ( !newTree.IsRoot ) throw new ArgumentException( "Tree is not a Root" );
			if ( !newTree.IsTree ) throw new ArgumentException( "Tree is not a tree" );

			for ( INode<T> n = newTree.Child ; n != null ; n = n.Next )
			{
				NodeTree<T> node = GetNodeTree( n );
				NodeTree<T> copy = node.CopyCore();
				InsertPreviousCore( copy );
			}
		}

		public void InsertNext( ITree<T> tree )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newTree = GetNodeTree( tree );

			if ( !newTree.IsRoot ) throw new ArgumentException( "Tree is not a Root" );
			if ( !newTree.IsTree ) throw new ArgumentException( "Tree is not a tree" );

			for ( INode<T> n = newTree.LastChild ; n != null ; n = n.Previous )
			{
				NodeTree<T> node = GetNodeTree( n );
				NodeTree<T> copy = node.CopyCore();
				InsertNextCore( copy );
			}
		}

		public void InsertChild( ITree<T> tree )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> newTree = GetNodeTree( tree );

			if ( !newTree.IsRoot ) throw new ArgumentException( "Tree is not a Root" );
			if ( !newTree.IsTree ) throw new ArgumentException( "Tree is not a tree" );

			for ( INode<T> n = newTree.LastChild ; n != null ; n = n.Previous )
			{
				NodeTree<T> node = GetNodeTree( n );
				NodeTree<T> copy = node.CopyCore();
				InsertChildCore( copy );
			}
		}

		public void Add( ITree<T> tree )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			this.Last.InsertNext( tree );
		}

		public void AddChild( ITree<T> tree )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			if ( this.Child == null )
				this.InsertChild( tree );
			else
				this.Child.Add( tree );
		}

		//-----------------------------------------------------------------------------

		protected virtual void InsertPreviousCore( INode<T> newINode )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !newINode.IsRoot ) throw new ArgumentException( "Node is not a Root" );
			if ( newINode.IsTree ) throw new ArgumentException( "Node is a tree" );

			IncrementVersion();

			OnInserting( this, NodeTreeInsertOperation.Previous, newINode );

			NodeTree<T> newNode = GetNodeTree( newINode );

			newNode._Parent = this._Parent;
			newNode._Previous = this._Previous;
			newNode._Next = this;
			this._Previous = newNode;

			if ( newNode.Previous != null )
			{
				NodeTree<T> Previous = GetNodeTree( newNode.Previous );
				Previous._Next = newNode;
			}
			else // this is a first node
			{
				NodeTree<T> Parent = GetNodeTree( newNode.Parent );
				Parent._Child = newNode;
			}

			OnInserted( this, NodeTreeInsertOperation.Previous, newINode );
		}

		protected virtual void InsertNextCore( INode<T> newINode )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !newINode.IsRoot ) throw new ArgumentException( "Node is not a Root" );
			if ( newINode.IsTree ) throw new ArgumentException( "Node is a tree" );

			IncrementVersion();

			OnInserting( this, NodeTreeInsertOperation.Next, newINode );

			NodeTree<T> newNode = GetNodeTree( newINode );

			newNode._Parent = this._Parent;
			newNode._Previous = this;
			newNode._Next = this._Next;
			this._Next = newNode;

			if ( newNode.Next != null )
			{
				NodeTree<T> Next = GetNodeTree( newNode.Next );
				Next._Previous = newNode;
			}

			OnInserted( this, NodeTreeInsertOperation.Next, newINode );
		}

		protected virtual void InsertChildCore( INode<T> newINode )
		{
			if ( !newINode.IsRoot ) throw new ArgumentException( "Node is not a Root" );
			if ( newINode.IsTree ) throw new ArgumentException( "Node is a tree" );

			IncrementVersion();

			OnInserting( this, NodeTreeInsertOperation.Child, newINode );

			NodeTree<T> newNode = GetNodeTree( newINode );

			newNode._Parent = this;
			newNode._Next = this._Child;
			this._Child = newNode;

			if ( newNode.Next != null )
			{
				NodeTree<T> Next = GetNodeTree( newNode.Next );
				Next._Previous = newNode;
			}

			OnInserted( this, NodeTreeInsertOperation.Child, newINode );
		}

		protected virtual void AddCore( INode<T> newINode )
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );

			NodeTree<T> lastNode = GetNodeTree( Last );

			lastNode.InsertNextCore( newINode );
		}

		protected virtual void AddChildCore( INode<T> newINode )
		{
			if ( this.Child == null )
				this.InsertChildCore( newINode );
			else
			{
				NodeTree<T> childNode = GetNodeTree( Child );

				childNode.AddCore( newINode );
			}
		}

		//-----------------------------------------------------------------------------

		public ITree<T> Cut( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			INode<T> n = this[ o ];
			if ( n == null ) return null;
			return n.Cut();
		}

		public ITree<T> Copy( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			INode<T> n = this[ o ];
			if ( n == null ) return null;
			return n.Copy();
		}

		public ITree<T> DeepCopy( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			INode<T> n = this[ o ];
			if ( n == null ) return null;
			return n.DeepCopy();
		}

		public bool Remove( T o )
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			INode<T> n = this[ o ];
			if ( n == null ) return false;

			n.Remove();
			return true;
		}

		//-----------------------------------------------------------------------------

		private NodeTree<T> BoxInTree( NodeTree<T> node )
		{
			if ( !node.IsRoot ) throw new ArgumentException( "Node is not a Root" );
			if ( node.IsTree ) throw new ArgumentException( "Node is a tree" );

			NodeTree<T> tree = CreateTree();

			tree.AddChildCore( node );

			return tree;
		}

		public ITree<T> Cut()
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			NodeTree<T> node = CutCore();

			return BoxInTree( node );
		}

		public ITree<T> Copy()
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			if ( IsTree )
			{
				NodeTree<T> NewTree = CopyCore();

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CopyCore();

				return BoxInTree( NewNode );
			}
		}

		public ITree<T> DeepCopy()
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			if ( IsTree )
			{
				NodeTree<T> NewTree = DeepCopyCore();

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = DeepCopyCore();

				return BoxInTree( NewNode );
			}
		}

		public void Remove()
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );

			RemoveCore();
		}

		//-----------------------------------------------------------------------------

		protected virtual NodeTree<T> CutCore()
		{
			if ( this.IsRoot ) throw new InvalidOperationException( "This is a Root" );

			IncrementVersion();

			OnCutting( this );

			INode<T> OldRoot = Root;

			if ( this._Next != null )
				this._Next._Previous = this._Previous;

			if ( this.Previous != null )
				this._Previous._Next = this._Next;
			else // this is a first node
			{
				Debug.Assert( Parent.Child == this );
				this._Parent._Child = this._Next;
				Debug.Assert( this.Next == null || this.Next.Previous == null );
			}

			this._Parent = null;
			this._Previous = null;
			this._Next = null;

			OnCutDone( OldRoot, this );

			return this;
		}

		protected virtual NodeTree<T> CopyCore()
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );
			if ( IsRoot && !IsTree ) throw new InvalidOperationException( "This is a Root" );

			if ( IsTree )
			{
				NodeTree<T> NewTree = CreateTree();

				OnCopying( this, NewTree );

				CopyChildNodes( this, NewTree, false );

				OnCopied( this, NewTree );

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CreateNode();

				NewNode._Data = Data;

				OnCopying( this, NewNode );

				CopyChildNodes( this, NewNode, false );

				OnCopied( this, NewNode );

				return NewNode;
			}
		}

		protected virtual NodeTree<T> DeepCopyCore()
		{
			if ( !Root.IsTree ) throw new InvalidOperationException( "This is not a tree" );
			if ( IsRoot && !IsTree ) throw new InvalidOperationException( "This is a Root" );

			if ( IsTree )
			{
				NodeTree<T> NewTree = CreateTree();

				OnCopying( this, NewTree );

				CopyChildNodes( this, NewTree, true );

				OnCopied( this, NewTree );

				return NewTree;
			}
			else
			{
				NodeTree<T> NewNode = CreateNode();

				NewNode._Data = DeepCopyData( Data );

				OnDeepCopying( this, NewNode );

				CopyChildNodes( this, NewNode, true );

				OnDeepCopied( this, NewNode );

				return NewNode;
			}
		}

		private void CopyChildNodes( INode<T> oldNode, NodeTree<T> newNode, bool bDeepCopy )
		{
			NodeTree<T> previousNewChildNode = null;

			for ( INode<T> oldChildNode = oldNode.Child ; oldChildNode != null ; oldChildNode = oldChildNode.Next )
			{
				NodeTree<T> newChildNode = CreateNode();