给定某二叉树三序遍历中的两个，我们即可以通过生成该二叉树，并遍历的方法，求出剩下的一序，具体代码如下
[java] view plain copy
package Tree;
import java.io.BufferedInputStream;
import java.util.*;
public class BT {
class Node{
Node l;//左儿子
Node r;//右儿子
char c;//结点字符
public Node(char c) {
this.c = c;
this.l = null;
this.r = null;
}
}
Node root;
char[] str1,str2;
public BT() {
root =null;
}
public void postOrder(Node n) {
if(n.l!=null) {
postOrder(n.l);
}
if(n.r!=null) {
postOrder(n.r);
}
System.out.print(n.c);
}
public void firstOrder() {
this.firstOrder(this.root);
}
public void firstOrder(Node n) {
System.out.print(n.c);
if(n.l!=null) {
firstOrder(n.l);
}
if(n.r!=null) {
firstOrder(n.r);
}
}
public void postOrder() {
this.postOrder(this.root);
}
public Node build(int s1,int e1,int s2,int e2) {
char c = str1[s1];
Node Root =new Node(c);
int index = 0;
for(int i = s2;i<=e2;i++) {
if(str2[i]==c) {
index = i;
break;
}
}
if(index!=s2) {//如果左子树不为空
Root.l = build(s1+1,s1+index-s2,s2,index-1);
}
if(index!=e2) {//如果右子树不为空
Root.r = build(s1+index-s2+1,e1,index+1,e2);
}
return Root;
}
public Node build1(int s1,int e1,int s2,int e2) {//中后序还原树
char c = str2[e2];
Node Root =new Node(c);
int index = 0;
for(int i = s1;i<=e1;i++) {
if(str1[i]==c) {
index = i;
break;
}
}
if(index!=s1) {
Root.l = build1(s1,index-1,s2,s2+index-s1-1);
}
if(index!=e1) {
Root.r = build1(index+1,e1,s2+index-s1+1,e2-1);
}
return Root;
}
public static void main(String[] args) {
String s1,s2 =null;
Scanner sc =new Scanner(new BufferedInputStream(System.in));
BT bt =new BT();
while(sc.hasNext()) {
s1 = sc.next();
s2 = sc.next();
bt.str1 =new char[s1.length()];
bt.str2 =new char[s1.length()];
bt.str1 = s1.toCharArray();
bt.str2 = s2.toCharArray();
bt.root = bt.build1(0, s1.length()-1, 0, s1.length()-1);
bt.firstOrder();
}
}
}
其中build是已知前中序，生成二叉树；build1是已知中后序，生成二叉树
网友评论