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

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

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

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

　　Java中InOrder遍歷二叉樹-遞歸

　　由于二叉樹是遞歸數據結構，因此遞歸是解決基于樹的問題的最佳方法。以下是二叉樹InOrder遍歷的步驟：

　　訪問左節點

　　訪問root

　　訪問右節點

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

　　在inOrder（TreeNode節點）中編寫方法

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

　　調用inOrder（node.left）以遞歸方式訪問左子樹

　　打印節點的值

　　調用inOrder（node.right）以遞歸方式遍歷右子樹。

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

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

　　Java中InOrder遍歷二叉樹-迭代

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

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

　   以上就是動力節點Java培訓機構小編介紹的“Java基礎學習：java遞歸算法”的內容，希望對大家有幫助，如有疑問，請在線咨詢，有專業老師隨時為你服務。