Fák bejárása (sorrend, előrendelés és utánrendelés) példákkal

Mi az a Tree Traversal?

A fa adatszerkezetében a bejárás a csomópontok valamilyen meghatározott módon történő meglátogatását jelenti. Nodes2 típusú bejárások léteznek. Általában ez a fajta bejárás a bináris fán alapul. A bináris fa azt jelenti, hogy minden csomópontnak maximum 2 csomópontja lehet.

A bináris fa egy jól ismert adatstruktúra. Van egy bináris keresési fa (BST). Ezt a fajta bejárást különféle célokra használják. A szintrend bejárása, két csomópont közötti mélység kiszámítására szolgál. Létezik egy másik fafajta, az „AVL”, ahol egy csomópont magasságának kiszámítása szükséges. A tömbben egy bináris fát is ábrázolhatunk, de a memória optimalizálásához struktúrát és mutatót használunk a következő csomópontra való hivatkozáshoz.

A fa bejárásának típusai

Ahogy megbeszéltük bináris fák, most az egyes bejárástípusokat tárgyaljuk. A típustól függően kétféle bejárás létezik. Korábban már említettük a szintrend vagy a Breadth-First Traversal szükségességét. Most Mélység-első bejárás hasonlóan a post order egy csomópont törlésére szolgál (erről később lesz szó), az előrendelés a bináris fa másolására szolgál, az „inorder” pedig nem csökkenő módon halad át a fán.

• Breadth-First Traversal
• Mélység-első bejárás
• Előrendelési bejárás
• Utólagos bejárás
• Rend szerinti bejárás

Breadth-First Traversal

Szintrendű bejárásnak is nevezik. Tekintsük a következő fát a szintrend bejárás bemutatására.

Tehát az „1” gyökércsomópontból indulunk ki. 1. szintként lesz megjelölve. Ekkor az algoritmus az aktuális csomópont összes gyermekéhez megy. Most meglátogatjuk a 2. és 3. csomópontot. 2-es szintként lesznek megjelölve.

Ezt követően, mivel 2 csomópontunk van a 2. szinten, meglátogatjuk a gyerekeiket is. Tehát meglátogatjuk az 5,6,8,7, 3, XNUMX, XNUMX-et, és XNUMX-as szintként jelöljük meg őket.

Csomópont szintje = szülőcsomópont szintje + 1

1. szint: 1

2. szint: 2 3

3. szint: 5 6 8 7

Hasonló algoritmust használnak a BFS (Breadth-First-Search).

Íme a szintrend bejárásának pszeudokódja:

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

Vegyünk egy példát, mint korábban. Ennél a bejárástípusnál először a bal oldali részfát keressük fel, majd a gyökeret, majd ezt követően a jobb oldali részfát. Az emlékezés megkönnyítésére azt mondhatjuk, hogy a sorrend úgy megy, mint bal-gyökér-jobb.

Tegyük fel, hogy a teljes fa gyökere 1. Most az algoritmus a következő:

• Látogassa meg az 1. csomópont bal oldali részfáját.
• Az aktuális csomópont 2 (mivel az 1 bal oldali részfája)

• Látogassa meg a 2 bal oldali részfáját. Az aktuális csomópont ezúttal 5 lesz.
• Az 5-ösre költözve nincs gyermeke, így az 5-ös csomópont látogatottként lesz megjelölve. Visszatér a szülőcsomóponthoz; ami a 2.
• Mivel a 2 bal oldali részfa meg van látogatva, most a 2 is meg lesz látogatva.
• A algoritmus áthelyezi az aktuális csomópontot a 2. csomópont jobb oldali részfájába, amely a 6. csomópont. A 6. csomópont meglátogatása után. A 2. szülőcsomópontra lép.
• Mivel a 2. csomópont látogatott, most meglátogatjuk a 2 szülőjét; ami az 1. csomópont.
• Ezt követően meglátogatjuk a megfelelő részfát.

