Tree Traversal (Inorder, Preorder, Postorder)

Vad är Tree Traversal?

I träddatastrukturen betyder traversering att besöka noder på ett specifikt sätt. Det finns två typer av traverseringar. Generellt sett är denna typ av traversering baserad på det binära trädet. Ett binärt träd innebär att varje nod kan ha maximalt 2 noder.

Ett binärt träd är en välkänd datastruktur. Det finns också ett binärt sökträd (BST). Denna typ av traversering används för olika ändamål. Nivåordningsgenomgången, den används för att beräkna djupet mellan två noder. Det finns en annan typ av träd som kallas "AVL", där det är nödvändigt att beräkna höjden på en nod. Vi kan representera ett binärt träd i arrayen, men för minnesoptimering kommer vi att använda struktur och pekare för att referera till nästa nod.

Typer av trädpassering

Som vi diskuterade binära träd, nu diskuterar vi de enskilda typerna av traverseringar. Beroende på typerna finns det två typer av traversering. Tidigare har vi nämnt nödvändigheten av nivåordning eller Breadth-First Traversal. Nu Depth-First Traversal som postorder används för radering av en nod (vi kommer att diskutera det senare), preorder används för att kopiera ett binärt träd, och "inorder" kommer att korsa trädet på ett icke-minskande sätt.

• Bredd-första genomgång
• Depth-First Traversal
• Förbeställ genomgång
• Genomgång efter order
• Beställningskorsning

Bredd-första genomgång

Det är också känt som genomgång av nivåordning. Låt oss överväga följande träd för att demonstrera nivåordningsgenomgången.

Så vi börjar från rotnoden "1". Den kommer att markeras som nivå 1. Sedan kommer algoritmen att gå till alla barn i den aktuella noden. Vi besöker nod 2 och 3 nu. De kommer att markeras som nivå 2.

Efter det, eftersom vi har 2 noder på nivå 2, kommer vi att besöka deras barn också. Så vi kommer att besöka 5,6,8,7 och markera dem som nivå 3. Här är en sak som inte nämns,

Nodens nivå = föräldernodens nivå + 1

Nivå 1: 1

Nivå 2: 2 3

Nivå 3: 5 6 8 7

En liknande algoritm används för BFS (Utöka första sökningen).

Här är pseudokoden för genomgång av nivåordning:

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ärt träd

Låt oss ta samma exempel som tidigare. I denna typ av traversering besöker vi först det vänstra underträdet, sedan roten och efter det det högra underträdet. För att göra det lättare att komma ihåg kan vi säga att det går som vänster-rot-höger.

För hela trädet, låt oss säga att roten är 1. Nu följer algoritmen:

• Besök det vänstra underträdet av nod 1.
• Den nuvarande noden är 2 (eftersom det är det vänstra underträdet av 1)

• Besök det vänstra underträdet av 2. Den aktuella noden kommer att vara 5 denna gång.
• Flytta till 5, det har inga barn, så nod 5 kommer att markeras som besökt. Den kommer att återgå till föräldranoden; vilket är 2.
• Eftersom det vänstra underträdet av 2 besöks, kommer nu 2 att besökas också.
• Ocuco-landskapet algoritm kommer att flytta den aktuella noden till höger underträd av nod 2, vilket är nod 6. Efter att ha besökt nod 6. Den kommer att flytta till sin överordnade nod 2.
• När nod 2 besöks kommer vi nu att besöka föräldern till 2; som är nod 1.
• Efter det kommer vi att besöka det högra underträdet.

Så den sista genomgången kommer att se ut så här:

I ordning: 5 → 2 → 6 → 1 → 8 → 3 → 7

Här är pseudokoden för in-order-traversal:

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

Detta är den rekursiva algoritmen för övergången av oordning. För Binärt sökträd (BST), Inorder-traversal ger den sorterade matrisen av värden.

Traversering efter beställning

I den här genomgången kommer vi att korsa underträdet längst till vänster först, sedan underträdet längst till höger efter roten. Alla övergångar kommer att vara i Post-Order. Låt oss visa ett exempel:

Här för rot = 1,

• Vi går först till vänster underträd. Så roten blir 2.
• Då har 2 lämnat underträdet, så vi går till nod 5. Nu är roten 5.
• Det har inget vänster underträd, det har inte heller något höger underträd. Så nu kommer vi att markera nod 5 som besökt och vi går till dess överordnade nod.

• Nu är roten 2 och dess vänstra underträd är helt besökt. Vi kommer nu att flytta till dess högra underträd. Så roten blir 6.
• Eftersom nod 6 inte har något vänster och höger underträd, kommer vi att markera nod 6 som besökt och flytta till dess överordnade nod 2.
• Nu besöks både vänster och höger underträd för nod 2. Det kommer också att markeras som besökt.
• Vi flyttar till föräldern till nod 2, som är nod 1.
• Det vänstra underträdet besöks för rot 1. På samma sätt kommer vi nu att besöka det högra underträdet.

Cirkeln markerad är det högra underträdet. Nu kommer vi att besöka det högra underträdet som vi besökte det vänstra underträdet. Efter det kommer vi att besöka noden. Så den sista genomgången blir:

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

Här är pseudokoden för genomgång av postorder:

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

Förbeställningstrafik

För förbeställningsgenomgången kommer algoritmen att besöka rotnoden först, efter det kommer den att flyttas till vänster respektive höger underträd. För att underlätta förståelsen kan vi tänka på förbeställning av genomgångsbesök som rot → vänster-höger.

Så låt oss välja nod 1 som rot.

• Enligt algoritmen kommer roten att upptäckas först, sedan det vänstra och sedan det högra underträdet.
• Så vi besöker rot 1. Sedan flyttar vi till dess vänstra underträd. Roten blir 2.
• Vi besöker nod 2 och går vidare till dess vänstra underträd. Så roten blir 3.
• Vi besöker nod 3, sedan flyttar vi till dess modernod. Nu besöks nod 2 och dess vänstra underträd. Dags att besöka rätt underträd.
• Vi flyttar till höger underträd, roten blir 4. Vi besöker 4. Eftersom 4 inte har någon underordnad nod, flyttar vi till dess förälder.
• Nu är roten 2 och den besöks tillsammans med dess vänstra och högra underträd. Så vi flyttar till dess överordnade nod. Nu blir root 1.
• På samma sätt kommer vi att besöka det högra underträdet.

Förbeställning: 1 → 2 → 3 → 4 → 5 → 6 → 7

Här är pseudokoden för förbeställningstraversering:

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

Genomförande 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)

Produktion:

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

Införande av C++ (Använder std::queue för nivåordning)

#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

Vanliga frågor