Puude läbimine (järjekorras, ettetellimisel ja järeltellimusel) koos näidetega

Mis on Tree Traversal?

Puu andmestruktuuris tähendab läbimine sõlmede külastamist mingil kindlal viisil. Seal on nodes2 tüüpi läbisõite. Üldiselt põhineb selline läbimine kahendpuul. Binaarne puu tähendab, et igal sõlmel võib olla maksimaalselt 2 sõlme.

Binaarne puu on hästi tuntud andmestruktuur. Samuti on olemas binaarne otsingupuu (BST). Seda tüüpi läbimist kasutatakse erinevatel eesmärkidel. Tasemejärjestuse läbimine, seda kasutatakse kahe sõlme vahelise sügavuse arvutamiseks. On veel üks puuliik, mida nimetatakse AVL-iks, mille puhul on vaja sõlme kõrgust arvutada. Võime esindada massiivi binaarpuud, kuid mälu optimeerimiseks kasutame struktuuri ja kursorit järgmisele sõlmele viitamiseks.

Puude läbimise tüübid

Nagu me rääkisime kahendpuud, käsitleme nüüd üksikuid läbisõidutüüpe. Sõltuvalt tüübist on kahte tüüpi läbimist. Varem oleme maininud tasemejärjestuse ehk Breadth-First Traversal'i vajalikkust. Nüüd Sügavus-esimene läbimine nagu postikorraldust kasutatakse sõlme kustutamiseks (me käsitleme seda hiljem), eeltellimust kasutatakse binaarpuu kopeerimiseks ja "inorder" läbib puu mittekahaneval viisil.

  • Breadth-First Traversal
  • Sügavus-esimene läbimine
  • Ettetellimisel läbisõit
  • Järeltellimus läbimine
  • Järjekorras läbisõit

Breadth-First Traversal

Seda tuntakse ka kui taseme-järjestuse läbimist. Vaatleme järgmist puud tasemejärjestuse läbimise demonstreerimiseks.

Breadth-First Traversal

Niisiis, alustame juursõlmest “1”. See märgitakse 1. tasemeks. Seejärel läheb algoritm kõigile praeguse sõlme lastele. Külastame nüüd sõlme 2 ja 3. Need märgitakse 2. tasemeks.

Pärast seda, kuna meil on 2. tasemel 2 sõlme, külastame ka nende lapsi. Niisiis, me külastame 5,6,8,7, 3, XNUMX, XNUMX ja märgime need XNUMX. tasemele. Siin on asi, mida ei mainita,

Sõlme tase = emasõlme tase + 1

1. tase: 1

Tase 2: 2 3

3. tase: 5 6 8 7

Sarnast algoritmi kasutatakse ka BFS (Breadth-First-Search).

Siin on tasemetellimuse läbimise pseudokood:

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

Toome sama näite, mis enne. Seda tüüpi läbimise puhul külastame esmalt vasakut alampuud, seejärel juurt ja pärast seda paremat alampuud. Meenutamise hõlbustamiseks võime öelda, et järjekord läheb nagu vasak-juur-parem.

Inorder Traversal Bianry Tree

Oletame, et kogu puu juur on 1. Nüüd järgneb algoritm:

  • Külastage sõlme 1 vasakut alampuud.
  • Praegune sõlm on 2 (kuna see on 1 vasakpoolne alampuu)

Inorder Traversal Bianry Tree

  • Külastage vasakut alampuud 2. Praegune sõlm on seekord 5.
  • Kolides 5. juurde, sellel pole lapsi, seega märgitakse sõlm 5 külastatuks. See naaseb vanemsõlme; mis on 2.
  • Kuna külastatakse 2 vasakut alampuud, siis nüüd külastatakse ka 2.
  • . algoritm liigutab praeguse sõlme 2. sõlme parempoolsesse alampuusse, mis on sõlm 6. Pärast sõlme 6 külastamist liigub see ülemsõlme 2.
  • Kuna külastatakse sõlme 2, siis nüüd külastame 2. vanemat; mis on sõlm 1.
  • Pärast seda külastame õiget alampuud.

