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

当我们有一个

先序遍历序列：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;
    }
  }
}

（编辑：应用网_丽江站长网）

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