采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的先序遍歷，為什么是先序呢？這是因?yàn)閳D的深度優(yōu)先遍歷算法首先訪問(wèn)節(jié)點(diǎn)，然后訪問(wèn)其相鄰點(diǎn)。它類(lèi)似于二叉樹(shù)的順序遍歷，首先訪問(wèn)子樹(shù)的根節(jié)點(diǎn)，然后訪問(wèn)子樹(shù)的子

采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的先序遍歷，為什么是先序呢？

這是因?yàn)閳D的深度優(yōu)先遍歷算法首先訪問(wèn)節(jié)點(diǎn)，然后訪問(wèn)其相鄰點(diǎn)。它類(lèi)似于二叉樹(shù)的順序遍歷，首先訪問(wèn)子樹(shù)的根節(jié)點(diǎn)，然后訪問(wèn)子樹(shù)的子節(jié)點(diǎn)（鄰接點(diǎn)）。圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的層次遍歷。

二叉樹(shù)先序遍歷的非遞歸算法具體實(shí)現(xiàn)？

二叉樹(shù)可以通過(guò)后序和中序遍歷進(jìn)行恢復(fù)，以方便其他樹(shù)的操作。在這里，我們先恢復(fù)二叉樹(shù)，然后進(jìn)行預(yù)序遍歷，得到預(yù)序遍歷的結(jié)果。我們同意恢復(fù)樹(shù)的函數(shù)稱(chēng)為restoretree（）?；謴?fù)左右子樹(shù)時(shí)，需要計(jì)算它們的位置，即H1、H2和Z1、Z2的值需要重新計(jì)算，并在更新后傳遞給restoretree（）函數(shù)。以左子樹(shù)的構(gòu)造為例，左子樹(shù)的第一個(gè)元素下標(biāo)為Z1，最后一個(gè)元素下標(biāo)為I-1，H1的對(duì)應(yīng)值為H1，H2的值為H1（I-Z1-1），即H1的當(dāng)前位置向前移動(dòng)I-Z1-1長(zhǎng)度。R代碼實(shí)現(xiàn)以實(shí)現(xiàn)前面提到的字母序列為例，因?yàn)楫?dāng)代碼恢復(fù)樹(shù)時(shí)，它首先恢復(fù)根節(jié)點(diǎn)，然后訪問(wèn)樹(shù)的左、右子樹(shù)，所以恢復(fù)過(guò)程也相當(dāng)于根優(yōu)先遍歷過(guò)程。如果只想先遍歷找到根，就不能構(gòu)建樹(shù)。我們可以刪除根優(yōu)先遍歷函數(shù)并簡(jiǎn)化其他一些語(yǔ)句，這兩段代碼的結(jié)果是相同的。以下是示例輸入和輸出。這里的代碼擴(kuò)展添加了一段代碼，它使用前序遍歷和中序遍歷來(lái)恢復(fù)二叉樹(shù)并進(jìn)行后序遍歷。R代碼可以像以前一樣簡(jiǎn)化。簡(jiǎn)化后，無(wú)需建樹(shù)即可遍歷。首先了解概念：前序遍歷：訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之前。中間順序遍歷：訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)時(shí)。后序遍歷：訪問(wèn)根節(jié)點(diǎn)的操作發(fā)生在遍歷其左右子樹(shù)之后。例：遍歷dbcefgha后，為了遍歷edcbahfg，先查找前序遍歷（聯(lián)機(jī)示例）解決方案：遍歷dbcefgha后，先看a是總根節(jié)點(diǎn)，然后按順序遍歷edcbahfg找到a的位置，然后edcb在a的左分支，HFG在a的右分支。重復(fù)前兩步，查找從最后一個(gè)位置的對(duì)應(yīng)點(diǎn)經(jīng)過(guò)遍歷，找到左、右分支依次遍歷，最后得到aecdbhgf，然后自己驗(yàn)證。深度和廣度是常見(jiàn)的樹(shù)木。深度遍歷：從樹(shù)的根開(kāi)始掃描，從頂層開(kāi)始掃描，從一層最左邊（或最右邊）的節(jié)點(diǎn)掃描到底層，直到下層沒(méi)有節(jié)點(diǎn)為止。此時(shí)，將掃描所有最左側(cè)（右側(cè)）的節(jié)點(diǎn)。從樹(shù)的頂部后退一步，查看層旁邊是否有兄弟節(jié)點(diǎn)。如果有，從最左邊（右邊）掃描。這是一個(gè)遞歸概念，使用此方法遍歷整個(gè)樹(shù)。寬度遍歷：從樹(shù)的根開(kāi)始掃描，掃描第一層的所有節(jié)點(diǎn)，掃描第二層的所有節(jié)點(diǎn)，掃描底部節(jié)點(diǎn)。