0

次のようなツリーがあるとします。

          8
     3         12
  4     5    6   15
1  2

3 を削除したい場合は、それを一番左のノード (この場合は 1) に置き換えます。その図では、2 が 4 に接続されます。

これをどのようにコーディングしますか？

なんらかのループで左端までトラバースし続けてから、各ポインターを適切にリセットする必要があることはわかっています。また、最後の左側のノードが右側の子を持つ場合も考慮する必要があります。

4

1 に答える 1

0

「方法」に取り組む前に、次の 2 つのことを確認してください。

(1) - これはマイナーです。この質問は、単純な二分木ではなく、二分探索木 (BST) のコンテキストでのみ意味があります。3 と 4 が入れ替わっているため、このツリーは BST ではありません。

(2) - BST で削除を実行し、結果のツリーも BST になるようにツリーを「修正」したい場合はいつでも、次の 2 つの選択肢があります。削除するノードの左側のサブツリー、または (b) 削除するノードの右側のサブツリーで最小値を選択し、それを削除するノードと入れ替えます。(これらのオプションが両方とも BST を残す理由を納得させる必要があります)。あなたの例 (3 と 4 が正しく配置されている) では、これは 4 を 3 または 5 のいずれかと交換することを意味します。

では「やり方」について。上記からオプション (a) を選択したとしましょう。あなたがする必要があるのは、4 から始めて 1 ステップ左に移動し、可能な限り右にトラバースする関数を作成することです (なぜこれが正しいのかを自分自身で納得させる必要があります)。右に移動できなくなったら、左のサブツリーで最大値を見つけたことがわかります。次に、削除するノードの代わりにこの値を交換し、取得したばかりの値を持つノードを削除します。

ここで示したツリーのコーディング方法を理解していれば、これは実際には非常に簡単にコーディングできます。コード固有の質問がある場合は、詳細を記入してください

于 2012-08-21T23:52:22.360 に答える