ডাটা স্ট্রাকচার - ৬ঃ বাইনারি ট্রি ট্রাভার্সাল

এই পর্বে আমরা শিখবো কিভাবে একটা বাইনারি ট্রি এর মধ্যে ট্রাভার্স করতে হয়। একটা ডাটা স্ট্রাকচারের ডেটাগুলো অ্যাক্সেস করার ক্ষেত্রে ট্রাভার্সাল জিনিসটা অনেক বেশী গুরুত্বপুর্ন। বাইনারি ট্রিতে ৩ ভাবে ট্রাভার্সাল চালানো যায়-

১। প্রি অর্ডার(Pre Order): প্রথমে রুট, তারপর লেফট, তারপর রাইটে যেতে হয়- Root->Left->Right-
 2, 7, 1, 6, 5, 10, 9, 8, 3, 4

২। ইন অর্ডার(In Order):  প্রথমে লেফট, তারপর রুট তারপর রাইট- Left->Root->Right:
1, 7,  5, 6, 10, 2, 9, 3, 8, 4

৩। পোস্ট অর্ডার(Post Order): প্রথমে লেফট তারপর রাইট এবং সবশেষে রুট- Left->Right->Root :
1, 5, 10, 6, 7, 3, 4, 8, 9, 2


ব্যাপারটা কিন্তু একদম সহজ, ইনঅর্ডারের ক্ষেত্রে আমরা সিমুলেট করে দেখি- বোঝার সুবিদার্থে আমরা মার্কার নামক একটা শব্দ ব্যাবহার করবো। ভিবিন্ন নোডে মুভ করবে, যখন যেখানে থাকবে সেটাকে আমরা ওই সময়ে রুট হিসেবে চিন্তা করবো যদি সেই নোডের চাইল্ড থাকে। 

ট্রাভার্সালের একদম শুরুতে মার্কার থাকবে দুই নোড- ২ তে। তার মানে এই মুহুর্তে রুট হল ২। কিন্তু নিয়মুনাযায়ী প্রথমে নিতে হবে লেফট কে। তাই মার্কার এখন লেফট এ চলে যাবে তা হল ৭। ৭ এরদুটো চাইল্ড আছে তার মানে ৭ হল তাদের রুট।  আবার ৭ এর আবার লেফট চাইল্ড আছে,  তাই বামে মুভ করবো আর তা হল- ১। মার্কার এখন ১ এ আছে। ১ এর কোন চাইল্ড নাই তাই এটাকে আমরা নিয়ে নিবো। তারপর এই নোডের জন্য যে, রুট তাকে নিয়ে নিবো। আর সেটা হল ৭। ৭ এর লেফট এবং রুট নেওয়া হল। বাকি থাকলো রাইট। মার্কার এখন ৭ এ রাইট চাইল্ডে যাবো। কিন্তু রাইট চাইল্ডের আবার লেফট চাইল্ড আছে তা হল ৬।  মার্কার এখন ৬ এ আছে। কিন্তু ৬ এর যেহেতু লেফট চাইল্ড আছে আমরা লেফটে চলে যাবো। তার মানে আমাদের মার্কার এখন ৫ এ। লেফট নিলাম এখন ৫ এর রুট নিবো আর তা হলো ৬। রুট নিলাম এখন বাকি আছে রাইট তা হলো ১০ । খেয়াল করো ২ এর লেফট নেওয়া হয়ে গেছে। এখন রুট নিবো তা হলো ২। লেফট, রুট নেওয়া হয়ে গেছে এখন বাকি আছে রাইট।

মার্কার এখন ৯ এ আছে। ৯ এর যেহেতু কোন লেফট নাই তাই লেফট থেকে নেওয়ার কিছু নাই। লেফট গেলো এখন নিবো রুট আর তা হল ৯। বাকি আছে রাইট। ৯ এর রাইটে আছে ৮। আমাদের মার্কার এখন ৮ এ ।  ৮ এর লেফট চাইল্ড ৩। মার্কার এখন ৩ এ। ৩ এর যেহেতু কোন চাইল্ড নাই ৩ ই হল ৮ এর লেফট। লেফট গেলো এখন বাকি আছে রুট। রুট হল ৮ । এখন বাকি আছে রাইট মার্কার এখন ৪ এ! ৪ কে নেই।

এভাবে বাকিগুলো নিজে নিজে সিমুলেট করে দেখো।


ইমপ্লিমেন্টেশনঃ
রিকার্সন দিয়ে এই কাজটা খুব সহজেই করা যায়। কেউ চাইলে লুপ দিয়েও করতে পারে-

 void preOrder(Node *node)  
 {  
   printf("%d ", node->data);  //print root
   if(node->left!= NULL){  //if there is any left child go to left 
     preOrder(node->left);  
   }  
   if(node->right!= NULL){  //if there is any right child go to right 
     preOrder(node->right);  
   }  
 }  

 void inOrder(Node *node)  
 {  
   if(node->left!= NULL){  //if there is any left child go to left 
     inOrder(node->left);  
   }  
   printf("%d ", node->data);  //print the root 
   if(node->right!= NULL){  //if there is any right child go to right
     inOrder(node->right);  
   }  
 }  

 void postOrder(Node *node)  
 {  
   if(node->left!= NULL){  //if there is any left child go to left 
     postOrder(node->left);  
   }  
   if(node->right!= NULL){  //if there is any right child go to right 
     postOrder(node->right);  
   }  
   printf("%d ", node->data);  //print the root 
 }