Annonser

Treet representerer nodene er koblet av kanter. Vi vil diskutere binære trær eller binary search tree spesielt.

Binære Trær er en spesiell datastructure brukes for lagring av data formål. Et binært tre er en spesiell tilstand som hver node kan ha maksimalt to barn., Et binært tre har fordeler av både et ordnet utvalg og en lenket liste som søk er like rask som i et sortert array og innsetting eller sletting drift er så rask som i en lenket liste.

Viktig Vilkår

Følgende er de viktigste vilkårene med hensyn til treet.

  • bane − Bane refererer til sekvens av noder langs kantene av et tre.

  • Rot − noden på toppen av treet kalles rot. Det er bare en rot per treet, og den ene veien fra rotnoden til en node.,

  • Forelder − Enhver node, unntatt root node har en kant oppover til en node kalles forelder.

  • Barn − noden under en gitt node koblet sammen med sin kant nedover kalles sine barn node.

  • Blad − noden som ikke har noen barn node kalles blad node.

  • Undertreet − Undertreet representerer etterkommere av en node.

  • Besøk − Besøk refererer til å sjekke verdien av en node når kontrollen er på noden.

  • Traversing − Traversering betyr passerer gjennom noder i en bestemt rekkefølge.,

  • Nivåer − Nivå på en node representerer generasjon av en node. Hvis rotnoden er på nivå 0, da er det neste barnet node er på nivå 1, sine barnebarn er på nivå 2, og så videre.

  • til − Tasten representerer en verdi på en node basert på et søk operasjonen som skal utføres for en node.

Binary Search Tree Representasjon

Binary Search tree viser en spesiell atferd. En node er venstre barn må ha en verdi som er mindre enn sine overordnede verdi og node har høyre barn må ha en verdi som er større enn den overordnede verdi.,

Vi kommer til å gjennomføre treet ved hjelp av node objekt og koble dem gjennom referanser.

Treet Node

– koden for å skrive et tre-noden vil være tilsvarende det som er gitt nedenfor. Det har en del data og referanser til venstre og høyre barn noder.

struct node { int data; struct node *leftChild; struct node *rightChild;};

I et tre, slik at alle noder har en felles konstruksjon.

BST Grunnleggende Operasjoner

De grunnleggende operasjonene som kan utføres på en binary search tree data struktur, er følgende −

  • Sett inn − sett inn et element i et tre/opprett et tre.,

  • Søk − Søk som et element i et tre.

  • Preorder Traversal − beveger seg rundt et tre i en pre-order måte.

  • Inorder Traversal − beveger seg rundt et tre i en ordre måte.

  • Postorder Traversal − beveger seg rundt et tre i en post-order måte.

skal Vi lære å lage (settes inn) en tre-struktur og søker en data element i et tre i dette kapitlet. Vi skal lære om tre gjennomgang av metoder i de kommende kapittel.

Sett inn Operasjon

Den aller første innsetting skaper treet., Etterpå, når et element er å bli satt inn, må du først finne riktig sted. Begynne å søke fra rotnoden, så hvis dataene er mindre enn tasten verdi, søker du etter tomt sted i venstre undertreet og sette inn data. Ellers, søker du etter tomt sted på rett undertreet og sette inn data.,

Algoritme

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

– Implementering

gjennomføringen av sett inn-funksjonen bør se ut som dette −

Søk Drift

Når et element er som det skal søkes i, begynne å søke fra rotnoden, så hvis dataene er mindre enn tasten verdi, søk etter element i venstre undertreet. Ellers søk etter element i høyre undertreet. Følg samme algoritme for hver node.

Algoritme

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

gjennomføringen av denne algoritmen bør se ut som dette.,

Å vite om gjennomføringen av binary search tree data struktur, vennligst klikk her.

Annonser