Drzewo binarne w C
w C, A drzewo binarne jest instancją drzewiastej struktury danych z węzłem nadrzędnym, który może posiadać maksymalnie dwa węzły podrzędne; 0, 1 lub 2 węzły potomne. Każdy pojedynczy węzeł w a drzewo binarne ma własną wartość i dwa wskaźniki do swoich dzieci, jeden wskaźnik dla lewego dziecka, a drugi dla prawego dziecka.
Deklaracja drzewa binarnego
A drzewo binarne można zadeklarować w C za pomocą obiektu o nazwie struktura który przedstawia jeden z węzłów w drzewie.
struktura węzeł {
typ danych nazwa_zmiennej ;
struktura węzeł * lewy ;
struktura węzeł * Prawidłowy ;
} ;
Powyżej znajduje się deklaracja jednego drzewo binarne nazwa węzła jako węzeł. Posiada trzy wartości; jedna to zmienna przechowująca dane, a dwie pozostałe to wskaźniki do dziecka. (lewe i prawe dziecko węzła nadrzędnego).
Fakty dotyczące drzewa binarnego
Nawet w przypadku dużych zestawów danych użycie pliku a drzewo binarne ułatwia i przyspiesza wyszukiwanie. Liczba gałęzi drzew nie jest ograniczona. W przeciwieństwie do tablicy, drzewa dowolnego rodzaju można tworzyć i powiększać w zależności od potrzeb danej osoby.
Implementacja drzewa binarnego w C
Poniżej znajduje się przewodnik krok po kroku dotyczący wdrażania a Drzewo binarne w C.
Krok 1: Zadeklaruj drzewo wyszukiwania binarnego
Utwórz węzeł struktury, który ma trzy typy danych, takie jak dane, *left_child i *right_child, gdzie dane mogą być typu całkowitego, a oba węzły *left_child i *right_child mogą być zadeklarowane jako NULL lub nie.
struktura węzeł{
int dane ;
struktura węzeł * prawe_dziecko ;
struktura węzeł * lewe_dziecko ;
} ;
Krok 2: Utwórz nowe węzły w drzewie wyszukiwania binarnego
Utwórz nowy węzeł, tworząc funkcję, która przyjmuje liczbę całkowitą jako argument i dostarcza wskaźnik do nowego węzła utworzonego z tą wartością. Użyj funkcji malloc() w C do dynamicznej alokacji pamięci dla utworzonego węzła. Zainicjuj lewe i prawe dziecko na NULL i zwróć nazwę węzła.
struktura węzeł * tworzyć ( dane typu danych )
{
struktura węzeł * Nazwa węzła = Malloc ( rozmiar ( struktura węzeł ) ) ;
Nazwa węzła -> dane = wartość ;
Nazwa węzła -> lewe_dziecko = Nazwa węzła -> prawe_dziecko = ZERO ;
powrót Nazwa węzła ;
}
Krok 3: Wstaw prawe i lewe dziecko w drzewie binarnym
Utwórz funkcje insert_left i insert_right, które przyjmą dwa wejścia, które będą wartością do wstawienia oraz wskaźnikiem do węzła, do którego zostaną podłączone oba elementy potomne. Wywołaj funkcję create, aby utworzyć nowy węzeł i przypisz zwrócony wskaźnik do lewego wskaźnika lewego dziecka lub prawego wskaźnika prawego dziecka rodzica głównego.
struktura węzeł * wstaw_lewo ( struktura węzeł * źródło , dane typu danych ) {źródło -> lewy = tworzyć ( dane ) ;
powrót źródło -> lewy ;
}
struktura węzeł * wstaw_w prawo ( struktura węzeł * źródło , dane typu danych ) {
źródło -> Prawidłowy = tworzyć ( dane ) ;
powrót źródło -> Prawidłowy ;
}
Krok 4: Wyświetl węzły drzewa binarnego za pomocą metod przechodzenia
Możemy wyświetlać drzewa za pomocą trzech metod przechodzenia w C. Te metody przechodzenia to:
1: Przechodzenie w przedsprzedaży
W tej metodzie przemierzania będziemy przechodzić przez węzły w kierunku od węzeł_nadrzędny->lewe_dziecko->prawe_potomne .
próżnia przed Sprzedaż ( węzeł * źródło ) {Jeśli ( źródło ) {
drukujf ( '%D \N ' , źródło -> dane ) ;
display_pre_order ( źródło -> lewy ) ;
display_pre_order ( źródło -> Prawidłowy ) ;
}
}
2: Przechodzenie po złożeniu zamówienia
W tej metodzie przemierzania będziemy przechodzić przez węzły w kierunku od lewe_dziecko->prawe_dziecko->węzeł_nadrzędny-> .
próżnia display_post_order ( węzeł * źródło ) {Jeśli ( drzewo_binarne ) {
display_post_order ( źródło -> lewy ) ;
display_post_order ( źródło -> Prawidłowy ) ;
drukujf ( '%D \N ' , źródło -> dane ) ;
}
}
3: Przechodzenie w kolejności
W tej metodzie przemierzania będziemy przechodzić przez węzły w kierunku od left_node->root_child->right_child .
próżnia wyświetl_w_kolejności ( węzeł * źródło ) {Jeśli ( drzewo_binarne ) {
wyświetl_w_kolejności ( źródło -> lewy ) ;
drukujf ( '%D \N ' , źródło -> dane ) ;
wyświetl_w_kolejności ( źródło -> Prawidłowy ) ;
}
}
Krok 5: Wykonaj usuwanie w drzewie binarnym
Możemy usunąć utworzone Drzewo binarne usuwając oba dzieci z funkcją węzła nadrzędnego w C w następujący sposób.
próżnia usuń_t ( węzeł * źródło ) {Jeśli ( źródło ) {
usuń_t ( źródło -> lewy ) ;
usuń_t ( źródło -> Prawidłowy ) ;
bezpłatny ( źródło ) ;
}
}
Program C drzewa wyszukiwania binarnego
Poniżej znajduje się pełna implementacja drzewa wyszukiwania binarnego w programowaniu C:
#include#include
struktura węzeł {
int wartość ;
struktura węzeł * lewy , * Prawidłowy ;
} ;
struktura węzeł * węzeł1 ( int dane ) {
struktura węzeł * tmp = ( struktura węzeł * ) Malloc ( rozmiar ( struktura węzeł ) ) ;
tmp -> wartość = dane ;
tmp -> lewy = tmp -> Prawidłowy = ZERO ;
powrót tmp ;
}
próżnia wydrukować ( struktura węzeł * Węzeł główny ) // wyświetlanie węzłów!
{
Jeśli ( Węzeł główny != ZERO ) {
wydrukować ( Węzeł główny -> lewy ) ;
drukujf ( '%D \N ' , Węzeł główny -> wartość ) ;
wydrukować ( Węzeł główny -> Prawidłowy ) ;
}
}
struktura węzeł * wstaw_węzeł ( struktura węzeł * węzeł , int dane ) // wstawianie węzłów!
{
Jeśli ( węzeł == ZERO ) powrót węzeł1 ( dane ) ;
Jeśli ( dane < węzeł -> wartość ) {
węzeł -> lewy = wstaw_węzeł ( węzeł -> lewy , dane ) ;
} w przeciwnym razie Jeśli ( dane > węzeł -> wartość ) {
węzeł -> Prawidłowy = wstaw_węzeł ( węzeł -> Prawidłowy , dane ) ;
}
powrót węzeł ;
}
int główny ( ) {
drukujf ( „Implementacja C drzewa wyszukiwania binarnego! \N \N ' ) ;
struktura węzeł * rodzic = ZERO ;
rodzic = wstaw_węzeł ( rodzic , 10 ) ;
wstaw_węzeł ( rodzic , 4 ) ;
wstaw_węzeł ( rodzic , 66 ) ;
wstaw_węzeł ( rodzic , Cztery pięć ) ;
wstaw_węzeł ( rodzic , 9 ) ;
wstaw_węzeł ( rodzic , 7 ) ;
wydrukować ( rodzic ) ;
powrót 0 ;
}
W powyższym kodzie najpierw deklarujemy a węzeł za pomocą struktura . Następnie inicjujemy nowy węzeł jako „ węzeł1 ” i przydzielaj pamięć dynamicznie za pomocą malloc() w C z danymi i dwoma wskaźnikami wpisz dzieci używając zadeklarowanego węzła. Następnie wyświetlamy węzeł według printf() funkcję i wywołać ją w główny() funkcjonować. A później węzeł_wstawiania() tworzona jest funkcja, gdzie jeśli dane węzła mają wartość NULL, to węzeł1 jest wycofany, w przeciwnym razie dane są umieszczane w węzeł (rodzic) lewego i prawego dziecka. Program rozpoczyna wykonywanie od główny() funkcja, która generuje węzeł przy użyciu kilku przykładowych węzłów jako elementów podrzędnych, a następnie używa metod przechodzenia w kolejności w celu wydrukowania zawartości węzła.
Wyjście
Wniosek
Drzewa są często wykorzystywane do przechowywania danych w postaci nieliniowej. Drzewa binarne to typy drzew, w których każdy węzeł (rodzic) ma dwoje potomków, lewe dziecko i prawe dziecko. A drzewo binarne jest wszechstronną metodą przesyłania i przechowywania danych. Jest bardziej wydajny w porównaniu do Linked-List w C. W powyższym artykule widzieliśmy koncepcję a Drzewo binarne z wdrażaniem krok po kroku a Drzewo wyszukiwania binarnego w C.