java二叉樹後序遍歷

A. 什麼是二叉樹先序，中序，後序遍歷

先序：是二叉樹遍歷中的一種，即先訪問根結點，然後遍歷左子樹，後遍歷右子樹。遍歷左、右子樹時，先訪問根結點，後遍歷左子樹，後遍歷右子樹，如果二叉樹為空則返回。

中序：是二叉樹遍歷中的一種，即乎鏈搏先遍歷左子樹，後訪問根結點，然後喚李遍歷右子樹。若二叉樹為空則結束返回。

後序：是二叉樹遍歷中歲祥的一種，即先遍歷左子樹，後遍歷右子樹，然後訪問根結點，遍歷左、右子樹時，仍先遍歷左子樹，後遍歷右子樹，最後遍歷根結點。

(1)java二叉樹後序遍歷擴展閱讀：

當對一棵數學表達式樹進行中序，前序和後序遍歷時，就分別得到表達式的中綴、前綴和後綴形式。

如果已知前序遍歷和中序遍歷，就能確定後序遍歷，同樣如果已知中序遍歷和後序遍歷，就能確定前序遍歷，如果已知前序遍歷和後序遍歷，就能直到中序遍歷。

B. 二叉樹的先序,中序,後序遍歷是

前序遍歷就是先遍歷根節點，然後遍歷左節點，最後是右節點；

中序遍歷就是先遍歷左節點，然後遍歷中間的根節點，最後是右節點；

後序遍歷就是先遍歷左節點，然後遍歷是右節點，最後是中間的根節點。

二叉樹的這三種遍歷方法，是按照每顆子樹的根節點順序遍歷的。

(2)java二叉樹後序遍歷擴展閱讀：

例子：已知二叉樹的後序遍歷序列是dabec，中序遍歷序列是debac，它的前序遍歷序列是（cedba）

(1)中序遍歷：debac

後序遍歷：dabec

後序遍歷序列的最後一個結點是根結點，所以可知c為根結點。

中序遍歷序列的根結點在中間，其左邊是左子樹，右邊是右子樹。所以從中序遍歷序列中可看出，根結點c只有左子樹，沒有右子樹。

(2)中序遍歷：deba

後序遍歷：dabe

後序遍歷序列的最後一個結點是根結點，所以可知e為c的左子樹的根結點。

中序遍歷序列的根結點在中間，其左邊是左子樹，右邊是右子樹。所以從中序遍歷序列中可看出，根結點e的左子結點是d，右子樹是ba。

(3)中序遍歷：ba

後序遍歷：ab

由後序遍歷序列可知b為e的右子樹的根結點。由中序遍歷序列中可看出，a為根結點b的右子結點。

C. 先序遍歷和後序遍歷是什麼

1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

(3)java二叉樹後序遍歷擴展閱讀：

圖的遍歷演算法主要有兩種，

一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；

另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。

如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。

如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。

利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。

寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：

1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；

2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。

3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；

4、遍歷完所有的頂點而可以重復，即所謂「旅行推銷員問題」。

對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。

D. 二叉樹的java實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹 4.只有右子樹 5.左右子樹都存在 有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

• 前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

• 中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

• 後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：

E. 關於二叉樹的前序、中序、後序三種遍歷

二叉樹中遍歷分為三種：前序、中序、後序，是根據根節點的順序命名的。

例如下圖：

該圖中，A為根節點，B、C分別為左右節點。前序順序為ABC（根節點最先，然後是同級先左後右），中序順序為BAC（先左後根最後右），後序為BCA（先左後右最後根）。

運用整體和部分的思維，很容易就能分析這些遍歷方式，舉例說明中序遍歷的過程，如下表：

F. 二叉樹的後序遍歷是什麼意思

樹的後序遍歷是指先依次後序遍歷每棵子樹，然後訪問根結點。當樹用二叉樹表示法(也叫孩子兄弟表示法)存儲時，可以找到唯一的一棵二叉樹與之對應，我們稱這棵二叉樹為該樹對應的二叉樹。那麼根據這個法則可知，樹的後序遍歷序列等同於該樹對應的二叉樹的中序遍歷。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。

⑴訪問結點本身（N），

⑵遍歷該結點的左子樹（L），

⑶遍歷該結點的右子樹（R）。

以上三種操作有六種執行次序：

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

注意：

前三種次序與後三種次序對稱，故只討段野含論先左後右的前三種次序。

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上。

(6)java二叉樹後序遍歷擴展閱讀：

二叉樹前序訪問如下：

從根結點出發，則第一次到達結點A，故輸出A;

繼續向左訪問，第一次訪問結點B，故輸出B；

按照同樣規則，輸出D，輸出H；

當到達葉子結點H，返回到D，此時已經是第二次脊殲到達D，故不在輸出D，進而向D右子樹訪問，D右子樹不為空，則訪問至I，第一次到達I，則輸出I；

I為葉子結點，則返回到D，D左右子樹已經訪問完畢，則返回到B，進而到B右子樹，第一次到達E，故輸出E；

向E左子樹，故輸出J；

按照同樣的訪問規則，繼續輸出C、F、G。

二叉樹中序訪問如下：

從根結點出發，則第一次到達結點A，不輸出A，繼續向左訪問，第一次訪問結點B，不輸出B；繼續到達D，H；

到達H，H左子樹為空，則返回到H，此時第二次訪問H，故輸出H；

H右子樹為空，則返回至D，此時第二次到達D，故輸出D；

由D返回至B，第二次到達B，故輸出握笑B；

按照同樣規則繼續訪問，輸出J、E、A、F、C、G。