当我们有一个
先序遍历序列：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;
public class BuildTreePreOrderInOrder {
* 3 5
* /
* 7 11
* /
* 9
*/
public static int treeNode = 0;//记录先序遍历节点的个数
private List 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);
}
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;
}
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;
}
public void preOrder(Node n) {
if (n != null) {
System.out.print(n.val + ",");
preOrder(n.left);
preOrder(n.right);
}
}
public void inOrder(Node n) {
if (n != null) {
inOrder(n.left);
System.out.print(n.val + ",");
inOrder(n.right);
}
}
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)//当所有有效节点都遍历到了就结束遍历
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();
}
}
}
}
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;依据这个规律逐层遍历，通过保存的父节点，找到子节点。并保存，不断向下遍历保存。
以上这篇通过先序遍历和中序遍历后的序列还原二叉树(实现方法)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持考高分网。
