ट्री ट्रैवर्सल्स (इनऑर्डर, प्रीऑर्डर और पोस्टऑर्डर) उदाहरणों के साथ

ट्री ट्रैवर्सल क्या है?

ट्री डेटा संरचना में, ट्रैवर्सल का अर्थ है किसी विशिष्ट तरीके से नोड्स पर जाना। नोड्स2 प्रकार के ट्रैवर्सल हैं। आम तौर पर, इस तरह का ट्रैवर्सल बाइनरी ट्री पर आधारित होता है। बाइनरी ट्री का मतलब है कि प्रत्येक नोड में अधिकतम 2 नोड हो सकते हैं।

बाइनरी ट्री एक प्रसिद्ध डेटा संरचना है। बाइनरी सर्च ट्री (BST) भी है। इस प्रकार के ट्रैवर्सल का उपयोग विभिन्न उद्देश्यों के लिए किया जाता है। लेवल ऑर्डर ट्रैवर्सल, इसका उपयोग दो नोड्स के बीच की गहराई की गणना करने के लिए किया जाता है। एक अन्य प्रकार का ट्री है जिसे "AVL" कहा जाता है, जहाँ नोड की ऊँचाई की गणना करना आवश्यक है। हम सरणी में बाइनरी ट्री का प्रतिनिधित्व कर सकते हैं, लेकिन मेमोरी ऑप्टिमाइज़ेशन के लिए, हम अगले नोड को संदर्भित करने के लिए संरचना और पॉइंटर का उपयोग करेंगे।

वृक्ष परिभ्रमण के प्रकार

जैसे हमने चर्चा की थी द्विआधारी पेड़अब हम ट्रैवर्सल के अलग-अलग प्रकारों पर चर्चा करते हैं। प्रकारों के आधार पर, ट्रैवर्सल के दो प्रकार हैं। पहले हमने लेवल ऑर्डर या ब्रेडथ-फर्स्ट ट्रैवर्सल की आवश्यकता का उल्लेख किया है। अब गहराई-प्रथम ट्रैवर्सल जैसे पोस्ट ऑर्डर का उपयोग नोड को हटाने के लिए किया जाता है (हम बाद में इस पर चर्चा करेंगे), प्रीऑर्डर का उपयोग बाइनरी ट्री की प्रतिलिपि बनाने के लिए किया जाता है, और "इनऑर्डर" ट्री को बिना घटते हुए तरीके से पार करेगा।

चौड़ाई-प्रथम ट्रैवर्सल
गहराई-प्रथम ट्रैवर्सल
प्री-ऑर्डर ट्रैवर्सल
पोस्ट-ऑर्डर ट्रैवर्सल
इन-ऑर्डर ट्रैवर्सल

चौड़ाई-प्रथम ट्रैवर्सल

इसे लेवल-ऑर्डर ट्रैवर्सल के नाम से भी जाना जाता है। आइए लेवल-ऑर्डर ट्रैवर्सल को दर्शाने के लिए निम्नलिखित ट्री पर विचार करें।

तो, हम रूट नोड “1” से शुरू करेंगे। इसे लेवल 1 के रूप में चिह्नित किया जाएगा। फिर एल्गोरिथ्म मौजूदा नोड के सभी बच्चों तक जाएगा। अब हम नोड 2 और 3 पर जाएँगे। उन्हें लेवल 2 के रूप में चिह्नित किया जाएगा।

उसके बाद, चूँकि हमारे पास लेवल 2 में 2 नोड हैं, हम उनके बच्चों को भी देखेंगे। इसलिए, हम 5,6,8,7 को देखेंगे और उन्हें लेवल 3 के रूप में चिह्नित करेंगे। यहाँ एक बात है जिसका उल्लेख नहीं किया गया है,

नोड का स्तर = मूल नोड का स्तर + 1

स्तर 1: 1

स्तर 2: 2 3

स्तर 3: 5 6 8 7

बीएफएस (BFS) के लिए एक समान एल्गोरिथ्म का उपयोग किया जाता है।चौड़ाई-पहले-खोज).

स्तर क्रम परिक्रमण के लिए छद्म कोड यहां दिया गया है:

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)

इनऑर्डर ट्रैवर्सल बियनरी ट्री

आइए पहले जैसा ही उदाहरण लें। इस प्रकार के ट्रैवर्सल में, हम सबसे पहले बाएं उपवृक्ष, फिर मूल, और उसके बाद दाएं उपवृक्ष पर जाते हैं। याद रखने में आसानी के लिए, हम कह सकते हैं कि क्रम बाएं-मूल-दाएं की तरह जाता है।

संपूर्ण वृक्ष के लिए, मान लें कि मूल 1 है। अब एल्गोरिथ्म इस प्रकार होगा:

नोड 1 के बाएं उपवृक्ष पर जाएँ।
वर्तमान नोड 2 है (क्योंकि यह 1 का बायां उपवृक्ष है)

2 के बाएं उपवृक्ष पर जाएँ। इस बार वर्तमान नोड 5 होगा।
5 पर जाने पर, इसका कोई संतान नहीं है, इसलिए नोड 5 को विज़िट किया गया के रूप में चिह्नित किया जाएगा। यह पैरेंट नोड पर वापस आ जाएगा; जो 2 है।
जैसे ही 2 के बाएं उपवृक्ष का दौरा किया जाता है, अब 2 का भी दौरा किया जाएगा।
RSI कलन विधि वर्तमान नोड को नोड 2 के दाएँ उपवृक्ष पर ले जाएगा, जो कि नोड 6 है। नोड 6 पर जाने के बाद, यह अपने मूल नोड 2 पर चला जाएगा।
चूँकि नोड 2 का दौरा हो चुका है, अब हम 2 के पैरेंट का दौरा करेंगे; जो कि नोड 1 है।
उसके बाद, हम सही उपवृक्ष पर जाएंगे।

