在計算機科學中，二叉樹是一種非常重要的數據結構。它可以用于搜索、排序、計算表達式等多種場景。本篇經驗將分享兩個算法，分別是如何通過遞歸方式和迭代方式完成二叉樹的中序遍歷。聲明二叉樹節(jié)點類在開始之前，我

在計算機科學中，二叉樹是一種非常重要的數據結構。它可以用于搜索、排序、計算表達式等多種場景。本篇經驗將分享兩個算法，分別是如何通過遞歸方式和迭代方式完成二叉樹的中序遍歷。

聲明二叉樹節(jié)點類

在開始之前，我們需要先聲明一個表示二叉樹節(jié)點的靜態(tài)內部類，通過該類對象可以構建一棵二叉樹結構。

```java

static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val x; }

}

```

通過遞歸方式實現二叉樹的中序遍歷

遞歸算法是一種基于函數自身調用的算法。對于二叉樹的中序遍歷，我們可以按照左子樹、根節(jié)點、右子樹的順序進行遞歸遍歷。

```java

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

if (root null) return;

inorderTraversalRecursive(root.left, res);

();

inorderTraversalRecursive(root.right, res);

}

```

通過迭代方式實現二叉樹的中序遍歷

迭代算法是一種基于循環(huán)的算法。對于二叉樹的中序遍歷，我們可以使用一個棧來存儲遍歷過程中的節(jié)點信息。

具體做法是，從根節(jié)點開始，將所有左子節(jié)點都壓入棧中，然后彈出棧頂節(jié)點并將其值添加到結果列表中。如果彈出的節(jié)點有右子節(jié)點，則將右子節(jié)點當作根節(jié)點再次執(zhí)行上述操作。直到棧為空為止。

```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;

}

}

```

本地測試主方法

為了測試算法的正確性，我們需要編寫一個本地測試主方法來創(chuàng)建一棵二叉搜索樹，并分別通過遞歸和迭代方式完成中序遍歷。最后將兩種方式的遍歷結果打印到控制臺。

```java

public static void main(String[] args) {

// 創(chuàng)建一棵二叉搜索樹

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);

// 將兩種方式的遍歷結果打印到控制臺

("遞歸方式遍歷結果：" (()));

("迭代方式遍歷結果：" (()));

}

```

運行本地測試主方法，觀察控制臺輸出。如果結果符合預期，則說明兩種方式的中序遍歷算法均已通過本地測試。

結語

本篇經驗介紹了如何通過遞歸和迭代兩種方式完成二叉樹的中序遍歷。這兩種算法各有優(yōu)缺點，在實際應用中需要根據具體情況選擇合適的算法。