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

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

聲明二叉樹(shù)節(jié)點(diǎn)類(lèi)

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

```java

static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val x; }

}

```

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

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

```java

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

if (root null) return;

inorderTraversalRecursive(root.left, res);

();

inorderTraversalRecursive(root.right, res);

}

```

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

迭代算法是一種基于循環(huán)的算法。對(duì)于二叉樹(shù)的中序遍歷，我們可以使用一個(gè)棧來(lái)存儲(chǔ)遍歷過(guò)程中的節(jié)點(diǎn)信息。

具體做法是，從根節(jié)點(diǎn)開(kāi)始，將所有左子節(jié)點(diǎn)都?jí)喝霔Ｖ校缓髲棾鰲ｍ敼?jié)點(diǎn)并將其值添加到結(jié)果列表中。如果彈出的節(jié)點(diǎn)有右子節(jié)點(diǎn)，則將右子節(jié)點(diǎn)當(dāng)作根節(jié)點(diǎn)再次執(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;

}

}

```

本地測(cè)試主方法

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

```java

public static void main(String[] args) {

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

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

// 通過(guò)遞歸方式完成中序遍歷

List res1 new ArrayList<>();

inorderTraversalRecursive(root, res1);

// 通過(guò)迭代方式完成中序遍歷

List res2 new ArrayList<>();

inorderTraversalIterative(root, res2);

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

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

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

}

```

運(yùn)行本地測(cè)試主方法，觀察控制臺(tái)輸出。如果結(jié)果符合預(yù)期，則說(shuō)明兩種方式的中序遍歷算法均已通過(guò)本地測(cè)試。

結(jié)語(yǔ)

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