Obilasci stabla (po redoslijedu, unaprijed i nakon redoslijeda) s primjerima

Što je Tree Traversal?

U strukturi podataka stabla, obilazak znači posjećivanje čvorova na neki specifičan način. Postoje čvorovi2 tipa obilaska. Općenito, ova vrsta obilaženja temelji se na binarnom stablu. Binarno stablo znači da svaki čvor može imati najviše 2 čvora.

Binarno stablo je dobro poznata struktura podataka. Tu je i stablo binarnog pretraživanja (BST). Ova vrsta prelaska koristi se u razne svrhe. Prolaz reda razine, koristi se za izračunavanje dubine između dva čvora. Postoji još jedna vrsta stabla koja se zove "AVL", gdje je potrebno izračunati visinu čvora. Možemo predstaviti binarno stablo u nizu, ali za optimizaciju memorije koristit ćemo strukturu i pokazivač za referenciranje sljedećeg čvora.

Vrste obilaska stabala

Kao što smo raspravili binarna stabla, sada raspravljamo o pojedinačnim tipovima obilazaka. Ovisno o vrsti, postoje dvije vrste obilaska. Prethodno smo spomenuli potrebu za redoslijedom razina ili obilaskom u širinu. Sada Dubinski prijelaz kao što se post order koristi za brisanje čvora (o tome ćemo raspravljati kasnije), preorder se koristi za kopiranje binarnog stabla, a "inorder" će preći stablo na neopadajući način.

Prijelaz u širinu
Dubinski prijelaz
Prelazak narudžbe
Prolaz nakon narudžbe
Prolaz po redu

Prijelaz u širinu

Također je poznato kao obilazak reda razine. Razmotrimo sljedeće stablo za demonstraciju obilaska reda razine.

Dakle, krenut ćemo od korijenskog čvora "1". Bit će označeno kao razina 1. Tada će algoritam ići do svih potomaka trenutnog čvora. Sada ćemo posjetiti čvor 2 i 3. Oni će biti označeni kao razina 2.

Nakon toga, kako imamo 2 čvora u razini 2, posjetit ćemo i njihovu djecu. Dakle, posjetit ćemo 5,6,8,7 i označiti ih kao razinu 3. Evo nešto što ne spominjemo,

Razina čvora = razina nadređenog čvora + 1

Razina 1: 1

Razina 2: 2 3

Razina 3: 5 6 8 7

Sličan algoritam se koristi za BFS (Traži prvo u širinu).

Evo pseudokoda za prolazak redoslijeda razina:

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

Inorder Traversal Bianry Tree

Uzmimo isti primjer kao i prije. U ovoj vrsti obilaska prvo posjećujemo lijevo podstablo, zatim korijen, a nakon toga desno podstablo. Radi lakšeg pamćenja, možemo reći da red ide kao lijevo-korijen-desno.

Za cijelo stablo, recimo da je korijen 1. Sada će algoritam slijediti:

Posjetite lijevo podstablo čvora 1.
Trenutačni čvor je 2 (jer je to lijevo podstablo od 1)

Posjetite lijevo podstablo 2. Trenutačni čvor će ovaj put biti 5.
Prelaskom na 5, nema potomaka, pa će čvor 5 biti označen kao posjećen. Vratit će se na roditeljski čvor; što je 2.
Kako se posjećuje lijevo podstablo od 2, sada će se također posjećivati 2.
The algoritam će premjestiti trenutni čvor u desno podstablo čvora 2, što je čvor 6. Nakon posjete čvoru 6. Premjestit će se na svoj nadređeni čvor 2.
Kako je čvor 2 posjećen, sada ćemo posjetiti roditelja od 2; što je čvor 1.
Nakon toga ćemo posjetiti desno podstablo.

Dakle, konačno prelaženje će izgledati ovako:

Redoslijedom: 5 → 2 → 6 → 1 → 8 → 3 → 7

Evo pseudokoda za obilazak redoslijedom:

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

Ovo je rekurzivni algoritam za obilazak neredom. Za Stablo binarnog pretraživanja (BST), Inorder traversal daje sortirano polje vrijednosti.

Prolaz nakon narudžbe

U ovom obilasku, prvo ćemo obići krajnje lijevo podstablo, zatim krajnje desno podstablo nakon korijena. Sva obilaženja bit će u post-narudžbi. Pokažimo primjer:

Ovdje za korijen = 1,

Prvo ćemo ići na lijevo podstablo. Dakle, korijen će postati 2.
Zatim 2 ima lijevo podstablo, pa ćemo ići na čvor 5. Sada je korijen 5.
Nema lijevo podstablo, niti desno podstablo. Dakle, sada ćemo označiti čvor 5 kao posjećen i otići ćemo na njegov nadređeni čvor.

Sada je korijen 2 i njegovo lijevo podstablo je potpuno posjećeno. Sada ćemo prijeći na njegovo desno podstablo. Dakle, korijen postaje 6.
Kako čvor 6 nema lijevo i desno podstablo, označit ćemo čvor 6 posjećenim i pomaknuti se na njegov nadređeni čvor 2.
Sada se i lijevo i desno podstablo posjećuju za čvor 2. I on će biti označen kao posjećen.
Premjestit ćemo se na roditelja čvora 2, a to je čvor 1.
Lijevo podstablo posjećuje se za korijen 1. Sada ćemo na sličan način posjetiti desno podstablo.

Označeni krug je desno podstablo. Sada ćemo posjetiti desno podstablo kao što smo posjetili lijevo podstablo. Nakon toga ćemo posjetiti čvor. Dakle, konačni prijelaz će biti:

PostOrder: 5 → 6 → 2 → 8 → 7 → 3 → 1

Evo pseudokoda za prolazak nakon narudžbe:

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

Prolaz prednarudžbe

Za obilazak prednarudžbe, algoritam će prvo posjetiti korijenski čvor, nakon toga će se pomaknuti na lijevo odnosno desno podstablo. Radi lakšeg razumijevanja, možemo zamisliti posjete prije naručivanja kao što su korijen → lijevo-desno.

Dakle, odaberimo čvor 1 kao korijen.

Prema algoritmu, prvo će se otkriti korijen, zatim lijevo, a zatim desno podstablo.
Dakle, posjetit ćemo korijen 1. Zatim ćemo se pomaknuti na njegovo lijevo podstablo. Korijen postaje 2.
Posjetit ćemo čvor 2 i pomaknuti se na njegovo lijevo podstablo. Dakle, korijen postaje 3.
Posjećujemo čvor 3, zatim prelazimo na njegov nadređeni čvor. Sada se posjećuje čvor 2 i njegovo lijevo podstablo. Vrijeme je za posjet desnom podstablu.
Premjestit ćemo se na desno podstablo, korijen postaje 4. Posjetit ćemo 4. Kako 4 nema podređeni čvor, pomaknut ćemo se na njegovog roditelja.
Sada je korijen 2 i posjećuje se zajedno sa svojim lijevim i desnim podstablom. Dakle, prijeći ćemo na njegov nadređeni čvor. Sada root postaje 1.
Slično, posjetit ćemo desno podstablo.

Prednarudžba: 1 → 2 → 3 → 4 → 5 → 6 → 7

Evo pseudokoda za prolazak nakon narudžbe:

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

Implementacija u Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

Izlaz:

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

Implementacija u C

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}