一聚教程网:一个值得你收藏的教程网站

热门教程

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

时间:2022-06-29 01:31:51 编辑:袖梨 来源:一聚教程网

本来就是基础知识,不能丢的太干净,今天竟然花了那么长的时间才写出来,记一下。

有如下的一颗完全二叉树:

先序遍历结果应该为:1  2  4  5  3  6  7

中序遍历结果应该为:4  2  5  1  6  3  7

后序遍历结果应该为:4  5  2  6  7  3  1

层序遍历结果应该为:1  2  3  4  5  6  7

二叉树的先序遍历、中序遍历、后序遍历其实都是一样的,都是执行递归操作。

我这记录一下层次遍历吧:层次遍历需要用到队列,先入队在出队,每次出队的元素检查是其是否有左右孩子,有则将其加入队列,由于利用队列的先进先出原理,进行层次遍历。

下面记录下完整代码(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);

       

    }

     

   }

 

遍历结果:

热门栏目