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

已知前序與中序的字元序列，輸出後序序列。

後序序列為：左子樹，右子樹，根

第一種 利用一個索引，從最大索引值寫入，依此遞減寫入右子樹和左子樹，循環利用遞歸實作。不使用String類的api

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

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

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

<code>public</code> <code>class</code> <code>BeforeMiddleTree {</code>

<code>                                           </code> 

<code>    </code><code>// i:表示要插入後序序列的位置對于生成的後序序列，應該從最後位置開始寫，</code>

<code>    </code><code>//從索引最大值遞減依此先寫入根，然後寫入右子樹，最後寫左子樹</code>

<code>    </code><code>public</code> <code>static</code> <code>int</code> <code>i = </code><code>0</code><code>;</code>

<code>    </code><code>public</code> <code>void</code> <code>getLast(</code><code>char</code><code>[] pre, </code><code>char</code><code>[] mid, </code><code>char</code><code>[] last)</code>

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

<code>        </code><code>// 如果序列的長度小于等于1，将該序列中的元素插入last序列，然後傳回</code>

<code>        </code><code>if</code> <code>(pre.length &lt;= </code><code>1</code><code>) {</code>

<code>            </code><code>last[i] = pre[</code><code>0</code><code>];</code>

<code>            </code><code>i--;</code>

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

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

<code>        </code><code>//如果序列長度大于1，則将二叉樹的根插入last序列，然後将序列分成兩個，分别進行遞歸</code>

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

<code>            </code><code>//添加元素</code>

<code>            </code><code>int</code> <code>j = </code><code>0</code><code>;</code>

<code>            </code><code>// 在mid中找到根元素，從此處将mid分成兩部分</code>

<code>            </code><code>for</code> <code>(; j &lt; mid.length &amp;&amp; pre[</code><code>0</code><code>] != mid[j]; j++);</code>

<code>            </code><code>//循環結束後j為根元素在mid中的索引位置</code>

<code>            </code><code>//兩部分以mid分開</code>

<code>            </code><code>char</code><code>[] newmid1 = </code><code>new</code> <code>char</code><code>[j];</code><code>//j-1</code>

<code>            </code><code>char</code><code>[] newmid2 = </code><code>new</code> <code>char</code><code>[mid.length - j - </code><code>1</code><code>];</code>

<code>            </code><code>char</code><code>[] newpre1 = </code><code>new</code> <code>char</code><code>[j];</code>

<code>            </code><code>char</code><code>[] newpre2 = </code><code>new</code> <code>char</code><code>[mid.length - j - </code><code>1</code><code>];</code>

<code>            </code><code>// 求右子樹的後序序列</code>

<code>            </code><code>//必須要保證j &lt; mid.length - 1，當相等的時候，表示沒有右子樹</code>

<code>            </code><code>if</code> <code>(j &lt; mid.length - </code><code>1</code><code>)</code>

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

<code>                </code><code>//初始化右子樹</code>

<code>                </code><code>for</code> <code>(</code><code>int</code> <code>n = </code><code>0</code><code>; n &lt; mid.length - j - </code><code>1</code><code>; n++) {</code>

<code>                    </code><code>newmid2[n] = mid[n + j + </code><code>1</code><code>];</code>

<code>                    </code><code>newpre2[n] = pre[n + j + </code><code>1</code><code>];</code>

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

<code>                </code><code>getLast(newpre2, newmid2, last);</code>

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

<code>            </code><code>// 求左子樹的後序序列</code>

<code>            </code><code>//必須要保證j&gt;0，當相等的時候，表示沒有左子樹</code>

<code>            </code><code>if</code> <code>(j &gt; </code><code>0</code><code>) {</code>

<code>                </code><code>for</code> <code>(</code><code>int</code> <code>m = </code><code>0</code><code>; m &lt; j; m++) {</code>

<code>                    </code><code>newmid1[m] = mid[m];</code>

<code>                    </code><code>newpre1[m] = pre[m + </code><code>1</code><code>];</code>

<code>                </code><code>getLast(newpre1, newmid1, last);</code>

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

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

<code>        </code><code>BeforeMiddleTree st = </code><code>new</code> <code>BeforeMiddleTree();</code>

<code>        </code><code>char</code><code>[] pre = {</code><code>'A'</code><code>,</code><code>'B'</code><code>,</code><code>'C'</code><code>,</code><code>'D'</code><code>,</code><code>'E'</code><code>,</code><code>'F'</code><code>,</code><code>'G'</code><code>};</code>

<code>        </code><code>char</code><code>[] mid = {</code><code>'C'</code><code>,</code><code>'D'</code><code>,</code><code>'B'</code><code>,</code><code>'E'</code><code>,</code><code>'A'</code><code>,</code><code>'G'</code><code>,</code><code>'F'</code><code>};</code>

<code>        </code><code>char</code><code>[] last = </code><code>new</code> <code>char</code><code>[pre.length];</code>

<code>        </code><code>i = mid.length-</code><code>1</code><code>;</code>

<code>        </code><code>st.getLast(pre, mid,last);</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>j=</code><code>0</code><code>;j&lt;last.length;j++)</code>

<code>            </code><code>System.out.print(last[j]);</code>

<code>}</code>

第二種，利用String的api，正向的進行周遊，先寫左子樹，後寫右子樹，最後寫根，循環利用遞歸實作。

63

64

65

66

67

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

<code>public</code> <code>class</code> <code>BeforeMiddleTree2 {</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>if</code> <code>(a1.length() == a2.length())</code>

<code>        </code><code>{</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>return</code> <code>state;</code>

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

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>cal_tree(String sa, String sb) {</code>

<code>        </code><code>boolean</code> <code>state = StringEquals(sa, sb);</code>

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

<code>        </code><code>//當是空字元串的時候</code>

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

<code>        </code><code>//當sa==sb==1的時候，則就添加</code>

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

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

<code>        </code><code>//擷取先序序列的第一個字元，作為根節點來劃分中序序列</code>

<code>        </code><code>char</code> <code>root = sa.charAt(</code><code>0</code><code>);</code>

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

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

<code>        </code><code>//拆分中序序列</code>

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

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

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

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

<code>        </code><code>//下面就是先左子樹，後右子樹，最後根節點。即後序順序</code>

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

<code>        </code><code>cal_tree(sa.substring(</code><code>1</code><code>, c.length() + </code><code>1</code><code>), c);</code>

<code>        </code><code>//先序右子樹，中序右子樹</code>

<code>        </code><code>cal_tree(sa.substring(</code><code>1</code> <code>+ c.length()), d);</code>

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

<code>        </code><code>res += String.valueOf(root);</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("DBACEGF","ABCDEFG");</code>

<code>        </code><code>//cal_tree("ABCD","BDAC");</code>

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

<code>        </code><code>String s2 = </code><code>"CDBEAGF"</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>System.out.println(</code><code>"wrong tree list!"</code><code>);</code>

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

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