Er is meer dan één manier om alle knooppunten in een BST te bezoeken.
Binaire bomen zijn een van de meest gebruikte gegevensstructuren bij het programmeren. Een binaire zoekboom (BST) maakt de opslag van gegevens mogelijk in de vorm van knooppunten (ouderknooppunt en kind knooppunt) zodat het linker kindknooppunt kleiner is dan het bovenliggende knooppunt en het rechter kindknooppunt is groter.
Binaire zoekbomen maken efficiënte doorloop-, zoek-, verwijderings- en invoegbewerkingen mogelijk. In dit artikel leer je over de drie manieren om een binaire zoekboom te doorlopen: preorder traversal, inorder traversal en postorder traversal.
Inorder doorkruisen
De inorder traversal is het proces van het doorlopen van knopen van a binaire zoekboom door de linker subboom recursief te verwerken, vervolgens het hoofdknooppunt te verwerken en ten slotte de rechter subboom recursief te verwerken. Omdat het knooppunten in oplopende waardevolgorde verwerkt, wordt de techniek inorder traversal genoemd.
Traverseren is het proces waarbij elk knooppunt in een boomstructuur precies één keer wordt bezocht.
Algoritme van Inorder Traversal
Herhaal dit om alle knooppunten van de BST te doorkruisen:
- Doorkruis recursief de linker substructuur.
- Bezoek het hoofdknooppunt.
- Doorloop recursief de rechter subboom.
Visualisatie van Inorder Traversal
Een visueel voorbeeld kan het doorlopen van de binaire zoekboom helpen verklaren. Deze afbeelding toont de inorder-traversal van een voorbeeld van een binaire zoekboom:
In deze binaire zoekboom is 56 het hoofdknooppunt. Eerst moet u de linker subboom 32 doorlopen, dan het wortelknooppunt 56 en vervolgens de rechter subboom 62.
Voor de deelboom 32, doorloopt u eerst de linker deelboom, 28. Deze substructuur heeft geen kinderen, dus doorloop vervolgens de 32 knoop. Ga vervolgens door de rechter subboom, 44, die ook geen kinderen heeft. Daarom is de volgorde van doorlopen voor de subboom geroot op 32 28 -> 32 -> 44.
Bezoek vervolgens het hoofdknooppunt, 56.
Loop dan door de rechter subboom, geroot op 62. Begin met het doorkruisen van de linker subboom, geroot op 58. Het heeft geen kinderen, dus bezoek vervolgens het 62-knooppunt. Doorloop ten slotte de rechter subboom, 88, die ook geen kinderen heeft.
Dus het algoritme bezoekt de knooppunten van de boom in de volgende volgorde:
28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88
Toepassing van Inorder Traversal
U kunt inorder traversal gebruiken om de waarden van knooppuntelementen in oplopende volgorde te krijgen. Om de waarden in aflopende volgorde te krijgen, keert u het proces gewoon om: bezoek de rechter substructuur, vervolgens het hoofdknooppunt en vervolgens de linker substructuur. U kunt het algoritme gebruiken om de prefixexpressie van een expressieboom te vinden.
Pre-order Traversal
Preorder traversal is vergelijkbaar met inorder, maar het verwerkt het root-knooppunt voordat recursief de linker substructuur en vervolgens de rechter substructuur wordt verwerkt.
Algoritme van Preorder Traversal
Herhaal om alle knooppunten van de BST te doorkruisen:
- Bezoek het hoofdknooppunt.
- Doorkruis recursief de linker substructuur.
- Doorloop recursief de rechter subboom.
Visualisatie van Preorder Traversal
De volgende afbeelding toont de pre-order doorloop van de binaire zoekboom:
Begin in deze binaire zoekboom met het verwerken van het hoofdknooppunt, 56. Doorkruis vervolgens de linker deelboom, 32, gevolgd door de rechter deelboom, 62.
Verwerk voor de linker substructuur de waarde op het hoofdknooppunt, 32. Ga vervolgens door de linker deelboom, 28, en ten slotte door de rechter deelboom, 44. Dit voltooit het doorkruisen van de linker subboom geroot op 32. De traversal vindt plaats in de volgende volgorde: 56 -> 32 -> 28 -> 44.
Verwerk voor de rechter substructuur de waarde op het hoofdknooppunt, 62. Ga vervolgens door de linker deelboom, 58, en ten slotte door de rechter deelboom, 88. Nogmaals, geen van beide knooppunten heeft kinderen, dus de doorgang is op dit punt voltooid.
Je hebt de volledige boom in de volgende volgorde doorlopen:
56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88
Toepassing van Preorder Traversal
U kunt pre-order traversal gebruiken om het gemakkelijkst een kopie van de boom te maken.
Overgang na bestelling
Postorder traversal is het proces waarbij knooppunten van een binaire zoekboom recursief worden doorlopen het verwerken van de linker subboom, dan recursief de rechter subboom verwerken, en ten slotte het verwerken van de hoofdknooppunt. Omdat het het root-knooppunt na beide substructuren verwerkt, wordt deze methode postorder-traversal genoemd.
Algoritme van Postorder Traversal
Herhaal dit om alle knooppunten van de BST te doorkruisen:
- Doorkruis recursief de linker substructuur.
- Doorloop recursief de rechter subboom.
- Bezoek het hoofdknooppunt.
Visualisatie van Postorder Traversal
De volgende afbeelding toont de postorder-traversal van de binaire zoekboom:
Begin met het doorlopen van de linker subboom, 32, en vervolgens de rechter subboom, 62. Werk af door het hoofdknooppunt te verwerken, 56.
Om de deelboom, geworteld op 32, te verwerken, gaat u door de linker deelboom, 28. Aangezien 28 geen kinderen heeft, gaat u naar de rechter subboom, 44. Proces 44 omdat het ook geen kinderen heeft. Verwerk ten slotte het rootknooppunt, 32. Je hebt deze subboom doorlopen in de volgorde 28 -> 44 -> 32.
Verwerk de rechter subboom op dezelfde manier om knooppunten te bezoeken in de volgorde 58 -> 88 → 62.
Verwerk ten slotte het rootknooppunt, 56. Je doorkruist de volledige boom in deze volgorde:
28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56
Toepassing van Postorder Traversal
U kunt postorder traversal gebruiken om een boom van blad tot wortel te verwijderen. U kunt het ook gebruiken om de postfix-expressie van een expressieboom te vinden.
Om alle bladknooppunten van een bepaald knooppunt te bezoeken voordat u het knooppunt zelf bezoekt, kunt u de postorder traversal-techniek gebruiken.
Tijd- en ruimtecomplexiteit van binaire zoekboomtraversals
De tijdscomplexiteit van alle drie de traversale technieken is Op), waar N is de grootte van de binaire boom. De ruimtelijke complexiteit van alle traversal-technieken is Oh), waar H is de hoogte van de binaire boom.
De grootte van de binaire boom is gelijk aan het aantal knooppunten in die boom. De hoogte van de binaire boom is het aantal randen tussen het wortelknooppunt van de boom en het verste bladknooppunt.
Python-code voor het doorlopen van binaire zoekbomen
Hieronder staat een Python-programma om alle drie de binaire zoekboomtraversals uit te voeren:
# 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)
Dit programma zou de volgende uitvoer moeten produceren:
Onmisbare algoritmen voor programmeurs
Algoritmen zijn een essentieel onderdeel van de reis van elke programmeur. Het is cruciaal voor een programmeur om goed thuis te zijn in algoritmen. U moet bekend zijn met enkele van de algoritmen, zoals samenvoegen, snel sorteren, binair zoeken, lineair zoeken, diepte eerst zoeken, enzovoort.
