মডিউল ১৭-৮ঃ In Order Traversal of Binary Tree

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

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

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

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

এখানে সব সময় left side এ গিয়ে এক এক করে সব node print হবে, তারপর 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;
    }
};


// in-order traversal এর function 
void inorder(Node *root)
{
  /* এটি base case অর্থাৎ root এ যদি null পাওয়া যায় তাহলে in-order traversal শেষ হবে */
    if (root == NULL)
    {
        return;
    }
    inorder(root->left);
    cout << root->val << " ";
    inorder(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
    inorder(root);

    return 0;
}