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中文网其他相关文章！