মডিউল ১৭-৫ঃ Pre Order Traversal of Binary Tree

Pre-order traversal এর বেলায় প্রথমে root তারপর left তারপর right print করা হয়। অর্থ্যাৎ root-:>left->right

নিচের উদাহরনে আমরা একটি Binary Tree এর pre-order traversal দেখতে পাচ্ছি। এখানে root এর আছে 10, এর left এ 20 এবং right এ 30. এখন এটার যদি pre-order traversal করতে হয় তাহলে আমাদের আগে root print করতে হবে। তারপর left side এর node গুলো সব print করতে হবে।

তারপর right side এর সব print করতে হবে। এখানে,

root 10. 
Left 20 
(আবার 20 এর নিচে যদি একটি subtree থাকে ঠিক একই rule follow করে  print করতে হবে।)
Right 30 
(আবার 30 এর নিচে যদি একটি subtree থাকে ঠিক একই rule follow করে  print করতে হবে।)

তাই প্রথমে print হবে 10, তারপর 20 এর পর 40, তারপর 60, এখানে আমরা 40 এর left side leaf node complete করেছি। এখন 40 এর right এ 100 print করতে হবে। এখন আমাদের 20 এর left side sub-tree comple এরপর আমাদের right side এর 90 print করতে হবে। এভাবে আমাদের root 10 এর left side sub-tree print করা শেষ এবার right side এর 30 এবং 30 এর যে sub tree রয়েছে সেটি print করতে হবে। Finally আমরা picture এর মতো একটি pre-traversal পাবো।

এবার code এর মাধ্যমে দেখা যাকঃ

এখানে সব সময় root print করা হয় একটা root print এর পর left side এ গিয়ে এক এক করে সব root print হবে তারপর right side এর node গুলো print হবে।

Code:

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};
// pre-order traversal এর function 
void preorder(Node *root)
{
    /* এটি base case অর্থাৎ root এ যদি null পাওয়া যায় তাহলে pre-order traversal শেষ হবে */
    if (root == NULL)
    {
        return;
    }
    //এখানে root print হবে।
    cout << root->val << " ";
    
    preorder(root->left);
    preorder(root->right);
}
int main()
{
    Node *root = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);
    Node *d = new Node(50);
    Node *e = new Node(60);
    Node *f = new Node(70);
    Node *g = new Node(80);
    Node *h = new Node(90);
    Node *i = new Node(100);

    // connection
    root->left = a;
    root->right = b;
    a->left = c;
    a->right = h;
    c->right = e;
    b->right = d;
    d->left = f;
    d->right = g;
    h->right = i;

    // call
    preorder(root);

    return 0;
}