已知前序与中序的字符序列，输出后序序列。
后序序列为：左子树，右子树，根
第一种 利用一个索引，从最大索引值写入，依此递减写入右子树和左子树，循环利用递归实现。不使用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 <= </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 < mid.length && 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 < mid.length - 1，当相等的时候，表示没有右子树</code>
<code> </code><code>if</code> <code>(j < 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 < 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>0，当相等的时候，表示没有左子树</code>
<code> </code><code>if</code> <code>(j > </code><code>0</code><code>) {</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>m = </code><code>0</code><code>; m < 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<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 < 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
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)