[C++][C] Wstawianie elementu do drzewa binarnego.

[koniczynka_92]

Bardzo proszę o pomoc w rozwiązaniu zadania :

Dane jest drzewo binarne, w którym elementy są rozmieszczone w taki sposób, że dla każdego węzła v spełnione zależności:

A: jeśli (v-> lewy!=NULL) to v-> klucz >=v->lewy ->klucz
B: jeśli (v-> prawy!=NULL) to v-> klucz >=v->prawy ->klucz

Zaimplementuj (w języku C/C++) operację void wstaw (int klucz) wstawiania elementu o zadanym kluczu do tego drzewa tak, aby własności A i B pozostały spełnione dla każdego węzła w tym drzewie.

[Chromosom]

Proponuję zastosować pętlę while, w której będziesz porównywać klucz elementu wstawianego oraz klucze elementów już istniejących.

[Gouranga]

w warunkach masz nieścisłość, załóżmy, że klucz o tej samej wartości będę wrzucać do prawego syna

ja zaproponuję rekurencję, załóżmy, że węzły drzewa to struktury typu BST:

Kod: Zaznacz cały

void insert(int key, BST *v){
  if (v == NULL) {
    //jeśli drzewo jest puste
    v = (BST*)malloc(sizeof(BST*));
    v->klucz = (int)malloc(sizeof(int));
    v->lewy = NULL;
    v->prawy = NULL;
    v->klucz = key;
  } else {
     //jeśli drzewo nie jest puste
     if ( key < v->klucz) {
       // wstawiamy mniejszy
       insert(key, v->lewy);
     } else {
        //wstawiamy większy lub równy
       insert(key, v->prawy);
     }
  }
}

tylko trzeba pamiętać, żeby założyć to drzewo

Kod: Zaznacz cały

typedef struct BST {
  int klucz;
  struct BST *lewy;
  struct BST *prawy;
} BST;

BST *root = NULL;

i każdorazowo wywoływać insert podając korzeń:

Kod: Zaznacz cały

insert(wartość, root)