Traversal Pohon (Inorder, Preorder & Postorder) dengan Contoh

Apa itu Penjelajahan Pohon?

Dalam struktur data pohon, traversal berarti mengunjungi node dengan cara tertentu. Ada jenis traversal node2. Umumnya traversal semacam ini didasarkan pada pohon biner. Pohon biner berarti setiap node dapat memiliki maksimal 2 node.

Pohon biner adalah struktur data yang terkenal. Ada juga pohon Pencarian Biner (BST). Jenis traversal ini digunakan untuk berbagai tujuan. Traversal urutan tingkat, digunakan untuk menghitung kedalaman antara dua node. Ada jenis pohon lain yang disebut “AVL”, yang memerlukan penghitungan ketinggian sebuah simpul. Kita dapat merepresentasikan pohon Biner dalam array, namun untuk optimasi memori, kita akan menggunakan struktur dan pointer untuk mereferensikan node berikutnya.

Jenis Penjelajahan Pohon

Seperti yang kita diskusikan pohon biner, sekarang kita membahas masing-masing jenis traversal. Tergantung pada jenisnya, ada dua jenis traversal. Sebelumnya kami telah menyebutkan perlunya urutan level atau Breadth-First Traversal. Sekarang Traversal Kedalaman-Pertama seperti post order digunakan untuk menghapus node (kita akan membahasnya nanti), preorder digunakan untuk menyalin pohon Biner, dan “inorder” akan melintasi pohon tanpa penurunan.

Traversal Luas-Pertama
Traversal Kedalaman-Pertama
Penjelajahan pra-pemesanan
Penjelajahan pasca pesanan
Inversal pesanan

Traversal Luas-Pertama

Ini juga dikenal sebagai traversal level-order. Mari kita perhatikan pohon berikut untuk menunjukkan traversal level-order.

Jadi, kita akan mulai dari node root “1”. Ini akan ditandai sebagai level 1. Kemudian algoritma akan menuju ke semua anak dari node saat ini. Kami akan mengunjungi node 2 dan 3 sekarang. Mereka akan ditandai sebagai level 2.

Setelah itu, karena kita memiliki 2 node di level 2, kita akan mengunjungi anaknya juga. Jadi, kita akan mengunjungi 5,6,8,7 dan menandainya sebagai level 3. Ada hal yang tidak perlu disebutkan,

Level node = level node induk + 1

Tingkat 1: 1

Tingkat 2: 2 3

Tingkat 3: 5 6 8 7

Algoritma serupa digunakan untuk BFS (Pencarian Luas-Pertama).

Berikut Pseudocode untuk traversal level order:

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)

Pohon Bianry Traversal Inorder

Mari kita ambil contoh yang sama seperti sebelumnya. Pada jenis traversal ini, pertama-tama kita mengunjungi subpohon kiri, lalu akar, dan setelah itu, subpohon kanan. Untuk memudahkan mengingat, kita dapat mengatakan urutannya seperti akar kiri-kanan.

Untuk keseluruhan pohon, misalkan akarnya adalah 1. Sekarang algoritmanya akan mengikuti:

Kunjungi subpohon kiri dari node 1.
Node saat ini adalah 2 (karena merupakan subpohon kiri dari 1)

Kunjungi subpohon kiri 2. Node saat ini akan menjadi 5 kali ini.
Pindah ke 5, tidak memiliki anak, sehingga node 5 akan ditandai sebagai telah dikunjungi. Ini akan kembali ke node induk; yaitu 2.
Ketika subpohon kiri dari 2 dikunjungi, sekarang subpohon 2 juga akan dikunjungi.
algoritma akan memindahkan node saat ini ke subpohon kanan dari node 2, yaitu node 6. Setelah mengunjungi node 6. Ia akan berpindah ke node 2 induknya.
Saat node 2 dikunjungi, sekarang kita akan mengunjungi induk dari 2; yaitu simpul 1.
Setelah itu, kita akan mengunjungi subpohon kanan.

Jadi traversal terakhir akan terlihat seperti ini:

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

Berikut Pseudocode untuk In-order traversal:

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

Ini adalah algoritma rekursif untuk inorder traversal. Untuk Pohon Pencarian Biner (BST), Inorder traversal memberikan susunan nilai yang diurutkan.

Traversal Pasca Pesanan

Dalam traversal ini, kita akan melintasi subpohon paling kiri terlebih dahulu, kemudian subpohon paling kanan setelah akar. Semua traversal akan berada dalam Post-Order. Mari kita tunjukkan sebuah contoh:

Di sini untuk root = 1,

Kita akan pergi ke subpohon kiri terlebih dahulu. Jadi rootnya akan menjadi 2.
Kemudian 2 telah meninggalkan subpohon, jadi kita akan menuju ke node 5. Sekarang root-nya adalah 5.
Ia tidak memiliki subpohon kiri, juga tidak memiliki subpohon kanan. Jadi, sekarang kita akan menandai node 5 sebagai telah dikunjungi dan kita akan menuju ke node induknya.

Sekarang akarnya adalah 2 dan subpohon kirinya telah dikunjungi sepenuhnya. Sekarang kita akan berpindah ke subpohon kanannya. Jadi akarnya menjadi 6.
Karena node 6 tidak memiliki subpohon kiri dan kanan, kita akan menandai node 6 yang telah dikunjungi dan berpindah ke node 2 induknya.
Sekarang, subpohon kiri dan kanan sedang dikunjungi untuk node 2. Subpohon tersebut juga akan ditandai sebagai telah dikunjungi.
Kita akan pindah ke induk dari node 2, yaitu node 1.
Subpohon kiri dikunjungi untuk root 1. Sekarang sama, kita akan mengunjungi subpohon kanan.

Lingkaran yang ditandai adalah subpohon sebelah kanan. Sekarang kita akan mengunjungi subpohon kanan seperti kita mengunjungi subpohon kiri. Setelah itu, kita akan mengunjungi node tersebut. Jadi traversal terakhirnya adalah:

Pesanan Pasca: 5 → 6 → 2 → 8 → 7 → 3 → 1

Berikut Pseudocode untuk Post-order traversal:

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

Praorder Traversal

Untuk preorder traversal, algoritma akan mengunjungi node root terlebih dahulu, setelah itu akan berpindah ke subtree kiri dan kanan. Untuk memudahkan pemahaman, kita dapat memikirkan seperti apa kunjungan traversal preorder akar → kiri-kanan.

Jadi, mari kita pilih node 1 sebagai root.

Sesuai algoritmanya, root akan ditemukan terlebih dahulu, lalu subpohon kiri, dan kemudian subpohon kanan.
Jadi, kita akan mengunjungi root 1. Kemudian kita akan berpindah ke subpohon kirinya. Akarnya menjadi 2.
Kita akan mengunjungi node 2 dan berpindah ke subpohon kirinya. Jadi akarnya menjadi 3.
Kita mengunjungi node 3, lalu kita pindah ke node induknya. Sekarang node 2 dan subpohon kirinya telah dikunjungi. Saatnya mengunjungi subpohon yang tepat.
Kita akan pindah ke subpohon kanan, akarnya menjadi 4. Kita akan mengunjungi 4. Karena 4 tidak memiliki simpul anak, kita akan pindah ke induknya.
Sekarang root adalah 2 dan dikunjungi bersama dengan subpohon kiri dan kanannya. Jadi, kita akan pindah ke node induknya. Sekarang root menjadi 1.
Demikian pula, kita akan mengunjungi subpohon kanan.

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

Berikut Pseudocode untuk Post-order traversal:

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

Implementasi di 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)

Keluaran:

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

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