「左右対称な二分木」:関数型プログラミングの初級問題 -45問目- （10分）

　二分木についての練習問題と答案です。問題は、OCaml公式ページのものを使いました。答案の作成時間は、約10分でした。

問題45.

　二分木が対称であるとは、根を通る垂直線であって、その線を鏡として右の部分木が左の部分木の鏡像となるような線が引けることを言う。
　与えられた二分木が対称であるか否か判断する関数is_symmetricを書け。

※　前回と同様に二分木の型には以下の定義を用います。
type 'a binary_tree =
| Empty
| Node of 'a * 'a binary_tree * 'a binary_tree

答案

本問の解き方

　「二分木が対称である」の定義における「右の部分木が左の部分木の鏡像」という点を基に解きます。

　具体的には、まず、所与の二分木における右部分木を左右反転させて反転右部分木を生成します。
　つぎに、その反転右部分木と、所与の二分木における左部分木とが一致するかを判定します。
　一致する場合、（かつその場合のみ）、「右の部分木が左の部分木の鏡像」であり、所与の「二分木は対称」ということになります。

　以上により、二分木が対称か否かが判定できます。

コード

type 'a binary_tree = Empty | Node of 'a*'a binary_tree*'a binary_tree

let rec reverse = function Empty -> Empty
 | Node (label, left, right) -> Node (label, reverse right, reverse left)

let rec is_same = function
 | (Node (_, left_a, right_a), Node (_, left_b, right_b)) ->
  is_same (left_a, left_b) && is_same (right_a, right_b)
 | (Empty, Empty) -> true
 | _ -> false

let is_symmetric = function Empty -> true
 | Node (_, left, right) -> is_same (left, (reverse right))

　関数reverseは、左右が反転した二分木を生成します。
　関数is_sameは、二つの二分木のトポロジーが一致するか否か判定します。　　

感想

　今回の問題は、前回に比べると簡単でした。
　左右反転も一致判定も、どちらも再帰的に定義できるので、容易に実装できました。

　しかし、二分木はリストと違い直感的に捉えることができません。
　リストは一本道なので処理の順序を想像しやすいのですが、二分木は文字通り枝分かれしているので、順序を想像することが難しいです。
　そのため、再帰的な定義をしただけで木の全体に処理が及ぶことに対し、いまいち納得できません。（まあ、納得できなくとも受け入れれば問題は解けるのですが…）　

　次回は、第46問です。雨が降って一気に秋らしくなりました。見出しも秋らしい食べ物にしてみました。手が届く価格ではないので食べたことはありません、秋が旬ですか？シャインマスカット。