與數(shù)組和鏈表不同，二叉樹有幾種遍歷方式。遍歷算法大致分為深度優(yōu)先和廣度優(yōu)先遍歷算法，這取決于算法實際如何工作。顧名思義，深度優(yōu)先在訪問同級別兄弟之前先向二叉樹縱深訪問，而廣度優(yōu)先是先訪問同一級別中的所有節(jié)點然后再進入下一級別，因此它也被稱為級別順序遍歷。PreOrder和InOrder樹遍歷算法都是深度優(yōu)先的，預(yù)序和中序算法之間的唯一區(qū)別是訪問二叉樹的根，左節(jié)點和右節(jié)點的順序。

　　InOrder遍歷算法首先訪問左節(jié)點，然后是root節(jié)點，最后是右節(jié)點。這與首先訪問根的預(yù)序遍歷不同。InOrder遍歷的一個重要特性是，如果給定的二叉樹是二叉搜索樹，它將按排序順序打印節(jié)點。

　　請記住，如果左子樹中的所有節(jié)點都低于root并且右子樹中的所有節(jié)點都大于root，則二叉樹稱為二叉搜索樹。

　　在示例中，使用二叉搜索樹來演示InOrder樹遍歷以排序順序打印二叉樹的節(jié)點，并分享了這個問題的遞歸和迭代解決方案。從面試的角度來看，這非常重要。即使遞歸解決方案更容易，占用更少的代碼行，并且更具可讀性，您也應(yīng)該知道如何在沒有Java遞歸的情況下遍歷二叉樹，以便在編程面試中做得更好。

　　Java中InOrder遍歷二叉樹-遞歸

　　由于二叉樹是遞歸數(shù)據(jù)結(jié)構(gòu)，因此遞歸是解決基于樹的問題的最佳方法。以下是二叉樹InOrder遍歷的步驟：

　　訪問左節(jié)點

　　訪問root

　　訪問右節(jié)點

　　要實現(xiàn)此算法，您可以使用InOrder遍歷編寫一個方法來遍歷二叉樹的所有節(jié)點，方法如下：

　　在inOrder（TreeNode節(jié)點）中編寫方法

　　檢查node==null，如果是，則返回，這是我們的基本情況。

　　調(diào)用inOrder（node.left）以遞歸方式訪問左子樹

　　打印節(jié)點的值

　　調(diào)用inOrder（node.right）以遞歸方式遍歷右子樹。

　　這將按照InOrder遍歷打印二叉樹的所有節(jié)點。如果二叉樹是二叉搜索樹，則樹的所有節(jié)點將按排序順序打印。這是一種在Java中實現(xiàn)InOrder算法的方法：

　　該方法是私有方法，因為它是通過另一個公共方法inorder（）公開的，后者不需要來自客戶端的參數(shù)。這是一個facade模式的例子，它使客戶端的方法更簡單。遞歸算法很容易理解，深入到左子樹，直到找到葉節(jié)點。一旦找到，遞歸堆棧就開始展開，打印節(jié)點數(shù)據(jù)并開始探索右子樹。

　　Java中InOrder遍歷二叉樹-迭代

　　您可以使用堆棧將遞歸的順序算法轉(zhuǎn)換為迭代的順序算法。。沒有遞歸的解決方案雖然不容易閱讀，但也不是很難理解。我們從根和進程開始，直到當前節(jié)點或Stack不為空。我們開始從左子樹推節(jié)點，直到到達葉節(jié)點。此時，我們pop（）最后一個元素，打印它的值，并通過指定current=current.right開始探索右子樹。這將一直持續(xù)到堆棧變空為止，此時，二叉樹的所有元素都被訪問，樹遍歷完成。

　　因為我們的二叉樹是一個二叉搜索樹，所以可以看到它們是按排序順序打印的。

　   以上就是動力節(jié)點Java培訓(xùn)機構(gòu)小編介紹的“Java基礎(chǔ)學(xué)習(xí)：java遞歸算法”的內(nèi)容，希望對大家有幫助，如有疑問，請在線咨詢，有專業(yè)老師隨時為你服務(wù)。