Jak wdrożyć drzewo binarne w C?

Drzewo jest wspólnym formatem danych do przechowywania informacji zawartych hierarchicznie. Drzewo składa się z węzłów połączonych krawędzie, przy czym każdy węzeł ma swój węzeł nadrzędny i jeden lub kilka węzłów dziecięcych. W tym artykule bada i analizuje Drzewa binarne i widzi wdrażanie Drzewa binarne w programowaniu C.

Binarne drzewo w c

W C, Drzewo binarne jest instancją struktury danych drzewa z węzłem nadrzędnym, który może mieć maksymalną liczbę dwóch węzłów dziecięcych; 0, 1 lub 2 węzły potomstwa. Każdy węzeł w Drzewo binarne ma własną wartość i dwoje wskaźników dla swoich dzieci, jeden wskaźnik dla lewego dziecka, a drugi dla właściwego dziecka.

Deklaracja drzewa binarnego

A Drzewo binarne można zadeklarować w C za pomocą obiektu wywołanego struct który przedstawia jeden z węzłów na drzewie.

Node struct
DataType var_name;
Node struct* lewy;
Node struct* racja;
;

Powyżej jest deklaracją jednego Drzewo binarne Nazwa węzła jako węzeł. Zawiera trzy wartości; jeden to zmienna przechowywania danych, a pozostałe dwa są wskaźnikami dziecka. (lewe i prawe dziecko węzła nadrzędnego).

Fakty z drzewa binarnego

Nawet w przypadku dużych zestawów danych, za pomocą Drzewo binarne sprawia, że ​​wyszukiwanie jest łatwiejsze i szybsze. Liczba gałęzi drzew nie jest ograniczona. W przeciwieństwie do tablicy, jakiekolwiek drzewa można wykonać i zwiększać w zależności od tego, co jest wymagane.

Wdrożenie drzewa binarnego w C

Poniżej znajduje się przewodnik krok po kroku do wdrożenia Drzewo binarne w c.

Krok 1: Dokonaj drzewa wyszukiwania binarnego

Utwórz węzeł struktury, który ma trzy typy danych, takie jak dane, *left_child i *prawe_child, w którym dane mogą być typu liczb całkowitych, a zarówno *lewy_child, jak i *prawe_child mogą być deklarowane jako null lub nie.

węzeł struct

dane int;
node struct *prawe_child;
struct node *left_child;
;

Krok 2: Utwórz nowe węzły w drzewie wyszukiwania binarnego

Utwórz nowy węzeł, tworząc funkcję, która akceptuje liczbę całkowitą jako argument i zapewnia 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 do null i zwróć Nodename.

Node struct* Utwórz (dane danych)

struct node* nodename = malloc (sizeof (struct node));
nodename-> data = wartość;
nodename-> left_child = nodename-> right_child = null;
zwróć Nodename;

Krok 3: Wstaw prawe i lewe dziecko w binarnym drzewie

Utwórz funkcje Insert_Left i Insert_right, które zaakceptują dwa wejścia, które są wartością, którą należy włożyć, oraz wskaźnik do węzła, do którego będą podłączone oba dzieci. Wywołaj funkcję Utwórz, 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.

struct node* insert_left (node ​​struct node* root, dane danych)
root-> left = create (dane);
zwróć root-> lewy;

struct node* insert_right (node ​​struct node* root, dane danych)
root-> right = Utwórz (dane);
zwróć root-> right;

Krok 4: Wyświetl węzły drzewa binarnego za pomocą metod przemieszczania

Możemy wyświetlać drzewa, używając trzech metod przemieszczania w C. Te metody przejścia to:

1: Przejazd w przedsprzedaży

W tej metodzie przejścia przejdziemy przez węzły w kierunku pary_node-> left_child-> right_child.

void przed_order (węzeł * root)
if (root)
printf („%d \ n”, root-> dane);
display_pre_order (root-> po lewej);
display_pre_order (root-> right);

2: Traversal po zamówieniu

W tej metodzie przejścia przejdziemy przez węzły w kierunku od left_child-> prawy_child-> marent_node->.

void display_post_order (węzeł * root)
if (binary_tree)
display_post_order (root-> po lewej);
display_post_order (root-> right);
printf („%d \ n”, root-> dane);

3: Traversal na zamówieniu

W tej metodzie przejścia przejdziemy przez węzły w kierunku left_node-> root_child-> prawy_child.

void display_in_order (węzeł * root)
if (binary_tree)
display_in_order (root-> po lewej);
printf („%d \ n”, root-> dane);
display_in_order (root-> right);

Krok 5: Wykonaj usunięcie 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.

void delete_t (węzeł * root)
if (root)
delete_t (root-> po lewej);
delete_t (root-> right);
wolny (root);

C Program drzewa wyszukiwania binarnego

Poniżej znajduje się pełna implementacja drzewa wyszukiwania binarnego w programowaniu C:

#włączać
#włączać
Node struct
wartość int;
Node struct * lewy, * po prawej;
;
Node struct * node1 (int data)
struct node * tmp = (struct node *) malloc (sizeof (struct node));
tmp -> wartość = dane;
tmp -> lewy = tmp -> prawy = null;
zwrócić tmp;

void print (node ​​struct * root_node) // Wyświetlanie węzłów!

if (root_node != Null)
print (root_node -> po lewej);
printf ("%d \ n", root_node -> wartość);
print (root_node -> po prawej);


Node struct * insert_node (węzeł struct *, int data) // Wkładanie węzłów!

if (node ​​== null) zwraca węzeł 1 (dane);
if (dane < node -> wartość)
node -> left = insert_node (węzeł -> lewy, dane);
else if (data> node -> wartość)
node -> right = insert_node (węzeł -> right, data);

Węzeł powrotny;

int main ()
printf („C Implementacja drzewa wyszukiwania binarnego!\ n \ n ”);
struct node * macierz = null;
nadrzędny = insert_node (nadrzędny, 10);
insert_node (macierz, 4);
INSERT_NODE (Parent, 66);
INSERT_NODE (Parent, 45);
insert_node (macierz, 9);
INSERT_NODE (Parent, 7);
druk (rodzic);
powrót 0;

W powyższym kodzie najpierw deklarujemy węzeł za pomocą struct. Następnie zainicjujemy nowy węzeł jako „Node1”I podzielić na dynamicznie pamięć za pomocą Malloc () W C z danymi i dwoma wskaźnikami wpisuje dzieci przy użyciu zadeklarowanego węzła. Następnie wyświetlamy węzeł przez printf () funkcjonować i wywołać to w główny() funkcjonować. A później insertion_node () Funkcja jest tworzona, gdzie, jeśli dane węzła są null, to Node1 jest emerytowany, w przeciwnym razie dane są umieszczane w węzeł(rodzic) lewego i prawego dziecka. Program rozpoczyna wykonywanie z główny() Funkcja, która generuje węzeł za pomocą kilku przykładowych węzłów jako dzieci, a następnie wykorzystuje metody przejścia na zamówienie do wydrukowania zawartości węzła.

Wyjście

Wniosek

Drzewa są często stosowane do przechowywania danych w formie nieliniowej. Drzewa binarne to rodzaje drzew, w których każdy węzeł (rodzic) ma dwa potomstwo lewe dziecko i prawe dziecko. A Drzewo binarne jest wszechstronną metodą przesyłania danych i przechowywania danych. Jest bardziej wydajny w porównaniu z Linked-List w C. W powyższym artykule widzieliśmy pojęcie Drzewo binarne z wdrożeniem krok po kroku Drzewo wyszukiwania binarnego w c.