Java中序遍歷

樹的中序遍歷是按照先訪問最左邊的節點，然後訪問根節點，最後訪問最右邊的節點的順序訪問樹的每個節點的方式。遍歷是我們存取給定資料結構的每個值元素的方式。每個線性資料結構只有一種方式來遍歷其元素。線性資料結構有陣列、堆疊、佇列和鍊錶。但對於像樹這樣的非線性資料結構，有多種可能的方式和順序來存取節點。基本的順序遍歷方法有中序、前序、後序三種。

開始您的免費軟體開發課程

網頁開發、程式語言、軟體測試及其他

在本文中，我們將研究中序遍歷方法及其在二元樹中的工作原理。我們還將看到如何使用 C 程式語言實作中序遍歷的範例之一。

中序遍歷的工作原理

使用中序遍歷來遍歷樹時所使用的演算法或步驟如下 –

• 首先要遍歷左子樹的所有節點，先訪問左節點，再訪問主節點，再訪問右節點。
• 現在，訪問樹的根節點。
• 在左子樹遍歷和根訪問之後，該訪問右子樹了。

考慮一棵樹，其中的節點如圖所示 –

在上面給出的樹的例子中，遍歷將首先從植物的最左邊的節點或葉子開始，即 3，然後我們將遍歷它的主要直接父節點，即 6。之後，我們將去用於搜尋其右子節點，但是，正如我們所看到的，6 個節點沒有右子節點，因此，現在將訪問6 個節點的直接父節點，即12，這樣將繼續我們的遍歷之旅。最終遍歷的順序如下圖 –
3-> 6-> 12-> 13-> 14-> 15-> 20-> 17-> 23-> 27

中序遍歷的應用

中序遍歷主要用於二元搜尋樹。採用中序遍歷的反向演算法得到節點值的非增序。如果我們希望以非遞減格式檢索節點，則無需使用中序遍歷的變體。我們可以利用上面討論的相同的中序遍歷方法來取得二元樹的非遞減值。

Java中序遍歷的實作

為了理解中序遍歷的流程及其在 Java 程式語言中的實現，您需要了解 java 方法以及類別和物件概念。下面的程式使用遞歸呼叫中序遍歷的方法，先存取左側子樹，然後存取根節點，然後存取右側子樹。在存取遍歷中的每個節點時，程式確保列印所存取的相同節點的值。因此，我們可以在輸出中看到所有節點是如何被存取的以及它們被存取的順序。

範例

代碼：

import java.util.Stack;
/*
* Implementation of inorder traversal of the binary tree.
* Inorder traversal involves travelling to he left most leaf or node of the
* tree and then the root node of the tree. The last node to be traversed is
* the rightmost node or leaf of the binary tree.
*
* input:
* 43
* / \
* 23 32
* / \ \
* 13 32 95
* / / \
* 3 49 67
*
* Resulting output: 3 13 23 32 43 32 95 49 67
*/
public class Main {
public static void main(String[] args) throws Exception {
// Firstly, we will create the binary tree as displayed in the comments
BinaryTreeToTraverse bt = BinaryTreeToTraverse.create();
// With the help of recursion that means calling the same function again and again,
// we will do inorder traversal of the binary tree
System.out
.println("Using recursion, display all the nodes of the binary tree that are resulted\n by following inorder traversal :- ");
bt.inOrderTraversal();
}
}
class BinaryTreeToTraverse {
static class binaryTreeNode {
String data;
binaryTreeNode leftNode, rightNode;
binaryTreeNode(String value) {
this.data = value;
leftNode = rightNode = null;
}
}
// Root node of the considered binary tree
binaryTreeNode rootNode;
/**
* Use the inorder algorithm for traversing through the nodes in binary tree
*/
public void inOrderTraversal() {
inOrderTraversal(rootNode);
}
private void inOrderTraversal(binaryTreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.leftNode);
System.out.printf("%s ", node.data);
inOrderTraversal(node.rightNode);
}
/**
* Consider the sample data to test the order in which the nodes are traversed in Java program
*
* @return a sample binary binaryTree for testing
*/
public static BinaryTreeToTraverse create() {
BinaryTreeToTraverse binaryTree = new BinaryTreeToTraverse();
binaryTreeNode rootNode = new binaryTreeNode("43");
binaryTree.rootNode = rootNode;
binaryTree.rootNode.leftNode = new binaryTreeNode("23");
binaryTree.rootNode.leftNode.leftNode = new binaryTreeNode("13");
binaryTree.rootNode.leftNode.leftNode.leftNode = new binaryTreeNode("3");
binaryTree.rootNode.leftNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode = new binaryTreeNode("32");
binaryTree.rootNode.rightNode.rightNode = new binaryTreeNode("95");
binaryTree.rootNode.leftNode.rightNode.leftNode = new binaryTreeNode("49");
binaryTree.rootNode.leftNode.rightNode.rightNode = new binaryTreeNode("67");
return binaryTree;
}
}

輸出：

上述程式執行的輸出如下：

結論

中序遍歷是深度優先遍歷方法之一，按照先遍歷左節點，再遍歷根，再遍歷右子樹的方式遍歷所有節點。在中序遍歷中，樹的最左邊的葉子是第一個被訪問的節點，而最右邊的葉子是最後一個被遍歷的節點。中序遍歷方法廣泛用於二元搜尋樹中，用於取得非遞減或非遞增順序的值。 java 實作可以以遞歸格式或迭代格式完成。這裡使用遞歸的方法來實現，反覆呼叫同一個方法來實現中序遍歷。

以上是Java中序遍歷的詳細內容。更多資訊請關注PHP中文網其他相關文章！