二分木の post-order 走査
木を使い終わり、ノードを 1 つ残らず解放する場面を考えます。手でメモリを返す言語では、ここを間違えると二度と使えない領域が残り続けます。
親を先に消すと、子に手が届かない
根から消していくとどうなるでしょうか。根を解放した瞬間、そこに書いてあった左と右の行き先も一緒に消えます。
プレーンテキスト
# 手動メモリ解放を行う言語の疑似コード
def wrong_free(node):
if node is None:
return
free(node) # 先に自分を消した
wrong_free(node.left) # もう読めない場所を読んでいる
wrong_free(node.right)運が良ければその場で落ちます。悪ければ、すでに他の用途へ配られた領域を読み、まったく無関係な値をノードとして扱い始めます。落ちる場所と原因が離れるので、追いかけるのがとても難しいバグになります。
子を片付けてから、自分を片付ける
順序を入れ替えるだけで解決します。
プレーンテキスト
# 手動メモリ解放を行う言語の疑似コード
def free_tree(node):
if node is None:
return
free_tree(node.left)
free_tree(node.right)
free(node) # 自分は最後左、右、自分。これが post-order です。自分を消す時点で、下にぶら下がっていたものはすべて片付いています。裏を返せば、自分を触るまでは子の情報が生きている、ということでもあります。
根が 1、左が 2、右が 3 の木で追ってみます。左へ降りて 2 を片付け、右へ降りて 3 を片付け、戻ってきて 1 を片付ける。並べると 2, 3, 1 です。根が最後にいるのが post-order の顔です。
下から答えを持ち上げる形は、全部これになる
解放だけの話ではありません。子の計算結果を受け取ってから自分の値を決める処理は、必ずこの順になります。フォルダの合計容量、部下の総数、閉じタグを書き出す順番。どれも下が確定するまで上が決まりません。
たとえばタグを組み立てる処理も同じ形です。
Python
def to_html(node):
if node is None:
return ""
inner = to_html(node.left) + to_html(node.right)
return "<" + node.tag + ">" + inner + "</" + node.tag + ">"中身が全部できあがるまで、閉じタグは書けません。だから子を先に組み立て、そのあとで自分の開きと閉じで挟みます。
逆に、自分の値が先に決まるなら post-order である必要はありません。単に値を並べるだけなら、どの順でも全ノードを 1 回ずつ訪れます。順序を選ぶ基準は「上が下の答えを必要とするかどうか」です。ここが分かると、木の問題でどの順を選ぶかで迷わなくなります。
書くときに間違えやすいのは、右の再帰の書き忘れです。左だけ書いても動いてしまい、左端の枝だけをたどって終わります。結果の件数がノードの数と合わないときは、まずここを疑ってください。もう 1 つは行き止まりの判定です。配列で受け取っている以上、範囲の外に出ていないかと、その場所が空でないかの両方を確かめる必要があります。片方だけだと、深い木で必ず落ちます。
なお、走査した結果を並べたとき、末尾に根が来ていれば post-order です。手元の出力がどれなのか分からなくなったら、最後の 1 件を見てください。
演習の visitPostorder(tree, i, result) は外側の関数と同じ段に置きます。木、添字、結果のリストをすべて引数で渡すので、入れ子の関数は使いません。result.append(...) は渡されたリストへ値を一つ加える操作です。根からの呼び出しは用意済みで、書くのは空の場所で止める条件と訪問順です。
解放例の free は手動でメモリを返す操作を表す疑似コードです。Python の組み込み関数ではありません。Python は参照されなくなったオブジェクトを自動で管理するため、この free は実行しません。演習では同じ左、右、根の順を、値を集める走査として書きます。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 用意済みの visitPostorder の中で再帰により指定の訪問順を実装する
- 戻り値は訪問順の値の配列。null は結果に含めない