遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有結點，使每一個結點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個結點轉換成為一個線性序列來表示。

設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹， 則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為后根次序遍歷）。

先序遍歷

首先訪問根，再先序遍歷左（右）子樹，最后先序遍歷右（左）子樹，C語言代碼如下：

1 2 3 4 5 6 7

void?XXBL(tree?*root){ ????//DoSomethingwithroot ????if(root->lchild!=NULL) ????????XXBL(root->lchild); ????if(root->rchild!=NULL) ????????XXBL(root->rchild); }

中序遍歷

首先中序遍歷左（右）子樹，再訪問根，最后中序遍歷右（左）子樹，C語言代碼如下

1 2 3 4 5 6 7 8

void?ZXBL(tree?*root) { ????if(root->lchild!=NULL) ????????ZXBL(root->lchild); ????????//Do?something?with?root ????if(root->rchild!=NULL) ????????ZXBL(root->rchild); }

后序遍歷

首先后序遍歷左（右）子樹，再后序遍歷右（左）子樹，最后訪問根，C語言代碼如下

1 2 3 4 5 6 7

void?HXBL(tree?*root){ ????if(root->lchild!=NULL) ????????HXBL(root->lchild); ????if(root->rchild!=NULL) ????????HXBL(root->rchild); ????????//Do?something?with?root }

層次遍歷

即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往后的層次越低）（兩個子女的級別相同）

?

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

?

我們首先找到根結點：一定是先序遍歷序列的第一個元素：1

然后，在中序序列尋找根，把中序序列分為兩個序列左子樹4，7，2和右子樹5，3，8，6

把先序序列也分為兩個：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?左子樹2，4，7和右子樹3，5，6，8

對左右重復同樣的過程：

先看左子樹：先序序列4，7，2，說明4一定是左子樹的根

把2，4，7分為2和7兩個序列，再重復過程，左邊確定完畢。

右子樹同樣：中序序列為5，3，8，6，先序序列為：3，5，6，8

取先序頭，3.一定是根

把中序序列分為? ? ?5和8，6兩個序列

對應的先序序列為 5和6，8兩個序列

?

然后確定了5是3的左孩子

對于先序序列6，8和中序序列8，6

還是先取先序的頭，6

?

現在只有8，中序序列8在左邊，是左孩子。

結束。

我們總結一下這種方法的過程：

1、根據先序序列確定當前樹的根（第一個元素）。

2、在中序序列中找到根，并以根為分界分為兩個序列。

3、這樣，確定了左子樹元素個數，把先序序列也分為兩個。

對左右子樹（對應的序列）重復相同的過程。

?

我們把思路用代碼實現：

# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution:# 返回構造的TreeNode根節點def reConstructBinaryTree(self, pre, tin):# write code here/#pre-先序數組 tin->中序數組if len(pre) == 0:return Noneroot = TreeNode(pre[0])//第一個元素為根pos = tin.index(pre[0])//劃分左右子樹root.left = self.reConstructBinaryTree( pre[1:1+pos], tin[:pos])root.right = self.reConstructBinaryTree( pre[pos+1:], tin[pos+1:])return root

輸入某二叉樹的后序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字

?

思路是類似的，只是我們確定根的時候，取后序序列的最后一個元素即可。

?

輸入某二叉樹的后序遍歷和先序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字

?

我們直白的表述一下，前序是中左右，后序是左右中。

所以，我們憑先序和后序序列其實是無法判斷根的孩子到底是左孩子還是右孩子。

比如先序序列1，5，后序序列是5，1

我們只知道1是這棵樹的根，但是我們不知道5是1的左孩子還是右孩子。

我們的中序序列是左中右，才可以明確的劃分出左右子樹，而先序后序不可以。

?

綜上，只有，只含葉子結點或者同時有左右孩子的結點的樹，才可以被先序序列后序序列確定唯一一棵樹。

最后不斷劃分先序和后序序列完成重建。

總結

以上是生活随笔為你收集整理的先序中序后序两两结合重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。