Wstawianie 4 lub 5 liczb w drzewie binarnym, ale uzyskanie tylko 3 liczb na wyjściu

Question

Jest to część laboratorium szkolnego zajmującego się rekurencją i drzewem binarnym. Jeśli pójdę wstawić 4 lub 5 liczb i wyprowadzę wynik, otrzymam 3 numery z powrotem. Oto kod do wkładki:

Node *insert(Node *t, int key) { 
    Node *insertParent; 
    Node *result=NULL; 

    if (t!=NULL) { 
     result=search(t,key,insertParent); 
    } else { 
     t=new Node; 
     t->data=key; 
     t->leftchild=NULL; 
     t->rightchild=NULL; 
     return t; 
    } 

    if (result==NULL) { 
     if (insertParent->data>key) { 
      insertParent->leftchild=new Node; 
      insertParent->leftchild->data=key; 
      insertParent->leftchild->leftchild=NULL; 
      insertParent->leftchild->rightchild=NULL; 
      return insertParent->leftchild; 
     } else if (insertParent->data<key) { 
      insertParent->rightchild=new Node; 
      insertParent->rightchild->data=key; 
      insertParent->rightchild->leftchild=NULL; 
      insertParent->rightchild->rightchild=NULL; 
      return insertParent->rightchild; 
     } 
    } else 
     return NULL; 
} 

Ale wierzę, że problem jest w funkcję wyszukiwania, a konkretnie wskaźnik węzeł odnośnikiem rodzica:

Node* search(Node *t, int key, Node *&parent) { 
    if (t!=NULL) { 
     parent=t; 
     if (t->data==key) 
      return t; 
     else if (t->data>key) 
      return search(t->leftchild,key,t); 
     else 
      return search(t->rightchild,key,t); 
    } else 
     return NULL; 
} 

Mam funkcję, która wyprowadza drzewo i mieć Sprawdziłem to na drzewie, które zbudowałem ręcznie i działa dobrze:

void inorder(Node *t) 
{ 
    if (t!=NULL) { 
     if (t->leftchild!=NULL) 
      inorder(t->leftchild); 

     cout << t->data << ", "; 

     if (t->rightchild!=NULL) 
      inorder(t->rightchild);      
    } 
} 

Nie szukam odpowiedzi, szukając tylko obszaru, który powinienem obejrzeć.

Answer 1

Odkryłem, że mój problem dotyczy funkcji wyszukiwania. Miało to związek z referencyjną zmienną węzła nadrzędnego. Musiałem użyć instrukcji four else/ifelse, aby móc zdecydować, którą drogę wybrać, rekurencyjnie lub nie.

Node* search(Node *t, int key, Node *&parent) { 
    if (t!=NULL) { 
     if (t->data==key) { 
      parent=NULL; 
      return t; 
     } else if (t->data>key && t->leftchild!=NULL) { 
      return search(t->leftchild,key,parent); // think this needs returned 
     } else if (t->data>key && t->leftchild==NULL) { 
      parent=t; 
      return NULL; 
     } else if (t->data<key && t->rightchild!=NULL) { 
      return search(t->rightchild,key,parent); //think this needs returned 
     } else if (t->data<key && t->rightchild==NULL) { 
      parent=t; 
      return NULL; 
     } 
    } else { 
     parent=NULL; 
     return NULL; 
    } 
} 

Ta zmiana funkcji wyszukiwania konieczność zmiany funkcji insert:

Node *insert(Node *t, int key) { 
    Node *insertParent=NULL; 
    Node *result=NULL; 

    if (t!=NULL) { 
     result=search(t,key,insertParent); 
    } else { 
     t=new Node; 
     t->data=key; 
     t->leftchild=NULL; 
     t->rightchild=NULL; 
     return t; 
    } 

    if (insertParent==NULL && result!=NULL) { 
     return NULL; 
    } else if (insertParent!=NULL && result==NULL) { 
     //key not found need to add 
     if (insertParent->data>key) { 
      insertParent->leftchild=new Node; 
      insertParent->leftchild->data=key; 
      insertParent->leftchild->leftchild=NULL; 
      insertParent->leftchild->rightchild=NULL; 
      return insertParent->leftchild; 
     } else { 
      insertParent->rightchild=new Node; 
      insertParent->rightchild->data=key; 
      insertParent->rightchild->leftchild=NULL; 
      insertParent->rightchild->rightchild=NULL; 
      return insertParent->rightchild; 
     } 
    } 
} 

Dziękujemy wszystkim, którzy pomogli ...

(także: I odpowiedział na moje własne pytanie. Czy to, co powinienem zrobić, czy powinienem edytować mój wpis? Pomyślę, że ludzie woleliby zobaczyć cały proces i nie kazali mi usunąć starego niedziałającego kodu ...)

Answer 2

Twoje podejrzenie jest prawidłowe. Śledzenie, jak parametr "nadrzędny" najwyższego poziomu jest aktualizowany po przeszukaniu więcej niż jednego węzła.

Answer 3

Node* search(Node *t, int key, Node *&parent) 
{ 
    if(t!=NULL) 
    { 
    parent=t; 
    if (t->data==key) 
     return t; 

    else if (t->data>key) 
     return search(t->leftchild, key, parent); // use “parent” because you want to assign parent to this variable 

    else 
     return search(t->rightchild,key, parent); 
    } 
    else  return NULL; 

}