ツリーの中シーケンスと後シーケンスで前シーケンスを取得

二叉木の遍歴方式でよく見られる3つは,先順遍歴(ABC),中順遍歴(BAC),後順遍歴(BCA)である.
先行パス:
二叉木が空であれば、空操作;それ以外の場合:

ルートノードにアクセスします.

左サブツリーを順に遍歴する.

右サブツリーを順に巡回します.

中間パス:
二叉木が空であれば、空操作;それ以外の場合:

中序は左サブツリーを遍歴する.

ルートノードにアクセスします.

では、右サブツリーを順に巡回します.

後の順序:
二叉木が空であれば、空操作;それ以外の場合:

後に左サブツリーを巡る.

後順に右サブツリーを遍歴する.

はルートノードにアクセスします.

遍歴シーケンスに基づいて二叉木を決定することを学習したとき、二叉木の先中または中後遍歴シーケンスによって唯一一本の二叉木を決定することができることが分かった.
アルゴリズムの説明に従ってjavaコードを使用して、中の後にシーケンスを巡回して、先のシーケンスのシーケンスを巡回するコードを取得します.

 1 package learn.normalcode;
 2 
 3 import java.util.ArrayList;
 4 
 5 public class BlankD {
 6     public static ArrayList ansList = new ArrayList<>(11);
 7     //                     
 8     public static void getAns(String middle, String back) {
 9         //               
10         int backLength = back.length(), middleLength = middle.length();
11         char c = '#';
12         if (backLength > 0) {
13             c = back.charAt(backLength - 1);
14             ansList.add(c);
15 
16             //  /              /    
17             int indexOfRoot = middle.indexOf(c);
18             getAns(middle.substring(0, indexOfRoot), back.substring(0, indexOfRoot));
19             getAns(middle.substring(indexOfRoot + 1, middleLength), back.substring(indexOfRoot, backLength - 1));
20         }
21         return;
22 
23     }
24     public static void main(String[] args) {
25         String middle = "SMBDCEAFHG", back = "MSDECBHGFA";
26         getAns(middle, back);
27         System.out.println(ansList);
28 
29         ansList.clear();
30         middle = "DCBA";
31         back = "DCBA";
32         getAns(middle, back);
33         System.out.println(ansList);
34 
35         ansList.clear();
36         middle = "SMBDCEA";
37         back = "MSDECBA";
38         getAns(middle, back);
39         System.out.println(ansList);
40     }
41 }

 
転載先:https://www.cnblogs.com/orzt/p/11529865.html