logo

Wprowadzenie

Funkcja wstawiania służy do dodania nowego elementu w drzewie wyszukiwania binarnego w odpowiednim miejscu. Funkcja wstawiania ma być tak zaprojektowana, aby przy każdej wartości węzeł naruszał właściwość drzewa poszukiwań binarnych.

  1. Przydziel pamięć dla drzewa.
  2. Ustaw część danych na wartość i ustaw lewy i prawy wskaźnik drzewa, wskaż NULL.
  3. Jeśli wstawiany element będzie pierwszym elementem drzewa, to lewy i prawy róg tego węzła będzie wskazywał NULL.
  4. W przeciwnym razie sprawdź, czy element jest mniejszy niż element główny drzewa, jeśli to prawda, to rekurencyjnie wykonaj tę operację z lewej strony korzenia.
  5. Jeśli to fałsz, wykonaj tę operację rekurencyjnie z prawym poddrzewem korzenia.

Wstaw (DRZEWO, ELEMENT)

    Krok 1:JEŚLI DRZEWO = NULL
    Przydziel pamięć dla DRZEWA
    USTAW DRZEWO -> DANE = ELEMENT
    USTAW DRZEWO -> LEWO = DRZEWO -> PRAWO = NULL
    W PRZECIWNYM RAZIE
    JEŚLI DANE POZYCJI
    Wstaw(DRZEWO -> LEWO, ELEMENT)
    W PRZECIWNYM RAZIE
    Wstaw(DRZEWO -> PRAWO, ELEMENT)
    [KONIEC JEŚLI]
    [KONIEC JEŚLI]Krok 2:KONIEC

wstawienie do drzewa wyszukiwania binarnego

Funkcja C

 #include #include void insert(int); struct node { int data; struct node *left; struct node *right; }; struct node *root; void main () { int choice,item; do { printf('
Enter the item which you want to insert?
'); scanf('%d',&item); insert(item); printf('
Press 0 to insert more ?
'); scanf('%d',&choice); }while(choice == 0); } void insert(int item) { struct node *ptr, *parentptr , *nodeptr; ptr = (struct node *) malloc(sizeof (struct node)); if(ptr == NULL) { printf('can't insert'); } else { ptr -> data = item; ptr -> left = NULL; ptr -> right = NULL; if(root == NULL) { root = ptr; root -> left = NULL; root -> right = NULL; } else { parentptr = NULL; nodeptr = root; while(nodeptr != NULL) { parentptr = nodeptr; if(item data) { nodeptr = nodeptr -> left; } else { nodeptr = nodeptr -> right; } } if(item data) { parentptr -> left = ptr; } else { parentptr -> right = ptr; } } printf('Node Inserted'); } } 

Wyjście

 Enter the item which you want to insert? 12 Node Inserted Press 0 to insert more ? 0 Enter the item which you want to insert? 23 Node Inserted Press 0 to insert more ? 1