既知のツリーの前の順序、中の順序の遍歴、後の順序の遍歴を求めて、javaは実現します
1842 ワード
思想を簡単に紹介して、まず前序を見て、前序が遍歴した最初のノードは、この木の根です.中順でそのルートの位置を見つけてindexとし、中順遍歴集合ではindexの前にあるルートに属する左サブツリー、indexの後にあるルートに属する右サブツリーである.そして,左右のサブ数に対して,このプロシージャを遍歴的に呼び出すと,ツリー構造を復元することができる.その後の後序遍歴も問題ではありません.
public class M {
public static class Tree{
public int value;
public Tree left;
public Tree right;
public Tree(int value) {
this.value=value;
}
}
public static void main(String[] args){
int[]preOrder={1,2,4,5,3,6,7};
int[]midOrder={4,2,5,1,6,3,7};
getBehindOrder(preOrder, midOrder);
}
public static void getBehindOrder(int[]pre,int[]mid){
if (pre==null||mid==null||pre.length!=mid.length) {
return;
}
Tree root=buildTree(pre, mid);
behindOrder(root);
}
public static void behindOrder(Tree root){//
if (root==null) {
return;
}
if (root.left!=null) {
behindOrder(root.left);
}
if (root.right!=null) {
behindOrder(root.right);
}
System.out.print(root.value+" ");
}
public static Tree buildTree(int[]preOrder,int[]midOrder){// ,
int value=preOrder[0];
int length=preOrder.length;
Tree root=new Tree(value);
root.left=root.right=null;
if (preOrder.length==1) {
return root;
}
int index=0;
while(midOrder[index]!=value)
index++;// index==length-1
if (index>0) {
// ,
int[]leftSubPreOrder=new int[index];
for(int i=0;i0){
int[]rightSubMidOrder=new int[length-index-1];
for(int i=0;i