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