二叉樹的確定-創(chuàng)新互聯(lián)

二叉樹的四種遍歷方法

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的思禮網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

1. 先序遍歷（根左右）：可以想象為，一個(gè)小人以一棵二叉樹根節(jié)點(diǎn)為起點(diǎn)，沿著二叉樹外沿，逆時(shí)針走一圈回到根節(jié)點(diǎn)，路上遇到的元素順序，就是先序遍歷的結(jié)果。

遍歷結(jié)果：A B D H I E J C F K G

動(dòng)圖演示

2. 中序遍歷（左根右）：可以看成，二叉樹每個(gè)節(jié)點(diǎn)，垂直方向投影下來（可以理解為每個(gè)節(jié)點(diǎn)從最左邊開始垂直掉到地上），然后從左往右數(shù)，得出的結(jié)果便是中序遍歷的結(jié)果。

遍歷結(jié)果：H D I B E J A F K C G

動(dòng)圖演示

3.后序遍歷（根左右）：按照先序遍歷的路徑把一串葡萄剪成一個(gè)一個(gè)的，遇到能剪下來的就把它剪下來。

遍歷結(jié)果：H I D J E B K F G C A

動(dòng)圖演示

4. 層次遍歷：從上到下 從左到右

遍歷結(jié)果：A B C D E F G H I J K

圖片展示

確定二叉樹的兩種方式：

（1）先序+中序

（2）后序+中序

現(xiàn)假設(shè)存在一棵二叉樹，其先序、中序和后序遍歷的結(jié)果如下：

先序遍歷：ABDEGCFH

中序遍歷：DBGEACFH

后序遍歷：DGEBHFCA

在介紹如何利用遍歷方式唯一確定一棵二叉樹之前，需要重點(diǎn)強(qiáng)調(diào)：無論利用什么方式來唯一確定一棵二叉樹，其本質(zhì)都是通過兩種遍歷結(jié)果來不斷遞歸地確定根結(jié)點(diǎn)和劃分左右子樹的過程！

先序遍歷+中序遍歷

先序遍歷+中序遍歷的要義是：利用先序遍歷確定根結(jié)點(diǎn)，再利用中序遍歷劃分左右子樹

步驟一：分析整棵二叉樹

對于先序遍歷，其遍歷方式是一個(gè)結(jié)點(diǎn)需要先訪問自己，再訪問其左子樹，接著才是其右子樹，故先序遍歷結(jié)果中的第一個(gè)元素一定是根結(jié)點(diǎn)，根據(jù)上述先序遍歷可以知道是A。 接著利用得到的A，在中序遍歷結(jié)果中找到A所在的位置，然后便可以將A左側(cè)的所有元素歸屬到根結(jié)點(diǎn)的左子樹，A右側(cè)的所有元素歸屬到根結(jié)點(diǎn)的右子樹，而之所以這樣做，是因?yàn)閷τ谥行虮闅v，其遍歷方式是一個(gè)結(jié)點(diǎn)先訪問其左子樹，再訪問自己，接著才是其右子樹，所以A前面的元素一定來自A的左子樹，A后面的一定來自A的右子樹。 根據(jù)上述分析，可以先畫出如下圖片：

步驟二：分析A的左子樹，即包含DBGE的這棵二叉樹。

這時(shí)可以把包含DBGE這四個(gè)元素的先序遍歷部分和中序遍歷部分單獨(dú)提取出來：

部分先序遍歷：BDEG

部分中序遍歷：DBGE

現(xiàn)在單獨(dú)觀察包含DBGE的這棵樹和它對應(yīng)的部分先序遍歷、部分中序遍歷，可以看到接下來的分析方式又與步驟一是一模一樣的了，即先確定這個(gè)樹（僅包含DBGE的這棵樹）的根結(jié)點(diǎn)，再確定它的兩棵子樹，現(xiàn)在根結(jié)點(diǎn)是部分先序遍歷的第一個(gè)元素，即B，根據(jù)B，在部分中序遍歷中劃分左右子樹，即左子樹包含D，右子樹包含GE，得到的圖片如下：

可以看到這時(shí)B的左子樹只有一個(gè)結(jié)點(diǎn)，所以可以認(rèn)為已經(jīng)確定好了，那么就只需要按照步驟一的方式對B的右子樹進(jìn)行同樣的分析即可。

步驟三：分析A的右子樹，即包含CFH的這顆二叉樹。

這時(shí)可以把包含CFH這三個(gè)元素的先序遍歷部分和中序遍歷部分單獨(dú)提取出來：

部分先序遍歷：CFH

部分中序遍歷：CFH

現(xiàn)在單獨(dú)觀察包含CFH的這棵樹和它對應(yīng)的部分先序遍歷、部分中序遍歷，可以看到接下來的分析方式又與步驟一是一模一樣的了，即先確定這個(gè)樹（僅包含CFH的這棵樹）的根結(jié)點(diǎn)，再確定它的兩棵子樹，現(xiàn)在根結(jié)點(diǎn)是部分先序遍歷的第一個(gè)元素，即C，根據(jù)C，在部分中序遍歷中劃分左右子樹，即左子樹為空，右子樹包含F(xiàn)H，得到的圖片如下：

可以看到這時(shí)C的左子樹沒有一個(gè)結(jié)點(diǎn)，所以可以認(rèn)為已經(jīng)確定好了，那么就只需要按照步驟一的方式對C的右子樹進(jìn)行同樣的分析即可。

步驟四：得到一顆完整的二叉樹。

根據(jù)上述步驟，完整地走一遍流程，便可以得到如下的一棵二叉樹：

后序遍歷+中序遍歷

后序遍歷+中序遍歷的要義是：利用后序遍歷確定根結(jié)點(diǎn)，再利用中序遍歷劃分左右子樹\n\n其實(shí)后序遍歷+中序遍歷唯一確定一棵二叉樹的方法與先序遍歷+中序遍歷唯一確定一棵二叉樹的方法本質(zhì)上是一樣的，唯一不同在于，利用后序遍歷+中序遍歷唯一確定一棵二叉樹的方法在每次確定根結(jié)點(diǎn)時(shí)，需要對后序遍歷的結(jié)果從后往前看，比如對于上述例子中的后序遍歷：DGEBHFCA，第一步確定根結(jié)點(diǎn)時(shí)，需要取最后一個(gè)元素，因?yàn)楹笮虮闅v是最后才訪問根結(jié)點(diǎn)，所以此時(shí)根結(jié)點(diǎn)的位置就是最后一個(gè)，而其他步驟就與先序遍歷+中序遍歷唯一確定一棵二叉樹的方法是一樣的。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁題目：二叉樹的確定-創(chuàng)新互聯(lián)
URL地址：http://muchs.cn/article12/csjhgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、企業(yè)網(wǎng)站制作、企業(yè)建站、App開發(fā)、網(wǎng)站內(nèi)鏈、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)