Trægennemgange (Inorder, Preorder & Postorder) med eksempler

Af: Sarah Chen Sarah Chen
Hours Opdateret

Hvad er Tree Traversal?

I trædatastrukturen betyder traversal at besøge noder på en bestemt måde. Der er nodes2 typer af gennemløb. Generelt er denne form for krydsning baseret på det binære træ. Et binært træ betyder, at hver node maksimalt kan have 2 noder.

Et binært træ er en velkendt datastruktur. Der er også et binært søgetræ (BST). Denne type traversering bruges til forskellige formål. Niveauordregennemgangen, den bruges til at beregne dybden mellem to noder. Der er en anden slags træ kaldet "AVL", hvor det er nødvendigt at beregne højden af ​​en node. Vi kan repræsentere et binært træ i arrayet, men til hukommelsesoptimering bruger vi struktur og pointer til at referere til den næste node.

Typer af trægennemgang

Som vi diskuterede binære træer, nu diskuterer vi de enkelte typer af gennemløb. Afhængigt af typerne er der to typer gennemløb. Tidligere har vi nævnt nødvendigheden af ​​niveaurækkefølge eller Breadth-First Traversal. Nu Dybde-første gennemkørsel ligesom postordre bruges til sletning af en node (vi vil diskutere det senere), preorder bruges til at kopiere et binært træ, og "inorder" vil krydse træet på en ikke-aftagende måde.

  • Bredde-første gennemgang
  • Dybde-første gennemkørsel
  • Forudbestil traversal
  • Gennemgang efter ordre
  • Bestil gennemgang

Bredde-første gennemgang

Det er også kendt som niveau-orden-gennemgangen. Lad os overveje følgende træ for at demonstrere niveaurækkefølgen.

Bredde-første gennemgang

Så vi starter fra rodnoden "1". Det vil blive markeret som niveau 1. Derefter vil algoritmen gå til alle børnene i den aktuelle node. Vi besøger node 2 og 3 nu. De vil blive markeret som niveau 2.

Efter det, da vi har 2 noder på niveau 2, besøger vi også deres børn. Så vi besøger 5,6,8,7 og markerer dem som niveau 3. Her er en ting, der ikke nævnes,

Nodeniveau = overordnet nodes niveau + 1

Niveau 1: 1

Niveau 2: 2 3

Niveau 3: 5 6 8 7

En lignende algoritme bruges til BFS (Bredde-først-søgning).

Her er Pseudokoden for niveaurækkefølgegennemgang:

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

Lad os få det samme eksempel som før. I denne type traversering besøger vi først det venstre undertræ, derefter roden og derefter det højre undertræ. For at lette hukommelsen kan vi sige, at rækkefølgen går som venstre-rod-højre.

Inorder Traversal Bianry Tree

For hele træet, lad os sige, at roden er 1. Nu vil algoritmen følge:

  • Besøg venstre undertræ af node 1.
  • Den aktuelle node er 2 (da det er venstre undertræ af 1)

Inorder Traversal Bianry Tree

  • Besøg venstre undertræ af 2. Den aktuelle node vil være 5 denne gang.
  • Flytter den til 5, den har ingen børn, så node 5 vil blive markeret som besøgt. Den vender tilbage til den overordnede node; hvilket er 2.
  • Da venstre undertræ af 2 besøges, vil nu 2 også blive besøgt.
  • algoritme vil flytte den aktuelle node til højre undertræ af node 2, som er node 6. Efter at have besøgt node 6. Den vil flytte til sin overordnede node 2.
  • Da node 2 er besøgt, vil vi nu besøge forælderen til 2; som er node 1.
  • Derefter besøger vi det rigtige undertræ.

Så den endelige gennemgang vil se sådan ud:

I rækkefølge: 5 → 2 → 6 → 1 → 8 → 3 → 7

Her er pseudokoden for gennemkørsel i rækkefølge:

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

Dette er den rekursive algoritme for gennemkøring af uorden. For Binært søgetræ (BST), Inorder traversal giver den sorterede matrix af værdier.

RELATEREDE ARTIKLER

Efterbestilling gennemkørsel

I denne traversering vil vi krydse undertræet længst til venstre først, derefter undertræet længst til højre efter roden. Alle gennemkørsler vil være i Post-Order. Lad os demonstrere et eksempel:

Efterbestilling gennemkørsel

Her for root = 1,

  • Vi går først til venstre undertræ. Så roden bliver 2.
  • Så har 2 forladt undertræet, så vi går til node 5. Nu er roden 5.
  • Det har intet venstre undertræ, det har heller ikke noget højre undertræ. Så nu vil vi markere node 5 som besøgt, og vi går til dens overordnede node.

Efterbestilling gennemkørsel

  • Nu er roden 2 og dens venstre undertræ er fuldstændig besøgt. Vi vil nu flytte til dets højre undertræ. Så roden bliver 6.
  • Da node 6 ikke har noget venstre og højre undertræ, markerer vi node 6 som besøgt og flytter til dens overordnede node 2.
  • Nu bliver både venstre og højre undertræ besøgt for node 2. Det vil også blive markeret som besøgt.
  • Vi flytter til forælderen til node 2, som er node 1.
  • Det venstre undertræ besøges for rod 1. På samme måde besøger vi det højre undertræ.

Efterbestilling gennemkørsel

Den markerede cirkel er det højre undertræ. Nu vil vi besøge det højre undertræ, som vi besøgte det venstre undertræ. Derefter besøger vi noden. Så den sidste gennemgang bliver:

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

Her er pseudokoden til postordre-gennemgang:

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

Forudbestil gennemgang

For forudbestillingsgennemgangen vil algoritmen først besøge rodnoden, derefter vil den flytte til henholdsvis venstre og højre undertræ. For at lette forståelsen kan vi tænke på forudbestil traversal besøg som rod → venstre-højre.

Forudbestil gennemgang

Så lad os vælge node 1 som rod.

  • I henhold til algoritmen vil roden blive opdaget først, derefter det venstre og derefter det højre undertræ.
  • Så vi besøger rod 1. Så flytter vi til dets venstre undertræ. Roden bliver 2.
  • Vi besøger node 2 og flytter til dets venstre undertræ. Så roden bliver 3.
  • Vi besøger node 3, så flytter vi til dens overordnede node. Nu er node 2 og dets venstre undertræ besøgt. Tid til at besøge det rigtige undertræ.
  • Vi flytter til det højre undertræ, roden bliver 4. Vi besøger 4. Da 4 ikke har nogen underordnet node, flytter vi til dens forælder.
  • Nu er root 2, og det besøges sammen med dets venstre og højre undertræ. Så vi flytter til dens overordnede node. Nu bliver root 1.
  • På samme måde besøger vi det rigtige undertræ.

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

Her er pseudokoden til postordre-gennemgang:

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

Gennemførelse 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) & 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

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

Produktion:

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

Gennemførelse af C++ (Bruger std:kø til niveaurækkefø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

Dagligt Guru99 Nyhedsbrev

Start dagen med de seneste og vigtigste AI-nyheder leveret lige nu.