與數(shù)組和鏈表不同，二叉樹(shù)有幾種遍歷方式。遍歷算法大致分為深度優(yōu)先和廣度優(yōu)先遍歷算法，這取決于算法實(shí)際如何工作。顧名思義，深度優(yōu)先在訪問(wèn)同級(jí)別兄弟之前先向二叉樹(shù)縱深訪問(wèn)，而廣度優(yōu)先是先訪問(wèn)同一級(jí)別中的所有節(jié)點(diǎn)然后再進(jìn)入下一級(jí)別，因此它也被稱(chēng)為級(jí)別順序遍歷。PreOrder和InOrder樹(shù)遍歷算法都是深度優(yōu)先的，預(yù)序和中序算法之間的唯一區(qū)別是訪問(wèn)二叉樹(shù)的根，左節(jié)點(diǎn)和右節(jié)點(diǎn)的順序。
InOrder遍歷算法首先訪問(wèn)左節(jié)點(diǎn)，然后是root節(jié)點(diǎn)，最后是右節(jié)點(diǎn)。這與首先訪問(wèn)根的預(yù)序遍歷不同。InOrder遍歷的一個(gè)重要特性是，如果給定的二叉樹(shù)是二叉搜索樹(shù)，它將按排序順序打印節(jié)點(diǎn)。
請(qǐng)記住，如果左子樹(shù)中的所有節(jié)點(diǎn)都低于root并且右子樹(shù)中的所有節(jié)點(diǎn)都大于root，則二叉樹(shù)稱(chēng)為二叉搜索樹(shù)。
在示例中，使用二叉搜索樹(shù)來(lái)演示InOrder樹(shù)遍歷以排序順序打印二叉樹(shù)的節(jié)點(diǎn)，并分享了這個(gè)問(wèn)題的遞歸和迭代解決方案。從面試的角度來(lái)看，這非常重要。即使遞歸解決方案更容易，占用更少的代碼行，并且更具可讀性，您也應(yīng)該知道如何在沒(méi)有Java遞歸的情況下遍歷二叉樹(shù)，以便在編程面試中做得更好。
Java中InOrder遍歷二叉樹(shù)-遞歸
由于二叉樹(shù)是遞歸數(shù)據(jù)結(jié)構(gòu)，因此遞歸是解決基于樹(shù)的問(wèn)題的最佳方法。以下是二叉樹(shù)InOrder遍歷的步驟：
訪問(wèn)左節(jié)點(diǎn)
訪問(wèn)root
訪問(wèn)右節(jié)點(diǎn)
要實(shí)現(xiàn)此算法，您可以使用InOrder遍歷編寫(xiě)一個(gè)方法來(lái)遍歷二叉樹(shù)的所有節(jié)點(diǎn)，方法如下：
在inOrder（TreeNode節(jié)點(diǎn)）中編寫(xiě)方法
檢查node==null，如果是，則返回，這是我們的基本情況。
調(diào)用inOrder（node.left）以遞歸方式訪問(wèn)左子樹(shù)
打印節(jié)點(diǎn)的值
調(diào)用inOrder（node.right）以遞歸方式遍歷右子樹(shù)。
這將按照InOrder遍歷打印二叉樹(shù)的所有節(jié)點(diǎn)。如果二叉樹(shù)是二叉搜索樹(shù)，則樹(shù)的所有節(jié)點(diǎn)將按排序順序打印。這是一種在Java中實(shí)現(xiàn)InOrder算法的方法：
該方法是私有方法，因?yàn)樗峭ㄟ^(guò)另一個(gè)公共方法inorder（）公開(kāi)的，后者不需要來(lái)自客戶(hù)端的參數(shù)。這是一個(gè)facade模式的例子，它使客戶(hù)端的方法更簡(jiǎn)單。遞歸算法很容易理解，深入到左子樹(shù)，直到找到葉節(jié)點(diǎn)。一旦找到，遞歸堆棧就開(kāi)始展開(kāi)，打印節(jié)點(diǎn)數(shù)據(jù)并開(kāi)始探索右子樹(shù)。
Java中InOrder遍歷二叉樹(shù)-迭代
您可以使用堆棧將遞歸的順序算法轉(zhuǎn)換為迭代的順序算法。。沒(méi)有遞歸的解決方案雖然不容易閱讀，但也不是很難理解。我們從根和進(jìn)程開(kāi)始，直到當(dāng)前節(jié)點(diǎn)或Stack不為空。我們開(kāi)始從左子樹(shù)推節(jié)點(diǎn)，直到到達(dá)葉節(jié)點(diǎn)。此時(shí)，我們pop（）最后一個(gè)元素，打印它的值，并通過(guò)指定current=current.right開(kāi)始探索右子樹(shù)。這將一直持續(xù)到堆棧變空為止，此時(shí)，二叉樹(shù)的所有元素都被訪問(wèn)，樹(shù)遍歷完成。
因?yàn)槲覀兊亩鏄?shù)是一個(gè)二叉搜索樹(shù)，所以可以看到它們是按排序順序打印的。
以上就是長(zhǎng)沙中公優(yōu)就業(yè)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java基礎(chǔ)學(xué)習(xí)：java遞歸算法”的內(nèi)容，希望對(duì)大家有幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢(xún)，有專(zhuān)業(yè)老師隨時(shí)為你服務(wù)。
