Existuje více než jeden způsob, jak navštívit všechny uzly v BST.

Binární stromy jsou jednou z nejpoužívanějších datových struktur v programování. Binární vyhledávací strom (BST) umožňuje ukládání dat ve formě uzlů (nadřazený uzel a podřízený uzel uzel) tak, že levý podřízený uzel je menší než nadřazený uzel a pravý podřízený uzel je větší.

Binární vyhledávací stromy umožňují efektivní operace procházení, vyhledávání, mazání a vkládání. V tomto článku se dozvíte o třech způsobech, jak procházet binárním vyhledávacím stromem: preorder traversal, inorder traversal a postorder traversal.

Inorder Traversal

Inorder traversal je proces procházení uzlů a binární vyhledávací strom rekurzivním zpracováním levého podstromu, pak zpracováním kořenového uzlu a nakonec rekurzivním zpracováním pravého podstromu. Vzhledem k tomu, že zpracovává uzly ve vzestupném pořadí hodnot, nazývá se tato technika procházení v pořadí.

Procházení je proces návštěvy každého uzlu ve stromové datové struktuře přesně jednou.

instagram viewer

Algoritmus procházení Inorder

Opakujte pro procházení všemi uzly BST:

  1. Rekurzivně projděte levý podstrom.
  2. Navštivte kořenový uzel.
  3. Rekurzivně projděte pravý podstrom.

Vizualizace průchodu Inorder

Vizuální příklad může pomoci vysvětlit procházení binárním vyhledávacím stromem. Tento obrázek ukazuje postupné procházení příkladu binárního vyhledávacího stromu:

V tomto binárním vyhledávacím stromu je 56 kořenový uzel. Nejprve musíte projít levý podstrom 32, poté kořenový uzel 56 a poté pravý podstrom 62.

U podstromu 32 nejprve projděte levý podstrom 28. Tento podstrom nemá žádné potomky, takže dále projděte uzel 32. Dále přejděte pravým podstromem 44, který také nemá žádné potomky. Pořadí procházení pro podstrom s kořenem na 32 je tedy 28 -> 32 -> 44.

Dále navštivte kořenový uzel, 56.

Poté projděte pravý podstrom s kořeny na 62. Začněte procházením jeho levého podstromu s kořenem na 58. Nemá žádné děti, takže příště navštivte uzel 62. Nakonec projděte pravý podstrom 88, který také nemá žádné potomky.

Algoritmus tedy navštíví uzly stromu v následujícím pořadí:

28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Aplikace Inorder Traversal

Pomocí inorder traversal můžete získat hodnoty prvků uzlů v rostoucím pořadí. Chcete-li získat hodnoty v sestupném pořadí, jednoduše proces otočte: navštivte pravý podstrom, poté kořenový uzel a poté levý podstrom. Algoritmus můžete použít k nalezení předponového výrazu stromu výrazů.

Předobjednávka Traversal

Preorder traversal je podobný jako inorder, ale zpracovává kořenový uzel před rekurzivním zpracováním levého podstromu a poté pravého podstromu.

Algoritmus procházení předobjednávky

Opakujte pro procházení všemi uzly BST:

  1. Navštivte kořenový uzel.
  2. Rekurzivně projděte levý podstrom.
  3. Rekurzivně projděte pravý podstrom.

Vizualizace předobjednávky Traversal

Následující obrázek ukazuje procházení předobjednávky binárním vyhledávacím stromem:

V tomto binárním vyhledávacím stromu začněte zpracováním kořenového uzlu, 56. Poté projděte levý podstrom 32, následovaný pravým podstromem 62.

Pro levý podstrom zpracujte hodnotu v kořenovém uzlu, 32. Dále projděte levý podstrom 28 a nakonec pravý podstrom 44. Tím je dokončeno procházení levého podstromu s kořenem na 32. Přechod probíhá v následujícím pořadí: 56 -> 32 -> 28 -> 44.

Pro pravý podstrom zpracujte hodnotu v kořenovém uzlu, 62. Dále projděte levý podstrom, 58, nakonec pravý podstrom, 88. Ani jeden uzel opět nemá žádné potomky, takže procházení je v tomto okamžiku dokončeno.

Prošli jste celý strom v následujícím pořadí:

56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88

Aplikace Preorder Traversal

Pro nejsnazší vytvoření kopie stromu můžete použít předobjednávkové procházení.

Postorder Traversal

Postorder traversal je proces procházení uzlů binárního vyhledávacího stromu rekurzivně zpracování levého podstromu, poté rekurzivní zpracování pravého podstromu a nakonec zpracování kořenový uzel. Protože zpracovává kořenový uzel po obou podstromech, nazývá se tato metoda postorder traversal.

Algoritmus Postorder Traversal

Opakujte pro procházení všemi uzly BST:

  1. Rekurzivně projděte levý podstrom.
  2. Rekurzivně projděte pravý podstrom.
  3. Navštivte kořenový uzel.

Vizualizace Postorder Traversal

Následující obrázek ukazuje procházení postorderu binárním vyhledávacím stromem:

Začněte procházením levého podstromu, 32, pak pravého podstromu, 62. Dokončete zpracováním kořenového uzlu, 56.

Chcete-li zpracovat podstrom s kořenem na 32, projděte jeho levý podstrom, 28. Protože 28 nemá žádné děti, přesuňte se do pravého podstromu, 44. Proces 44, protože také nemá žádné děti. Nakonec zpracujte kořenový uzel, 32. Tento podstrom jste prošli v pořadí 28 -> 44 -> 32.

Zpracujte pravý podstrom pomocí stejného přístupu k návštěvě uzlů v pořadí 58 -> 88 → 62.

Nakonec zpracujte kořenový uzel, 56. Celý strom projdete v tomto pořadí:

28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56

Aplikace Postorder Traversal

K odstranění stromu od listu ke kořenu můžete použít postorder traversal. Můžete jej také použít k nalezení postfixového výrazu stromu výrazů.

Chcete-li navštívit všechny listové uzly určitého uzlu před návštěvou samotného uzlu, můžete použít techniku ​​postorder traversal.

Časová a prostorová složitost procházení binárních vyhledávacích stromů

Časová náročnost všech tří traverzálních technik je Na), kde n je velikost binární strom. Prostorová složitost všech traverzálních technik je Ach), kde h je výška binárního stromu.

Velikost binárního stromu se rovná počtu uzlů v tomto stromu. Výška binárního stromu je počet hran mezi kořenovým uzlem stromu a jeho nejvzdálenějším listovým uzlem.

Python kód pro procházení binárního vyhledávacího stromu

Níže je uveden program Python, který provede všechny tři procházení binárního vyhledávacího stromu:

# 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)

Tento program by měl vytvořit následující výstup:

Algoritmy, které musíte znát pro programátory

Algoritmy jsou nezbytnou součástí cesty každého programátora. Pro programátora je klíčové dobře se orientovat v algoritmech. Měli byste být obeznámeni s některými algoritmy, jako je slučovací třídění, rychlé třídění, binární vyhledávání, lineární vyhledávání, hloubkové první vyhledávání a tak dále.