快捷導(dǎo)航

圖解二叉樹(shù)的三種遍歷方式及java實(shí)現(xiàn)代碼

更新時(shí)間：2017年07月07日 11:56:43 作者：Acamy丶

本篇文章主要介紹了圖解二叉樹(shù)的三種遍歷方式及java實(shí)現(xiàn)代碼，具有一定的參考價(jià)值，有興趣的可以了解一下

二叉樹(shù)(binary tree)是一顆樹(shù)，其中每個(gè)節(jié)點(diǎn)都不能有多于兩個(gè)的兒子。

1.二叉樹(shù)節(jié)點(diǎn)

作為圖的特殊形式，二叉樹(shù)的基本組成單元是節(jié)點(diǎn)與邊；作為數(shù)據(jù)結(jié)構(gòu)，其基本的組成實(shí)體是二叉樹(shù)節(jié)點(diǎn)（binary tree node），而邊則對(duì)應(yīng)于節(jié)點(diǎn)之間的相互引用。

如下，給出了二叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)圖示和相關(guān)代碼：

  // 定義節(jié)點(diǎn)類：
  private static class BinNode {
    private Object element;
    private BinNode lChild;// 定義指向左子樹(shù)的指針
    private BinNode rChild;// 定義指向右子樹(shù)的指針

    public BinNode(Object element, BinNode lChild, BinNode rChild) {
      this.element = element;
      this.lChild = lChild;
      this.rChild = rChild;
    }
  }

2.遞歸遍歷

二叉樹(shù)本身并不具有天然的全局次序，故為實(shí)現(xiàn)遍歷，需通過(guò)在各節(jié)點(diǎn)與其孩子之間約定某種局部次序，間接地定義某種全局次序。

按慣例左兄弟優(yōu)先于右兄弟，故若將節(jié)點(diǎn)及其孩子分別記作V、L和R，則下圖所示，局部訪問(wèn)的次序可有VLR、LVR和LRV三種選擇。根據(jù)節(jié)點(diǎn)V在其中的訪問(wèn)次序，三種策略也相應(yīng)地分別稱作先序遍歷、中序遍歷和后序遍歷，下面將分別介紹。

2.1 先序遍歷

圖示：

代碼實(shí)現(xiàn)：

  /**
   * 對(duì)該二叉樹(shù)進(jìn)行前序遍歷 結(jié)果存儲(chǔ)到list中 前序遍歷
   */
  public static void preOrder(BinNode node) {
    list.add(node); // 先將根節(jié)點(diǎn)存入list
    // 如果左子樹(shù)不為空繼續(xù)往左找，在遞歸調(diào)用方法的時(shí)候一直會(huì)將子樹(shù)的根存入list，這就做到了先遍歷根節(jié)點(diǎn)
    if (node.lChild != null) {
      preOrder(node.lChild);
    }
    // 無(wú)論走到哪一層，只要當(dāng)前節(jié)點(diǎn)左子樹(shù)為空，那么就可以在右子樹(shù)上遍歷，保證了根左右的遍歷順序
    if (node.rChild != null) {
      preOrder(node.rChild);
    }
  }

2.2 中序遍歷

圖示：

代碼實(shí)現(xiàn)：

  /**
   * 對(duì)該二叉樹(shù)進(jìn)行中序遍歷 結(jié)果存儲(chǔ)到list中
   */
  public static void inOrder(BinNode node) {
    if (node.lChild != null) {
      inOrder(node.lChild);
    }
    list.add(node);
    if (node.rChild != null) {
      inOrder(node.rChild);
    }
  }

2.3 后序遍歷

實(shí)例圖示：

代碼實(shí)現(xiàn)：

  /**
   * 對(duì)該二叉樹(shù)進(jìn)行后序遍歷 結(jié)果存儲(chǔ)到list中
   */
  public static void postOrder(BinNode node) {
    if (node.lChild != null) {
      postOrder(node.lChild);
    }
    if (node.rChild != null) {
      postOrder(node.rChild);
    }
    list.add(node);
  }

附：測(cè)試相關(guān)代碼

  private static BinNode root;
  private static List<BinNode> list = new ArrayList<BinNode>();

  public static void main(String[] args) {
    init();
    // TODO Auto-generated method stub
    //preOrder(root);
    //inOrder(root);
    postOrder(root);
    for (int i = 0; i < list.size(); i++) {
      System.out.print(list.get(i).element + " ");
    }
  }

  // 樹(shù)的初始化:先從葉節(jié)點(diǎn)開(kāi)始,由葉到根
  public static void init() {
    BinNode b = new BinNode("b", null, null);
    BinNode a = new BinNode("a", null, b);
    BinNode c = new BinNode("c", a, null);

    BinNode e = new BinNode("e", null, null);
    BinNode g = new BinNode("g", null, null);
    BinNode f = new BinNode("f", e, g);
    BinNode h = new BinNode("h", f, null);

    BinNode d = new BinNode("d", c, h);

    BinNode j = new BinNode("j", null, null);
    BinNode k = new BinNode("k", j, null);
    BinNode m = new BinNode("m", null, null);
    BinNode o = new BinNode("o", null, null);
    BinNode p = new BinNode("p", o, null);
    BinNode n = new BinNode("n", m, p);
    BinNode l = new BinNode("l", k, n);

    root = new BinNode("i", d, l);
  }

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: