১৮-৩ঃ Binary Tree Input থিওরি

একটি বাইনারী ট্রি এর Node এর ডিজাইন করে , এরপর Root Node তৈরি করে , প্রত্যেকটি Node এর সাথে ম্যানুয়ালী তার Left child এবং Right child কানেক্ট করে একটি Binary Tree তৈরি করা আমরা শিখেছি। এক্ষেত্রে আমরা Node গুলো manually বানিয়ে তারপর কানেক্ট করেছিলাম । এই মডিউলে আমরা দেখবো কীভাবে User Input নিয়ে Binary Tree টি ডিজাইন করা যায় , যাতে করে আমরা Real World বাইনারী ট্রি নিয়ে কাজ করতে পারি। আমরা গত মডিউলে যখন Level Order Traversal করতেছিলাম , তখন একটি Procedure এর উপর খুব জোর দিয়েছিলাম। তা হলো , যখন কোন একটি Node সারির শুরুতে আসবে তখন আমরা ঐ Node কে পিক করবো , ঐ Node এর কাজগুলো করবো এরপর পরবর্তী তে লাইনে তার Children গুলোকে দাড় করিয়ে দিবো । এই ক্ষেত্রে যদি আমরা খেয়াল করে দেখি তবে দেখতে পাবো , Level by level কাজগুলো সংগঠিত হচ্ছে । অর্থাৎ , আগের লেভেল এর Node গুলোর কাজ আগে হবে , এরপর পরের Level এর Node গুলোর কাজ করা হবে। Input নেয়ার ক্ষেত্রেও আমরা Node গুলো এই order এ ইনপুট নিবো । একটি ইনপুট নিয়ে দেখে নেয়া যাক ।

উক্ত Binary Tree এর Root Node হলো A , তাই এরপর A এর কাজ শেষ হওয়ার পর সারিতে শুরুতে থাকবে B , B এর left child D E , তাহলে এরপরে আসবে

• সবার আগে input এ থাকবে A , এরপর A এর left child হলো B , এবং right child হলো C তার মানে এরপর input এ আসবে B C

• B এর left child হলো D , এবং right child হলো E তার মানে এরপর input এ আসবে D E .

• এরপর লাইনের শুরুতে থাকা C এর left child হলো F , এবং right child এ কেও নেই। তার মানে এরপর input এ আসবে F -1 .

• এরপর লাইনের শুরুতে থাকা D এর left child হলো G , এবং right child এ কেও নেই। তার মানে এরপর input এ আসবে G -1 .

• এরপর E । E এর কোনো children নাই । তাই এরপর ইনপুট আসবে left এ -1 , right এ -1 . সুতারাং input -1 -1 .

• লাইনে আছে F . F এর left child H , right child নেই। ইনপুটঃ H -1

• এরপর আছে G . G এর left right খালি , তাই ইনপুট -1 -1 .

• H এর left children I , এবং right -1

• এরপর সর্বশেষ I এর left এবং right child নেই সুতারাং -1 -1 .

Overall Tree এর ইনপুট টি হবে A B C D E F -1 G -1 -1 -1 H -1 -1 -1 I -1 -1 -1 . চিন্তা করলে বুঝা যাবে যে , working procedure গত মডিউলের মতো হবে । তবে চেঞ্জ হবে কোথায় ? গত মডিউলে আমরা শুধু মাত্র প্রিন্ট করেছিলাম। Input নেয়ার ক্ষেত্রে আমরা একটি Node এর children গুলোকে তার সাথে connect ও করে দিবো। কোড দেখার মাধ্যমে আমরা বিষয়টি আরো ভালোভাবে বুঝতে পারবো। নেক্সট মডিউলে আমরা Binary Tree এর ইনপুট নেয়ার কোড দেখবো।