通过二叉树的中序序列和后序序列获取前序序列.pdf

通通过过⼆⼆叉叉树树的的中中序序序序列列和和后后序序序序列列获获取取前前序序序序列列

⼆叉树的遍历⽅式常见的三种是：先序遍历(ABC)、中序遍历(BAC)、后序遍历(BCA)

先序遍历：

若⼆叉树为空，空操作；否：

1.访问根结点;

2.先序遍历左⼦树；

3.先序遍历右⼦树。

中序遍历：

若⼆叉树为空，空操作；否：

1.中序遍历左⼦树；

2.访问根结点；

3.中序遍历右⼦树。

后序遍历：

若⼆叉树为空，空操作；否：

1.后序遍历左⼦树；

2.后序遍历右⼦树；

3.访问根结点。

在学习到根据遍历序列确定⼆叉树时，知道了：可以通过⼆叉树的先中或者中后遍历序列唯⼀确定⼀棵⼆叉树。

根据算法描述使⽤java码出依据中后遍历序列来获取先序遍历序列的代码：

1packagelearn.normalcode;

2

3importjava.util.ArrayList;

5publicclassBlankD{

6publicstaticArrayListCharacteransList=newArrayList(11);

7//通过⼆叉树的中序序列和后序序列获取前序序列

8publicstaticvoidgetAns(Stringmiddle,Stringback){

9//后序序列的最后⼀个结点为根结点

10intbackLength=back.length(),middleLength=middle.length();

11charc=#;

12if(backLength0){

13c=back.charAt(backLength-1);

1ansList.add(c);

15

16//从中/后序序列中分裂出左右⼦树的中/后序序列

17intindexOfRoot=middle.indexOf(c);

18getAns(middle.substring(0,indexOfRoot),back.substring(0,indexOfRoot));

19getAns(middle.substring(indexOfRoot+1,middleLength),back.substring(indexOfRoot,backLength-1));

20}

21return;

22

23}

2publicstaticvoidmain(String[]args){

25Stringmiddle=SMBDCEAFHG,back=MSDECBHGFA;

26getAns(middle,back);

27System.out.println(ansList);

28

29ansList.clear();

30middle=DCBA;

31back=DCBA;

32getAns(middle,back);

33System.out.println(ansList);

3

35ansList.clear();

36middle=SMBDCEA;

37back=MSDECBA;

38getAns(middle,back);

39System.out.println(ansList);

0}

1}