中序遍历 In-order Traversal

jack.yang

发布于 2025-04-05 11:54:51

11700

代码可运行

运行总次数：0

代码可运行

定义

中序遍历（In-order Traversal）在二叉搜索树（BST）中非常有用，因为它会按照升序的方式访问节点。但在其他类型的树中，这种顺序就不一定了。

示例

下面我会首先解释二叉搜索树的中序遍历，然后用一个图例来说明。

二叉搜索树的中序遍历

在二叉搜索树中，中序遍历会先访问左子树，然后访问根节点，最后访问右子树。由于二叉搜索树的特性（对于任意节点，其左子树所有节点的值都小于它，其右子树所有节点的值都大于它），这样的遍历顺序会使得节点值按照升序排列。

伪代码

function inorderTraversal(node):
    if node is not None:
        # 递归访问左子树
        inorderTraversal(node.left)
        # 访问根节点
        print(node.value)
        # 递归访问右子树
        inorderTraversal(node.right)

假设我们有一个如下的二叉搜索树：

按照中序遍历的顺序，我们得到的节点值序列是：2, 3, 4, 5, 6, 7, 8。这是一个升序序列。

其他类型树的中序遍历

对于非二叉搜索树的其他类型树（如普通二叉树、N叉树等），中序遍历同样遵循“左-根-右”的顺序，但节点的值不一定按升序排列。

图例说明（普通二叉树）

考虑以下普通二叉树：

/ \

2 3

/ \ \

4 5 6

中序遍历的顺序是：4, 2, 5, 1, 3, 6。这里节点的值并不按升序排列。

实现

在Java中，你可以使用递归或非递归（使用栈）的方式来实现中序遍历。以下是递归实现的Java代码示例：

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.com 删除

遍历