建站
咨詢
售后
建站咨詢
新聞中心
二叉樹的四種遍歷方法
成都創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的思禮網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！先序遍歷（根左右）：可以想象為，一個小人以一棵二叉樹根節(jié)點為起點，沿著二叉樹外沿，逆時針走一圈回到根節(jié)點，路上遇到的元素順序，就是先序遍歷的結(jié)果。
遍歷結(jié)果：A B D H I E J C F K G
動圖演示
中序遍歷（左根右）：可以看成，二叉樹每個節(jié)點，垂直方向投影下來（可以理解為每個節(jié)點從最左邊開始垂直掉到地上），然后從左往右數(shù)，得出的結(jié)果便是中序遍歷的結(jié)果。
遍歷結(jié)果：H D I B E J A F K C G
動圖演示
3.后序遍歷（根左右）：按照先序遍歷的路徑把一串葡萄剪成一個一個的，遇到能剪下來的就把它剪下來。
遍歷結(jié)果：H I D J E B K F G C A
動圖演示
4. 層次遍歷：從上到下 從左到右
遍歷結(jié)果：A B C D E F G H I J K
圖片展示
確定二叉樹的兩種方式：
（1）先序+中序
（2）后序+中序
現(xiàn)假設(shè)存在一棵二叉樹，其先序、中序和后序遍歷的結(jié)果如下：
先序遍歷：ABDEGCFH
中序遍歷：DBGEACFH
后序遍歷：DGEBHFCA
在介紹如何利用遍歷方式唯一確定一棵二叉樹之前，需要重點強調(diào)：無論利用什么方式來唯一確定一棵二叉樹，其本質(zhì)都是通過兩種遍歷結(jié)果來不斷遞歸地確定根結(jié)點和劃分左右子樹的過程！
先序遍歷+中序遍歷
先序遍歷+中序遍歷的要義是：利用先序遍歷確定根結(jié)點，再利用中序遍歷劃分左右子樹
步驟一：分析整棵二叉樹
對于先序遍歷，其遍歷方式是一個結(jié)點需要先訪問自己，再訪問其左子樹，接著才是其右子樹，故先序遍歷結(jié)果中的第一個元素一定是根結(jié)點，根據(jù)上述先序遍歷可以知道是A。 接著利用得到的A，在中序遍歷結(jié)果中找到A所在的位置，然后便可以將A左側(cè)的所有元素歸屬到根結(jié)點的左子樹，A右側(cè)的所有元素歸屬到根結(jié)點的右子樹，而之所以這樣做，是因為對于中序遍歷，其遍歷方式是一個結(jié)點先訪問其左子樹，再訪問自己，接著才是其右子樹，所以A前面的元素一定來自A的左子樹，A后面的一定來自A的右子樹。 根據(jù)上述分析，可以先畫出如下圖片：
步驟二：分析A的左子樹，即包含DBGE的這棵二叉樹。
這時可以把包含DBGE這四個元素的先序遍歷部分和中序遍歷部分單獨提取出來：
部分先序遍歷：BDEG
部分中序遍歷：DBGE
現(xiàn)在單獨觀察包含DBGE的這棵樹和它對應(yīng)的部分先序遍歷、部分中序遍歷，可以看到接下來的分析方式又與步驟一是一模一樣的了，即先確定這個樹（僅包含DBGE的這棵樹）的根結(jié)點，再確定它的兩棵子樹，現(xiàn)在根結(jié)點是部分先序遍歷的第一個元素，即B，根據(jù)B，在部分中序遍歷中劃分左右子樹，即左子樹包含D，右子樹包含GE，得到的圖片如下：
可以看到這時B的左子樹只有一個結(jié)點，所以可以認為已經(jīng)確定好了，那么就只需要按照步驟一的方式對B的右子樹進行同樣的分析即可。
步驟三：分析A的右子樹，即包含CFH的這顆二叉樹。
這時可以把包含CFH這三個元素的先序遍歷部分和中序遍歷部分單獨提取出來：
部分先序遍歷：CFH
部分中序遍歷：CFH
現(xiàn)在單獨觀察包含CFH的這棵樹和它對應(yīng)的部分先序遍歷、部分中序遍歷，可以看到接下來的分析方式又與步驟一是一模一樣的了，即先確定這個樹（僅包含CFH的這棵樹）的根結(jié)點，再確定它的兩棵子樹，現(xiàn)在根結(jié)點是部分先序遍歷的第一個元素，即C，根據(jù)C，在部分中序遍歷中劃分左右子樹，即左子樹為空，右子樹包含F(xiàn)H，得到的圖片如下：
可以看到這時C的左子樹沒有一個結(jié)點，所以可以認為已經(jīng)確定好了，那么就只需要按照步驟一的方式對C的右子樹進行同樣的分析即可。
步驟四：得到一顆完整的二叉樹。
根據(jù)上述步驟，完整地走一遍流程，便可以得到如下的一棵二叉樹：
后序遍歷+中序遍歷
后序遍歷+中序遍歷的要義是：利用后序遍歷確定根結(jié)點，再利用中序遍歷劃分左右子樹\n\n其實后序遍歷+中序遍歷唯一確定一棵二叉樹的方法與先序遍歷+中序遍歷唯一確定一棵二叉樹的方法本質(zhì)上是一樣的，唯一不同在于，利用后序遍歷+中序遍歷唯一確定一棵二叉樹的方法在每次確定根結(jié)點時，需要對后序遍歷的結(jié)果從后往前看，比如對于上述例子中的后序遍歷：DGEBHFCA，第一步確定根結(jié)點時，需要取最后一個元素，因為后序遍歷是最后才訪問根結(jié)點，所以此時根結(jié)點的位置就是最后一個，而其他步驟就與先序遍歷+中序遍歷唯一確定一棵二叉樹的方法是一樣的。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
網(wǎng)站題目：二叉樹的確定-創(chuàng)新互聯(lián)
當前地址：http://fisionsoft.com.cn/article/csjhgc.html
