Cum să traversezi un arbore de căutare binar

Arborii binari sunt una dintre cele mai utilizate structuri de date în programare. Un arbore de căutare binar (BST) permite stocarea datelor sub formă de noduri (nodul părinte și nodul copil nodul) astfel încât nodul copil stâng este mai mic decât nodul părinte și nodul copil drept este mai mare.

Arborii binari de căutare permit operații eficiente de parcurgere, căutare, ștergere și inserare. În acest articol, veți afla despre cele trei moduri de a parcurge un arbore de căutare binar: parcurgerea precomandă, traversarea în ordine și traversarea post-comandă.

Traversarea în ordine

Parcurgerea în ordine este procesul de parcurgere a nodurilor a arbore binar de căutare procesând recursiv subarborele din stânga, apoi procesând nodul rădăcină și, în final, procesând recursiv subarborele din dreapta. Deoarece procesează nodurile în ordine crescătoare a valorii, tehnica se numește traversare în ordine.

Traversarea este procesul de vizitare a fiecărui nod dintr-o structură de date arborescentă exact o dată.

Algoritmul traversării în ordine

Repetați pentru a traversa toate nodurile BST:

1. Traversați recursiv subarborele din stânga.
2. Vizitați nodul rădăcină.
3. Traversați recursiv subarborele din dreapta.

Vizualizarea traversării în ordine

Un exemplu vizual poate ajuta la explicarea traversării arborelui de căutare binar. Această figură arată parcurgerea în ordine a unui exemplu de arbore binar de căutare:

În acest arbore de căutare binar, 56 este nodul rădăcină. Mai întâi, trebuie să traversați subarborele din stânga 32, apoi nodul rădăcină 56 și apoi subarborele din dreapta 62.

Pentru subarborele 32, traversați mai întâi subarborele din stânga, 28. Acest subarbore nu are copii, așa că apoi traversați nodul 32. Apoi, traversați subarborele din dreapta, 44, care, de asemenea, nu are copii. Prin urmare, ordinea de parcurgere pentru subarborele înrădăcinat la 32 este 28 -> 32 -> 44.

Apoi, vizitați nodul rădăcină, 56.

Apoi, traversați subarborele din dreapta, înrădăcinat la 62. Începeți prin a parcurge subarborele din stânga, înrădăcinat la 58. Nu are copii, așa că vizitați nodul 62 în continuare. În cele din urmă, traversați subarborele din dreapta, 88, care, de asemenea, nu are copii.

Deci algoritmul vizitează nodurile arborelui în următoarea ordine:

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

Aplicarea traversării în ordine

Puteți utiliza traversarea în ordine pentru a obține valorile elementelor nodului în ordine crescătoare. Pentru a obține valorile în ordine descrescătoare, pur și simplu inversați procesul: vizitați subarborele din dreapta, apoi nodul rădăcină, apoi subarborele din stânga. Puteți utiliza algoritmul pentru a găsi expresia prefixului unui arbore de expresii.

Precomandă Traversal

Parcurgerea precomanda este similară cu inorder, dar procesează nodul rădăcină înainte de a procesa recursiv subarborele din stânga, apoi subarborele din dreapta.

Algoritmul traversării precomenzilor

Repetați pentru a traversa toate nodurile BST:

1. Vizitați nodul rădăcină.
2. Traversați recursiv subarborele din stânga.
3. Traversați recursiv subarborele din dreapta.

Vizualizarea traversării precomenzilor

Următoarea figură arată parcurgerea în precomandă a arborelui de căutare binar:

În acest arbore de căutare binar, începeți prin a procesa nodul rădăcină, 56. Apoi traversați subarborele din stânga, 32, urmat de subarborele din dreapta, 62.

Pentru subarborele din stânga, procesați valoarea la nodul rădăcină, 32. Apoi, traversați subarborele din stânga, 28, apoi în cele din urmă subarborele din dreapta, 44. Aceasta completează traversarea subarborelui din stânga cu rădăcină la 32. Parcurgerea are loc în următoarea ordine: 56 -> 32 -> 28 -> 44.

Pentru subarborele din dreapta, procesați valoarea la nodul rădăcină, 62. Apoi, traversați subarborele din stânga, 58, apoi în cele din urmă subarborele din dreapta, 88. Din nou, niciunul dintre noduri nu are copii, așa că traversarea este completă în acest moment.

Ați străbătut arborele complet în următoarea ordine:

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

Aplicarea traversării precomenzilor

Puteți utiliza traversarea precomanda pentru a crea o copie a arborelui cel mai ușor.

Traversare după comandă

Parcurgerea postorder este procesul de parcurgere recursiv a nodurilor unui arbore binar de căutare procesând subarborele din stânga, apoi procesând recursiv subarborele din dreapta și, în final, procesând nodul rădăcină. Deoarece procesează nodul rădăcină după ambii subarbori, această metodă se numește traversare post-ordine.

Algoritm de traversare a postorderului

Repetați pentru a traversa toate nodurile BST:

1. Traversați recursiv subarborele din stânga.
2. Traversați recursiv subarborele din dreapta.
3. Vizitați nodul rădăcină.

Vizualizarea traversării post-comandă

Următoarea figură arată traversarea post-comandă a arborelui de căutare binar:

Începeți prin a parcurge subarborele din stânga, 32, apoi subarborele din dreapta, 62. Terminați prin procesarea nodului rădăcină, 56.

Pentru a procesa subarborele, înrădăcinat la 32, traversați subarborele din stânga, 28. Deoarece 28 nu are copii, treceți în subarborele din dreapta, 44. Procesul 44 deoarece nici nu are copii. În sfârșit, procesați nodul rădăcină, 32. Ați parcurs acest subarboresc în ordinea 28 -> 44 -> 32.

Procesați subarborele drept folosind aceeași abordare pentru a vizita nodurile în ordinea 58 -> 88 → 62.

În cele din urmă, procesați nodul rădăcină, 56. Veți traversa arborele complet în această ordine:

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

Aplicarea Traversarii Postorder

Puteți folosi traversarea post-comandă pentru a șterge un arbore de la frunză la rădăcină. De asemenea, îl puteți folosi pentru a găsi expresia postfixă a unui arbore de expresii.

Pentru a vizita toate nodurile frunze ale unui anumit nod înainte de a vizita nodul în sine, puteți utiliza tehnica de traversare post-ordine.

Complexitatea în timp și spațiu a traversărilor arborelui de căutare binar

Complexitatea în timp a tuturor celor trei tehnici de traversare este Pe), Unde n este dimensiunea arbore binar. Complexitatea spațială a tuturor tehnicilor de traversare este Oh), Unde h este înălțimea arborelui binar.

Mărimea arborelui binar este egală cu numărul de noduri din arborele respectiv. Înălțimea arborelui binar este numărul de muchii dintre nodul rădăcină al arborelui și cel mai îndepărtat nod al frunzei.

Cod Python pentru traversarea arborelui de căutare binar

Mai jos este un program Python pentru a efectua toate cele trei traversări ale arborelui de căutare binar:

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

Acest program ar trebui să producă următorul rezultat:

Algoritmi obligatorii pentru programatori

Algoritmii sunt o parte esențială a călătoriei fiecărui programator. Este crucial ca un programator să fie bine versat în algoritmi. Ar trebui să fiți familiarizați cu unii dintre algoritmi, cum ar fi sortarea prin îmbinare, sortarea rapidă, căutarea binară, căutarea liniară, căutarea în profunzime și așa mai departe.