私は、主に再帰を実装し、使用した特定のコーディング要素の理解を確認するための学習演習として、BSTからノードを再帰的に削除するコードを記述していました。この場合、問題は参照によって私のBSTノードにポインターを渡すことにあるようです。
私のBSTコードのpsrtは次のとおりです。（これは、私が実装または使用するもののコードではありません。単なる演習です。言語で試してみたいいくつかのことを実装するための例として、BSTを選択しました）
ヘッダー-
//BST.h
class TNode
{
public:
TNode():data(0), left(0), right(0) {}
int data;
TNode* left;
TNode* right;
};
class BST
{
private:
TNode* Head;
public:
BST();
void InsertData(int data);
void InsertNode(TNode* node);
void DeleteData(int data);
private:
void InsertDataPrivate(int data, TNode* &root);
void InsertNodePrivate(TNode* node, TNode* &root);
void DeleteDataPrivate(int data, TNode* &root);
};
CPP-
//BST.cpp
#include "BST.h"
BST::BST(): Head(0)
{
}
void BST::InsertData(int data)
{
InsertDataPrivate(data, Head);
}
void BST::InsertNode(TNode* node)
{
InsertNodePrivate(node, Head);
}
void BST::DeleteData(int data)
{
DeleteDataPrivate(data, Head);
}
void BST::InsertDataPrivate(int data, TNode* &root)
{
if(root == 0)
{
root = new TNode();
root->data = data;
}
else if(data < root->data) InsertDataPrivate(data, root->left);
else if(data > root->data) InsertDataPrivate(data, root->right);
}
void BST::InsertNodePrivate(TNode* node, TNode* &root)
{
if(root == 0) // Deep Copy
{
root = new TNode();
root->data = node->data;
}
else if(node->data < root->data) InsertNodePrivate(node, root->left);
else if(node->data > root->data) InsertNodePrivate(node, root->right);
}
void BST::DeleteDataPrivate(int data, TNode* &root)
{
if( 0 == root ) return;
if( root->data == data )
{
if(0 == root->left && 0 == root->right)
{
delete root;
root = 0;
}
else if(0 == root->left)
{
TNode* current = root;
root = root->right;
delete current;
current = 0;
}
else if(0 == root->right)
{
TNode* current = root;
root = root->left;
delete current;
current = 0;
}
else
{
TNode* biggestOnLeft = root->left;
TNode* smallestOnRight = root->right;
int i = 0;
while (biggestOnLeft->right) // check if left subtree is longer than right subtree
{
biggestOnLeft = biggestOnLeft->right;
--i;
}
while (smallestOnRight->left)
{
smallestOnRight = smallestOnRight->left;
++i;
}
if(i < 0) // left subtree is longer than right subtree
{
root->data = biggestOnLeft->data;
DeleteDataPrivate(biggestOnLeft->data, biggestOnLeft);
}
else // right subtree is longer than or equal in size to left subtree
{
root->data = smallestOnRight->data;
DeleteDataPrivate(smallestOnRight->data, smallestOnRight);
}
}
}
else if(data < root->data && 0 !=root->left)
{
DeleteDataPrivate(data, root->left);
}
else if(data > root->data && 0 !=root->right)
{
DeleteDataPrivate(data, root->right);
}
}
私のテストコードは次のとおりです-
//TestMain.cpp
#include "stdafx.h"
#include "BST.h"
int _tmain(int argc, _TCHAR* argv[])
{
BST bst;
bst.InsertData(32);
bst.InsertData(46);
bst.InsertData(3463);
bst.InsertData(32);
bst.InsertData(856);
bst.InsertData(8098);
bst.InsertData(345);
bst.InsertData(234554);
bst.InsertData(77);
bst.InsertData(9);
bst.InsertData(15);
bst.InsertData(390);
bst.InsertData(350);
bst.InsertData(400);
bst.InsertData(76);
bst.InsertData(78);
bst.InsertData(355);
bst.DeleteData(77);
return 0;
}
bst.DeleteData(77);私が問題を抱えていると言う最後のステップで。'77'のノードは正常に削除され、BSTから2つの子を持つノードを削除する方法で'78'に置き換えられます。ただし、「77」の親ノードを削除する前に「78」のノードを削除した後も、null以外の場所を指しています。
DeleteDataPrivate(int data, TNode* &root);削除後にTNodeポインタをNULLに設定するプライベート関数を呼び出しています。また、関数で参照ごとのポインターを渡して、再帰スタックが展開されるときにNULL値が削除されたノードポインターに割り当てられるようにします。これは起こりません。誰かが私がここで間違っていることを説明できますか？
ありがとうございました。
チンメイ
アップデート
以下のDanのコメントによると、問題は、ポインタのコピーを作成し、何にも割り当てられていないローカル変数に値が渡されることでした。ポインタからポインタを使用してこれを説明するように関数を変更し、巻き戻し再帰によって返されるTNodeポインタの値が、TNodeポインタのコピーではなく、メモリ内の正しい場所に格納されるようにしました。
変更された機能は次のとおりです
void BST::DeleteDataPrivate(int data, TNode* &root)
{
if( 0 == root ) return;
if( root->data == data )
{
if(0 == root->left && 0 == root->right)
{
delete root;
root = 0;
}
else if(0 == root->left)
{
TNode* current = root;
root = root->right;
delete current;
current = 0;
}
else if(0 == root->right)
{
TNode* current = root;
root = root->left;
delete current;
current = 0;
}
else
{
TNode* biggestOnLeft = root->left;
TNode* smallestOnRight = root->right;
int i = 0;
while (biggestOnLeft->right) // check if left subtree is longer than right subtree
{
biggestOnLeft = biggestOnLeft->right;
--i;
}
while (smallestOnRight->left)
{
smallestOnRight = smallestOnRight->left;
++i;
}
TNode** locationOfDeletedNode = 0;
if(i < 0) // left subtree is longer than right subtree
{
locationOfDeletedNode = &(root->left);
while(*locationOfDeletedNode != biggestOnLeft) locationOfDeletedNode = &((*locationOfDeletedNode)->right);
}
else // right subtree is longer than or equal in size to left subtree
{
locationOfDeletedNode = &(root->right);
while(*locationOfDeletedNode != smallestOnRight) locationOfDeletedNode = &((*locationOfDeletedNode)->left);
}
root->data = (*locationOfDeletedNode)->data;
DeleteDataPrivate((*locationOfDeletedNode)->data, *locationOfDeletedNode);
}
}
else if(data < root->data && 0 !=root->left)
{
DeleteDataPrivate(data, root->left);
}
else if(data > root->data && 0 !=root->right)
{
DeleteDataPrivate(data, root->right);
}
}
もちろん、これはより適切に構成することができますが、ここでの私の目標は、ここで単純だがトリッキーなことを学ぶことでした。ダンや他の人たちのおかげで、ここでそれを行いました。