Tree Traversal (în ordine, precomandă, postcomandă)

Ce este Tree Traversal?

În structura de date arborescentă, traversarea înseamnă vizitarea nodurilor într-un mod specific. Există două tipuri de traversări. În general, acest tip de traversare se bazează pe arborele binar. Un arbore binar înseamnă că fiecare nod poate avea maximum 2 noduri.

Un arbore binar este o structură de date binecunoscută. Există, de asemenea, un arbore de căutare binar (BST). Acest tip de traversare este utilizat în diverse scopuri. Parcursul nivelului de ordine, este folosit pentru calcularea adâncimii dintre două noduri. Există un alt tip de arbore numit „AVL”, unde este necesară calcularea înălțimii unui nod. Putem reprezenta un arbore binar în matrice, dar pentru optimizarea memoriei, vom folosi structura și pointerul pentru a face referire la următorul nod.

Tipuri de traversare a copacilor

Așa cum am discutat arbori binari, acum discutăm despre tipurile individuale de traversări. În funcție de tipuri, există două tipuri de traversare. Anterior am menționat necesitatea ordinii de nivel sau a traversării pe lățime. Acum Adâncime-Prima traversare așa cum ordinea post este folosită pentru ștergerea unui nod (o vom discuta mai târziu), preordinea este folosită pentru a copia un arbore binar, iar „inorder” va traversa arborele într-o manieră nedescrescătoare.

• Lățimea-Prima traversare
• Adâncime-Prima traversare
• Parcurs de precomandă
• Parcurs după comandă
• Parcurgere în ordine

Lățimea-Prima traversare

Este cunoscută și sub denumirea de traversare în ordinea nivelurilor. Să luăm în considerare următorul arbore pentru a demonstra traversarea în ordinea nivelurilor.

Deci, vom începe de la nodul rădăcină „1”. Va fi marcat ca nivelul 1. Apoi algoritmul va merge la toți copiii nodului curent. Vom vizita acum nodurile 2 și 3. Ele vor fi marcate ca nivelul 2.

După aceea, deoarece avem 2 noduri la nivelul 2, vom vizita și copiii lor. Deci, vom vizita 5,6,8,7 și le vom marca ca nivelul 3. Iată un lucru fără mențiune,

Nivelul nodului = nivelul nodului părinte + 1

Nivelul 1: 1

Nivelul 2: 2 3

Nivelul 3: 5 6 8 7

Un algoritm similar este utilizat pentru BFS (Lățimea-întâi-căutare).

Iată pseudocodul pentru traversarea ordinii de nivel:

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)

Arbore binar de traversare în ordine neordonată

Să avem același exemplu ca înainte. În acest tip de traversare, vizităm mai întâi subarborele din stânga, apoi rădăcina și după aceea, subarborele din dreapta. Pentru ușurință de amintire, putem spune că în ordine merge ca stânga-rădăcină-dreapta.

Pentru întregul arbore, să presupunem că rădăcina este 1. Acum algoritmul va urma:

• Vizitați subarborele din stânga al nodului 1.
• Nodul curent este 2 (deoarece este subarborele din stânga lui 1)

• Vizitați subarborele din stânga al lui 2. Nodul curent va fi 5 de data aceasta.
• Trecând la 5, nu are copii, așa că nodul 5 va fi marcat ca vizitat. Se va întoarce la nodul părinte; care este 2.
• Deoarece subarborele din stânga al lui 2 este vizitat, acum 2 va fi vizitat și.
• Algoritmul va muta nodul curent în subarborele din dreapta al nodului 2, care este nodul 6. După vizitarea nodului 6. Se va muta în nodul părinte 2.
• Pe măsură ce nodul 2 este vizitat, acum vom vizita părintele lui 2; care este nodul 1.
• După aceea, vom vizita subarborele potrivit.

Deci traversarea finală va arăta astfel:

În ordine: 5 → 2 → 6 → 1 → 8 → 3 → 7

Iată pseudocodul pentru traversarea în ordine:

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

Acesta este algoritmul recursiv pentru traversarea în ordine. Pentru Arborele de căutare binar (BST), Inorder traversal oferă matricea sortată de valori.

Traversare după comandă

În această traversare, vom parcurge mai întâi subarborele din stânga, apoi subarborele din dreapta după rădăcină. Toate traversările vor fi în Post-Comandă. Să demonstrăm un exemplu:

Aici pentru rădăcină = 1,

• Vom merge mai întâi la subarborele din stânga. Deci rădăcina va deveni 2.
• Apoi 2 a părăsit subarborele, așa că vom merge la nodul 5. Acum rădăcina este 5.
• Nu are subarborele din stânga, de asemenea, nu are subarborele din dreapta. Deci, acum vom marca nodul 5 ca vizitat și vom merge la nodul său părinte.

• Acum rădăcina este 2 și subarborele său din stânga este complet vizitat. Acum ne vom deplasa la subarborele din dreapta. Deci rădăcina devine 6.
• Deoarece nodul 6 nu are subarborele din stânga și din dreapta, vom marca nodul 6 vizitat și vom trece la nodul părinte 2.
• Acum, atât subarborele din stânga cât și din dreapta sunt vizitate pentru nodul 2. De asemenea, va fi marcat ca vizitat.
• Vom trece la părintele nodului 2, care este nodul 1.
• Subarborele din stânga este vizitat pentru rădăcina 1. Acum, în mod similar, vom vizita subarborele din dreapta.

Cercul marcat este subarborele din dreapta. Acum vom vizita subarborele din dreapta așa cum am vizitat subarborele din stânga. După aceea, vom vizita nodul. Deci traversarea finală va fi:

PostComandă: 5 → 6 → 2 → 8 → 7 → 3 → 1

Iată pseudocodul pentru traversarea după comandă:

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

Precomandă Traversal

Pentru parcurgerea precomenzii, algoritmul va vizita mai întâi nodul rădăcină, după care se va deplasa în subarborele din stânga și respectiv din dreapta. Pentru ușurință de înțelegere, ne putem gândi la vizite de traversare precomandate, cum ar fi rădăcină → stânga-dreapta.

Deci, să selectăm nodul 1 ca rădăcină.

• Conform algoritmului, rădăcina va fi descoperită mai întâi, apoi stânga și apoi subarborele din dreapta.
• Deci, vom vizita rădăcina 1. Apoi ne vom deplasa la subarborele din stânga. Rădăcina devine 2.
• Vom vizita nodul 2 și ne vom deplasa la subarborele său din stânga. Deci, rădăcina devine 3.
• Vizităm nodul 3, apoi trecem la nodul său părinte. Acum sunt vizitate nodul 2 și subarborele din stânga. E timpul să vizitezi subarborele potrivit.
• Vom trece la subarborele din dreapta, rădăcina devine 4. Vom vizita 4. Deoarece 4 nu are nod copil, ne vom muta la părintele său.
• Acum rădăcina este 2 și este vizitată împreună cu subarborele din stânga și din dreapta. Deci, vom trece la nodul său părinte. Acum rădăcina devine 1.
• În mod similar, vom vizita subarborele potrivit.

Precomandă: 1 → 2 → 3 → 4 → 5 → 6 → 7

Iată pseudocodul pentru traversarea precomenzii:

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

Implementarea în 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) >
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)

ieșire:

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

Implementarea în 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);
}

Ieșire:

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

Implementarea a C++ (Folosind std::queue pentru ordinea nivelului)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// 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);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new 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("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

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

Întrebări frecvente