编程语言中如何通过先序遍历和中序遍历后的序列还原二叉树

小编给大家分享一下编程语言中如何通过先序遍历和中序遍历后的序列还原二叉树，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！

当我们有一个

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

运行结果：

最后逐层输出二叉树的基本思想：

* 1.因为推导出来的二叉树是保存在Node类对象的子对象里面的，（类似于c语言的结构体）如果通过递归实现层次遍历的话，不容易实现

* 2.这里采用List队列逐层保存Node对象节点的方式实现对二叉树的层次遍历输出

* 3.如果父节点的位置为i,那么子节点的位置为，2i 和 2i+1;依据这个规律逐层遍历，通过保存的父节点，找到子节点。并保存，不断向下遍历保存。

看完了这篇文章，相信你对“编程语言中如何通过先序遍历和中序遍历后的序列还原二叉树”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！