Der er mere end én måde at besøge alle noderne i en BST på.

Binære træer er en af ​​de mest brugte datastrukturer i programmering. Et binært søgetræ (BST) tillader lagring af data i form af noder (overordnet node og underordnet). node), sådan at den venstre underordnede knude er mindre end den overordnede knude, og den højre underknude er større.

Binære søgetræer tillader effektiv gennemgang, søgning, sletning og indsættelsesoperationer. I denne artikel lærer du om de tre måder at krydse et binært søgetræ på: preorder traversal, inorder traversal og postorder traversal.

Inorder Traversal

Inorder-gennemgangen er processen med at krydse noder af en binært søgetræ ved rekursivt at behandle venstre undertræ, derefter bearbejde rodknudepunktet og til sidst rekursivt bearbejde det højre undertræ. Da den behandler noder i stigende værdirækkefølge, kaldes teknikken inorder traversal.

Traversering er processen med at besøge hver node i en trædatastruktur nøjagtigt én gang.

Algoritme for Inorder Traversal

instagram viewer

Gentag for at krydse alle noder i BST:

  1. Gå rekursivt gennem det venstre undertræ.
  2. Besøg rodnoden.
  3. Gå rekursivt gennem det højre undertræ.

Visualisering af Inorder Traversal

Et visuelt eksempel kan hjælpe med at forklare krydsning af binært søgetræ. Denne figur viser den uordensmæssige gennemgang af et eksempel på et binært søgetræ:

I dette binære søgetræ er 56 rodknuden. Først skal du krydse det venstre undertræ 32, derefter rodknudepunktet 56 og derefter det højre undertræ 62.

For undertræet 32 ​​skal du først krydse det venstre undertræ, 28. Dette undertræ har ingen børn, så kryds derefter 32 noden. Derefter skal du krydse det højre undertræ, 44, som heller ikke har nogen børn. Derfor er gennemløbsrækkefølgen for undertræet med rod ved 32 28 -> 32 -> 44.

Besøg derefter rodnoden, 56.

Gå derefter gennem det højre undertræ med rod på 62. Start med at krydse dets venstre undertræ, forankret på 58. Den har ingen børn, så besøg 62-knuden næste gang. Til sidst krydser du det højre undertræ, 88, som heller ikke har nogen børn.

Så algoritmen besøger træets noder i følgende rækkefølge:

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

Anvendelse af Inorder Traversal

Du kan bruge inorder-gennemgang til at få værdierne af nodeelementer i stigende rækkefølge. For at få værdierne i faldende rækkefølge skal du blot vende processen om: besøg det højre undertræ, derefter rodknuden og derefter det venstre undertræ. Du kan bruge algoritmen til at finde præfiksudtrykket for et udtrykstræ.

Forudbestil gennemkørsel

Forudbestillingsgennemgang ligner inorder, men den behandler rodknudepunktet før rekursiv behandling af det venstre undertræ og derefter det højre undertræ.

Algoritme for Preorder Traversal

Gentag for at krydse alle noder i BST:

  1. Besøg rodnoden.
  2. Gå rekursivt gennem det venstre undertræ.
  3. Gå rekursivt gennem det højre undertræ.

Visualisering af Preorder Traversal

Følgende figur viser forudbestillingsgennemgangen af ​​det binære søgetræ:

I dette binære søgetræ skal du starte med at behandle rodknuden, 56. Gå derefter gennem det venstre undertræ, 32, efterfulgt af det højre undertræ, 62.

For det venstre undertræ skal du behandle værdien ved rodnoden, 32. Derefter skal du krydse det venstre undertræ, 28, og til sidst det højre undertræ, 44. Dette fuldender gennemgangen af ​​det venstre undertræ med rod på 32. Gennemgangen sker i følgende rækkefølge: 56 -> 32 -> 28 -> 44.

For det højre undertræ skal du behandle værdien ved rodnoden, 62. Derefter skal du krydse det venstre undertræ, 58, og til sidst det højre undertræ, 88. Igen har ingen af ​​knudepunkterne nogen børn, så gennemkørslen er fuldført på dette tidspunkt.

Du har krydset hele træet i følgende rækkefølge:

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

Anvendelse af Preorder Traversal

Du kan bruge preorder traversal for at oprette en kopi af træet nemmest.

Postordre gennemkørsel

Postorder-gennemgang er processen med at krydse noder i et binært søgetræ ved rekursivt behandle det venstre undertræ, derefter rekursivt behandle det højre undertræ og til sidst behandle det rodknude. Da den behandler rodknuden efter begge undertræer, kaldes denne metode postorder traversal.

Algoritme for Postorder Traversal

Gentag for at krydse alle noder i BST:

  1. Gå rekursivt gennem det venstre undertræ.
  2. Gå rekursivt gennem det højre undertræ.
  3. Besøg rodnoden.

Visualisering af postordergennemgang

Følgende figur viser postorder-gennemgangen af ​​det binære søgetræ:

Start med at krydse det venstre undertræ, 32, og derefter det højre undertræ, 62. Afslut ved at behandle rodnoden, 56.

For at behandle undertræet, forankret på 32, skal du krydse dets venstre undertræ, 28. Da 28 ikke har nogen børn, flyt til højre undertræ, 44. Proces 44, da den heller ikke har børn. Til sidst skal du behandle rodnoden, 32. Du har krydset dette undertræ i rækkefølgen 28 -> 44 -> 32.

Bearbejd det højre undertræ ved at bruge samme tilgang til at besøge noder i rækkefølgen 58 -> 88 → 62.

Til sidst skal du behandle rodknuden, 56. Du vil krydse hele træet i denne rækkefølge:

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

Anvendelse af Postordre Traversal

Du kan bruge postorder traversal til at slette et træ fra blad til rod. Du kan også bruge det til at finde postfix-udtrykket for et udtrykstræ.

For at besøge alle bladknuderne i en bestemt knude, før du besøger selve knudepunktet, kan du bruge postorder-traversal-teknikken.

Tid og rums kompleksitet af binære søgetrægennemgange

Tidskompleksiteten af ​​alle tre traversalteknikker er På), hvor n er størrelsen på binært træ. Rumkompleksiteten af ​​alle traversalteknikker er O(h), hvor h er højden af ​​det binære træ.

Størrelsen af ​​det binære træ er lig med antallet af noder i det pågældende træ. Højden af ​​det binære træ er antallet af kanter mellem træets rodknude og dets fjerneste bladknude.

Python-kode til binær søgetrægennemgang

Nedenfor er et Python-program til at udføre alle tre binære søgetrægennemgange:

# 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 program skal producere følgende output:

Must-Know Algoritmer for programmører

Algoritmer er en væsentlig del af enhver programmørs rejse. Det er afgørende for en programmør at være velbevandret i algoritmer. Du bør være bekendt med nogle af algoritmerne som fletter sortering, hurtig sortering, binær søgning, lineær søgning, dybde først søgning, og så videre.