如何實(shí)現(xiàn)二叉樹(shù)的遞歸和迭代中序遍歷
在計(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
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í)喝霔V校缓髲棾鰲m敼?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
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
inorderTraversalRecursive(root, res1);
// 通過(guò)迭代方式完成中序遍歷
List
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ù)具體情況選擇合適的算法。