Drzewo wyszukiwania binarnego C ++

BST to struktura danych, która utrzymuje dane na posortowanej liście. Jest znany jako binarne drzewo wyszukiwania, ponieważ na drzewie każdy węzeł ma maksimum dwojga dzieci, którego nie można dalej zwiększyć. Jest to znane jako drzewo wyszukiwania, ponieważ służy do wyszukiwania lub znalezienia dowolnego obecnego elementu. Wdrożymy to zjawisko w języku C ++.

Realizacja

W implementacji pierwszym krokiem jest użycie struktury do inicjalizacji klucza typu liczb całkowitych i węzłów lewej i prawej. Węzły te są zdefiniowane za pomocą wskaźnika zmiennego, ponieważ oba zapisują adresy alternatywnych węzłów. Następnie zamykamy strukturę.

Ponownie utworzymy nowy węzeł za pośrednictwem struktury. Parametr funkcji będzie zawierać dane, które chcemy wprowadzić w węźle.

Node struct *newNode (int Item)

Utworzy nową temperaturę węzła, która będzie przechowywać w nim dane, a rozmiar pamięci zostanie przydzielony przez Malloc (). Dodamy wartość elementu w kluczowej części węzła. Podczas gdy lewe i prawe części, które są wcześniej zadeklarowane w strukturze, są teraz zadeklarowane jako zerowe, ponieważ jest to pierwszy węzeł. Temp zostanie zwrócony.

Utworzona jest funkcja o nazwie „inorder” i zaakceptuje węzeł główny w parametrze. Jak wiemy, drzewo zawiera trzy główne części: węzeł, po lewej i prawej stronie drzewa. Użyjemy podnośnika IF, aby sprawdzić, czy korzeń nie jest zerowy. Następnie wywołaj funkcję i wyślij lewą część korzenia. To wyświetli sam główny root ze strzałką, która będzie oznaczała kierunek ścieżki na drzewie. Następnie, aby przejść w prawo, wywołaj funkcję zinter z prawem korzenia jako parametr.

Inorder (root -> po lewej)

W ten sposób wykonywane jest przemieszczanie władzy. Aby wstawić nowy węzeł do drzewa, użyjemy funkcji, która przyjmie węzeł i klucz jako wartości parametrów. Jeśli drzewo jest już puste, nowy węzeł zostanie zwrócony. W drugim przypadku, jeśli drzewo nie jest puste, najpierw przejdź na prawą stronę i wstaw tutaj nowy węzeł. Do wstawienia użyjemy instrukcji IF-ELSE, aby sprawdzić zamówienie dla klucza. Nowy klucz przejdzie na lewą stronę w celu wznoszenia. Jeśli część, która sprawdzi nowy klucz, jest już niższa niż wartość obecna w węźle, wprowadź klucz do lewej części węzła.

Węzeł -> lewy = wstaw (węzeł -> lewy, klucz)

Podczas gdy jeśli klucz jest większy, przejdzie do właściwej części.

Po wstawieniu węzła sprawdzimy następny węzeł lub węzeł, który jest następcą. Tworzona jest funkcja wartości min, która utworzy nowy węzeł o nazwie *. Ten węzeł zostanie przypisany przez wartość przekazaną jako argument funkcji. Najpierw znajdzie węzeł narożny lub liść lewego trybu po lewej stronie drzewa. Używamy pętli, która iteruje, dopóki nie zakończy się przemieszczenie węzła. Innymi słowy, lewa część bieżącego węzła nie jest zerowa.

Prąd = prąd -> lewy

Przypisuj bieżący węzeł wartość następnego prądu wewnątrz pętli po lewej stronie.

Nasze drzewo jest przemierzane i zorganizowane przez dodanie liści po obu stronach. Każda wartość zostanie wstawiona przez wywołanie funkcji wykonane z programu głównego. Teraz musimy wyszukać dowolny element i usuniemy go po jego znalezieniu.

Drzewo w C ++ działa na tym samym zjawisku, co lista połączona. Zastosujemy wyszukiwanie binarne na drzewie i wykonamy operację usuwania, aby usunąć jeden węzeł lub liść z drzewa. Tworzona jest funkcja węzła usuwania; będzie zawierał drzewo i wartość jako parametry. Najpierw sprawdzimy, że drzewa muszą mieć w sobie wartości. Zatem zostanie użyte, a jeśli korzeń jest zerowy, oznacza to zwrócenie tylko korzenia.

If (klucz klucza)

Klucz, który chcesz usunąć, jest mniejszy niż węzeł główny. Następnie przejdź na lewą stronę i wywołaj funkcję usuwania lewą częścią drzewa, a klucz do usunięcia.

Root -> left = deleTenode (root -> lewy, klucz);

I to samo dotyczy części else-jeśli. Jeśli klawisz jest większy niż klawisz węzła, przejdź do właściwej ścieżki, wywołaj funkcję Usuń. Przejdź odpowiednią część drzewa i klucz, aby łatwo było znaleźć węzeł, który chcesz usunąć.

Teraz, zbliżając się do części innej, ma zastosowanie, jeśli węzeł jest sam, nie ma jeszcze liści lub ma przed sobą tylko jedno dziecko. Wewnątrz części else ponownie, jeśli zostanie użyte instrukcja, która sprawdzi, czy po prawej stronie nie ma węzła, dodaj wartość po prawej stronie węzła do nowego węzła tymczasowego, podobnie dla lewej strony.

Struct node * temp = root -> lewy;

W tym stanie uwolnij korzeń. To usunie wartość z korzenia.

Wolny (root);

Jeśli jakikolwiek węzeł zawiera z nim dwa liście, aby przeszukać wartość, użyjemy funkcji wartości min, a właściwa część zostanie wysłana do funkcji.

MinValuenode (root -> right);

Po znalezieniu wartości do usunięcia, ogłosimy ją ostatnią częścią drzewa, aby można było go łatwo usunąć.

Root -> key = temp -> klucz;

Po wykonaniu tego usuń węzeł,

Root -> right = usuń węzeł (węzeł -> right, temp -> klucz);

Po zamknięciu funkcji zadeklarujemy główny program tutaj. Węzeł główny zostanie początkowo ustawiony jako null. Korzystając z wywołania funkcji INSERT (), użyjemy danych root i liczby do węzła.

Wstaw (root, 5);

Funkcja inorienta jest wywoływana do przemieszczania drzewa.

Inorder (root);

Następnie, aby usunąć węzeł, wywołamy funkcję Usuń.

Root = deleTenode (root, 10);

Po usunięciu wartości są ponownie wyświetlane.

Po napisaniu kodu wykonamy go w terminalu Ubuntu za pośrednictwem kompilatora.

$ g ++ -o plik pliku.C
$ ./plik

Jak widać, siedem elementów jest wprowadzanych do węzła. Jeden jest usunięty, a reszta będzie wyświetlana w takiej samej kolejności, jak poprzednio.

Wniosek

Drzewo wyszukiwania binarnego służy do przechowywania wartości w sortowanej formie. Aby wyszukać dowolny numer, wszystkie liczby muszą być sortowane najpierw w kolejności. Następnie określony numer jest przeszukiwany przez podzielenie drzewa na dwie części, tworząc poddrzewa. Implementacja BST odbywa się w systemie Ubuntu, wyjaśniając przykład w opracowany sposób. Mamy nadzieję, że ten artykuł jest pomocny. Sprawdź inne artykuły z Linux, aby uzyskać więcej wskazówek i samouczków.