小編給大家分享一下編程語(yǔ)言中如何通過先序遍歷和中序遍歷后的序列還原二叉樹，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

在永春等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、做網(wǎng)站 網(wǎng)站設(shè)計(jì)制作按需求定制網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,網(wǎng)絡(luò)營(yíng)銷推廣,成都外貿(mào)網(wǎng)站建設(shè)公司,永春網(wǎng)站建設(shè)費(fèi)用合理。

當(dāng)我們有一個(gè)

先序遍歷序列：1,3,7,9,5,11

中序遍歷序列：9,7,3,1,5,11

我們可以很輕松的用筆寫出對(duì)應(yīng)的二叉樹。但是用代碼又該如何實(shí)現(xiàn)？

下面我們來(lái)簡(jiǎn)單談?wù)劵舅枷搿?/p>

首先，先序遍歷的順序是根據(jù) 根-左孩子-右孩子的順序遍歷的，那么我們可以率先確認(rèn)的是先序遍歷序列的第一個(gè)數(shù)就是根節(jié)點(diǎn)，然后中序遍歷是根據(jù) 左孩子-根-右孩子的順序遍歷的。我們通過先序遍歷確認(rèn)了根節(jié)點(diǎn)，那么我們只需要在中序遍歷中找到根節(jié)點(diǎn)的位置，然后就可以很好地區(qū)分出，那些屬于左子樹的節(jié)點(diǎn)，那些是屬于右子樹的節(jié)點(diǎn)了。如下圖：

我們確定數(shù)字1為根節(jié)點(diǎn)，然后根據(jù)中序遍歷的遍歷順序確定，中序遍歷序列中數(shù)字1的左邊全部為左子樹節(jié)點(diǎn)，右邊全部為右子樹。通過左子樹節(jié)點(diǎn)的個(gè)數(shù)，得出先序遍歷序列中從根節(jié)點(diǎn)往后的連續(xù)3個(gè)數(shù)是屬于左子樹的，剩下的為右子樹。這樣再在左右子樹的序列中重復(fù)以上步驟，最終找到?jīng)]有子節(jié)點(diǎn)為止。

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

package com.tree.traverse;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Caijh
 *
 * 2017年6月2日 下午7:21:10
 */

public class BuildTreePreOrderInOrder {

  /** 
   *       1 
   *       / \
   *      3  5 
   *      /   \
   *     7    11
   *    / 
   *   9    
   */ 
  public static int treeNode = 0;//記錄先序遍歷節(jié)點(diǎn)的個(gè)數(shù)
  private List nodeList = new ArrayList<>();//層次遍歷節(jié)點(diǎn)的隊(duì)列
  public static void main(String[] args) {
    BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder();
    int[] preOrder = { 1, 3, 7, 9, 5, 11};
    int[] inOrder = { 9, 7, 3, 1, 5, 11};
    
    treeNode = preOrder.length;//初始化二叉樹的節(jié)點(diǎn)數(shù)
    Node root = build.buildTreePreOrderInOrder(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1);
    System.out.print("先序遍歷：");
    build.preOrder(root);
    System.out.print("\n中序遍歷：");
    build.inOrder(root);
    System.out.print("\n原二叉樹：\n");
    build.prototypeTree(root);
  }

