二分木の pre-order 走査
木をまるごと複製したい、という場面から入ります。設定のツリーを複製して片方だけ書き換える、といった用途です。作る順番を間違えると、これが妙に面倒になります。
子から作ると、つなぐ相手がまだ居ない
葉のほうから新しいノードを作っていくと、作った直後は宙に浮いたままです。誰かの子として登録したくても、その相手はまだ存在しません。作った端から一時的な置き場に貯めておいて、親ができたら引き取りに行く、という段取りが要ります。置き場の管理でコードが 2 倍に膨らみます。
しかも複製では、ノードを使い回せません。同じノードを両方の木から指してしまうと、片方を書き換えたときにもう片方まで変わります。必ず新しく作る必要があるぶん、作る順番がそのまま効いてきます。
順序を逆にすると、この面倒がまるごと消えます。先に自分を作ってしまえば、子から返ってきたものをその場で自分の左右へ差し込めるからです。
自分を先に作ってから、子に降りる
Python
def copy_tree(node):
if node is None:
return None
fresh = Node(node.value)
fresh.left = copy_tree(node.left)
fresh.right = copy_tree(node.right)
return freshJavaScript
function copyTree(node) {
if (node === null) return null;
const fresh = new Node(node.value);
fresh.left = copyTree(node.left);
fresh.right = copyTree(node.right);
return fresh;
}自分、左、右。この順が pre-order です。fresh を先に作っているので、子の複製が返ってきた瞬間に行き先が決まります。置き場も、あとで組み立て直す処理も要りません。
書き出した順に、そのまま読み戻せる
保存にも同じ順が向いています。木をファイルへ書き出すとき根から先に書いておけば、読み込む側は 1 つ目を根にして、続きを子として足していくだけで形が戻ります。葉から並べた列を渡されても、どれが誰の子だったかは分かりません。
たとえば [1, 2, 3, None, 4] の木を保存するなら、空の子をすべて書き出して 1, 2, 空, 4, 空, 空, 3, 空, 空 とします。各ノードの後には左と右の記録が必ず続き、空はそこで枝を終える印なので、先頭から同じ形を作り直せます。読む側は「今から作るのは誰の左か右か」だけを覚えていればよく、木全体を一度メモリへ広げる必要もありません。
ls -R や find の出力も同じです。親フォルダの名前が先に出て、その中身が続きます。人がフォルダを開いていく順そのもので、上から順に読み下せる表示はたいていこの順で作られています。
保存と違い、今回の演習は値だけを集める走査です。つまずきやすいのは、空の場所まで結果に混ぜてしまうことです。子が無い場所を訪問して何かを残すと、木に存在しない値が並びます。行き止まりでは何も残さずに戻る、を守ってください。件数がノード数と合わないときは、まずそこを疑います。
演習の visitPreorder(tree, i, result) は外側の関数と同じ段に置きます。木、添字、結果のリストをすべて引数で渡すので、入れ子の関数は使いません。result.append(...) は渡されたリストへ値を一つ加える操作です。根からの呼び出しは用意済みで、書くのは空の場所で止める条件と訪問順です。
要件
- tree は BFS 順の配列で、null (Python では None) は欠損ノードを表す
- 用意済みの visitPreorder の中で再帰により指定の訪問順を実装する
- 戻り値は訪問順の値の配列。null は結果に含めない