JAVA#层序遍历自动生成二叉树#二叉树的遍历#队列#

        利用队列创建一颗二叉树，我们事先把要创建的二叉树按照层序遍历的顺序存储在一个object类型的数组中，节点不存在的情况用0代替，然后将参数传到函数中，便会生成有一给二叉树。

        由于每个空节点都要用0代替，所以我们在创建数组是，要把包括叶子节点的后续节点都要置为0，这是这个方法不足的地方

 //        1
 //     2    3
 //   0  5  0  0
这种情况就要将叶子节点 5 的后续节点都补上0，即
Object []obj={1,2,3,0,5,0,0,0,0}

        另外由于充当参数的类型是object，所以后续比较大小什么的可能会出现问题，所以可以根据需要将参数类型设置为型如int 等其他基本数据类型。

        思想就是每次弹出一个节点的同时，弹出两个数据， 第一个数据作为节点的左孩子，第二个数据作为节点的右孩子，同时将新产生的左右节点分别入队。

public static treeNode buildTreeAuto(Object []obj){
        treeNode BT;
        ArrayBlockingQueue dataQ =new ArrayBlockingQueue(50) ;//存储数据
        ArrayBlockingQueue treeQ =new ArrayBlockingQueue(50) ;//存储节点

        for(int i=0;i 
二叉树的遍历差不多用的都是递归
 
//二叉树的遍历
    //先序遍历
    public static void rootFirsTravel(treeNode T){
        if(T!=null){
            System.out.print(T.getData());
            rootFirsTravel(T.LeftT()) ;
            rootFirsTravel(T.RightT()) ;
        }
    }

    //中序遍历
    public static void rootMidTravel(treeNode T){
        if(T!=null){
            rootMidTravel(T.LeftT()) ;
            System.out.print(T.getData());
            rootMidTravel(T.RightT()) ;
        }
    }

    //后序遍历
    public static void rootLastTravel(treeNode T){
        if(T!=null){
            rootMidTravel(T.LeftT()) ;
            rootMidTravel(T.RightT()) ;
            System.out.println(T.getData());
        }
    }

    //层序遍历
    public static void stepTravel(treeNode T){
        ArrayBlockingQueue queue=new ArrayBlockingQueue(50);
        if(T==null)
            return;
        queue.add(T);
        while(!queue.isEmpty()){
            T=(treeNode) queue.poll();
            System.out.print(T.getData());
            if(T.LeftT()!=null){
                queue.add(T.LeftT()) ;
            }
            if(T.RightT()!=null){
                queue.add(T.RightT()) ;
            }
        }
    }
 
让我们分别从满二叉树，和非满二叉树两种情况测试：
 
    
    //       1                1
    //     2   3            2   3
    //    0 5 0 0         4  5 6 7
    //     6 7           00 00 00 00
    //    00 00
      public static void main(String[] args) {
      Object []test1={1,2,3,0,5,0,0,6,7,0,0,0,0} ;
      treeNode myTest1=buildTreeAuto(test1) ;
      System.out.print("前序遍历结果：");
      rootFirsTravel(myTest1);
      System.out.println();
      System.out.print("层序遍历结果：");
      stepTravel(myTest1);

        System.out.println("n");
        Object []test2={1,2,3,4,5,6,7,0,0,0,0,0,0,0,0} ;
        treeNode myTest2=buildTreeAuto(test2) ;
        System.out.print("前序遍历结果：");
        rootFirsTravel(myTest2);
        System.out.println();
        System.out.print("层序遍历结果：");
        stepTravel(myTest2);
 
结果展示：
 
D:Javajdkbinjava.exe "-javaagent:D:ideaIntelliJ IDEA 2021.3.1
前序遍历结果：125673
层序遍历结果：123567

前序遍历结果：1245367
层序遍历结果：1234567
Process finished with exit code 0