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

Camille ·

更新时间:2024-09-21

· 784 次阅读

当我们有一个

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

中序遍历序列：9,7,3,1,5,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, 3, 7, 9, 5, 11};
    int[] inOrder = { 9, 7, 3, 1, 5, 11};
    treeNode = preOrder.length;//初始化二叉树的节点数
    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);
  }
  /**
   * 分治法
   * 通过先序遍历结果和中序遍历结果还原二叉树
   * @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, 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根节点，在中序遍历结果中区分出：中左子树和右子树
   * @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;
    }
  }
}

运行结果：