JAva:シーケンス配列を求める(中シーケンス遍歴と後シーケンス遍歴前シーケンス遍歴を探し、dfs(ツリーの検索)もある)
6814 ワード
JAva:順序付けを求める
タイトル
参照:https://blog.csdn.net/a1439775520/article/details/92798355?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158488090119724839256194%2522%252C%2522scm%2522%253A%252220140713.130056874…%2522%257D&request_id=158488090119724839256194&biz_id=0&utm_source=distribute.pc_search_result.none-task
解析
後の順序の最後のノードは必ず先の順序の最初のノードである.ルートノードが分かれば,左サブツリーと右サブツリーを中系列で分割できる.左右のサブツリーを再帰的に処理すると,先順遍歴の結果が得られる.mid,back,pre配列でそれぞれ中序,後序,先序を表す.
タイトル
。 。( , <=8)。
, ,
,
BADC
BDCA
ABCD
参照:https://blog.csdn.net/a1439775520/article/details/92798355?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158488090119724839256194%2522%252C%2522scm%2522%253A%252220140713.130056874…%2522%257D&request_id=158488090119724839256194&biz_id=0&utm_source=distribute.pc_search_result.none-task
解析
後の順序の最後のノードは必ず先の順序の最初のノードである.ルートノードが分かれば,左サブツリーと右サブツリーを中系列で分割できる.左右のサブツリーを再帰的に処理すると,先順遍歴の結果が得られる.mid,back,pre配列でそれぞれ中序,後序,先序を表す.
import java.util.Scanner;
public class {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc=new Scanner(System.in);
String mid=sc.next();
String back=sc.next();
makeTree(mid,back);
}
//
public static void makeTree(String mid,String back){
char root=back.charAt(back.length()-1);//
System.out.print(root);
//
int rootInMid=mid.indexOf(root);
//
if(rootInMid>0){
// , ,rootInMid
makeTree(mid.substring(0,rootInMid),back.substring(0,rootInMid));
}
//
if(rootInMid<mid.length()-1){
makeTree(mid.substring(rootInMid+1),back.substring(rootInMid,back.length()-1));
}
}
}