Nii et lõplik läbimine näeb välja selline:

Järjestus: 5 → 2 → 6 → 1 → 8 → 3 → 7

Siin on järjekorras läbimise pseudokood:

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

See on järjestuse läbimise rekursiivne algoritm. jaoks Binaarne otsingupuu (BST), Inorder traversal annab sorteeritud väärtuste massiivi.

Tellimusejärgne läbimine

Selles läbimises läbime kõigepealt vasakpoolseima alampuu, seejärel juure järel kõige parempoolsema alampuu. Kõik läbisõidud on järeltellimusel. Toome näite:

Tellimusejärgne läbimine

Siin juur = 1,

  • Me läheme kõigepealt vasakpoolsesse alampuusse. Nii et juurest saab 2.
  • Siis on 2 lahkunud alampuust, seega läheme sõlme 5. Nüüd on juur 5.
  • Sellel pole vasakut alampuud ega ka paremat alampuud. Nüüd märgime sõlme 5 külastatuks ja läheme selle emasõlme juurde.

Tellimusejärgne läbimine

  • Nüüd on juur 2 ja selle vasak alampuu on täielikult külastatud. Liigume nüüd selle paremasse alampuusse. Nii et juur muutub 6-ks.
  • Kuna sõlmel 6 pole vasakut ja paremat alampuud, märgime sõlme 6 külastatuks ja liigume selle emasõlme 2 juurde.
  • Nüüd külastatakse sõlme 2 jaoks nii vasakut kui ka paremat alampuud. Ka see märgitakse külastatuks.
  • Liigume 2. sõlme emale, mis on sõlm 1.
  • Vasakpoolset alampuud külastatakse juur 1 jaoks. Nüüd külastame samamoodi ka paremat alampuud.

Tellimusejärgne läbimine

Märgitud ring on parempoolne alampuu. Nüüd külastame paremat alampuud, nagu me külastasime vasakut alampuud. Pärast seda külastame sõlme. Nii et viimane läbimine on järgmine:

Järeltellimus: 5 → 6 → 2 → 8 → 7 → 3 → 1

Siin on tellimusejärgse läbimise pseudokood:

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

Ettetellige läbimine

Eeltellimuse läbimise jaoks külastab algoritm kõigepealt juursõlme, seejärel liigub see vastavalt vasakule ja paremale alampuule. Arusaadavuse hõlbustamiseks võime mõelda ettetellitavatele läbisõidukülastustele nagu juur → vasak-parem.

Ettetellige läbimine

Niisiis, valime juureks sõlme 1.

  • Algoritmi kohaselt avastatakse kõigepealt juur, seejärel vasak ja seejärel parem alampuu.
  • Niisiis, me külastame juurt 1. Seejärel liigume selle vasakpoolsesse alampuusse. Juurest saab 2.
  • Külastame sõlme 2 ja liigume selle vasakpoolsesse alampuusse. Niisiis, juur muutub 3-ks.
  • Külastame sõlme 3, seejärel liigume selle ülemsõlme. Nüüd külastatakse sõlme 2 ja selle vasakut alampuud. Aeg külastada õiget alampuud.
  • Liigume paremale alampuule, juureks saab 4. Külastame 4. Kuna 4-l ei ole alampuud, liigume selle vanema juurde.
  • Nüüd on juur 2 ja seda külastatakse koos selle vasaku ja parema alampuuga. Nii et liigume selle emasõlme juurde. Nüüd saab juurtest 1.
  • Samamoodi külastame õiget alampuud.

Ettetellimine: 1 → 2 → 3 → 4 → 5 → 6 → 7

Siin on tellimusejärgse läbimise pseudokood:

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

Rakendamine sisse 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)

Väljund:

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

Rakendamine C-s

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

Väljund:

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

Programmi rakendamine C++ (Kasutades taseme järjestuse jaoks std:järjekorda)

#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