木構造とは（全体像）
木構造は、データを「親と子」の階層でつなげた形のデータ構造。1つの根（ルート）から枝分かれして広がっていく、上下さかさまの木のような形だ。
用語はシンプル。
- 節点（ノード） … データを置く点
- 枝 … 親子をつなぐ線
- 根（ルート） … 一番上の節点
- 葉（リーフ） … その先がない（子を持たない）節点
この木をたどる順番（走査）には3種類あり、計算式を木で表すと、たどる順番によって式の書き方（記法）が変わる——これが逆ポーランド記法につながる。
詳しく：3つの走査と逆ポーランド記法だけ覚えれば戦える
ここが記事の心臓部。まずは3つの走査の順番。
木の3つの走査
| 走査 | 訪れる順番 | 別名 |
|---|---|---|
| 前置（preorder） | 根 → 左 → 右 | 行きがけ |
| 中置（inorder） | 左 → 根 → 右 | 通りがけ |
| 後置（postorder） | 左 → 右 → 根 | 帰りがけ |
「根をいつ訪れるか」で名前が決まる。前は根が先、中は根が真ん中、後は根が最後、と覚えるとラクだ。
この走査と対応するのが、計算式の3つの記法。
式の3つの記法（A＋Bの例）
| 記法 | 書き方 | 演算子の位置 |
|---|---|---|
| 前置（ポーランド） | ＋ A B | 前 |
| 中置 | A ＋ B | 真ん中（人間に馴染む） |
| 後置（逆ポーランド） | A B ＋ | うしろ |
主役は後置記法（逆ポーランド記法・RPN）。`A B ＋`のように演算子をうしろに置くのが特徴で、2つの強みがある。
- 括弧がいらない … 計算の順番が並び順だけで決まり、あいまいさがない。
- スタックで簡単に計算できる … 「数字が来たら積む、演算子が来たら2つ取り出して計算し、結果を積む」だけ。
たとえば`3 4 ＋ 5 ×`は、3と4を積む→＋で取り出して7にして積む→5を積む→×で取り出して35。つまり(3＋4)×5＝35が、括弧なしで計算できる。
わかりやすく言い換えると
要するに、逆ポーランド記法は「演算子をうしろに置く電卓の中の言葉」だ。
人間は「3＋4」と真ん中に演算子を置く（中置）が、コンピュータは`3 4 ＋`とうしろに置くほうが扱いやすい。なぜなら、スタック（積み重ねるお皿）を使えば、上から順に積んで計算するだけで答えが出るから。括弧で「どこから計算するか」を悩む必要がない、というわけだ。
①数字 … お皿に積む
②演算子 … 上の2枚を取り出して計算し、結果を積む
試験のツボ
🔴 一番出る：逆ポーランド記法（後置）の特徴
①演算子をうしろに置く（A B ＋）
②括弧がいらず、あいまいさがない
③スタックで簡単に計算できる
🔴 次に出る：3つの走査の順番
①前置＝根→左→右／中置＝左→根→右／後置＝左→右→根
②「根をいつ訪れるか」で名前が決まる
🟡 押さえると安定：木構造の用語
①節点（ノード）・枝・根（ルート）・葉（リーフ）
②計算式も木で表せる
よくある間違い
①「逆ポーランド記法は括弧が必要で、計算しにくい」→ ✗ 逆。括弧がいらず、スタックで簡単・高速に計算できる。
②「中置記法は左→根→右ではなく、根→左→右の順である」→ ✗ 根→左→右は前置。中置は左→根→右。
③「逆ポーランド記法は演算子を式の先頭に置く」→ ✗ 先頭に置くのは前置（ポーランド）。逆ポーランドはうしろ。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（走査の順番）
木構造の走査に関する次の記述のうち、正しいものはどれか。
- 前置（行きがけ）の走査は、左の子・右の子・根の順に節点をたどる方式である
- 中置（通りがけ）の走査は、左の子・根・右の子の順に節点をたどる方式である
- 後置（帰りがけ）の走査は、根・左の子・右の子の順に節点をたどる方式である
- 前置・中置・後置のどれも、節点をたどる順番はまったく同じものとされている
解答は 2 だぜ。
中置（通りがけ）は「左の子 → 根 → 右の子」の順だ。「根をいつ訪れるか」で名前が決まり、中置は根が真ん中だな。
選択肢1は前置を「左・右・根」としているが前置は根が先（根→左→右）。選択肢3は後置を「根・左・右」としているが後置は根が最後。選択肢4は「同じ順番」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 前置は根→左→右 |
| 2 | ✓ | 中置は左→根→右で正しい |
| 3 | ✗ | 後置は左→右→根 |
| 4 | ✗ | 走査ごとに順番が違う |
オリジナル問題2（逆ポーランドの計算）
逆ポーランド記法 `3 4 ＋ 5 ×` を計算した結果として、正しいものはどれか。
- 演算子を先に計算するため 3＋4×5 とみなされ、答えは23になると考えられる
- 逆ポーランド記法は計算できない書き方なので、答えは求められないとされる
- かっこの付け方によって答えが変わり、一通りには定まらないものとされている
- スタックで前から計算すると (3＋4)×5 となり、答えは35になると分かる
解答は 4 だぜ。
`3 4 ＋ 5 ×`は、3と4を積む→＋で7にする→5を積む→×で計算、と前から処理すると(3＋4)×5＝35だ。括弧なしでスタックだけで計算できる。
選択肢1は「23」になる計算順で誤り。選択肢2は「計算できない」が誤り。選択肢3は「一通りに定まらない」が誤りで、逆ポーランドはあいまいさがないぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 前から処理すると(3＋4)×5 |
| 2 | ✗ | スタックで計算できる |
| 3 | ✗ | あいまいさはなく一通りに定まる |
| 4 | ✓ | (3＋4)×5＝35で正しい |
オリジナル問題3（逆ポーランドの特徴）
逆ポーランド記法（後置記法）の特徴に関する次の記述のうち、正しいものはどれか。
- 演算子をうしろに置き、括弧がいらず、スタックで簡単に計算できる書き方だ
- 演算子を式の先頭に置く書き方で、人間が最も読みやすいとされる記法である
- 計算するたびに必ず括弧を補う必要があり、機械での処理には向かない記法だ
- 中置記法と書き方も計算方法もまったく同じで、区別する意味がない記法である
解答は 1 だぜ。
逆ポーランド記法は演算子をうしろに置き、括弧がいらず、スタックで簡単に計算できるのが特徴だ。コンピュータにとって扱いやすい書き方だな。
選択肢2は「先頭に置く・人間に読みやすい」で前置や中置の話。選択肢3は「括弧が必要・機械に向かない」が逆。選択肢4は「中置と同じ」が誤りだぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 演算子うしろ・括弧不要・スタックで計算 |
| 2 | ✗ | 先頭に置くのは前置 |
| 3 | ✗ | 括弧不要で機械に向く |
| 4 | ✗ | 中置とは書き方が異なる |
まとめ
押さえどころ
- 🔴 逆ポーランド記法 ＝ 演算子をうしろに置く。括弧がいらず、スタックで簡単に計算できる。
- 🔴 3つの走査 ＝ 前置（根→左→右）・中置（左→根→右）・後置（左→右→根）。
- 🟡 木構造の用語 ＝ 節点（ノード）・枝・根（ルート）・葉（リーフ）。
次に学ぶ
- 構文解析（LL・LR） ── 計算式を木に組み立てる処理。木構造や記法の知識が、構文解析の理解に直結する。
- スタックとキュー ── 逆ポーランド記法の計算で使う「スタック」の基本。データ構造の基礎としてセットで押さえたい。
執筆: SikakuQuest編集部