大家好，我是小夏，我來(lái)為大家解答以上問(wèn)題。二叉樹遍歷代碼，二叉樹遍歷很多人還不知道，現(xiàn)在讓我們一起來(lái)看看吧！

1、1．遍歷方案

2、 從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作：

3、 （1）訪問(wèn)結(jié)點(diǎn)本身(N)，

4、 （2）遍歷該結(jié)點(diǎn)的左子樹(L)，

5、 （3）遍歷該結(jié)點(diǎn)的右子樹(R)。

6、以上三種操作有六種執(zhí)行次序：

7、 NLR、LNR、LRN、NRL、RNL、RLN。

8、 注意：

9、 前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序。

10、2．三種遍歷的命名

11、 根據(jù)訪問(wèn)結(jié)點(diǎn)操作發(fā)生位置命名：

12、 ① NLR：前序遍歷(PreorderTraversal亦稱(先序遍歷))

13、 ——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之前。

14、 ② LNR：中序遍歷(InorderTraversal)

15、 ——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之中(間)。

16、 ③ LRN：后序遍歷(PostorderTraversal)

17、 ——訪問(wèn)結(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹之后。

18、 注意：

19、 由于被訪問(wèn)的結(jié)點(diǎn)必是某子樹的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為先根遍歷、中根遍歷和后根遍歷。

20、遍歷算法

21、1．中序遍歷的遞歸算法定義：

22、 若二叉樹非空，則依次執(zhí)行如下操作：

23、 (1)遍歷左子樹；

24、 (2)訪問(wèn)根結(jié)點(diǎn)；

25、 (3)遍歷右子樹。

26、2．先序遍歷的遞歸算法定義：

27、 若二叉樹非空，則依次執(zhí)行如下操作：

28、 (1) 訪問(wèn)根結(jié)點(diǎn)；

29、 (2) 遍歷左子樹；

30、 (3) 遍歷右子樹。

31、3．后序遍歷得遞歸算法定義：

32、 若二叉樹非空，則依次執(zhí)行如下操作：

33、 (1)遍歷左子樹；

34、 (2)遍歷右子樹；

35、 (3)訪問(wèn)根結(jié)點(diǎn)。

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