二分木の可視化＆走査計算

木の演習問題やコーディング面接では、二分木を、nullを含むレベル順のリスト[1, 2, 3, null, 4]として与えるか、値を1つずつ二分探索木に挿入する形で説明します。このツールは、どちらの形式からでも木を作成して描画し、先行順・中間順・後行順・レベル順の走査結果とともに、高さ、葉の数、そしてBST・平衡・完全・full・perfectかどうかを示します。BSTに値を挿入・削除して結果を見ることもできます。

使い方

1. 木の与え方を選びます。nullを含むレベル順のリスト、またはBSTに挿入する値です。
2. 値をカンマか空白で区切って入力します。
3. 必要なら、値を挿入または削除します（二分探索木のみ）。
4. 走査結果、図、性質の表を確認します。

計算式

先行順 = 根、左、右 · 中間順 = 左、根、右 · 後行順 = 左、右、根 · レベル順 = 幅優先、左から右

レベル順のリストでは、各ノードが次の2つの要素を左右の子として受け取り、LeetCodeと同様にnullは存在しない子を表します。BSTへの挿入は、小さい値は左、大きい値は右へ進み、重複は読み飛ばします。子が2つあるノードの削除では、中間順の後続（または先行）をそのノードにコピーし、そのノードを削除します。値がすべて数値のときは数値として、そうでなければテキストとして比較します。高さは辺の数を数えるため、ノード1つの高さは0です。

計算例

サンプルは、Wikipediaの木の走査の記事にある木で、根はFです。先行順はF B A D C E G I H、中間順はA B C D E F G H I（整列しているのでBST）、後行順はA C E D B H I G F、レベル順はF B G A D I C E Hです。ノードは9個、葉は4個（A、C、E、H）、高さは3で、Gに左の子がないのにIが埋まっているため、完全ではありません。