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

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

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

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

```java

static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val x; }

}

```

通過遞歸方式實現(xiàn)二叉樹的中序遍歷

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

```java

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

if (root null) return;

inorderTraversalRecursive(root.left, res);

();

inorderTraversalRecursive(root.right, res);

}

```

通過迭代方式實現(xiàn)二叉樹的中序遍歷

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

具體做法是，從根節(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)建一棵二叉搜索樹，并分別通過遞歸和迭代方式完成中序遍歷。最后將兩種方式的遍歷結(jié)果打印到控制臺。

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

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

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

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

}

```

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

結(jié)語

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