Wyszukiwanie rodzica w drzewie BST

0

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?

0

Skoro potrzebujesz tego to zastanów się czy nie dodać jako dodatkowe pole:

struct node { int key; struct node *left,*right,*parent; };
struct node *getParent(struct node *root,int key)
  {
   struct node *parent=NULL;
   while(root)
     {
      if(root->key>key) root=(parent=root)->left;
      else if(root->key<key) root=(parent=root)->right;
      else return parent;
     }
   return NULL; // ewentualnie parent wtedy to będzie miejsce gdzie należy dodać ten klucz.
  }
0

Dzieki, zaraz sprobuje.

Przy dodawaniu wszystko jest raczej ok, bo inorder i proste wyswietlanie struktury drzewa pokazuje dobrze.

Dodawanie mam tak zrobione:

void add(struct node **node,int key)
{
    if(!*node)
    {
        struct node *temp=malloc(sizeof(struct node));
        temp->key=key;
        temp->left=temp->right=NULL;
        *node=temp;
    }
    else if((*node)->key == key)
    {
        printf("Element jest juz w drzewie!\n");
    }
    else if((*node)->key > key)
       return add(&(*node)->left,key);
    else
       return add(&(*node)->right,key);
}

Ale teraz to nie jestem juz niczego pewien i sie zaczalem zastanawiac czy to jest dobrze

0

mialem wszystko pomieszane... na lewo dawalem wieksze a na prawo mniejsze... /facepalm

0

Jeżeli nie równoważysz drzewa na bieżąco to lepiej zapomnij o rekurencyjnym wywołaniu, tym bardziej da się to zrobić w normalnej pętle.

0

Wiem, ale nie wprowadzam duzo danych wiec stos sie nie przepelni.

Cos mi sie ciagle to miesza...

Moglbys sprawdzic czy to dodawanie co wczesniej wstawilem jest dobre?

void add(struct node **node,int key)
{
    if(!*node) //jesli wezel pusty to wstaw tutaj nowy
    {
        struct node *temp=malloc(sizeof(struct node));
        temp->key=key;
        temp->left=temp->right=NULL;
        *node=temp;
    }
    else if((*node)->key == key)
    {
        printf("Element jest juz w drzewie!\n");
    }
    else if((*node)->key > key) 
       return add(&(*node)->left,key); //jesli klucz sprawdzanego wezla wiekszy od wstawianego klucza to dodaj gdzies w lewym poddrzewie(w lewym poddrzewie elementy mniejsze)
    else
       return add(&(*node)->right,key); //w przeciwnym razie dodaj gdzies w prawym poddrzewie
}
0

Na 100% złe, ponieważ:

  1. W dwóch przypadkach na cztery brak return
  2. W jednym z przypadków funkcja maże po wyjściu standardowym
  3. Użyta rekurencja w nierównoważonym drzewie

1 użytkowników online, w tym zalogowanych: 0, gości: 1