java 完全二叉树的构建与四种遍历方法示例

importjava.util.ArrayDeque;

importjava.util.ArrayList;

importjava.util.List;

importjava.util.Queue;

/**

 * 定义二叉树节点元素

 * @author bubble

 *

 */

classNode { 

  publicNode leftchild;

  publicNode rightchild;

  publicintdata;

  publicNode(intdata) {

    this.data = data;

  }

}

publicclassTestBinTree {

  /**

   * 将一个arry数组构建成一个完全二叉树

   * @param arr 需要构建的数组

   * @return 二叉树的根节点

   */

  publicNode initBinTree(int[] arr) {

    if(arr.length ==1) {

      returnnewNode(arr[0]);

    }

    ListnodeList =newArrayList<>();

    for(inti =0; i < arr.length; i++) {

      nodeList.add(newNode(arr[i]));

    }

    inttemp =0;

    while(temp <= (arr.length -2) /2) {//注意这里，数组的下标是从零开始的

      if(2* temp +1< arr.length) {

        nodeList.get(temp).leftchild = nodeList.get(2* temp +1);

      }

      if(2* temp +2< arr.length) {

        nodeList.get(temp).rightchild = nodeList.get(2* temp +2);

      }

      temp++;

    }

    returnnodeList.get(0);

    }

  /**

   * 层序遍历二叉树，，并分层打印

   * @param root 二叉树根节点

   *

   */

   publicvoidtrivalBinTree(Node root) {

    QueuenodeQueue =newArrayDeque<>();

    nodeQueue.add(root);

    Node temp =null;

    intcurrentLevel =1; //记录当前层需要打印的节点的数量

    intnextLevel =0;//记录下一层需要打印的节点的数量

    while((temp = nodeQueue.poll()) !=null) {

      if(temp.leftchild !=null) {

        nodeQueue.add(temp.leftchild);

        nextLevel++;

      }

      if(temp.rightchild !=null) {

        nodeQueue.add(temp.rightchild);

        nextLevel++;

      }

      System.out.print(temp.data +" ");

      currentLevel--;

      if(currentLevel ==0) {

        System.out.println();

        currentLevel = nextLevel;

        nextLevel =0;

      }

    }

  }

   /**

    * 先序遍历

    * @param root 二叉树根节点

    */

    publicvoidpreTrival(Node root) {

      if(root ==null) {

        return;

      }

      System.out.print(root.data +" ");

      preTrival(root.leftchild);

      preTrival(root.rightchild);

    }

    /**

     * 中序遍历

     * @param root 二叉树根节点

     */

    publicvoidmidTrival(Node root) {

      if(root ==null) {

        return;

      }

      midTrival(root.leftchild);

      System.out.print(root.data +" ");

      midTrival(root.rightchild);

    }

    /**

     * 后序遍历

     * @param root 二叉树根节点

     */

    publicvoidafterTrival(Node root) {

      if(root ==null) {

        return;

      }

      afterTrival(root.leftchild);

      afterTrival(root.rightchild);

      System.out.print(root.data +" ");

    }

    publicstaticvoidmain(String[] args) {

      TestBinTree btree =newTestBinTree();

      int[] arr =newint[] {1,2,3,4,5,6,7};

      Node root = btree.initBinTree(arr);

      System.out.println("层序遍历(分层打印)：");

      btree.trivalBinTree(root);

      System.out.println("n先序遍历：");

      btree.preTrival(root);

      System.out.println("n中序遍历：");

      btree.midTrival(root);

      System.out.println("n后序遍历：");

      btree.afterTrival(root);

    }

   }