Tregjennomgang (Inorder, Preorder, Postorder)

Hva er Tree Traversal?

I datastrukturen for treet betyr traversering å besøke noder på en spesifikk måte. Det finnes to typer traverseringer. Vanligvis er denne typen traversering basert på det binære treet. Et binært tre betyr at hver node kan ha maksimalt 2 noder.

Et binært tre er en velkjent datastruktur. Det er også et binært søketre (BST). Denne typen traversering brukes til ulike formål. Nivårekkefølgen, den brukes til å beregne dybden mellom to noder. Det er en annen type tre kalt "AVL", der det er nødvendig å beregne høyden på en node. Vi kan representere et binært tre i matrisen, men for minneoptimalisering vil vi bruke struktur og peker for å referere til neste node.

Typer trekryssing

Som vi diskuterte binære trær, nå diskuterer vi de enkelte typene traverseringer. Avhengig av typene er det to typer traversering. Tidligere har vi nevnt nødvendigheten av nivårekkefølge eller Breadth-First Traversal. Nå Dybde-første traversering som postordre brukes for sletting av en node (vi vil diskutere det senere), preorder brukes for å kopiere et binært tre, og "inorder" vil krysse treet på en ikke-minskende måte.

• Breadth-First Traversal
• Dybde-første traversering
• Forhåndsbestill traversering
• Traversering etter bestilling
• Traversering i rekkefølge

Breadth-First Traversal

Det er også kjent som nivårekkefølgen. La oss vurdere følgende tre for å demonstrere nivårekkefølgen.

Så vi starter fra rotnoden "1". Den vil bli merket som nivå 1. Deretter vil algoritmen gå til alle barna til gjeldende node. Vi besøker node 2 og 3 nå. De vil bli merket som nivå 2.

Etter det, siden vi har 2 noder på nivå 2, besøker vi barna deres også. Så vi besøker 5,6,8,7 og markerer dem som nivå 3. Her er en ting som ikke nevnes,

Nivå av node = overordnet nodes nivå + 1

Nivå 1: 1

Nivå 2: 2 3

Nivå 3: 5 6 8 7

En lignende algoritme brukes for BFS (Bredde-først-søk).

Her er pseudokoden for gjennomgang av nivåordre:

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 binærtre

La oss ta det samme eksempelet som før. I denne typen traversering besøker vi først det venstre undertreet, deretter roten, og deretter det høyre undertreet. For å lette å huske kan vi si at rekkefølgen går som venstre-rot-høyre.

For hele treet, la oss si at roten er 1. Nå vil algoritmen følge:

• Besøk det venstre undertreet til node 1.
• Den nåværende noden er 2 (ettersom det er venstre undertre av 1)

• Gå til venstre undertre av 2. Gjeldende node vil være 5 denne gangen.
• Flytter til 5, den har ingen barn, så node 5 vil bli merket som besøkt. Den vil gå tilbake til overordnet node; som er 2.
• Ettersom venstre undertre av 2 er besøkt, vil nå 2 også bli besøkt.
• Ocuco algoritme vil flytte gjeldende node til høyre undertre av node 2, som er node 6. Etter å ha besøkt node 6. Den vil flytte til sin overordnede node 2.
• Ettersom node 2 er besøkt, vil vi nå besøke forelderen til 2; som er node 1.
• Etter det besøker vi det høyre undertreet.

Så den endelige gjennomgangen vil se slik ut:

I rekkefølge: 5 → 2 → 6 → 1 → 8 → 3 → 7

Her er pseudokoden for in-order traversering:

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

Dette er den rekursive algoritmen for gjennomgang av uorden. For Binært søketre (BST), Inorder-gjennomgang gir den sorterte matrisen av verdier.

Traversering etter bestilling

I denne traverseringen vil vi krysse undertreet lengst til venstre først, deretter undertreet lengst til høyre etter roten. Alle gjennomgangene vil være i etterbestilling. La oss demonstrere et eksempel:

Her for rot = 1,

• Vi går først til venstre undertre. Så roten blir 2.
• Da har 2 forlatt undertreet, så vi går til node 5. Nå er roten 5.
• Det har ikke noe venstre undertre, det har heller ikke noe høyre undertre. Så nå vil vi merke node 5 som besøkt, og vi går til dens overordnede node.

• Nå er roten 2 og venstre undertre er fullstendig besøkt. Vi vil nå flytte til høyre undertre. Så roten blir 6.
• Siden node 6 ikke har noe venstre og høyre undertre, vil vi merke node 6 som besøkt og flytte til overordnet node 2.
• Nå blir både venstre og høyre undertre besøkt for node 2. Det vil også bli merket som besøkt.
• Vi går til overordnet til node 2, som er node 1.
• Det venstre undertreet besøkes for rot 1. På samme måte besøker vi det høyre undertreet.

Sirkelen merket er det høyre undertreet. Nå skal vi besøke det høyre undertreet slik vi besøkte det venstre undertreet. Etter det vil vi besøke noden. Så den siste gjennomgangen blir:

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

Her er pseudokoden for etterbestilling:

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

Forhåndsbestill Traversal

For forhåndsbestillingsgjennomgangen vil algoritmen besøke rotnoden først, etter det vil den flytte til henholdsvis venstre og høyre undertre. For å lette forståelsen, kan vi tenke på forhåndsbestill traversale besøk som rot → venstre-høyre.

Så la oss velge node 1 som roten.

• I henhold til algoritmen vil roten bli oppdaget først, deretter det venstre og deretter det høyre undertreet.
• Så vi besøker rot 1. Deretter flytter vi til venstre undertre. Roten blir 2.
• Vi besøker node 2 og går til dens venstre undertre. Dermed blir roten 3.
• Vi besøker node 3, så flytter vi til dens overordnede node. Nå er node 2 og dets venstre undertre besøkt. På tide å besøke det riktige undertreet.
• Vi flytter til høyre undertre, roten blir 4. Vi besøker 4. Siden 4 ikke har noen underordnet node, flytter vi til dens overordnede node.
• Nå er root 2 og den besøkes sammen med venstre og høyre undertre. Så vi går til overordnet node. Nå blir root 1.
• På samme måte besøker vi det høyre undertreet.

Forhåndsbestilling: 1 → 2 → 3 → 4 → 5 → 6 → 7

Her er pseudokoden for forhåndsbestillingsgjennomgang:

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

Gjennomføring i 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)

Utgang:

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

Implementering i 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);
}

Produksjon:

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

Implementering av C++ (Bruker std::queue for nivårekkefølge)

#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

Spørsmål og svar