二叉树相关操作（Java实现）

àì夳堔傛蜴生んèń 2022-05-28 03:58 155阅读 0赞

package myTest;
    import java.util.ArrayList;
    
    //二叉树的节点类，你可以将它写成内部类的形式
    class BTreeNode {
       int data;
       BTreeNode Left;
       BTreeNode Right;
       public BTreeNode(int data) { 
          this.data=data;
          this.Left=null;
          this.Right=null;
       }
       public BTreeNode(int data,BTreeNode Left,BTreeNode Right) { 
    	      this.data=data;
    	      this.Left=Left;
    	      this.Right=Right;
    	   }
       public BTreeNode getLeft() {  
           return Left;  
       }  
       public void setLeft(BTreeNode Left) {  
           this.Left = Left;  
       }  
       public BTreeNode getRight() {  
           return Right;  
       }  
       public void setRight(BTreeNode Right) {  
           this.Right = Right;  
       }  
       public int getData() {  
           return data;  
       }  
       public void setData(int data) {  
           this.data = data;  
       }   
       
    }
    //二叉树的创建
    //(1)* 创建树
    //*
    //* 以完全二叉树的格式来创建（子树不存在的用-1填充），
    //* 对完全二叉树中每一个节点从0开始进行编号，
    //* 那么第i个节点的左孩子的编号为2*i+1，右孩子为2*i+2。
    public class BTreeFactory{
    	/*完全二叉树格式+for循环建立二叉树
    	 *for循环创建。基本思路是先针对输入数组产生相同大小的节点对象数组，存储这些节点对象的引用变量和对应的数据存储到一个数组中。
    	 *之后用for循环再进行Left和Right的保存
    	 */
    	public static BTreeNode CreateTree1(int[]a,int k){
    		ArrayList<BTreeNode>aList=new ArrayList<BTreeNode>();
    		if(a.length==0) return null;
    		for(int i=0;i<a.length;i++)
    		{ //-1表示该位置处节点为空
    		  if(a[i]!=-1){aList.add(new BTreeNode(a[i]));}
    		  else {aList.add(null);}
    		}
    		//针对前N/2的节点的Left和Right进行赋值
    		for(int i=0;i<aList.size()/2;i++){
    			if(aList.get(i)!=null){
    				aList.get(i).Left=aList.get(2*i+1);
    				if((2*i+2)<aList.size())
    				  {aList.get(i).Right=aList.get(2*i+2);}
    			}
    			
    		}
    		return aList.get(0);	
    	}
    	
    	/*完全二叉树的输入格式+递归法
    	 */
    	public static BTreeNode CreateTree2(int[]a,int k){
    		if(a.length==0) return null;//如果数组长度为0，则不创建节点
    		if(k>(a.length-1)) return null;//遍历完了数组中所有的值
    		if(a[k]==-1) return null;//如果当前值为-1，则不建立节点
    		BTreeNode root=new BTreeNode(a[k]);//创建当前节点
    		root.Left=CreateTree2(a, 2*k+1);
    		root.Right=CreateTree2(a,2*k+2);
    		return root;	
    	}
    	/*根据先序遍历和中序遍历创建二叉树
    	 */
    	public static int[] GetPartArray(int[]a,int start,int end){
    		if(end<start) return null;
    		int[]aa=new int[end-start+1];
    		for(int i=start;i<=end;i++){
    			aa[i-start]=a[i];
    		}
    		return aa;
    	}
    	public static int GetPosition(int[]a,int target){
    		int pos=-1;
    		for(int i=0;i<a.length;i++){
    			if(a[i]==target) {pos=i;break;}
    		}
    		return pos;
    	}
    	/*根据先序遍历和中序遍历创建二叉树
    	 */
    	public static BTreeNode CreateTree3(int[]a,int[]b){
    		if(a==null) return null;
    		BTreeNode root=new BTreeNode(a[0]);
    		if(a.length==1)
    			{root.Left=null;
    			root.Right=null;}
    		else{int Posroot=GetPosition(b,a[0]);
    			root.Left=CreateTree3(GetPartArray(a, 1, Posroot),GetPartArray(b, 0, Posroot-1));
    		    root.Right=CreateTree3(GetPartArray(a, Posroot+1, a.length-1),GetPartArray(b, Posroot+1, a.length-1));
    		    }
    		
    			
    		return root;
    	}
    	/*根据中序遍历和后序遍历建立二叉树
    	 * 
    	 */
    	public static BTreeNode CreateTree4(int[]b,int[]c){
    		if(c==null) return null;
    		BTreeNode root=new BTreeNode(c[c.length-1]);
    		if(c.length==1)
    			{root.Left=null;
    			root.Right=null;}
    		else{int Posroot=GetPosition(b,c[c.length-1]);
    			root.Left=CreateTree4(GetPartArray(b, 0, Posroot-1),GetPartArray(c, 0, Posroot-1));
    		    root.Right=CreateTree4(GetPartArray(b, Posroot+1, b.length-1),GetPartArray(c, Posroot, c.length-2));
    		    }
    		
    			
    		return root;
    	}
    	
    	/*先序遍历输出一个二叉树
    	 * 
    	 */
    	public static void PrePrintBTree(BTreeNode root){
    		if(root==null) 
              	{return;}
    		else
    		{System.out.println(root.data);
    		PrePrintBTree(root.Left);
    		PrePrintBTree(root.Right);
    		}
    			
    	}
    	/*中序遍历输出一个二叉树
    	 * 
    	 */
    	public static void MidPrintBTree(BTreeNode root){
    		if(root==null) 
    			{return;}
    		else
    		{MidPrintBTree(root.Left);
    		 System.out.println(root.data);
    		 MidPrintBTree(root.Right);
    		}
    			
    	}
    	/*后序遍历输出一个二叉树
    	 * 
    	 */
    	public static void LastPrintBTree(BTreeNode root){
    		if(root==null) 
    			{return;}
    		else
    		{LastPrintBTree(root.Left); 
    		 LastPrintBTree(root.Right);
    		 System.out.println(root.data);
    		}
    			
    	}
    		
    	
    	
    	public static void main(String[]args){
    		//完全二叉树层序遍历格式的输入
    	    int[]arr={89,73,82,-1,-1,92,5,-1,-1,-1,-1,69};
    	    //完全二叉树格式的输入+递归法创建
    		BTreeNode root=CreateTree2(arr,0);
    		//先序遍历
    		System.out.println("先序遍历:");
    		PrePrintBTree(root);
    		//中序遍历
    		System.out.println("中序遍历:");
    		MidPrintBTree(root);
    		//后序遍历
    		System.out.println("后序遍历:");
    		LastPrintBTree(root);
    		//完全二叉树格式先序遍历的输入+for循环创建
    		BTreeNode root2=CreateTree1(arr,0);
    		//先序遍历
    		System.out.println("先序遍历:");
    		PrePrintBTree(root2);
    		//中序遍历
    		System.out.println("中序遍历:");
    		MidPrintBTree(root2);
    		//后序遍历
    		System.out.println("后序遍历:");
    		LastPrintBTree(root2);
    		//以先序加中序的数组来创建一个二叉树
    		int[]a={5,2,1,4,3,6,8,7,9,11,10};//先序遍历结果
    		int[]b={1,2,3,4,5,6,7,8,9,10,11};//中序遍历结果
    		int[]c={1,3,4,2,7,10,11,9,8,6,5};//后序遍历结果
    		BTreeNode root3=CreateTree3(a, b);
    		//先序遍历
    		System.out.println("先序遍历:");
    		PrePrintBTree(root3);
    		//中序遍历
    		System.out.println("中序遍历:");
    		MidPrintBTree(root3);
    		//后序遍历
    		System.out.println("后序遍历:");
    		LastPrintBTree(root3);
    		BTreeNode root4=CreateTree4(b, c);
    		//先序遍历
    		System.out.println("先序遍历:");
    		PrePrintBTree(root4);
    		//中序遍历
    		System.out.println("中序遍历:");
    		MidPrintBTree(root4);
    		//后序遍历
    		System.out.println("后序遍历:");
    		LastPrintBTree(root4);
    	}
    	
    	
    }