如何实现二叉树的递归和迭代中序遍历

在计算机科学中，二叉树是一种非常重要的数据结构。它可以用于搜索、排序、计算表达式等多种场景。本篇经验将分享两个算法，分别是如何通过递归方式和迭代方式完成二叉树的中序遍历。

声明二叉树节点类

在开始之前，我们需要先声明一个表示二叉树节点的静态内部类，通过该类对象可以构建一棵二叉树结构。

```java

static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val x; }

}

```

通过递归方式实现二叉树的中序遍历

递归算法是一种基于函数自身调用的算法。对于二叉树的中序遍历，我们可以按照左子树、根节点、右子树的顺序进行递归遍历。

```java

private static void inorderTraversalRecursive(TreeNode root, List res) {

if (root null) return;

inorderTraversalRecursive(root.left, res);

();

inorderTraversalRecursive(root.right, res);

}

```

通过迭代方式实现二叉树的中序遍历

迭代算法是一种基于循环的算法。对于二叉树的中序遍历，我们可以使用一个栈来存储遍历过程中的节点信息。

具体做法是，从根节点开始，将所有左子节点都压入栈中，然后弹出栈顶节点并将其值添加到结果列表中。如果弹出的节点有右子节点，则将右子节点当作根节点再次执行上述操作。直到栈为空为止。

```java

private static void inorderTraversalIterative(TreeNode root, List res) {

Stack stack new Stack<>();

TreeNode curr root;

while (curr ! null || !()) {

while (curr ! null) {

stack.push(curr);

curr curr.left;

}

curr stack.pop();

();

curr curr.right;

}

}

```

本地测试主方法

为了测试算法的正确性，我们需要编写一个本地测试主方法来创建一棵二叉搜索树，并分别通过递归和迭代方式完成中序遍历。最后将两种方式的遍历结果打印到控制台。

```java

public static void main(String[] args) {

// 创建一棵二叉搜索树

TreeNode root new TreeNode(5);

root.left new TreeNode(3);

root.right new TreeNode(6);

root.left.left new TreeNode(2);

root.left.right new TreeNode(4);

// 通过递归方式完成中序遍历

List res1 new ArrayList<>();

inorderTraversalRecursive(root, res1);

// 通过迭代方式完成中序遍历

List res2 new ArrayList<>();

inorderTraversalIterative(root, res2);

// 将两种方式的遍历结果打印到控制台

("递归方式遍历结果：" (()));

("迭代方式遍历结果：" (()));

}

```

运行本地测试主方法，观察控制台输出。如果结果符合预期，则说明两种方式的中序遍历算法均已通过本地测试。

结语

本篇经验介绍了如何通过递归和迭代两种方式完成二叉树的中序遍历。这两种算法各有优缺点，在实际应用中需要根据具体情况选择合适的算法。

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。