Reklamer

Træet repræsenterer knuder forbundet med kanter. Vi vil diskutere binært træ eller binært søgetræ specifikt.

binært træ er en speciel datastruktur, der bruges til datalagring. Et binært træ har en særlig betingelse, at hver knude kan have højst to børn., Et binært træ har fordelene ved både et ordnet array og en linket liste, da søgning er så hurtig som i et sorteret array, og indsættelse eller sletning er så hurtig som i linket liste.

vigtige udtryk

Følgende er de vigtige udtryk med hensyn til træ.

  • sti − sti refererer til sekvensen af knuder langs kanterne af et træ.

  • rod − knuden øverst på træet kaldes rod. Træ og en sti fra rodknuden til en hvilken som helst knude.,

  • forælder − enhver node undtagen rodnoden har en kant opad til en node kaldet forælder.

  • barn − knuden under en given knude, der er forbundet med dens kant nedad, kaldes dens barneknude.

  • blad − knuden, der ikke har nogen børneknude, kaldes bladknuden.

  • Subtree − Subtree repræsenterer efterkommere af en node.

  • besøg − besøg refererer til at kontrollere værdien af en node, når kontrollen er på noden.

  • Traversing − Traversing betyder at passere gennem noder i en bestemt rækkefølge.,

  • niveauer − niveau af en knude repræsenterer genereringen af en knude. Hvis rodnoden er på niveau 0, er dens næste barneknude på niveau 1, dets barnebarn er på niveau 2 og så videre.

  • keys − tasten repræsenterer en værdi af en node baseret på hvilken en søgning operation skal udføres for en node.

Binary Search Tree Representation

Binary Search tree udviser en særlig adfærd. En knudepunkts venstre barn skal have en værdi, der er mindre end forældrenes værdi, og knudepunktets højre barn skal have en værdi, der er større end forældreværdien.,

Vi kommer til at gennemføre træ ved hjælp node objekt og forbinde dem gennem referencer.

Træknude

koden til at skrive en træknude ville svare til det, der er angivet nedenfor. Det har en datadel og henvisninger til sine venstre og højre barn noder.

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

i et træ deler alle noder fælles konstruktion.

BST Grundlæggende Operationer

De grundlæggende operationer, der kan udføres på en binær søgning træ datastrukturen, er følgende −

  • Indsæt − Indsætter et element i et træ/opret et træ.,

  • Søg − søger et element i et træ.

  • Preorder Traversal − krydser et træ på en forudbestillings måde.

  • Inorder Traversal − krydser et træ på en ordens måde.

  • Postorder Traversal − krydser et træ på en postordre måde.

Vi skal lære at oprette (indsætte i) en træstruktur og søge et dataelement i et træ i dette kapitel. Vi vil lære om træ gennemkører metoder i det kommende kapitel.

Indsæt Operation

den allerførste indsættelse skaber træet., Bagefter, når et element skal indsættes, først finde sin rette placering. Begynd at søge fra rodnoden, og hvis dataene er mindre end nøgleværdien, skal du søge efter den tomme placering i venstre undertræ og indsætte dataene. Ellers skal du søge efter den tomme placering i højre undertræ og indsætte dataene.,

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

Gennemførelsen

gennemførelse af indsæt-funktionen, skal se ud som dette −

Søgning

Når et element skal søges i, starte med at søge fra root node, så hvis dataene er mindre end den centrale værdi, søg efter det element i det venstre undertræ. Ellers skal du søge efter elementet i den rigtige undertræ. Følg den samme algoritme for hver knude.

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

implementeringen af denne algoritme skal se sådan ud.,

for at vide om gennemførelsen af binær søgning træ datastruktur, skal du klikke her.

Reklamer