Java完全二叉树的创建与四种遍历方法分析

2019-11-26 11:02:12

字体：大中小

来源：转载

供稿：网友

本文实例讲述了Java完全二叉树的创建与四种遍历方法。分享给大家供大家参考，具体如下：

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

先序遍历结果应该为：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实现），包括几种遍历方法：

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;/** * 定义二叉树节点元素 * @author bubble * */class Node {  public Node leftchild;  public Node rightchild;  public int data;  public Node(int data) {    this.data = data;  }}public class TestBinTree {  /**   * 将一个arry数组构建成一个完全二叉树   * @param arr 需要构建的数组   * @return 二叉树的根节点   */  public Node initBinTree(int[] arr) {    if(arr.length == 1) {      return new Node(arr[0]);    }    List<Node> nodeList = new ArrayList<>();    for(int i = 0; i < arr.length; i++) {      nodeList.add(new Node(arr[i]));    }    int temp = 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++;    }    return nodeList.get(0);    }  /**   * 层序遍历二叉树   * @param root 二叉树根节点   * @param nodeQueue ，用到的队列数据结构   */   public void trivalBinTree(Node root, Queue<Node> nodeQueue) {    nodeQueue.add(root);    Node temp = null;    while ((temp = nodeQueue.poll()) != null) {      System.out.print(temp.data + " ");      if (temp.leftchild != null) {        nodeQueue.add(temp.leftchild);      }      if (temp.rightchild != null) {        nodeQueue.add(temp.rightchild);      }    }  }   /**    * 先序遍历    * @param root 二叉树根节点    */    public void preTrival(Node root) {      if(root == null) {        return;      }      System.out.print(root.data + " ");      preTrival(root.leftchild);      preTrival(root.rightchild);    }    /**     * 中序遍历     * @param root 二叉树根节点     */    public void midTrival(Node root) {      if(root == null) {        return;      }      midTrival(root.leftchild);      System.out.print(root.data + " ");      midTrival(root.rightchild);    }    /**     * 后序遍历     * @param root 二叉树根节点     */    public void afterTrival(Node root) {      if(root == null) {        return;      }      afterTrival(root.leftchild);      afterTrival(root.rightchild);      System.out.print(root.data + " ");    }    public static void main(String[] args) {      TestBinTree btree = new TestBinTree();      int[] arr = new int[] {1,2,3,4,5,6,7};      Node root = btree.initBinTree(arr);      Queue<Node> nodeQueue = new ArrayDeque<>();      System.out.println("武林网测试结果：");      System.out.println("层序遍历：");      btree.trivalBinTree(root, nodeQueue);      System.out.println("/n先序遍历：");      btree.preTrival(root);      System.out.println("/n中序遍历：");      btree.midTrival(root);      System.out.println("/n后序遍历：");      btree.afterTrival(root);    }}

运行结果：