Java已知二叉樹的中序後序求先序序列

已經中序，後序，求先序。

先序的順序為：先根節點，後左子樹，後右子樹。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

<code>package</code> <code>whut.tree;</code>

<code>//利用java api來進行周遊</code>

<code>////已知二叉樹後序和中序，求先序</code>

<code>public</code> <code>class</code> <code>MiddleAfterTree {</code>

<code>    </code><code>//全局變量存放後序序列</code>

<code>    </code><code>//先寫根，後寫左子樹，最後寫右子樹</code>

<code>    </code><code>public</code> <code>static</code> <code>String res = </code><code>""</code><code>;</code>

<code>    </code><code>//兩個字元串是否包含了相同的字元</code>

<code>    </code><code>public</code> <code>static</code> <code>boolean</code> <code>StringEquals(String a1, String a2) {</code>

<code>        </code><code>boolean</code> <code>state = </code><code>true</code><code>;</code>

<code>        </code><code>if</code> <code>(a1.length() != a2.length()) {</code>

<code>            </code><code>state = </code><code>false</code><code>;</code>

<code>        </code><code>}</code>

<code>        </code><code>if</code> <code>(a1.length() == a2.length()) {</code>

<code>            </code><code>for</code> <code>(</code><code>int</code> <code>i = </code><code>0</code><code>; i &lt; a1.length(); i++) {</code>

<code>                </code><code>if</code> <code>(a2.indexOf(a1.charAt(i)) == -</code><code>1</code><code>)</code>

<code>                    </code><code>state = </code><code>false</code><code>;</code>

<code>            </code><code>}</code>

<code>        </code><code>return</code> <code>state;</code>

<code>    </code><code>}</code>

<code>    </code><code>//進行周遊輸出</code>

<code>    </code><code>//參數依此為中序序列，後序序列</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>cal_tree(String smid, String slast) {</code>

<code>        </code><code>boolean</code> <code>state = StringEquals(smid, slast);</code>

<code>        </code><code>if</code> <code>(state == </code><code>false</code><code>)</code>

<code>            </code><code>return</code><code>;</code>

<code>        </code><code>if</code> <code>(smid.length() == </code><code>0</code><code>)</code>

<code>        </code><code>//每次添加都是添加中序的字元，當中序字元串長度為1的時候，就傳回</code>

<code>        </code><code>if</code> <code>(smid.length() == </code><code>1</code><code>) {</code>

<code>            </code><code>res += smid;</code>

<code>        </code><code>//後序序列中最後一個就是根</code>

<code>        </code><code>char</code> <code>root = slast.charAt(slast.length()-</code><code>1</code><code>);</code>

<code>        </code><code>//擷取字元在中序序列總的位置</code>

<code>        </code><code>//mid代表的是索引</code>

<code>        </code><code>int</code> <code>mid = smid.indexOf(root);</code>

<code>        </code><code>//中序序列的左子樹</code>

<code>        </code><code>String c=smid.substring(</code><code>0</code><code>, mid);</code>

<code>        </code><code>//中序序列的右子樹</code>

<code>        </code><code>String d = smid.substring(mid+</code><code>1</code><code>);</code>

<code>        </code><code>//寫入根</code>

<code>        </code><code>res += String.valueOf(root);</code>

<code>        </code><code>//中序左子樹，後序左子樹</code>

<code>        </code><code>cal_tree(c,slast.substring(</code><code>0</code><code>, c.length()));</code>

<code>        </code><code>//中序右子樹，後序右子樹,注意這裡後序的右子樹要最大為slast.length()-1</code>

<code>        </code><code>cal_tree(d,slast.substring(c.length(),slast.length()-</code><code>1</code><code>));</code>

<code>        </code><code>return</code><code>;</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] agrs) {</code>

<code>        </code><code>//cal_tree("ADEFGHMZ","AEFDHZMG");=GDAFEMHZ</code>

<code>        </code><code>//cal_tree("CDBEAGF","DCEBGFA");=ABCDEFG</code>

<code>        </code><code>String s1 = </code><code>"ADEFGHMZ"</code><code>;</code>

<code>        </code><code>String s2 = </code><code>"AEFDHZMG"</code><code>;</code>

<code>        </code><code>cal_tree(s1, s2);</code>

<code>        </code><code>if</code> <code>(res.length() != s1.length())</code>

<code>        </code><code>{</code>

<code>            </code><code>System.out.println(</code><code>"wrong tree list!"</code><code>);</code>

<code>        </code><code>else</code> <code>{</code>

<code>            </code><code>System.out.println(res);</code>

<code>}</code>

<code></code>

本文轉自 zhao_xiao_long 51CTO部落格，原文連結:http://blog.51cto.com/computerdragon/1305991