wyszukiwanie elementu w drzewie binarnym

Question

Mam problem z napisaniem funkcji wyszukującej element o zadanym kluczu.
Macie pomysł jaki jest błąd w tej rekurencji?

Tree* search(Tree *root, int x)
{
	if (root == NULL) return NULL;
	if (root->key == x) return root;
	if (root->left) search(root->left, x);
	if(root->right) search(root->right, x);
}

 

Answer 1

przede wszystkim nie sprawdzaj czy lewy i prawy wskaźnik istnieją tylko

Tree* search(Tree *root, int x)

{

if (root == NULL) return NULL;

if (root->key == x) return root;

if (root->key<x) search(root->left, x);///tu możesz dać else

if(root->key>x) search(root->right, x);
}
 

if (root->left) taki zapis odpowiada if(root->left!=NULL)

Comments

Tylko, że nie jest to drzewo BST, tylko po prostu drzewo binarne, więc niekoniecznie element o mniejszym kluczu będzie po lewej, co komplikuje problem. :(

Answer 2

To zwraca NULL?

Answer 3

sorki myślałem że chodzi o uporządkowane, ale jeśli nie jest uporządkowane to najlepiej dać wszystkie elementy do listy i po niej szukać, nieuporządkowane drzewo traci swoje właściwości niskiej złożoności obliczeniowej

 

to co napisałeś nie bedzie działać, bo napodkanie returna wcale nie kończy innych rekurencji które wywołałeś

pozdrawiam

Comments

masz rację, właśnie myślałem że return wyjdzie mi z funkcji, ale okazuje się że zostaną jeszcze inne wywołane przed nią i nie wiadomo bardzo co z tym zrobić.

Niestety, szukanie po liście mi nie wystarczy, bo muszę zbudować konkretne drzewo w celu dekompresji pliku.

Pozdrawiam

Answer 4

Ja bym próbował w taki sposób:

Tree* search(Tree *root, int x)
{
    if (root == NULL) return NULL;
    if (root->key == x) return root;
     
    if (root->left)
    {
         Tree* l = search(root->left, x);
    }
    
    if(l !=NULL)
    {
         return l;
    }

    if (root->right)
    {
         Tree* l = search(root->right, x);
    }
    else
    {
         return NULL;
    }

    if(r !=NULL)
    {
         return r;
    }

    return NULL;
}

Nie jestem pewien czy będzie w tej formie działeć. Teraz nie mam jak tego sprawdzić. Jednak koncepcyjnie jest w porządku.