  /**
   * 分治法
   * 通過先序遍歷結(jié)果和中序遍歷結(jié)果還原二叉樹
   * @param preOrder  先序遍歷結(jié)果序列
   * @param preOrderBegin   先序遍歷起始位置下標(biāo)
   * @param preOrderEnd  先序遍歷末尾位置下標(biāo)
   * @param inOrder  中序遍歷結(jié)果序列
   * @param inOrderBegin  中序遍歷起始位置下標(biāo)
   * @param inOrderEnd   中序遍歷末尾位置下標(biāo)
   * @return
   */
  public Node buildTreePreOrderInOrder(int[] preOrder, int preOrderBegin, int preOrderEnd, int[] inOrder, int inOrderBegin, int inOrderEnd) {
    if (preOrderBegin > preOrderEnd || inOrderBegin > inOrderEnd) {
      return null;
    }
    int rootData = preOrder[preOrderBegin];//先序遍歷的第一個(gè)字符為當(dāng)前序列根節(jié)點(diǎn)
    Node head = new Node(rootData);
    int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍歷結(jié)果集中根節(jié)點(diǎn)的位置
    int offSet = divider - inOrderBegin - 1;//計(jì)算左子樹共有幾個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)數(shù)減一，為數(shù)組偏移量
    Node left = buildTreePreOrderInOrder(preOrder, preOrderBegin + 1, preOrderBegin + 1 + offSet, inOrder, inOrderBegin,inOrderBegin + offSet);
    Node right = buildTreePreOrderInOrder(preOrder, preOrderBegin + offSet + 2, preOrderEnd, inOrder, divider + 1, inOrderEnd);
    head.left = left;
    head.right = right;
    return head;
  }
  /**
   * 通過先序遍歷找到的rootData根節(jié)點(diǎn)，在中序遍歷結(jié)果中區(qū)分出：中左子樹和右子樹
   * @param inOrder  中序遍歷的結(jié)果數(shù)組
   * @param rootData  根節(jié)點(diǎn)位置
   * @param begin  中序遍歷結(jié)果數(shù)組起始位置下標(biāo)
   * @param end  中序遍歷結(jié)果數(shù)組末尾位置下標(biāo)
   * @return return中序遍歷結(jié)果數(shù)組中根節(jié)點(diǎn)的位置
   */
  public int findIndexInArray(int[] inOrder, int rootData, int begin, int end) {
    for (int i = begin; i <= end; i++) {
      if (inOrder[i] == rootData)
        return i;
    }
    return -1;
  }
  /**
   * 二叉樹先序遍歷結(jié)果
   * @param n
   */
  public void preOrder(Node n) {
    if (n != null) {
      System.out.print(n.val + ",");
      preOrder(n.left);
      preOrder(n.right);
    }
  }
  /**
   * 二叉樹中序遍歷結(jié)果
   * @param n
   */
  public void inOrder(Node n) {
    if (n != null) {
      inOrder(n.left);
      System.out.print(n.val + ",");
      inOrder(n.right);
    }
  }
  /**
   * 還原后的二叉樹
   * 二叉數(shù)層次遍歷
   * 基本思想：
   *   1.因?yàn)橥茖?dǎo)出來(lái)的二叉樹是保存在Node類對(duì)象的子對(duì)象里面的，（類似于c語(yǔ)言的結(jié)構(gòu)體）如果通過遞歸實(shí)現(xiàn)層次遍歷的話，不容易實(shí)現(xiàn)
   *   2.這里采用List隊(duì)列逐層保存Node對(duì)象節(jié)點(diǎn)的方式實(shí)現(xiàn)對(duì)二叉樹的層次遍歷輸出
   *   3.如果父節(jié)點(diǎn)的位置為i,那么子節(jié)點(diǎn)的位置為，2i 和 2i+1;依據(jù)這個(gè)規(guī)律逐層遍歷，通過保存的父節(jié)點(diǎn)，找到子節(jié)點(diǎn)。并保存，不斷向下遍歷保存。
   * @param tree
   */
  public void prototypeTree(Node tree){
    //用list存儲(chǔ)層次遍歷的節(jié)點(diǎn)
    if(tree !=null){
      if(tree!=null)
        nodeList.add(tree);
      nodeList.add(tree.left);
      nodeList.add(tree.right);
      int count=3;
      //從第三層開始
      for(int i=3;count=treeNode)//當(dāng)所有有效節(jié)點(diǎn)都遍歷到了就結(jié)束遍歷
            break;
          j+=2;//每次存儲(chǔ)兩個(gè)子節(jié)點(diǎn)，所以每次加2
        }
      }
      int flag=0,floor=1;
      for(Node node:nodeList){
        if(node!=null)
          System.out.print(node.val+" ");
        else
          System.out.print("# ");//#號(hào)表示空節(jié)點(diǎn)
        flag++;
        /**
         * 逐層遍歷輸出二叉樹
         * 
         */
        if(flag>=Math.pow(2, floor-1)){
          flag=0;
          floor++;
          System.out.println();
        }
      }
    }
  }
  /**
   * 內(nèi)部類
   * 1.每個(gè)Node類對(duì)象為一個(gè)節(jié)點(diǎn)，
   * 2.每個(gè)節(jié)點(diǎn)包含根節(jié)點(diǎn)，左子節(jié)點(diǎn)和右子節(jié)點(diǎn)
   */
  class Node {
    Node left;
    Node right;
    int val;
    public Node(int val) {
      this.val = val;
    }
  }
}

運(yùn)行結(jié)果：

最后逐層輸出二叉樹的基本思想：

* 1.因?yàn)橥茖?dǎo)出來(lái)的二叉樹是保存在Node類對(duì)象的子對(duì)象里面的，（類似于c語(yǔ)言的結(jié)構(gòu)體）如果通過遞歸實(shí)現(xiàn)層次遍歷的話，不容易實(shí)現(xiàn)

* 2.這里采用List隊(duì)列逐層保存Node對(duì)象節(jié)點(diǎn)的方式實(shí)現(xiàn)對(duì)二叉樹的層次遍歷輸出

* 3.如果父節(jié)點(diǎn)的位置為i,那么子節(jié)點(diǎn)的位置為，2i 和 2i+1;依據(jù)這個(gè)規(guī)律逐層遍歷，通過保存的父節(jié)點(diǎn)，找到子節(jié)點(diǎn)。并保存，不斷向下遍歷保存。

看完了這篇文章，相信你對(duì)“編程語(yǔ)言中如何通過先序遍歷和中序遍歷后的序列還原二叉樹”有了一定的了解，如果想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！