Binær søket tre C ++

BST er en datastruktur som opprettholder dataene i en sortert liste. Det er kjent som et binært søketre fordi hver node i treet har maksimalt to barn som ikke kan økes ytterligere. Dette er kjent som et søketre fordi det brukes til å søke eller finne ethvert element til stede. Vi vil implementere dette fenomenet på C ++ -språket.

Gjennomføring

I en implementering er det første trinnet å bruke en struktur for å initialisere heltallstypen og både venstre og høyre sideknuter. Disse nodene er definert ved å bruke en variabel peker, da de begge lagrer adressene til de alternative nodene. Etter det lukker vi strukturen.

Vi vil lage en ny node igjen gjennom en struktur. Parameteren til funksjonen vil inneholde dataene vi ønsker å legge inn i noden.

struct node *newNode (int element)

Den vil lage en ny nodetemperatur som vil lagre data i den, og størrelsen på minnet vil bli tildelt gjennom Malloc (). Vi vil legge til vareverdien i nøkkeldelen av noden. Mens venstre og høyre del, som er erklært tidligere i strukturen, er erklært som null nå fordi det er den første noden. Temp vil bli returnert.

En funksjon med navnet "Inder" opprettes, og den vil akseptere rotnoden i parameteren. Som vi vet inneholder treet tre hoveddeler: node, venstre og høyre side av treet. Vi vil bruke en if-uttalelse for å sjekke om roten ikke er null. Ring deretter funksjonen og send den venstre delen av roten. Dette vil vise roten med en pil som vil betegne banen i treet. Neste, for å krysse riktig, ring inder -funksjonen med rotenes rett som parameter.

Inder (root -> venstre)

Slik er inderingen som krysser. For å sette inn en ny node i treet, vil vi bruke en funksjon som tar en node og nøkkelen som parameterverdier. Hvis treet allerede er tomt, vil den nye noden bli returnert. I det andre tilfellet, hvis treet ikke er tomt, så gå først til høyre side og sett inn en ny node her. For innsetting vil vi bruke en if-ests-uttalelse for å sjekke ordren for nøkkelen. Den nye nøkkelen vil gå til venstre for den stigende ordenen. Hvis delen som vil sjekke den nye tasten er mindre enn verdien som er til stede i noden allerede, må du angi nøkkelen til venstre del av noden.

Node -> venstre = innsats (node ​​-> venstre, nøkkel)

Mens nøkkelen er større, vil den gå til riktig del.

Etter innsetting av noden, vil vi sjekke den neste noden eller noden som er etterfølgeren. En funksjon av minverdien opprettes som vil opprette en ny node med et navn *strøm. Denne noden vil bli tildelt av en verdi som er gitt som et argument til funksjonen. Den vil først finne hjørneknuten eller venstre modusblad på venstre side av treet. Vi bruker en stundsløyfe som itererer til nodens kryssing er ferdig. Med andre ord, venstre del av den nåværende noden er ikke null.

Nåværende = strøm -> Venstre

Fortsett å tilordne gjeldende node den neste strømens verdi inne i løkken til venstre.

Treet vårt er krysset og organisert ved å legge til blader på begge sider. Hver verdi vil bli satt inn gjennom funksjonssamtalen fra hovedprogrammet. Nå må vi søke etter ethvert element og vil slette det når det er funnet.

Treet i C ++ fungerer på samme fenomen som den koblede listen gjør. Vi vil bruke det binære søket på treet og utføre en slettoperasjon for å slette en node eller blad fra treet. En funksjon av sletteknuten opprettes; Den vil inneholde treet og verdien som parametere. Vi vil først sjekke at trærne må ha verdier inni seg. Så vil if-statementet bli brukt, og hvis roten er null, betyr det bare å returnere roten.

If (nøkkelnøkkel)

Nøkkelen du vil slette er mindre enn rotnoden. Gå deretter til venstre og ring slettfunksjonen med venstre del av treet, og nøkkelen som skal slettes.

Root -> venstre = Deletenode (root -> venstre, nøkkel);

Og det samme gjelder den andre-hvis-delen. Hvis nøkkelen er større enn nodetasten, kan du gå til riktig vei, ring slettfunksjonen. Passere den rette delen av treet og nøkkelen slik at det blir lett å finne noden du vil slette.

Nå, kommer mot den andre delen, som er aktuelt hvis noden er alene, ikke har noe blad videre, eller bare har et enkelt barn foran. Inne i den andre delen igjen, hvis en uttalelse vil bli brukt som vil sjekke om det ikke er noen node på høyre side, kan du legge til verdien på høyre side av noden til den nye temp -noden, på samme måte for venstre side.

Struct node * temp = root -> venstre;

I den tilstanden, frigjør roten. Dette vil fjerne verdien fra roten.

Gratis (rot);

Hvis noen node inneholder to blader med den, for å søke på verdien, vil vi bruke Min Value -funksjonen, og den rette delen vil bli sendt til funksjonen.

MinValuenode (root -> høyre);

Når verdien som skal slettes blir funnet, vil vi erklære det den siste delen av treet slik at det enkelt kan slettes.

Root -> nøkkel = temp -> nøkkel;

Etter å ha gjort dette, slett noden,

Root -> høyre = slett node (node ​​-> høyre, temp -> nøkkel);

Etter å ha avsluttet funksjonen, vil vi erklære hovedprogrammet her. Rotnoden vil bli satt som null til å begynne med. Ved hjelp av Insert () -funksjonen vil vi bruke roten og nummerdataene til noden.

Sett inn (rot, 5);

Inder -funksjonen er kalt for traversal av treet.

Inder (rot);

Deretter, for å slette noden, vil vi ringe slettfunksjonen.

Root = Deletenode (root, 10);

Etter sletting vises verdiene igjen.

Etter å ha skrevet koden, vil vi utføre den i terminalen til Ubuntu gjennom kompilatoren.

$ g ++ -o filfil.c
$ ./fil

Som du kan se, blir de syv varene lagt inn i noden. Den ene blir slettet, og resten vil vises i samme rekkefølge som før.

Konklusjon

Et binært søketre brukes til å lagre verdiene i den sorterte formen. For å søke på et hvilket som helst tall, må alle tallene sorteres først i orden. Etter det blir det angitte nummeret søkt ved å dele treet i to deler, lage undertrær. BST -implementeringen gjøres i Ubuntu -systemet ved å forklare et eksempel på en utdypet måte. Vi håper du fant denne artikkelen nyttig. Sjekk de andre Linux -hint -artiklene for flere tips og opplæringsprogrammer.