Det finns mer än ett sätt att besöka alla noder i en BST.

Binära träd är en av de mest använda datastrukturerna inom programmering. Ett binärt sökträd (BST) tillåter lagring av data i form av noder (föräldernod och barn). nod) så att den vänstra undernoden är mindre än den överordnade noden och den högra undernoden är större.

Binära sökträd tillåter effektiv genomgång, sökning, radering och infogning. I den här artikeln kommer du att lära dig om de tre sätten att gå igenom ett binärt sökträd: genomgång av förbeställning, genomgång av inorder och genomgång av efterbeställning.

Inorder Traversal

Inordersgenomgången är processen att korsa noder för a binärt sökträd genom att rekursivt bearbeta det vänstra underträdet, sedan bearbeta rotnoden, och slutligen rekursivt bearbeta det högra underträdet. Eftersom den bearbetar noder i stigande värdeordning, kallas tekniken inorder-traversal.

Traversering är processen att besöka varje nod i en träddatastruktur exakt en gång.

Algoritm för Inorder Traversal

instagram viewer

Upprepa för att korsa alla noder i BST: n:

  1. Gå rekursivt genom det vänstra underträdet.
  2. Besök rotnoden.
  3. Gå rekursivt genom det högra underträdet.

Visualisering av Inorder Traversal

Ett visuellt exempel kan hjälpa till att förklara genomgång av binärt sökträd. Den här figuren visar ordningsföljden av ett exempel på binärt sökträd:

I detta binära sökträd är 56 rotnoden. Först måste du korsa det vänstra underträdet 32, sedan rotnoden 56 och sedan det högra underträdet 62.

För underträdet 32, gå först genom det vänstra underträdet, 28. Det här underträdet har inga underordnade, så gå sedan genom noden 32. Gå sedan igenom det högra underträdet, 44, som inte heller har några barn. Därför är genomgångsordningen för underträdet med rötter vid 32 28 -> 32 -> 44.

Besök sedan rotnoden, 56.

Gå sedan igenom det högra underträdet, rotat på 62. Börja med att korsa dess vänstra underträd, rotat på 58. Den har inga barn, så besök noden 62 härnäst. Gå slutligen genom det högra underträdet, 88, som inte heller har några barn.

Så algoritmen besöker trädets noder i följande ordning:

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

Tillämpning av Inorder Traversal

Du kan använda inorder-traversal för att få värdena för nodelement i ökande ordning. För att få värdena i fallande ordning, vänd helt enkelt processen: besök det högra underträdet, sedan rotnoden och sedan det vänstra underträdet. Du kan använda algoritmen för att hitta prefixuttrycket för ett uttrycksträd.

Förbeställ Traversal

Förbeställningsgenomgång liknar inorder, men den bearbetar rotnoden innan den rekursivt bearbetar det vänstra underträdet, sedan det högra underträdet.

Algoritm för förbeställningstrafik

Upprepa för att korsa alla noder i BST: n:

  1. Besök rotnoden.
  2. Gå rekursivt genom det vänstra underträdet.
  3. Gå rekursivt genom det högra underträdet.

Visualisering av förbeställningstrafik

Följande figur visar förbeställningsgenomgången av det binära sökträdet:

I detta binära sökträd, börja med att bearbeta rotnoden, 56. Gå sedan över det vänstra underträdet, 32, följt av det högra underträdet, 62.

För det vänstra underträdet, bearbeta värdet vid rotnoden, 32. Gå sedan igenom det vänstra underträdet, 28, och sedan det högra underträdet, 44. Detta avslutar genomgången av det vänstra underträdet med rötter vid 32. Traverseringen sker i följande ordning: 56 -> 32 -> 28 -> 44.

För det högra underträdet, bearbeta värdet vid rotnoden, 62. Gå sedan igenom det vänstra underträdet, 58, och slutligen det högra underträdet, 88. Återigen, ingen av noderna har några barn, så övergången är klar vid denna tidpunkt.

Du har korsat hela trädet i följande ordning:

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

Tillämpning av Preorder Traversal

Du kan använda förbeställningsgenomgång för att skapa en kopia av trädet enklast.

Postorder Traversal

Postorder-traversering är processen att korsa noder i ett binärt sökträd rekursivt bearbeta det vänstra underträdet, sedan rekursivt bearbeta det högra underträdet och slutligen bearbeta det rotnod. Eftersom den bearbetar rotnoden efter båda underträden kallas denna metod för postorder-traversal.

Algoritm för Postorder Traversal

Upprepa för att korsa alla noder i BST: n:

  1. Gå rekursivt genom det vänstra underträdet.
  2. Gå rekursivt genom det högra underträdet.
  3. Besök rotnoden.

Visualisering av Postorder-traversering

Följande figur visar postorder-genomgången av det binära sökträdet:

Börja med att korsa det vänstra underträdet, 32, sedan det högra underträdet, 62. Avsluta med att bearbeta rotnoden, 56.

För att bearbeta underträdet, rotat på 32, gå igenom dess vänstra underträd, 28. Eftersom 28 inte har några barn, flytta till höger underträd, 44. Process 44 eftersom den inte heller har några barn. Bearbeta slutligen rotnoden, 32. Du har korsat detta underträd i ordningen 28 -> 44 -> 32.

Bearbeta det högra underträdet med samma metod för att besöka noder i ordningen 58 -> 88 → 62.

Bearbeta slutligen rotnoden, 56. Du korsar hela trädet i denna ordning:

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

Tillämpning av Postorder Traversal

Du kan använda postorder-traversering för att ta bort ett träd från löv till rot. Du kan också använda den för att hitta postfix-uttrycket för ett uttrycksträd.

För att besöka alla lövnoder i en viss nod innan du besöker själva noden kan du använda postorder-traversaltekniken.

Tid och rums komplexitet hos binära sökträdsövergångar

Tidskomplexiteten för alla tre traverseringsteknikerna är På), var n är storleken på binärt träd. Rymdkomplexiteten hos alla traverseringstekniker är Åh), var h är höjden på det binära trädet.

Storleken på det binära trädet är lika med antalet noder i det trädet. Höjden på det binära trädet är antalet kanter mellan trädets rotnod och dess lövnod längst bort.

Python-kod för genomgång av binär sökträd

Nedan finns ett Python-program för att utföra alla tre genomgångar av binära sökträd:

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

Detta program bör producera följande utdata:

Måste-känna algoritmer för programmerare

Algoritmer är en viktig del av varje programmerares resa. Det är avgörande för en programmerare att vara väl insatt i algoritmer. Du bör vara bekant med några av algoritmerna som sammanslagningssortering, snabbsortering, binär sökning, linjär sökning, djup första sökning och så vidare.