バイナリ検索ツリーからノードを削除するメソッドを作成したいと思います。BST削除ノードメソッドがツリーの残りの部分を切り捨てる
これは私の方法である:
public void remove(Node node)
\t //Removes a given node and puts one of the nodes below it in its place until it reaches the end
\t {
\t \t
\t \t if (node.left != null) //If the node to the left is not empty
\t \t {
\t \t \t node.value = node.left.value; //Moves up the left node to take its place
\t \t \t remove(node.left); //Goes to the next node
\t \t \t if (node.left.right == null && node.left.left == null)
\t \t \t \t node.left = null; //Removes the last node at the end of the tree after moving it up
\t \t }
\t \t else if (node.right != null)
\t \t {
\t \t \t node.value = node.right.value; //Moves up the left node to take its place
\t \t \t remove(node.right); //Goes to the next node
\t \t \t if (node.right.left == null && node.right.right == null)
\t \t \t \t node.right = null; //Removes the last node at the end of the tree after moving it up
\t \t \t
\t \t } \t
\t \t
\t }
問題はそれだけでいくつかのケースで動作しています。
のは、私が60、70、65ツリーが
50
/\
60
/ \
70
/\
65
が、その後ができます私はこれが動作しているようです60の削除を選択すると言う
ようになるはずです (ルートノードが50である)を入力します例えばましょう最初は大丈夫です。 しかし、私が信頼する検索メソッドを実行すると、そのポインタのいずれにもノードがないことが返されます。私が想定していることは、65が上に移動する前に70がヌルに設定されていることです。そして、65は技術的にもツリーに接続されていないので、検索メソッドはそれを見つけることができません。
だから、このようなものは:
50
/\
70
/ \
/\
65
問題は、私はこれが起こっする方法を理解していない、です。それが原因文が(事実ではない場合、最初の場合のステートメントは
if (node.left.right == null && node.left.left == null)
node.left = null;
。また
if (node.right.left == null && node.right.right == null)
node.right = null;
、放置しておく場合には、両方のポインタポイントは、nullにあればnullにノードを設定する必要があり、特に以来!= null)、それは単純に "else"(そして正しいものを削除)に進むべきではありませんか?
どのような提案やヒントも大歓迎です。
自分に好意を行うと、SwingコードからBSTコードを分離。 BSTの単体テストを書いて正しく動作することを確認してから、フロントエンドに接続します。 –
ここに木を作る方法は分かりませんが、オリジナルの木をとり、60の場所に65を入れてください。私はあなたが思っているような木を持つことは可能ではないと思います。 – Marichyasana
@Marichyasanaの例のツリーは正しいBSTです。あなたの変更から生じるものはそうではありません。 – Matt