ツリーループjava
2227 ワード
タイトルの説明
二叉木の前序、中序、後序遍歴の定義:前序遍歴:いずれかのサブツリーに対して、先にフォローにアクセスし、それからその左サブツリーを遍歴し、最後にその右サブツリーを遍歴する.中序遍歴:いずれかのサブツリーに対して、まず左サブツリーを遍歴し、それからルートにアクセスし、最後に右サブツリーを遍歴する.≪後順ループ|Back Sequence Rolling|emdw≫:いずれかのサブツリーに対して、左サブツリーをループし、右サブツリーをループし、最後にルートにアクセスします.1本の二叉木の前序遍歴と中序遍歴を与え、後序遍歴を求める(ヒント:与えられた前序遍歴と中序遍歴は後序遍歴を一意に決定することができる).
入力
2つの文字列は、長さnが26以下である.第1の動作の前順序は遍歴し、第2の動作の中で順序は遍歴する.ツリーのノード名は大文字でA,B,C....最大26個のノードです.
しゅつりょく
入力サンプルには複数のグループがあり、各グループのテストサンプルに対して、1行を出力し、後順に遍歴する文字列とします.
サンプル入力
サンプル出力
既知の後の順序、中の順序、前の順序を求めます
二叉木の前序、中序、後序遍歴の定義:前序遍歴:いずれかのサブツリーに対して、先にフォローにアクセスし、それからその左サブツリーを遍歴し、最後にその右サブツリーを遍歴する.中序遍歴:いずれかのサブツリーに対して、まず左サブツリーを遍歴し、それからルートにアクセスし、最後に右サブツリーを遍歴する.≪後順ループ|Back Sequence Rolling|emdw≫:いずれかのサブツリーに対して、左サブツリーをループし、右サブツリーをループし、最後にルートにアクセスします.1本の二叉木の前序遍歴と中序遍歴を与え、後序遍歴を求める(ヒント:与えられた前序遍歴と中序遍歴は後序遍歴を一意に決定することができる).
入力
2つの文字列は、長さnが26以下である.第1の動作の前順序は遍歴し、第2の動作の中で順序は遍歴する.ツリーのノード名は大文字でA,B,C....最大26個のノードです.
しゅつりょく
入力サンプルには複数のグループがあり、各グループのテストサンプルに対して、1行を出力し、後順に遍歴する文字列とします.
サンプル入力
ABC
CBA
ABCDEFG
DCBAEFG
サンプル出力
CBA
DCBGFEA
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
String pre = in.next();
String mid = in.next();
String ans = postOrder(pre,mid);
System.out.println(ans);
}
in.close();
}
private static String postOrder(String pre, String mid) {
// TODO Auto-generated method stub
if(pre.length()==1)return pre;
else if(pre.length()==0)return "";
String root,left,right;
root = String.valueOf(pre.charAt(0));
int m = mid.indexOf(root);
left = postOrder(pre.substring(1,m+1),mid.substring(0,m));
right = postOrder(pre.substring(m+1),mid.substring(m+1));
return left+right+root;
}
}
既知の後の順序、中の順序、前の順序を求めます
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
String post = in.next();
String mid = in.next();
String ans = preOrder(post,mid);
System.out.println(ans);
}
in.close();
}
private static String preOrder(String post, String mid) {
// TODO Auto-generated method stub
if(post.length()==1)return post;
else if(post.length()==0)return "";
String root,left,right;
root = String.valueOf(post.charAt(post.length()-1));
int m = mid.indexOf(root);
left = preOrder(post.substring(post.length()-mid.length(),m),mid.substring(0,m));
right = preOrder(post.substring(m,post.length()-1),mid.substring(m+1));
return root+left+right;
}
}