अतः अंतिम परिभ्रमण इस प्रकार दिखाई देगा:

क्रमानुसार: 5 → 2 → 6 → 1 → 8 → 3 → 7

इन-ऑर्डर ट्रैवर्सल के लिए छद्म कोड यहां दिया गया है:

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

यह इनऑर्डर ट्रैवर्सल के लिए पुनरावर्ती एल्गोरिथ्म है। बाइनरी सर्च ट्री (BST), इनऑर्डर ट्रैवर्सल मानों की क्रमबद्ध सरणी देता है।

पोस्ट-ऑर्डर ट्रैवर्सल

इस ट्रैवर्सल में, हम सबसे पहले सबसे बाएं सबट्री को पार करेंगे, फिर रूट के बाद सबसे दाएं सबट्री को पार करेंगे। सभी ट्रैवर्सल पोस्ट-ऑर्डर में होंगे। आइए एक उदाहरण प्रदर्शित करें:

यहाँ मूल = 1 के लिए,

हम पहले बाएं उपवृक्ष पर जाएंगे। तो मूल 2 हो जाएगा।
अब 2 ने उपवृक्ष छोड़ दिया है, इसलिए हम नोड 5 पर जाएंगे। अब मूल 5 है।
इसका कोई बायाँ उपवृक्ष नहीं है, साथ ही इसका कोई दायाँ उपवृक्ष भी नहीं है। तो, अब हम नोड 5 को विज़िटेड के रूप में चिह्नित करेंगे और हम इसके पैरेंट नोड पर जाएँगे।

अब मूल 2 है और इसका बायाँ उपवृक्ष पूरी तरह से देखा जा चुका है। अब हम इसके दाएँ उपवृक्ष पर जाएँगे। तो मूल 6 हो जाता है।
चूंकि नोड 6 में कोई बायां और दायां उपवृक्ष नहीं है, इसलिए हम नोड 6 को विज़िट किया हुआ चिह्नित करेंगे और इसे इसके मूल नोड 2 पर ले जाएंगे।
अब, नोड 2 के लिए बाएँ और दाएँ दोनों उपवृक्षों का दौरा किया जा रहा है। इसे भी दौरा किया गया के रूप में चिह्नित किया जाएगा।
हम नोड 2 के पैरेंट पर जाएंगे, जो कि नोड 1 है।
मूल 1 के लिए बाएं उपवृक्ष का दौरा किया जाता है। अब इसी प्रकार, हम दाएं उपवृक्ष का दौरा करेंगे।

चिन्हित वृत्त दायाँ उपवृक्ष है। अब हम दाएँ उपवृक्ष पर जाएँगे जैसे हमने बाएँ उपवृक्ष पर जा कर देखा था। उसके बाद, हम नोड पर जाएँगे। तो अंतिम यात्रा इस प्रकार होगी:

पोस्टऑर्डर: 5 → 6 → 2 → 8 → 7 → 3 → 1

पोस्ट-ऑर्डर ट्रैवर्सल के लिए छद्म कोड यहां दिया गया है:

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

त्राटक ट्रैवराल

प्रीऑर्डर ट्रैवर्सल के लिए, एल्गोरिथ्म पहले रूट नोड पर जाएगा, उसके बाद, यह क्रमशः बाएं और दाएं सबट्री पर जाएगा। समझने में आसानी के लिए, हम प्रीऑर्डर ट्रैवर्सल विज़िट के बारे में इस तरह सोच सकते हैं मूल → बाएँ-दाएँ.

तो, आइए नोड 1 को रूट के रूप में चुनें।

एल्गोरिथ्म के अनुसार, सबसे पहले मूल की खोज की जाएगी, फिर बाएं, और फिर दाएं उपवृक्ष की।
तो, हम मूल 1 पर जाएँगे। फिर हम उसके बाएँ उपवृक्ष पर जाएँगे। मूल 2 हो जाता है।
हम नोड 2 पर जाएंगे और उसके बाएं उपवृक्ष पर जाएंगे। तो, मूल 3 हो जाएगा।
हम नोड 3 पर जाते हैं, फिर उसके पैरेंट नोड पर जाते हैं। अब नोड 2 और उसके बाएं उपवृक्ष पर जाते हैं। अब दाएं उपवृक्ष पर जाने का समय है।
हम दाएं उपवृक्ष पर जाएंगे, मूल 4 हो जाएगा। हम 4 पर जाएंगे। चूंकि 4 का कोई संतान नोड नहीं है, इसलिए हम इसके पैरेंट पर जाएंगे।
अब रूट 2 है और इसे इसके बाएं और दाएं सबट्री के साथ देखा जाता है। इसलिए, हम इसके पैरेंट नोड पर जाएंगे। अब रूट 1 हो जाता है।
इसी प्रकार, हम दाएँ उपवृक्ष पर जाएँगे।

प्रीऑर्डर: 1 → 2 → 3 → 4 → 5 → 6 → 7

पोस्ट-ऑर्डर ट्रैवर्सल के लिए छद्म कोड यहां दिया गया है:

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

कार्यान्वयन 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)

आउटपुट:

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

सी में कार्यान्वयन

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