二叉樹前序中序后序口訣（二叉樹前序中序后序）

大家好，我是小夏，我來為大家解答以上問題。二叉樹前序中序后序口訣，二叉樹前序中序后序很多人還不知道，現在讓我們一起來看看吧！

1、對于例題的后序遍歷的答案是，gdbehfca.

2、解答過程：

3、1）定義解釋：樹的遍歷的三種情況，是根據左子樹、右子樹、根這3者的不同訪問次序來定義的。根左右（根先訪問），則為先序遍歷；左根右，則為中序遍歷；左右根，則為后序遍歷。

4、2）已知先序和中序遍歷結果，求樹的結構和后序遍歷結果：

5、先序遍歷結果給我們帶來的信息是，根在哪。

6、中序遍歷結果給我們帶來的信息是，左、右子樹在哪。

7、所以樹結構的還原過程是，根據先序找到一個根；然后根據這個根和中序遍歷結果找到它的相應的左、右子樹；依次往下。

8、對于例題而言：

9、先序遍歷的第一個節點是a，則說明a是整棵樹的根。然后在中序遍歷結果中，由a斷開，找到a的左子樹和右子樹，即dgb是a的左子樹中的節點集合，echf是a的右子樹集合。（dgb）a(echf)

10、然后開始遞歸求解：還原（dgb）和(echf)

11、（dgb）的先序遍歷結果是：bdg（從題目中的先序遍歷中，截取）

12、（dgb）的中序遍歷結果是：dgb（從題目中的中序遍歷中，截取）

13、所以b為根，（dg）為左子樹，右子樹為空。即（dgb）= (dg)b

14、同理：（echf）=（e）c（hf）

15、第3次遞歸：（dg）= d(g);(hf)= (h)f

16、最后得到的結果就是：

17、（（d(g)）b）a （(e)c((h)f)）

18、(在這種表示中，括號的層數代表在樹中的層數)

19、 a

20、 b c

21、 d e f

22、 g h

23、根據這個樹，后序遍歷為先左、右，最后根

24、先訪問（dgb） (echf) 然后是a

25、（dgb）這棵樹的后序遍歷為gdb

26、（echf）這棵樹的后序遍歷為ehfc

27、所以最后結果為gdb ehfc a

本文到此講解完畢了，希望對大家有幫助。