admin管理员组文章数量:1032087
中序遍历 In
定义
中序遍历（In-order Traversal）在二叉搜索树（BST）中非常有用，因为它会按照升序的方式访问节点。但在其他类型的树中，这种顺序就不一定了。
示例
下面我会首先解释二叉搜索树的中序遍历，然后用一个图例来说明。
二叉搜索树的中序遍历
在二叉搜索树中，中序遍历会先访问左子树，然后访问根节点，最后访问右子树。由于二叉搜索树的特性（对于任意节点，其左子树所有节点的值都小于它，其右子树所有节点的值都大于它），这样的遍历顺序会使得节点值按照升序排列。
伪代码
代码语言：javascript代码运行次数：0运行复制function inorderTraversal(node):
if node is not None:
# 递归访问左子树
inorderTraversal(node.left)
# 访问根节点
print(node.value)
# 递归访问右子树
inorderTraversal(node.right)假设我们有一个如下的二叉搜索树：
代码语言：javascript代码运行次数：0运行复制 5
/ \
3 7
/ \ / \
2 4 6 8按照中序遍历的顺序，我们得到的节点值序列是：2, 3, 4, 5, 6, 7, 8。这是一个升序序列。
其他类型树的中序遍历
对于非二叉搜索树的其他类型树（如普通二叉树、N叉树等），中序遍历同样遵循“左-根-右”的顺序，但节点的值不一定按升序排列。
图例说明（普通二叉树）
考虑以下普通二叉树：
1
/ \
2 3
/ \ \
4 5 6
中序遍历的顺序是：4, 2, 5, 1, 3, 6。这里节点的值并不按升序排列。
实现
在Java中，你可以使用递归或非递归（使用栈）的方式来实现中序遍历。以下是递归实现的Java代码示例：
代码语言：javascript代码运行次数：0运行复制import java.util.ArrayList;
import java.util.List;
// 定义二叉树节点类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
// 二叉树工具类
public class BinaryTreeTraversal {
// 中序遍历二叉树
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
// 中序遍历辅助方法
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
inorderHelper(node.left, result); // 遍历左子树
result.add(node.val); // 访问根节点
inorderHelper(node.right, result); // 遍历右子树
}
// 创建并打印二叉搜索树的中序遍历结果
public void printInOrderBST() {
// 创建二叉搜索树
TreeNode rootBST = new TreeNode(5);
rootBST.left = new TreeNode(3);
rootBST.right = new TreeNode(7);
rootBST.left.left = new TreeNode(2);
rootBST.left.right = new TreeNode(4);
rootBST.right.left = new TreeNode(6);
rootBST.right.right = new TreeNode(8);
// 中序遍历并打印结果
List<Integer> resultBST = inorderTraversal(rootBST);
System.out.print("二叉搜索树的中序遍历结果: ");
for (int val : resultBST) {
System.out.print(val + " ");
}
System.out.println();
}
// 创建并打印普通二叉树的中序遍历结果
public void printInOrderRegular() {
// 创建普通二叉树
TreeNode rootRegular = new TreeNode(1);
rootRegular.left = new TreeNode(2);
rootRegular.right = new TreeNode(3);
rootRegular.left.left = new TreeNode(4);
rootRegular.left.right = new TreeNode(5);
rootRegular.right.right = new TreeNode(6);
// 中序遍历并打印结果
List<Integer> resultRegular = inorderTraversal(rootRegular);
System.out.print("普通二叉树的中序遍历结果: ");
for (int val : resultRegular) {
System.out.print(val + " ");
}
System.out.println();
}
// 主方法
public static void main(String[] args) {
BinaryTreeTraversal btt = new BinaryTreeTraversal();
btt.printInOrderBST(); // 打印二叉搜索树的中序遍历结果
btt.printInOrderRegular(); // 打印普通二叉树的中序遍历结果
}
}当你运行这段代码时，它会首先打印出二叉搜索树的中序遍历结果（一个升序序列），然后打印出普通二叉树的中序遍历结果（一个非升序序列）。 输出结果将会是： 二叉搜索树的中序遍历结果: 2 3 4 5 6 7 8 普通二叉树的中序遍历结果: 4 2 5 1 3 6 这验证了中序遍历对于二叉搜索树会产生升序序列（如果所有节点值都不重复），而对于普通二叉树则不一定。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-05-24，如有侵权请联系 cloudcommunity@tencent 删除遍历递归搜索二叉树traversal中序遍历 In
定义
中序遍历（In-order Traversal）在二叉搜索树（BST）中非常有用，因为它会按照升序的方式访问节点。但在其他类型的树中，这种顺序就不一定了。
示例
下面我会首先解释二叉搜索树的中序遍历，然后用一个图例来说明。
二叉搜索树的中序遍历
在二叉搜索树中，中序遍历会先访问左子树，然后访问根节点，最后访问右子树。由于二叉搜索树的特性（对于任意节点，其左子树所有节点的值都小于它，其右子树所有节点的值都大于它），这样的遍历顺序会使得节点值按照升序排列。
伪代码
代码语言：javascript代码运行次数：0运行复制function inorderTraversal(node):
if node is not None:
# 递归访问左子树
inorderTraversal(node.left)
# 访问根节点
print(node.value)
# 递归访问右子树
inorderTraversal(node.right)假设我们有一个如下的二叉搜索树：
代码语言：javascript代码运行次数：0运行复制 5
/ \
3 7
/ \ / \
2 4 6 8按照中序遍历的顺序，我们得到的节点值序列是：2, 3, 4, 5, 6, 7, 8。这是一个升序序列。
其他类型树的中序遍历
对于非二叉搜索树的其他类型树（如普通二叉树、N叉树等），中序遍历同样遵循“左-根-右”的顺序，但节点的值不一定按升序排列。
图例说明（普通二叉树）
考虑以下普通二叉树：
1
/ \
2 3
/ \ \
4 5 6
中序遍历的顺序是：4, 2, 5, 1, 3, 6。这里节点的值并不按升序排列。
实现
在Java中，你可以使用递归或非递归（使用栈）的方式来实现中序遍历。以下是递归实现的Java代码示例：
代码语言：javascript代码运行次数：0运行复制import java.util.ArrayList;
import java.util.List;
// 定义二叉树节点类
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
// 二叉树工具类
public class BinaryTreeTraversal {
// 中序遍历二叉树
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderHelper(root, result);
return result;
}
// 中序遍历辅助方法
private void inorderHelper(TreeNode node, List<Integer> result) {
if (node == null) return;
inorderHelper(node.left, result); // 遍历左子树
result.add(node.val); // 访问根节点
inorderHelper(node.right, result); // 遍历右子树
}
// 创建并打印二叉搜索树的中序遍历结果
public void printInOrderBST() {
// 创建二叉搜索树
TreeNode rootBST = new TreeNode(5);
rootBST.left = new TreeNode(3);
rootBST.right = new TreeNode(7);
rootBST.left.left = new TreeNode(2);
rootBST.left.right = new TreeNode(4);
rootBST.right.left = new TreeNode(6);
rootBST.right.right = new TreeNode(8);
// 中序遍历并打印结果
List<Integer> resultBST = inorderTraversal(rootBST);
System.out.print("二叉搜索树的中序遍历结果: ");
for (int val : resultBST) {
System.out.print(val + " ");
}
System.out.println();
}
// 创建并打印普通二叉树的中序遍历结果
public void printInOrderRegular() {
// 创建普通二叉树
TreeNode rootRegular = new TreeNode(1);
rootRegular.left = new TreeNode(2);
rootRegular.right = new TreeNode(3);
rootRegular.left.left = new TreeNode(4);
rootRegular.left.right = new TreeNode(5);
rootRegular.right.right = new TreeNode(6);
// 中序遍历并打印结果
List<Integer> resultRegular = inorderTraversal(rootRegular);
System.out.print("普通二叉树的中序遍历结果: ");
for (int val : resultRegular) {
System.out.print(val + " ");
}
System.out.println();
}
// 主方法
public static void main(String[] args) {
BinaryTreeTraversal btt = new BinaryTreeTraversal();
btt.printInOrderBST(); // 打印二叉搜索树的中序遍历结果
btt.printInOrderRegular(); // 打印普通二叉树的中序遍历结果
}
}当你运行这段代码时，它会首先打印出二叉搜索树的中序遍历结果（一个升序序列），然后打印出普通二叉树的中序遍历结果（一个非升序序列）。 输出结果将会是： 二叉搜索树的中序遍历结果: 2 3 4 5 6 7 8 普通二叉树的中序遍历结果: 4 2 5 1 3 6 这验证了中序遍历对于二叉搜索树会产生升序序列（如果所有节点值都不重复），而对于普通二叉树则不一定。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-05-24，如有侵权请联系 cloudcommunity@tencent 删除遍历递归搜索二叉树traversal本文标签： 中序遍历 In
版权声明：本文标题：中序遍历 In 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1747906447a2225833.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论