Tehát a végső bejárás így fog kinézni:

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

Íme az In-order bejárás pszeudokódja:

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

Ez az inorder bejárás rekurzív algoritmusa. A Bináris keresőfa (BST), Az Inorder bejárás megadja az értékek rendezett tömbjét.

Rendelés utáni bejárás

Ebben a bejárásban először a bal szélső részfán fogjuk bejárni, majd a gyökér után a jobb szélső részfán. Minden bejárás utólagos rendelésben történik. Mutassunk egy példát:

Itt gyökér = 1,

• Először a bal oldali részfához megyünk. Tehát a gyökér 2 lesz.
• Ekkor a 2 elhagyta a részfát, így az 5-ös csomópontra megyünk. Most a gyökér 5.
• Nincs bal oldali részfája, és nincs jobb oldali részfája sem. Tehát most az 5-ös csomópontot meglátogatottként jelöljük meg, és áttérünk a szülőcsomópontjára.

• Most a gyökér 2, és a bal oldali részfája teljesen fel van látogatva. Most áttérünk a jobb oldali részfájára. Tehát a gyökér 6 lesz.
• Mivel a 6. csomópontnak nincs bal- és jobboldali részfája, a 6. csomópontot meglátogatottnak jelöljük, és áttérünk a 2. szülőcsomópontra.
• Most a 2. csomópont bal és jobb oldali részfáját is meglátogatják. Ez is látogatottként lesz megjelölve.
• Áttérünk a 2. csomópont szülőjére, amely az 1. csomópont.
• A bal oldali részfa meglátogatása az 1. gyökér számára. Most hasonlóképpen meglátogatjuk a jobb oldali részfát.

A jelölt kör a jobb oldali részfa. Most meglátogatjuk a jobb oldali részfát, ahogy a bal oldali részfát. Ezt követően meglátogatjuk a csomópontot. Tehát a végső bejárás a következő lesz:

Utólagos rendelés: 5 → 6 → 2 → 8 → 7 → 3 → 1

Íme a rendelés utáni bejárás pszeudokódja:

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

Előrendelési bejárás

Az előrendelési bejárásnál az algoritmus először a gyökércsomópontot keresi fel, majd ezt követően a bal, illetve a jobb oldali részfába lép. A könnyebb érthetőség kedvéért gondolhatunk előrendelhető bejárási látogatásokra, mint pl gyökér → bal-jobb.

Tehát válasszuk az 1-es csomópontot gyökérként.

• Az algoritmus szerint először a gyökér kerül felfedezésre, majd a bal, majd a jobb oldali részfa.
• Tehát meglátogatjuk a gyökér 1-et. Ezután áttérünk a bal oldali részfájára. A gyökér 2 lesz.
• Meglátogatjuk a 2. csomópontot, és áttérünk a bal oldali részfájára. Tehát a gyökér 3 lesz.
• Meglátogatjuk a 3. csomópontot, majd áttérünk a szülőcsomópontjára. Most a 2. csomópont és annak bal oldali részfája kerül megtekintésre. Ideje meglátogatni a megfelelő részfát.
• A megfelelő részfára lépünk, a gyökér 4 lesz. Meglátogatjuk a 4-et. Mivel a 4-nek nincs gyermek csomópontja, áttérünk a szülőjére.
• Most a gyökér 2, és a bal és a jobb oldali részfával együtt felkeresik. Tehát áttérünk a szülőcsomópontra. Most a gyökér 1 lesz.
• Hasonlóképpen meglátogatjuk a megfelelő részfát.

Előrendelés: 1 → 2 → 3 → 4 → 5 → 6 → 7

Íme a rendelés utáni bejárás pszeudokódja:

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

Végrehajtás 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)

output:

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

Megvalósítás C-ben

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

Kimenet:

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

Végrehajtása C++ (std:queue használata a szintrendhez)

#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