通过先序遍历和中序遍历后的序列还原二叉树(实现要领)

当我们有一个

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

中序遍历序列：9,1,11

我们可以很轻松的用笔写出对应的二叉树。可是用代码又该怎样实现？

下面我们来简朴谈谈根基头脑。

起首，先序遍历的次序是按照 根-左孩子-右孩子 的次序遍历的，那么我们可以率先确认的是先序遍历序列的第一个数就是根节点，然后中序遍历是按照 左孩子-根-右孩子 的次序遍历的。我们通过先序遍历确认了根节点，那么我们只必要在中序遍历中找到根节点的位置，然后就可以很好地域分出，那些属于左子树的节点，那些是属于右子树的节点了。如下图：

我们确定命字1为根节点，然后按照中序遍历的遍历次序确定，中序遍历序列中数字1的左边所有为左子树节点，右边所有为右子树。通过左子树节点的个数，得出先序遍历序列中从根节点今后的持续3个数是属于左子树的，剩下的为右子树。这样再在阁下子树的序列中一再以上步调，最终找到没有子节点为止。

实当代码如下：

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;//记录先序遍历节点的个数
  private List<Node> nodeList = new ArrayList<>();//条理遍历节点的行列
  public static void main(String[] args) {
    BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder();
    int[] preOrder = { 1,11};
    int[] inOrder = { 9,11};
    
    treeNode = preOrder.length;//初始化二叉树的节点数
    Node root = build.buildTreePreOrderInOrder(preOrder,preOrder.length - 1,inOrder,preOrder.length - 1);
    System.out.print("先序遍历：");
    build.preOrder(root);
    System.out.print("n中序遍历：");
    build.inOrder(root);
    System.out.print("n原二叉树：n");
    build.prototypeTree(root);
  }

  /**
   * 分治法
   * 通过先序遍历功效和中序遍历功效还原二叉树
   * @param preOrder  先序遍历功效序列
   * @param preOrderBegin   先序遍历起始位置下标
   * @param preOrderEnd  先序遍历末端位置下标
   * @param inOrder  中序遍历功效序列
   * @param inOrderBegin  中序遍历起始位置下标
   * @param inOrderEnd   中序遍历末端位置下标
   * @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];//先序遍历的第一个字符为当前序列根节点
    Node head = new Node(rootData);
    int divider = findIndexInArray(inOrder,rootData,inOrderBegin,inOrderEnd);//找打中序遍历功效齐集根节点的位置
    int offSet = divider - inOrderBegin - 1;//计较左子树共有几个节点，节点数减一，为数组偏移量
    Node left = buildTreePreOrderInOrder(preOrder,preOrderBegin + 1,preOrderBegin + 1 + offSet,inOrderBegin + offSet);
    Node right = buildTreePreOrderInOrder(preOrder,preOrderBegin + offSet + 2,preOrderEnd,divider + 1,inOrderEnd);
    head.left = left;
    head.right = right;
    return head;
  }
  /**
   * 通过先序遍历找到的rootData根节点，在中序遍历功效中区分出：中左子树和右子树
   * @param inOrder  中序遍历的功效数组
   * @param rootData  根节点位置
   * @param begin  中序遍历功效数组起始位置下标
   * @param end  中序遍历功效数组末端位置下标
   * @return return中序遍历功效数组中根节点的位置
   */
  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;
  }
  /**
   * 二叉树先序遍历功效
   * @param n
   */
  public void preOrder(Node n) {
    if (n != null) {
      System.out.print(n.val + ",");
      preOrder(n.left);
      preOrder(n.right);
    }
  }
  /**
   * 二叉树中序遍历功效
   * @param n
   */
  public void inOrder(Node n) {
    if (n != null) {
      inOrder(n.left);
      System.out.print(n.val + ",");
      inOrder(n.right);
    }
  }
  /**
   * 还原后的二叉树
   * 二叉数条理遍历
   * 根基头脑：
   *   1.由于推导出来的二叉树是生涯在Node类工具的子工具内里的，（相同于c说话的布局体）假如通过递归实现条理遍历的话，不轻易实现
   *   2.这里回收List行列逐层生涯Node工具节点的方法实现对二叉树的条理遍历输出
   *   3.假如父节点的位置为i,那么子节点的位置为，2i 和 2i+1;依据这个纪律逐层遍历，通过生涯的父节点，找到子节点。并生涯，不绝向下遍历生涯。
   * @param tree
   */
  public void prototypeTree(Node tree){
    //用list存储条理遍历的节点
    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;i++){
        //第i层第一个子节点的父节点的位置下标
        int index = (int) Math.pow(2,i-1-1)-1;
        /**
         * 二叉树的每一层节点数遍历
         * 由于第i层的最大节点数为2的i-1次方个，
         */
        for(int j=1;j<=Math.pow(2,i-1);){
          //计较有用的节点的个数，和遍历序列的总数做较量，作为判定轮回竣事的符号
          if(nodeList.get(index).left!=null)
            count++;
          if(nodeList.get(index).right!=null)
            count++;
          nodeList.add(nodeList.get(index).left);
          nodeList.add(nodeList.get(index).right);
          index++;
          if(count>=treeNode)//当全部有用节点都遍历到了就竣事遍历
            break;
          j+=2;//每次存储两个子节点，以是每次加2
        }
      }
      int flag=0,floor=1;
      for(Node node:nodeList){
        if(node!=null)
          System.out.print(node.val+" ");
        else
          System.out.print("# ");//#号暗示空节点
        flag++;
        /**
         * 逐层遍历输出二叉树
         * 
         */
        if(flag>=Math.pow(2,floor-1)){
          flag=0;
          floor++;
          System.out.println();
        }
      }
    }
  }
  /**
   * 内部类
   * 1.每个Node类工具为一个节点，
   * 2.每个节点包括根节点，左子节点和右子节点
   */
  class Node {
    Node left;
    Node right;
    int val;
    public Node(int val) {
      this.val = val;
    }
  }
}

（编辑：湖南网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!