Dzień dobry, chcę napisać iteracyjnie drzewo BST - zrobiłem dodawanie, które działa poprawnie, ale mam problem z funkcją usuwającą (na razie tylko przypadek, gdy usuwany węzeł nie ma potomków, lub ma tylko jednego). Otóż funkcja nie działa, gdy próbuję usunąć korzeń posiadający potomka - przy usuwaniu innych węzłów wszystko jest OK. Chyba robię coś źle z tym "parentem", ale nie wiem co.
Kod:
struct BstNode
{
int data;
BstNode *left, *right;
};
BstNode* GetNewNode(int data)
{
BstNode* newNode = new BstNode();
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
void Insert(BstNode** root, int data)
{
BstNode ***current = &root;
while (**current)
{
if((**current)->data == data)
{
cout <<"element jest juz w drzewie!" <<endl;
return;
}
if (data < (**current)->data)
{
*current = &(**current)->left;
}
else
{
*current = &(**current)->right;
}
}
**current = GetNewNode(data);
}
void Remove(BstNode **root, int key)
{
BstNode **parent, ***p; // p - usuwany wezel
parent=NULL;
p=&root;
while((**p!=NULL) && (key!=(**p)->data))
{
parent=&(**p);
if((**p)->data < key) *p=&(**p)->right;
else *p=&(**p)->left;
}
if((**p)==NULL)
{
cout << "brak elementu! " <<endl;
return;
}
if(((**p)->right)==NULL && (**p)->left==NULL) //lisc
{
if((**p)==*root)
{
*root=NULL;
return;
}
if((*parent)->right==(**p))
(*parent)->right = NULL;
else (*parent)->left = NULL;
return;
}
if(((**p)->right)==NULL ) //usuwany wezel ma tylko lewe poddrzewo
{
if((*parent)->right== (**p))
(*parent)->right = (**p)->left;
else
(*parent)->left = (**p)->left;
return;
}
if(((**p)->left)==NULL ) //usuwany wezel ma tylko prawe poddrzewo
{
if((*parent)->right==(**p))
(*parent)->right = (**p)->right;
else
(*parent)->left = (**p)->right;
return;
}
}
int main()
{
BstNode* root = NULL;
Insert(&root,9);
/* ... */
Remove(&root, 9);
}