二叉树相关操作（Java实现）-蒲公英云

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);
    }
}