Loading...

中順巡回 (Inorder)

初級

Inorder Traversal

左部分木 -> 根 -> 右部分木の順に訪問する巡回方法です。

📊 計算量

区分	計算量
最良	O(N)
平均	O(N)
最悪	O(N)
空間	O(H)

🏷️ Tags

木構造再帰巡回

📖 概念紹介

中順巡回は左部分木 -> 根 -> 右部分木の順に訪問する木の巡回方法です。

1/29

Loading...

👀中順巡回とは？

左部分木を先に訪問し、根、右部分木の順に巡回します。

基礎学習

中順巡回 (Inorder)

定義

中順巡回は左部分木 -> 根 -> 右部分木の順に訪問する木の巡回方法です。

主な特性

✓BSTでは昇順で訪問
✓左の端まで行ってから根を訪問
✓DFS（深さ優先探索）の一形態

時間計算量

最良

O(N)

平均

O(N)

最悪

O(N)

空間計算量

O(H)

中順巡回 (Inorder) | AlgoNote