Tree Traversals (Inorder, Preorder & Postorder) met voorbeelden

Door: Sara Chen Sara Chen
Hours Bijgewerkt

Wat is boomtraversal?

In de boomdatastructuur betekent traversal het op een specifieke manier bezoeken van knooppunten. Er zijn knooppunten2 soorten traversals. Over het algemeen is dit soort traversal gebaseerd op de binaire boom. Een binaire boom betekent dat elk knooppunt maximaal 2 knooppunten kan hebben.

Een binaire boom is een bekende datastructuur. Er is ook een binaire zoekboom (BST). Dit type traversal wordt voor verschillende doeleinden gebruikt. De niveauvolgorde wordt gebruikt voor het berekenen van de diepte tussen twee knooppunten. Er is een ander soort boom genaamd “AVL”, waarbij het berekenen van de hoogte van een knooppunt noodzakelijk is. We kunnen een binaire boom in de array weergeven, maar voor geheugenoptimalisatie gebruiken we structuur en aanwijzer om naar het volgende knooppunt te verwijzen.

Soorten boomtraversal

Zoals we besproken hebben binaire bomen, nu bespreken we de individuele soorten traversals. Afhankelijk van de typen zijn er twee soorten traversal. Eerder hebben we de noodzaak van niveauvolgorde of Breadth-First Traversal genoemd. Nu Diepte-eerste verplaatsing zoals post order wordt gebruikt voor het verwijderen van een knooppunt (we zullen dit later bespreken), preorder wordt gebruikt voor het kopiëren van een binaire boom, en “inorder” zal de boom op een niet-afnemende manier doorkruisen.

  • Breedte-eerste traversal
  • Diepte-eerste verplaatsing
  • Doorloop vooraf bestellen
  • Traversatie na bestelling
  • In volgorde doorlopen

Breedte-eerste traversal

Het staat ook bekend als de level-order traversal. Laten we de volgende boom beschouwen om de level-order traversal te demonstreren.

Breedte-eerste traversal

We beginnen dus vanaf het hoofdknooppunt “1”. Het wordt gemarkeerd als niveau 1. Vervolgens gaat het algoritme naar alle kinderen van het huidige knooppunt. We bezoeken nu knooppunt 2 en 3. Ze worden gemarkeerd als niveau 2.

Daarna zullen we, omdat we twee knooppunten hebben op niveau 2, ook hun kinderen bezoeken. We bezoeken dus 2 en markeren ze als niveau 5,6,8,7. Hier is iets dat niet wordt vermeld:

Knooppuntniveau = niveau van het bovenliggende knooppunt + 1

Niveau 1: 1

Niveau 2: 2 3

Niveau 3: 5 6 8 7

Een soortgelijk algoritme wordt gebruikt voor de BFS (Breedte-eerst-zoekopdracht).

Hier is de pseudocode voor het doorlopen van niveauvolgorde:

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-boom

Laten we hetzelfde voorbeeld nemen als voorheen. Bij dit soort traversal bezoeken we eerst de linker deelboom, dan de wortel, en daarna de rechter deelboom. Voor het gemak kunnen we zeggen dat de volgorde van links naar rechts gaat.

Inorder Traversal Bianry-boom

Laten we voor de hele boom zeggen dat de wortel 1 is. Nu volgt het algoritme:

  • Bezoek de linker subboom van knooppunt 1.
  • Het huidige knooppunt is 2 (aangezien dit de linkerdeelboom van 1 is)

Inorder Traversal Bianry-boom

  • Bezoek de linker subboom van 2. Het huidige knooppunt zal deze keer 5 zijn.
  • Verhuizen naar 5, het heeft geen kinderen, dus knooppunt 5 wordt gemarkeerd als bezocht. Het keert terug naar het bovenliggende knooppunt; dat is 2.
  • Omdat de linker subboom van 2 wordt bezocht, zullen er nu ook 2 worden bezocht.
  • De algoritme zal het huidige knooppunt naar de rechter subboom van knooppunt 2 verplaatsen, dat wil zeggen knooppunt 6. Na een bezoek aan knooppunt 6. Het zal naar het bovenliggende knooppunt 2 gaan.
  • Nu knooppunt 2 wordt bezocht, bezoeken we nu de ouder van knooppunt 2; dat is knooppunt 1.
  • Daarna bezoeken we de juiste subboom.

