Hvordan implementere binært tre i C?

Et tre er et vanlig dataformat for lagring av informasjon som er hierarkisk. Et tre består av noder koblet sammen med kanter, hvor hver node har sin overordnede node og en eller flere barneknuter. Denne artikkelen studerer og analyser binære trær og ser implementeringen av binære trær I C -programmering.

Binært tre i C

I C, a binært tre er en forekomst av en tredatastruktur med en overordnede node som kan ha et maksimalt antall to barneknuter; 0, 1 eller 2 avkomnoder. Hver eneste node i en binært tre har en egen verdi og to pekere til barna, den ene pekeren for venstre barn og den andre for det rette barnet.

Erklæring om binært tre

EN binært tre kan erklæres i C ved hjelp av et objekt som heter struktur som skildrer en av nodene i treet.

struct node
Datatype var_name;
struktur node* til venstre;
struct node* høyre;
;

Over er en erklæring om en binært tre Node navn som en node. Det har tre verdier; Den ene er datalagringsvariabelen, og de to andre er pekerne til barnet. (venstre og høyre barn av overordnet nod).

Fakta om binært tre

Selv for store datasett, ved hjelp av en binært tre gjør søket enklere og raskere. Antall tregrener er ikke begrenset. I motsetning til en matrise, kan trær av noe slag lages og økes basert på hva som kreves av et individ.

Binær treimplementering i C

Følgende er en trinn-for-trinns guide til å implementere en Binært tre i c.

Trinn 1: Erklær et binært søketre

Lag en strukturnode som har tre typer data, for eksempel data, *venstre_barn og *høyre_barn, der data kan være av heltallstype, og både *venstre_child og *høyre_childnoder kan deklareres som null eller ikke.

Struct Node

int -data;
struct node *right_child;
Struct Node *Left_child;
;

Trinn 2: Lag nye noder i binært søketre

Lag en ny node ved å lage en funksjon som godtar et heltall som et argument og gir pekeren til den nye noden som er opprettet med den verdien. Bruk Malloc () -funksjonen i C for dynamisk minnetildeling for den opprettede noden. Initialiser venstre og høyre barn til null og returner nodenavnet.

Struct Node* Create (DataType Data)

struct node* nodename = malloc (sizeof (struct node));
Nodename-> data = verdi;
Nodename-> venstre_child = Nodename-> Right_child = NULL;
Return Nodename;

Trinn 3: Sett høyre og venstre barn i binært tre

Opprett funksjoner insert_left og insert_right som vil akseptere to innganger, som er verdien som skal settes inn og pekeren til noden som begge barna vil bli tilkoblet. Ring CREATE -funksjonen for å lage en ny node og tilordne den returnerte pekeren til venstre peker til venstre barn eller høyre peker til høyre barn av rotforelderen.

struct node* insert_left (struct node* root, datatype data)
root-> venstre = opprette (data);
returner rot-> venstre;

struct node* insert_right (struct node* root, datatype data)
root-> rett = opprette (data);
Returner rot-> høyre;

Trinn 4: Vis noder av binært tre ved bruk av traversale metoder

Vi kan vise trær ved å bruke tre metoder for traversal i C. Disse kryssingsmetodene er:

1: Forhåndsbestill krysse

I denne traversal -metoden vil vi gå gjennom nodene i en retning fra Parent_node-> venstre_child-> Right_child.

void pre_order (node ​​* root)
if (root)
printf ("%d \ n", root-> data);
display_pre_order (root-> venstre);
display_pre_order (root-> høyre);

2: Traversal etter ordre

I denne traversal -metoden vil vi gå gjennom nodene i en retning fra venstre_child-> høyre_child-> parent_node->.

void display_post_order (node ​​* root)
if (binary_tree)
display_post_order (root-> venstre);
display_post_order (root-> høyre);
printf ("%d \ n", root-> data);

3: I orden Traversal

I denne traversal -metoden vil vi gå gjennom nodene i en retning fra venstre_node-> root_child-> høyre_barn.

void display_in_order (node ​​* root)
if (binary_tree)
display_in_order (root-> venstre);
printf ("%d \ n", root-> data);
display_in_order (root-> høyre);

Trinn 5: Utfør sletting i binært tre

Vi kan slette den opprettet Binært tre Ved å slette begge barna med overordnet nodefunksjon i C som følger.

void Delete_t (node ​​* root)
if (root)
delete_t (root-> venstre);
delete_t (root-> høyre);
gratis (rot);

C -program for binært søketre

Følgende er fullstendig implementering av binært søketre i C -programmering:

#inkludere
#inkludere
struct node
int verdi;
struct node * til venstre, * høyre;
;
struct node * node1 (int data)
struct node * tmp = (struct node *) malloc (sizeof (struct node));
tmp -> verdi = data;
tmp -> venstre = tmp -> høyre = null;
return tmp;

void print (struct node * root_node) // vise nodene!

if (root_node != Null)
print (root_node -> venstre);
printf ("%d \ n", root_node -> verdi);
print (root_node -> høyre);


Struct Node * Insert_Node (Struct Node * Node, Int Data) // Sett inn noder!

if (node ​​== null) return node1 (data);
hvis (data < node -> verdi)
Node -> venstre = insert_node (node ​​-> venstre, data);
annet hvis (data> node -> verdi)
Node -> høyre = insert_node (node ​​-> høyre, data);

Returnode;

int main ()
printf ("C implementering av binært søketre!\ n \ n ");
struct node * foreldre = null;
foreldre = innsats_node (overordnet, 10);
insert_node (foreldre, 4);
insert_node (foreldre, 66);
insert_node (overordnet, 45);
insert_node (foreldre, 9);
insert_node (foreldre, 7);
trykk (overordnet);
retur 0;

I koden ovenfor erklærer vi først a Node ved hjelp av struktur. Så initialiserer vi en ny node som "Node1”Og tildel minnet dynamisk ved hjelp av Malloc () I C med data og to pekere type barn som bruker den erklærte noden. Etter dette viser vi noden av printf () funksjon og kall det i hoved() funksjon. Og så innsetting_node () funksjon opprettes, hvor hvis nodedata er null da Node1 er pensjonert, ellers plasseres data i Node(foreldre) av venstre og høyre barn. Programmet starter utførelse fra hoved() Funksjon, som genererer en node ved hjelp av noen få prøveknuter som barn og deretter bruker ordre om traversal-metoder for å skrive ut nodeinnholdet.

Produksjon

Konklusjon

Trær brukes ofte for å oppbevare data i en ikke-lineær form. Binære trær er typer trær der hver node (overordnet) har to avkom til venstre barn og det høyre barnet. EN binært tre er en allsidig metode for å overføre og lagre data. Det er mer effektivt sammenlignet med koblet liste i C. I artikkelen ovenfor har vi sett begrepet en Binært tre med trinn-for-trinns implementering av en Binært søketre i c.