Probuje napisac funkcje do wyszukiwania rodzica w drzewie bst.
Struktura wezla:
struct node{
int key;
struct node *left,*right;
}
Mam taki kod:
struct node* getParent(struct node *root,int key)
{
while(1)
{
if(root->left)
{
if(root->left->key == key)
return root;
}
if(root->right)
{
if(root->right->key == key)
return root;
}
root = (key > root->key) ? root->left : root->right;
}
};
Key w deklaracji funkcji to wartosc okreslajaca dla jakiego elementu w drzewie szukamy rodzica.
Ale po wywolaniu funkcji getParent program mi sie wiesza.
Wiem ze to dla korzenia nie bedzie dzialac. Dla uproszczenia zakladam ze wezel o podanym key istnieje w drzewie.
Jak zamienilem :
root = (key > root->key) ? root->left : root->right;
na
root = (key > root->key) ? root->right : root->left;
To dziala -.-
Ale dlaczego? Przeciez jesli klucz jest wiekszy od klucza wezla to powinienem dalej przeszukiwac lewe poddrzewo?