সি-তে বাইনারি ট্রি
সি, এ বাইনারি গাছ প্যারেন্ট নোড সহ একটি ট্রি ডেটা স্ট্রাকচারের একটি উদাহরণ যা সর্বাধিক দুটি চাইল্ড নোডের অধিকারী হতে পারে; 0, 1, বা 2 সন্তান নোড। প্রতিটি একক নোড a বাইনারি গাছ এর নিজস্ব একটি মান রয়েছে এবং এর বাচ্চাদের জন্য দুটি পয়েন্টার রয়েছে, একটি বাম সন্তানের জন্য এবং অন্যটি ডান সন্তানের জন্য।
বাইনারি গাছের ঘোষণা
ক বাইনারি গাছ নামক বস্তু ব্যবহার করে সি-তে ঘোষণা করা যেতে পারে গঠন যেটি গাছের একটি নোডকে চিত্রিত করে।
গঠন নোড {
ডেটাটাইপ var_name ;
গঠন নোড * বাম ;
গঠন নোড * অধিকার ;
} ;
উপরে একটি ঘোষণা বাইনারি গাছ একটি নোড হিসাবে নোড নাম। এটি তিনটি মান ধারণ করে; একটি হল ডেটা-স্টোরিং ভেরিয়েবল এবং অন্য দুটি হল শিশুর জন্য নির্দেশক৷ (প্যারেন্ট নোডের বাম এবং ডান সন্তান)।
বাইনারি গাছের ঘটনা
এমনকি ডেটার বড় সেটের জন্য, a ব্যবহার করে বাইনারি গাছ অনুসন্ধান সহজ এবং দ্রুত করে তোলে। গাছের শাখার সংখ্যা সীমিত নয়। একটি অ্যারের বিপরীতে, একজন ব্যক্তির প্রয়োজনীয়তার উপর ভিত্তি করে যে কোনও ধরণের গাছ তৈরি এবং বাড়ানো যেতে পারে।
সি-তে বাইনারি ট্রি ইমপ্লিমেন্টেশন
নিম্নলিখিত একটি বাস্তবায়নের জন্য একটি ধাপে ধাপে নির্দেশিকা বাইনারি গাছ সি তে
ধাপ 1: একটি বাইনারি অনুসন্ধান গাছ ঘোষণা করুন
একটি স্ট্রাকট নোড তৈরি করুন যাতে তিন ধরনের ডেটা থাকে, যেমন ডেটা, *left_child, এবং *right_child, যেখানে ডেটা পূর্ণসংখ্যার প্রকারের হতে পারে এবং *left_child এবং *right_child নোডগুলিকে NULL বা না বলে ঘোষণা করা যেতে পারে।
গঠন নোড{
int তথ্য ;
গঠন নোড * ডান_শিশু ;
গঠন নোড * বাম_শিশু ;
} ;
ধাপ 2: বাইনারি সার্চ ট্রিতে নতুন নোড তৈরি করুন
একটি ফাংশন তৈরি করে একটি নতুন নোড তৈরি করুন যা একটি পূর্ণসংখ্যাকে একটি আর্গুমেন্ট হিসাবে গ্রহণ করে এবং সেই মান দিয়ে তৈরি নতুন নোডে পয়েন্টার প্রদান করে। তৈরি নোডের জন্য গতিশীল মেমরি বরাদ্দের জন্য C-তে malloc() ফাংশন ব্যবহার করুন। বাম এবং ডান চাইল্ডকে NULL তে সূচনা করুন এবং নোডনাম ফেরত দিন।
গঠন নোড * সৃষ্টি ( ডেটাটাইপ ডেটা )
{
গঠন নোড * নোড নেম = malloc ( আকার ( গঠন নোড ) ) ;
নোড নেম -> তথ্য = মান ;
নোড নেম -> বাম_শিশু = নোড নেম -> ডান_শিশু = খালি ;
প্রত্যাবর্তন নোড নেম ;
}
ধাপ 3: বাইনারি ট্রিতে ডান এবং বাম শিশু সন্নিবেশ করান
insert_left এবং insert_right ফাংশন তৈরি করুন যা দুটি ইনপুট গ্রহণ করবে, যেটি সন্নিবেশিত করার মান এবং নোডের পয়েন্টার যেখানে উভয় শিশুই সংযুক্ত হবে। একটি নতুন নোড তৈরি করতে ক্রিয়েট ফাংশনটিকে কল করুন এবং বাম সন্তানের বাম পয়েন্টারে বা রুট প্যারেন্টের ডান সন্তানের ডান পয়েন্টারে ফেরত পয়েন্টার বরাদ্দ করুন।
গঠন নোড * সন্নিবেশ_বাম ( গঠন নোড * মূল , ডেটাটাইপ ডেটা ) {মূল -> বাম = সৃষ্টি ( তথ্য ) ;
প্রত্যাবর্তন মূল -> বাম ;
}
গঠন নোড * insert_right ( গঠন নোড * মূল , ডেটাটাইপ ডেটা ) {
মূল -> অধিকার = সৃষ্টি ( তথ্য ) ;
প্রত্যাবর্তন মূল -> অধিকার ;
}
ধাপ 4: ট্রাভার্সাল পদ্ধতি ব্যবহার করে বাইনারি গাছের নোডগুলি প্রদর্শন করুন
আমরা C-তে ট্রাভার্সালের তিনটি পদ্ধতি ব্যবহার করে গাছ প্রদর্শন করতে পারি। এই ট্রাভার্সাল পদ্ধতিগুলি হল:
1: প্রি-অর্ডার ট্রাভার্সাল
এই ট্রাভার্সাল পদ্ধতিতে, আমরা নোডগুলির মধ্য দিয়ে একটি দিক থেকে যাবো parent_node->left_child->right_child .
অকার্যকর পূর্বাদেশ ( নোড * মূল ) {যদি ( মূল ) {
printf ( '%d \n ' , মূল -> তথ্য ) ;
প্রদর্শন_পূর্ব_অর্ডার ( মূল -> বাম ) ;
প্রদর্শন_পূর্ব_অর্ডার ( মূল -> অধিকার ) ;
}
}
2: পোস্ট-অর্ডার ট্রাভার্সাল
এই ট্রাভার্সাল পদ্ধতিতে, আমরা নোডগুলির মধ্য দিয়ে একটি দিক থেকে যাবো left_child->right_child->parent_node-> .
অকার্যকর প্রদর্শন_পোস্ট_অর্ডার ( নোড * মূল ) {যদি ( বাইনারি_ট্রি ) {
প্রদর্শন_পোস্ট_অর্ডার ( মূল -> বাম ) ;
প্রদর্শন_পোস্ট_অর্ডার ( মূল -> অধিকার ) ;
printf ( '%d \n ' , মূল -> তথ্য ) ;
}
}
3: ইন-অর্ডার ট্রাভার্সাল
এই ট্রাভার্সাল পদ্ধতিতে, আমরা নোডগুলির মধ্য দিয়ে একটি দিক থেকে যাবো left_node->root_child->right_child .
অকার্যকর ডিসপ্লে_ইন_অর্ডার ( নোড * মূল ) {যদি ( বাইনারি_ট্রি ) {
ডিসপ্লে_ইন_অর্ডার ( মূল -> বাম ) ;
printf ( '%d \n ' , মূল -> তথ্য ) ;
ডিসপ্লে_ইন_অর্ডার ( মূল -> অধিকার ) ;
}
}
ধাপ 5: বাইনারি ট্রিতে মুছে ফেলার কাজ করুন
আমরা তৈরি মুছে দিতে পারেন বাইনারি গাছ নিম্নলিখিত হিসাবে C-তে প্যারেন্ট নোড ফাংশন সহ উভয় সন্তানকে মুছে ফেলার মাধ্যমে।
অকার্যকর ডিলিট_টি ( নোড * মূল ) {যদি ( মূল ) {
ডিলিট_টি ( মূল -> বাম ) ;
ডিলিট_টি ( মূল -> অধিকার ) ;
বিনামূল্যে ( মূল ) ;
}
}
বাইনারি অনুসন্ধান গাছের সি প্রোগ্রাম
সি প্রোগ্রামিং-এ বাইনারি সার্চ ট্রির সম্পূর্ণ বাস্তবায়ন নিম্নরূপ:
#include#include
গঠন নোড {
int মান ;
গঠন নোড * বাম , * অধিকার ;
} ;
গঠন নোড * নোড1 ( int তথ্য ) {
গঠন নোড * tmp = ( গঠন নোড * ) malloc ( আকার ( গঠন নোড ) ) ;
tmp -> মান = তথ্য ;
tmp -> বাম = tmp -> অধিকার = খালি ;
প্রত্যাবর্তন tmp ;
}
অকার্যকর ছাপা ( গঠন নোড * root_node ) // নোড প্রদর্শন!
{
যদি ( root_node != খালি ) {
ছাপা ( root_node -> বাম ) ;
printf ( '%d \n ' , root_node -> মান ) ;
ছাপা ( root_node -> অধিকার ) ;
}
}
গঠন নোড * insert_node ( গঠন নোড * নোড , int তথ্য ) // নোড ঢোকানো!
{
যদি ( নোড == খালি ) প্রত্যাবর্তন নোড1 ( তথ্য ) ;
যদি ( তথ্য < নোড -> মান ) {
নোড -> বাম = insert_node ( নোড -> বাম , তথ্য ) ;
} অন্য যদি ( তথ্য > নোড -> মান ) {
নোড -> অধিকার = insert_node ( নোড -> অধিকার , তথ্য ) ;
}
ফিরে নোড ;
}
int প্রধান ( ) {
printf ( 'সি বাস্তবায়ন বাইনারি অনুসন্ধান গাছ! \n \n ' ) ;
গঠন নোড * অভিভাবক = খালি ;
অভিভাবক = insert_node ( অভিভাবক , 10 ) ;
insert_node ( অভিভাবক , 4 ) ;
insert_node ( অভিভাবক , 66 ) ;
insert_node ( অভিভাবক , চার পাঁচ ) ;
insert_node ( অভিভাবক , 9 ) ;
insert_node ( অভিভাবক , 7 ) ;
ছাপা ( অভিভাবক ) ;
ফিরে 0 ;
}
উপরের কোডে, আমরা প্রথমে a ঘোষণা করি নোড ব্যবহার গঠন . তারপরে আমরা একটি নতুন নোড শুরু করি ' নোড1 এবং গতিশীলভাবে ব্যবহার করে মেমরি বরাদ্দ করুন malloc() সি-তে ডেটা এবং দুটি পয়েন্টার টাইপ শিশু ঘোষিত নোড ব্যবহার করে। এই পরে, আমরা দ্বারা নোড প্রদর্শন printf() ফাংশন এবং এটি কল করুন প্রধান() ফাংশন এরপর সন্নিবেশ_নোড() ফাংশন তৈরি করা হয়, যেখানে নোড ডেটা NULL হলে নোড1 অবসরপ্রাপ্ত, অন্যথায় ডেটা স্থাপন করা হয় নোড বাম এবং ডান সন্তানের (পিতামাতা)। প্রোগ্রাম থেকে নির্বাহ শুরু হয় প্রধান() ফাংশন, যা শিশুদের হিসাবে কয়েকটি নমুনা নোড ব্যবহার করে একটি নোড তৈরি করে এবং তারপর নোডের বিষয়বস্তু মুদ্রণের জন্য ইন-অর্ডার ট্রাভার্সাল পদ্ধতি ব্যবহার করে।
আউটপুট
উপসংহার
একটি নন-লিনিয়ার আকারে ডেটা রাখার জন্য গাছগুলি প্রায়শই নিযুক্ত করা হয়। বাইনারি গাছ গাছের ধরন যেখানে প্রতিটি নোডের (পিতামাতার) দুটি সন্তান রয়েছে বাম সন্তান এবং ডান সন্তান। ক বাইনারি গাছ তথ্য স্থানান্তর এবং সংরক্ষণের একটি বহুমুখী পদ্ধতি। সি-তে লিঙ্কড-লিস্টের তুলনায় এটি আরও কার্যকর। উপরের নিবন্ধে, আমরা একটি ধারণাটি দেখেছি। বাইনারি গাছ একটি ধাপে ধাপে বাস্তবায়নের সাথে বাইনারি অনুসন্ধান গাছ সি তে