Det er mer enn én måte å besøke alle nodene i en BST.
Binære trær er en av de mest brukte datastrukturene i programmering. Et binært søketre (BST) tillater lagring av data i form av noder (overordnet node og barn node) slik at den venstre barnenoden er mindre enn den overordnede noden og den høyre barnenoden er større.
Binære søketrær tillater effektiv traversering, søk, sletting og innsettingsoperasjoner. I denne artikkelen vil du lære om de tre måtene å krysse et binært søketre på: preorder traversal, inorder traversal og postorder traversal.
Inorder Traversal
Inorder-traversal er prosessen med å krysse noder til en binært søketre ved å rekursivt behandle venstre undertre, deretter behandle rotnoden, og til slutt rekursivt behandle det høyre undertreet. Siden den behandler noder i stigende verdirekkefølge, kalles teknikken inorder-traversal.
Traversering er prosessen med å besøke hver node i en tredatastruktur nøyaktig én gang.
Algoritme for Inorder Traversal
Gjenta for å krysse alle noder i BST:
- Gjennomgå det venstre undertreet rekursivt.
- Besøk rotnoden.
- Gå rekursivt gjennom høyre undertre.
Visualisering av Inorder Traversal
Et visuelt eksempel kan hjelpe til med å forklare binært søketregjennomgang. Denne figuren viser gjennomgangen i rekkefølgen til et eksempel på et binært søketre:
I dette binære søketreet er 56 rotnoden. Først må du krysse venstre undertre 32, deretter rotnoden 56, og deretter høyre undertre 62.
For undertreet 32, kryss først det venstre undertreet, 28. Dette undertreet har ingen barn, så kryss deretter 32-noden. Deretter går du gjennom høyre undertre, 44, som heller ikke har noen barn. Derfor er traverseringsrekkefølgen for undertreet forankret ved 32 28 -> 32 -> 44.
Gå deretter til rotnoden, 56.
Deretter krysser du det høyre undertreet, forankret på 62. Start med å krysse venstre undertre, forankret på 58. Den har ingen barn, så besøk 62-noden neste gang. Til slutt, kryss det høyre undertreet, 88, som heller ikke har barn.
Så algoritmen besøker nodene til treet i følgende rekkefølge:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Anvendelse av Inorder Traversal
Du kan bruke inorder-gjennomgang for å få verdiene til nodeelementer i økende rekkefølge. For å få verdiene i synkende rekkefølge, reverser du prosessen: gå til høyre undertre, deretter rotnoden og deretter venstre undertre. Du kan bruke algoritmen til å finne prefiksuttrykket til et uttrykkstre.
Forhåndsbestill Traversal
Forhåndsbestillingsgjennomgang ligner på inorder, men den behandler rotnoden før den rekursivt behandler det venstre undertreet, deretter det høyre undertreet.
Algoritme for forhåndsbestillingsgjennomgang
Gjenta for å krysse alle noder i BST:
- Besøk rotnoden.
- Gjennomgå det venstre undertreet rekursivt.
- Gå rekursivt gjennom høyre undertre.
Visualisering av Preorder Traversal
Følgende figur viser forhåndsbestillingsgjennomgangen til det binære søketreet:
I dette binære søketreet, start med å behandle rotnoden, 56. Gå deretter gjennom venstre undertre, 32, etterfulgt av høyre undertre, 62.
For det venstre undertreet, behandle verdien ved rotnoden, 32. Deretter går du gjennom venstre undertre, 28, og til slutt høyre undertre, 44. Dette fullfører kryssingen av det venstre undertreet med rot på 32. Traverseringen skjer i følgende rekkefølge: 56 -> 32 -> 28 -> 44.
For det høyre undertreet, behandle verdien ved rotnoden, 62. Deretter går du gjennom venstre undertre, 58, og til slutt høyre undertre, 88. Igjen, ingen av nodene har noen barn, så kryssingen er fullført på dette tidspunktet.
Du har krysset hele treet i følgende rekkefølge:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Anvendelse av Preorder Traversal
Du kan bruke preorder traversal for å lage en kopi av treet enklest.
Postordregjennomgang
Postorder-traversering er prosessen med å krysse noder i et binært søketre med rekursivt behandle det venstre undertreet, deretter rekursivt behandle det høyre undertreet, og til slutt behandle det rotnoden. Siden den behandler rotnoden etter begge undertrærne, kalles denne metoden postorder-traversal.
Algoritme for Postorder Traversal
Gjenta for å krysse alle noder i BST:
- Gjennomgå det venstre undertreet rekursivt.
- Gå rekursivt gjennom høyre undertre.
- Besøk rotnoden.
Visualisering av Postordre Traversal
Følgende figur viser postorder-gjennomgangen til det binære søketreet:
Start med å krysse venstre undertre, 32, deretter høyre undertre, 62. Avslutt med å behandle rotnoden, 56.
For å behandle undertreet, forankret ved 32, krysser du dets venstre undertre, 28. Siden 28 ikke har noen barn, flytt til høyre undertre, 44. Prosess 44 siden den heller ikke har barn. Til slutt, behandle rotnoden, 32. Du har krysset dette undertreet i rekkefølgen 28 -> 44 -> 32.
Behandle det høyre undertreet ved å bruke samme tilnærming for å besøke noder i rekkefølgen 58 -> 88 → 62.
Til slutt, behandle rotnoden, 56. Du vil krysse hele treet i denne rekkefølgen:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Anvendelse av Postordre Traversal
Du kan bruke postordre-traversering for å slette et tre fra blad til rot. Du kan også bruke den til å finne postfix-uttrykket til et uttrykkstre.
For å besøke alle bladnodene til en bestemt node før du besøker selve noden, kan du bruke postorder-traversalteknikken.
Tid og rom kompleksiteten til binære søketregjennomganger
Tidskompleksiteten til alle tre traverseringsteknikkene er På), hvor n er størrelsen på binært tre. Romkompleksiteten til alle traverseringsteknikkene er Åh), hvor h er høyden på det binære treet.
Størrelsen på det binære treet er lik antall noder i det treet. Høyden på det binære treet er antall kanter mellom treets rotnode og dets fjerneste bladnode.
Python-kode for binær søketregjennomgang
Nedenfor er et Python-program for å utføre alle de tre binære søketre-gjennomgangene:
# Node class is used to create individual nodes
# of the Binary Search Tree (BST)
classNode:
def__init__(self, element):
self.left = None
self.right = None
self.value = element# Function to perform the inorder tree traversal
definorder(root):
if root:
# Traverse left subtree
inorder(root.left)# Traverse root
print(str(root.value) + ", ", end='')# Traverse right subtree
inorder(root.right)# Function to perform the postorder tree traversal
defpostorder(root):
if root:
# Traverse left subtree
postorder(root.left)# Traverse right subtree
postorder(root.right)# Traverse root
print(str(root.value) + ", ", end='')# Function to perform the preorder tree traversal
defpreorder(root):
if root:
# Traverse root
print(str(root.value) + ", ", end='')# Traverse left subtree
preorder(root.left)# Traverse right subtree
preorder(root.right)
# Creating nodes of the tree
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)
print("Inorder Traversal of BST: ")
inorder(root)
print()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)
Dette programmet skal produsere følgende utgang:
Må-kunne-algoritmer for programmerere
Algoritmer er en viktig del av enhver programmerers reise. Det er avgjørende for en programmerer å være godt kjent med algoritmer. Du bør være kjent med noen av algoritmene som flettesortering, hurtigsortering, binært søk, lineært søk, dybde først søk, og så videre.
