ट्री ट्रैवर्सल (Preorder, Inorder & Postorder)


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना MAQ ओरेकल स्नैपडील
बाइनरी ट्री पेड़ वृक्ष का त्राटक

पहले हमें इसके बारे में जानना होगा बाइनरी ट्री में ट्रैवर्सल क्या है। ट्रैवर्सल एक प्रकार की विधि है जिसमें हम सभी नोड्स पर एक बार किसी विशिष्ट तरीके / क्रम से जाते हैं। मूल रूप से दो प्रकार के ट्रैवर्सल हैं बाइनरी ट्री:

हम पहले से ही जानते हैं कि क्या है BFS की अवधारणा। अब, हम Preorder, Inorder और Postorder ट्रैवर्सल देखते हैं और ये ट्रैवर्सल्स एक बाइनरी ट्री के DFS का हिस्सा हैं। तो, हम सभी पेड़ों के प्रकार को विस्तार से देखते हैं:

ट्री ट्रैवर्सल (Preorder, Inorder & Postorder)

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

इस ट्रैवर्सल में, हम पहले करंट नोड के डेटा को प्रिंट करते हैं और फिर लेफ्ट सबट्री में जाते हैं और उसके बाद राइट सबट्री में जाते हैं। उपरोक्त बाइनरी ट्री का प्रीऑर्डर ट्रैवर्सल है 0।

कलन विधि

Algorithm: 
Preorder(root): 
Step:1 Print the data of the Node. 
Step:2 Move to the left side of the node(traverse left-subtree). 
Step:3 Move to the right side of the node(traverse right-subtree).

इनवर्टर ट्रैवर्सल

इस ट्रैवर्सल में, हम पहले बाएं सबट्री पर जाते हैं और फिर नोड के डेटा को प्रिंट करते हैं। नोड के डेटा को प्रिंट करने के बाद दाईं ओर सबट्री पर जाएं। उपरोक्त बाइनरी ट्री का इनवर्टर ट्रैवर्सल है 1।

कलन विधि

Algorithm:  
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

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

इस ट्रैवर्सल में, हम पहले बाएं सबट्री में जाते हैं और फिर राइट सबट्री में जाते हैं। मूविंग प्रिंट के बाद नोड का डेटा। उपरोक्त बाइनरी ट्री का पोस्टऑर्डर ट्रैवर्सल है 1।

कलन विधि

Algorithm: 
Postorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree). 
Step:3 Print the data of the Node.

कार्यान्वयन

/*C++ Implementation of print the Preorder, Inorder, Postorder traversal of given binary tree*/ 
#include<bits/stdc++.h> 
using namespace std; 
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/
struct Node{
    int data;
    struct Node* left;// for left child;
    struct Node* right;// for right child;
    Node(int value)// create a node using new Node;
    {
        data=value;
        left=NULL;
        right=NULL;
    }
};
/*Function which print preorder of the given tree*/ 
void Preorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    cout<<root->data<<" ";
    Preorder_tree(root->left);
    Preorder_tree(root->right);
}
/*Function which print inorder of the given tree*/ 
void Inorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    cout<<root->data<<" ";
    Preorder_tree(root->right);
}
/*Function which print postorder of the given tree*/ 
void Postorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    Preorder_tree(root->right);
    cout<<root->data<<" ";
}
int main() 
{ 
    /*construct tree*/
    Node* root= new Node(0);//root node;
    root->left= new Node(1);
    root->right= new Node(2);
    root->left->left= new Node(3);
    root->left->right= new Node(4);
    root->right->left= new Node(5);
    root->right->right= new Node(6);
    cout<<"Preorder traversal of BT: ";
    Preorder_tree(root);cout<<"\n";
    cout<<"Inorder traversal of BT: ";
    Inorder_tree(root);cout<<"\n";
    cout<<"Postorder traversal of BT: ";
    Postorder_tree(root);cout<<"\n";
    return 0; 
}
Preorder traversal of BT: 0 1 3 4 2 5 6 
Inorder traversal of BT: 1 3 4 0 2 5 6 
Postorder traversal of BT: 1 3 4 2 5 6 0

समय जटिलता

पर) जहां N किसी दिए गए बाइनरी ट्री में मौजूद नोड्स की कुल संख्या है।

संदर्भ