根据先序遍历和中序遍历恢复出二叉树
Java:根据先序序列和中序序列恢复二叉树
1.先给出节点类，该节点是一个英雄节点（包含英雄的编号、姓名、当前节点的左子树根节点和右子树根节点）
class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, String name) {
super();
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
} 2.二叉树类，该类中包含一个根节点，以及一个函数(根据先序和中序恢复出二叉树的函数)
public class BinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
public HeroNode getRoot() {
return root;
}
//根据先序遍历和中序遍历序列恢复二叉树
public HeroNode rebuildBinaryTree(ArrayList<HeroNode> preod, int preOrderStart, int preOrderEnd, ArrayList<HeroNode> inod, int inOrderStart, int inOrderEnd) {
if(preOrderStart>preOrderEnd||inOrderStart>inOrderEnd) {
return null;
}
HeroNode root=preod.get(preOrderStart);
for(int i=inOrderStart;i<=inOrderEnd;i++) {
if(inod.get(i).getNo()==root.getNo()) {
root.setLeft(rebuildBinaryTree(preod, preOrderStart+1, preOrderStart+(i-inOrderStart), inod, inOrderStart, i-1));
root.setRight(rebuildBinaryTree(preod, preOrderStart+(i-inOrderStart)+1, preOrderEnd, inod, i+1, inOrderEnd));
//return root;
}
}
return root;
}
} 3.测试类
public class BinaryTreeDemo {
public static void main(String[] args) {
//先定义一棵树
BinaryTree binaryTree=new BinaryTree();
//定义所有的子孙节点
HeroNode root=new HeroNode(1,"宋江");
HeroNode root1=new HeroNode(2, "吴用");
HeroNode root2=new HeroNode(3, "卢俊义");
HeroNode root3=new HeroNode(4, "林冲");
//测试：根据先序序列和中序序列恢复二叉树
//先序遍历序列
ArrayList<HeroNode> preod=new ArrayList<HeroNode>();
preod.add(root);
preod.add(root1);
preod.add(root2);
preod.add(root3);
//后续遍历序列
ArrayList<HeroNode> inod=new ArrayList<HeroNode>();
inod.add(root1);
inod.add(root);
inod.add(root2);
inod.add(root3);
binaryTree.setRoot(binaryTree.rebuildBinaryTree(preod, 0, preod.size()-1, inod, 0, inod.size()-1));
//测试结果
System.out.println("前序遍历");//1 2 3 4
binaryTree.preOrder();
System.out.println("中序遍历");//2 1 3 4
binaryTree.inOrder();
System.out.println("后序遍历");//2 4 3 1
binaryTree.postOrder();
}
} 4.在测试类中，为了测试最后的结果，需要检测恢复的二叉树的前序、中序、后续结果是否正确，而为了代码简介好看，节点类以及二叉树类中的“前序遍历”，“中序遍历”和“后续遍历”的函数省去了，需要的补充如下:
4.1 英雄节点类中的“前序遍历”，“中序遍历”和“后续遍历”函数。
//前序遍历
public void preOrder() {
System.out.println(this);
if(this.left!=null) {
this.left.preOrder();
}
if(this.right!=null) {
this.right.preOrder();
}
}
//中序遍历
public void inOrder() {
if(this.left!=null) {
this.left.inOrder();
}
System.out.println(this);
if(this.right!=null) {
this.right.inOrder();
}
}
//后序遍历
public void postOrder() {
if(this.left!=null) {
this.left.postOrder();
}
if(this.right!=null) {
this.right.postOrder();
}
System.out.println(this);
} 4.2 二叉树类中的“前序遍历”，“中序遍历”和“后续遍历”函数。
//前序遍历
public void preOrder() {
if(this.root!=null) {
this.root.preOrder();
}
}
//中序遍历
public void inOrder() {
if(this.root!=null) {
this.root.inOrder();
}
}
//后序遍历
public void postOrder() {
if(this.root!=null) {
this.root.postOrder();
}
} 
