tree.java

数据结构 包括数组(Array包) 和二叉树(Tree) 链表(Linelist包) 等等

package Tree;

import java.util.Stack;

//////////////////////////////////////////////////////////////////////
public class Tree {
	public  Node root;//定义根节点
	public Node current;//定义当前节点
	
	public Tree(){
		root=null;//初始化树
		current=root;
	}
//=============================================================
	public void insertNode(int id,String name){
		Node newNode=new Node(id,name);
		if(root==null){//如果没有根节点
			root=newNode;//新节点就是根节点
		}else{
			current=root;
			Node parent;
			while(true){
				parent=current;
				if(id<current.id){//加入左子树？
					current=current.leftChild;
					if(current==null){//到达最下层？
					    parent.leftChild=newNode;	
					    return;
					}
				}//end of left
				else{
				   current=current.rightChild;
				   if(current==null){
					   parent.rightChild=newNode;
					   return;
				   }
				}//end else go right
			}//end while
			
		}//end root is null?						
	}//end insert;
	
//====================================================================
	 public void inOrder(Node localNode){
		    if(localNode!=null){
		    	inOrder(localNode.leftChild);
		    	localNode.displayNode();
		    	inOrder(localNode.rightChild);
		    }
	 }
//===================================================================	
     public Node findNode(int key){
    	 Node parent=root;
    	 current=root;
    	 while(current.id!=key){
    		 parent=current;
    		 if(current.id>key ){
    			 current=current.leftChild;
    			   
    		 }else{
    			 current=current.rightChild;
    			 
    		 }
    		if(current==null)
    			return null;
    	 }
    	 Node last=current;
    	 return last;
     }
//======================================================================
     public boolean deleteNode(int key){
    	 Node parent=root;
    	 current=root;
    	 boolean isLeftChild=true;
    	 
    	 while(current.id!=key){//寻找要删除的位置
    		 parent=current;
    		 if(current.id>key ){
    			 current=current.leftChild;
    			 isLeftChild=true;
    		 }else{
    			 current=current.rightChild;
    			  isLeftChild=false; 
    		 }
    		 
    		 if(current==null)//找不到节点 
        		 return false;
    	 }
    	
    
    	 
    	 if(current.leftChild==null && current.rightChild==null){
    		 //如果当前节点的左孩子和右孩子都是空,直接删除
    		   if(current==root)//如果是根节点
    			   root=null;
    		   else if(isLeftChild){//如果是左孩子节点
    			   parent.leftChild=null;
    		   }else{
    			   parent.rightChild=null;
    		   }   		    		 
    	 }
    	 
    	 else if(current.leftChild==null){//如果当前节点没有左孩子
    		   if(current==root)//如果当前节点是根
    			    root=current.rightChild;
    		   else if(isLeftChild){//如果当前节点是左子树
    			    parent.leftChild=current.rightChild;
    		   }else{
    			   parent.rightChild=current.rightChild;
    		   }
    		 
    	 }
    	 
    	 else if(current.rightChild==null){//如果当前节点没有右孩子
    		   if(current==root)
    			   root=current.leftChild;
    		   else if(isLeftChild){
    			   parent.leftChild=current.leftChild;
    		   }else{
    			   parent.rightChild=current.leftChild;
    		   }
    		 
    	 }
    	 
    	 else{//如果当前节点有两个孩子
    		 //用寻找继承节点函数
    		 
    		 Node sucessor=getSucessor(current);//得到继承节点
    		 
    		 if(current==root){
    			 root=sucessor;
    		 }else if(isLeftChild){ 
    			 parent.leftChild=sucessor;
    		 }else {
    			 parent.rightChild=sucessor;
    		 }
    		 
    		 sucessor.leftChild=current.leftChild;//把 删除节点的左孩子传给继承节点（继承节点不可能有左孩子）
    	 }
    	 
    	 
    	 
    		 
    	 return true;
    	 
    	 
     }
//===========================================================================
     private Node getSucessor(Node delNode){
    	   Node sucessor=delNode;
    	   Node sucessorParent=delNode;
    	   Node cur=delNode.rightChild;
    	   while(cur!=null){
    		   sucessorParent=sucessor;
    		   sucessor=cur;
    		   cur=cur.leftChild;//向左子数移动
    		   
    		   
    	   }
    	   if(sucessor!=delNode.rightChild){//不是删除节点的右孩子，而是在右孩子的 左子树里
    	     sucessorParent.leftChild=sucessor.rightChild;
    	     sucessor.rightChild=delNode.rightChild;//把删除节点的右孩子传给继承节点
    	   }
    	   
    	   return sucessor;
     }
     
     

     
//==============================================================================     
     public void displayTree(){
    	 Stack golbalStack=new Stack();
    	 golbalStack.push(root);
    	 int nBlank=32;
    	 boolean isRowEmpty=false;
    	 System.out.println("-------------------------------");
    	 while(isRowEmpty==false){
    		 Stack localStack =new Stack();
    		 isRowEmpty=true;
    		  for(int i=0;i<nBlank;i++)
    			  System.out.println(' ');
    		  while(golbalStack.isEmpty()==false){
    			  Node temp=(Node)golbalStack.pop();
    			  if(temp!=null){
    				   System.out.println(temp.id);
    				   localStack.push(temp.leftChild);
    				   localStack.push(temp.rightChild);
    				   if(temp.leftChild!=null || temp.rightChild!=null){
    					   isRowEmpty=false;
    				   }
    				   
    			  }else{
    				  System.out.print("--");
    				  localStack.push(null);
    				  localStack.push(null);
    				  
    			  }
    			  
    			  for(int j=0;j<nBlank*2.1;j++){
    				  System.out.print(' ');
    			  }  
    		  }
  			  System.out.println();
			   nBlank/=2;
			   while(localStack.isEmpty()==false)
    		     golbalStack.push(localStack.pop());
    	 }
    	 System.out.println("-------------------------------");
    	 
     }
//==================================================================================
     public void displayTree2(){
    	 int brank=32;
    	 Stack stackG=new Stack();
    	 stackG.push(root);
    	 for(int i=0;i<brank;i++)
		      System.out.print(' ' );
    	 System.out.println("[root: "+root.id+"]");
    	 while(!stackG.isEmpty()){
    		  Stack stackL=new Stack();
    		  for(int i=0;i<brank;i++)
    		      System.out.print(' ' );
    			  
    		 while(!stackG.isEmpty()){
    			 
    			 Node node=(Node)(stackG.pop()); 
    		       System.out.print("[");
    		       
    		       if(node.leftChild==null)
    		       System.out.print("left: == ");
    		       else{
    		       System.out.print("left: "+node.leftChild.id+" ");
    		       stackL.push(node.leftChild);
    		       }
    		       
    		       if(node.rightChild==null)
    		       System.out.print("right: == "); 
    		       else{
    		       System.out.print("right: "+node.rightChild.id);
    		       stackL.push(node.rightChild);
    		       }
    		       
    		       System.out.print("]");
    		       for(int i=0;i<brank/3;i++)
    		       System.out.print(" ");
    		 }
    		 
    		 brank=brank/2;
    		 while(!stackL.isEmpty())
    		    stackG.push(stackL.pop());
    		 System.out.println();
    		 
    		 
    		 
    	 }
    	 
    	 
    	 
    	 
    	 
    	 
     }
     
//===========================================================
     
     
     
     
}