De uiteindelijke passage ziet er dus als volgt uit:

In volgorde: 5 → 2 → 6 → 1 → 8 → 3 → 7

Hier is de pseudocode voor het doorlopen van bestellingen:

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

Dit is het recursieve algoritme voor de inorder-traversal. Voor de Binaire zoekboom (BST)Inorder traversal geeft de gesorteerde reeks waarden.

GERELATEERDE ARTIKELEN

Traversatie na bestelling

Bij deze doorgang doorkruisen we eerst de meest linkse subboom en daarna de meest rechtse subboom na de wortel. Alle traversals zullen in Post-Order plaatsvinden. Laten we een voorbeeld demonstreren:

Traversatie na bestelling

Hier voor root = 1,

  • We gaan eerst naar de linker subboom. Dus de wortel wordt 2.
  • Dan heeft 2 de subboom verlaten, dus we gaan naar knooppunt 5. Nu is de wortel 5.
  • Het heeft geen linkerdeelboom, en ook geen rechterdeelboom. Dus nu markeren we knooppunt 5 als bezocht en gaan we naar het bovenliggende knooppunt.

Traversatie na bestelling

  • Nu is de wortel 2 en is de linker subboom volledig bezocht. We gaan nu naar de rechter subboom. Dus de wortel wordt 6.
  • Omdat knooppunt 6 geen linker- en rechtersubboom heeft, markeren we het bezochte knooppunt 6 en gaan we naar het bovenliggende knooppunt 2.
  • Nu worden zowel de linker als de rechter subboom bezocht voor knooppunt 2. Deze wordt ook gemarkeerd als bezocht.
  • We gaan naar het bovenliggende knooppunt van knooppunt 2, dat is knooppunt 1.
  • De linker subboom wordt bezocht voor root 1. Op dezelfde manier bezoeken we nu de rechter subboom.

Traversatie na bestelling

De gemarkeerde cirkel is de rechter deelboom. Nu zullen we de rechter subboom bezoeken zoals we de linker subboom bezochten. Daarna bezoeken we het knooppunt. De uiteindelijke doorgang zal dus zijn:

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

Hier is de pseudocode voor post-order traversal:

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

Traversal reserveren

Voor de pre-order-traversal zal het algoritme eerst het hoofdknooppunt bezoeken, daarna zal het respectievelijk naar de linker en rechter subboom gaan. Voor het gemak van het begrip kunnen we denken aan pre-order traversal-bezoeken zoals wortel → links-rechts.

Traversal reserveren

Laten we dus knooppunt 1 als root selecteren.

  • Volgens het algoritme wordt eerst de wortel ontdekt, vervolgens de linker en vervolgens de rechter subboom.
  • We gaan dus naar root 1. Daarna gaan we naar de linker subboom. De wortel wordt 2.
  • We bezoeken knooppunt 2 en gaan naar de linker subboom. De wortel wordt dus 3.
  • We bezoeken knooppunt 3 en gaan vervolgens naar het bovenliggende knooppunt. Nu worden knooppunt 2 en de linker subboom bezocht. Tijd om de juiste subboom te bezoeken.
  • We gaan naar de rechter subboom, de wortel wordt 4. We bezoeken 4. Omdat 4 geen onderliggend knooppunt heeft, gaan we naar het bovenliggende knooppunt.
  • Nu is root 2 en wordt deze samen met de linker en rechter subboom bezocht. We gaan dus naar het bovenliggende knooppunt. Nu wordt wortel 1.
  • Op dezelfde manier bezoeken we de juiste subboom.

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

Hier is de pseudocode voor post-order traversal:

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

implementatie in 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

Implementatie in 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);
}

Uitgang:

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

Invoer van C++ (Gebruik std:queue voor niveauvolgorde)

#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

Je houdt misschien van: