c - 二分木ノードをどのように削除できますか?

Question

いくつかの整数値を使用してバイナリ ツリーを作成しました。コードでツリーを検索できます。しかし、ノードの削除操作を続行する方法がわかりません。

では、どうすればノードを削除できますか?

Answer 1

ウィキペディアのエントリ - Binary Search Tree - BST 操作の実装方法について説明しています。

削除: 考慮すべきいくつかのケースがあります。

• リーフの削除: ツリーから単純に削除できるため、子のないノードの削除は簡単です。
• 1 つの子を持つノードの削除: 削除して、その子に置き換えます。
• 2 つの子を持つノードの削除: 削除するノードを「N」と呼びます。N を削除しないでください。代わりに、順序どおりの後続ノードまたは順序どおりの先行ノード "R" のいずれかを選択します。N の値を R の値に置き換えてから、R を削除します (注: R 自体には最大 1 つの子があります)。