【基本情報 科目B】二分木の後順走査をやさしく解説！「自分って何？」が分かれば簡単

はじめに

基本情報技術者試験の科目Bでは、二分木の走査（巡回） がよく出題されます。

参考書を見ると、

左 → 右 → 自分

と書かれていることが多いですが、

• 「自分って誰？」
• 「node.val って何？」
• 「何を出力しているの？」

と混乱する人も多いです。

今回は、そんな疑問を ハク と レイ と一緒にやさしく解説します。

---

二分木とは？

二分木とは、1つのノードが

• 左の子
• 右の子

を持つデータ構造です。

今回の例は次のような木になっています。

---

ノードとは？

図の中の丸1つ1つが ノード（節） です。

例えば、

• ×
• ÷
• +
• a
• b

などがすべてノードです。

---

node.val とは？

各ノードには値が入っています。

ノード	node.val
×	×
+	+
a	a
f	f

つまり、

node.val

は

今見ているノードの値

を表します。

「自分」とは？

「自分」とは、

今 traverse(node) に渡されている node

のことです。

---

例1

traverse(×)

このときの自分は ×

---

例2

traverse(+)

このときの自分は +

---

例3

traverse(a)

このときの自分は a

---

後順走査（Postorder Traversal）とは？

後順走査では、

左 → 右 → 自分

の順番で処理します。

---

+ の部分だけ見る

処理順：

1. a
2. b
3. +

出力：

ab+

---

プログラム

traverse(Node: node)

if (node が 未定義)
    return
else
    traverse(node.left)
    traverse(node.right)
    node.val を出力する
endif

---

なぜこの順番で出力されるの？

木全体では、

---

左部分木の出力

ab+cd-÷

---

右部分木の出力

ef+

---

最後にルート

×

---

最終結果

ab+cd-÷ef+×

---

---

前順・中順・後順の違い

走査方法	順番
前順走査	自分 → 左 → 右
中順走査	左 → 自分 → 右
後順走査	左 → 右 → 自分

---

覚え方

• 前順：自分が先
• 中順：自分が真ん中
• 後順：自分が最後

---

まとめ

• ノード = 木の中の1つ1つの丸
• node.val = 今見ているノードの値
• 「自分」 = 現在のノード
• 後順走査 = 左 → 右 → 自分
• 今回の出力結果は

ab+cd-÷ef+×

---