سی میں بائنری ٹری
سی میں، اے بائنری درخت پیرنٹ نوڈ کے ساتھ ٹری ڈیٹا سٹرکچر کی ایک مثال ہے جس میں زیادہ سے زیادہ دو چائلڈ نوڈس ہو سکتے ہیں۔ 0، 1، یا 2 اولاد کے نوڈس۔ a میں ہر ایک نوڈ بائنری درخت اس کی اپنی ایک قدر ہے اور اس کے بچوں کے لیے دو اشارے ہیں، ایک پوائنٹر بائیں بچے کے لیے اور دوسرا دائیں بچے کے لیے۔
بائنری ٹری کا اعلان
اے بائنری درخت نامی آبجیکٹ کا استعمال کرتے ہوئے C میں اعلان کیا جاسکتا ہے۔ ساخت جو درخت میں موجود نوڈس میں سے ایک کو دکھاتا ہے۔
ساخت نوڈ {
ڈیٹا ٹائپ var_name ;
ساخت نوڈ * بائیں ;
ساخت نوڈ * صحیح ;
} ;
اوپر ایک کا اعلان ہے۔ بائنری درخت نوڈ کا نام بطور نوڈ۔ یہ تین اقدار رکھتا ہے؛ ایک ڈیٹا اسٹور کرنے والا متغیر ہے اور دوسرے دو بچے کی طرف اشارہ کرتے ہیں۔ (والدین نوڈ کا بائیں اور دائیں بچہ)۔
بائنری ٹری کے حقائق
یہاں تک کہ ڈیٹا کے بڑے سیٹوں کے لیے، استعمال کرتے ہوئے a بائنری درخت تلاش کو آسان اور تیز تر بناتا ہے۔ درخت کی شاخوں کی تعداد محدود نہیں ہے۔ ایک صف کے برعکس، کسی فرد کی ضرورت کی بنیاد پر کسی بھی قسم کے درخت بنائے اور بڑھائے جا سکتے ہیں۔
سی میں بائنری ٹری کا نفاذ
ایک کو لاگو کرنے کے لیے درج ذیل ایک مرحلہ وار گائیڈ ہے۔ بائنری درخت سی میں
مرحلہ 1: بائنری سرچ ٹری کا اعلان کریں۔
ایک سٹرک نوڈ بنائیں جس میں تین قسم کے ڈیٹا ہوں، جیسے کہ ڈیٹا، *left_child، اور *right_child، جہاں ڈیٹا انٹیجر قسم کا ہوسکتا ہے، اور *left_child اور *right_child دونوں نوڈس کو NULL قرار دیا جاسکتا ہے یا نہیں۔
ساخت نوڈ{
int ڈیٹا ;
ساخت نوڈ * حق_بچہ ;
ساخت نوڈ * بائیں_بچہ ;
} ;
مرحلہ 2: بائنری سرچ ٹری میں نئے نوڈس بنائیں
ایک فنکشن بنا کر ایک نیا نوڈ بنائیں جو انٹیجر کو بطور دلیل قبول کرے اور اس قدر کے ساتھ بنائے گئے نئے نوڈ کو پوائنٹر فراہم کرے۔ تخلیق شدہ نوڈ کے لیے ڈائنامک میموری ایلوکیشن کے لیے C میں malloc() فنکشن استعمال کریں۔ بائیں اور دائیں بچے کو NULL میں شروع کریں اور نوڈ نام واپس کریں۔
ساخت نوڈ * بنانا ( ڈیٹا ٹائپ ڈیٹا )
{
ساخت نوڈ * nodeName = malloc ( کا سائز ( ساخت نوڈ ) ) ;
nodeName -> ڈیٹا = قدر ;
nodeName -> بائیں_بچہ = nodeName -> حق_بچہ = خالی ;
واپسی nodeName ;
}
مرحلہ 3: بائنری ٹری میں دائیں اور بائیں بچوں کو داخل کریں۔
insert_left اور insert_right فنکشنز بنائیں جو دو ان پٹس کو قبول کریں گے، جو کہ داخل کی جانے والی ویلیو ہیں اور نوڈ کا پوائنٹر جس سے دونوں بچے جڑے ہوں گے۔ نیا نوڈ بنانے کے لیے تخلیق فنکشن کو کال کریں اور واپس کیے گئے پوائنٹر کو بائیں بچے کے بائیں پوائنٹر یا روٹ پیرنٹ کے دائیں بچے کے دائیں پوائنٹر کو تفویض کریں۔
ساخت نوڈ * داخل_بائیں ( ساخت نوڈ * جڑ ، ڈیٹا ٹائپ ڈیٹا ) {جڑ -> بائیں = بنانا ( ڈیٹا ) ;
واپسی جڑ -> بائیں ;
}
ساخت نوڈ * داخل_دائیں ( ساخت نوڈ * جڑ ، ڈیٹا ٹائپ ڈیٹا ) {
جڑ -> صحیح = بنانا ( ڈیٹا ) ;
واپسی جڑ -> صحیح ;
}
مرحلہ 4: ٹراورسل طریقوں کا استعمال کرتے ہوئے بائنری ٹری کے نوڈس ڈسپلے کریں۔
ہم سی میں ٹراورسل کے تین طریقے استعمال کر کے درختوں کو ظاہر کر سکتے ہیں۔ یہ ٹراورسل طریقے ہیں:
1: پری آرڈر ٹراورسل
اس ٹراورسل طریقہ میں، ہم نوڈس سے ایک سمت میں جائیں گے۔ parent_node->left_child-> right_child .
باطل پری_آرڈر ( نوڈ * جڑ ) {اگر ( جڑ ) {
printf ( '%d \n ' ، جڑ -> ڈیٹا ) ;
ڈسپلے_پری_آرڈر ( جڑ -> بائیں ) ;
ڈسپلے_پری_آرڈر ( جڑ -> صحیح ) ;
}
}
2: پوسٹ آرڈر ٹراورسل
اس ٹراورسل طریقہ میں، ہم نوڈس سے ایک سمت میں جائیں گے۔ بائیں_بچہ->دائیں_بچہ->والدین_نوڈ-> .
باطل ڈسپلے_پوسٹ_آرڈر ( نوڈ * جڑ ) {اگر ( بائنری_ٹری ) {
ڈسپلے_پوسٹ_آرڈر ( جڑ -> بائیں ) ;
ڈسپلے_پوسٹ_آرڈر ( جڑ -> صحیح ) ;
printf ( '%d \n ' ، جڑ -> ڈیٹا ) ;
}
}
3: ان آرڈر ٹراورسل
اس ٹراورسل طریقہ میں، ہم نوڈس سے ایک سمت میں جائیں گے۔ بائیں_نوڈ->روٹ_چائلڈ->دائیں_بچہ .
باطل ڈسپلے_ان_آرڈر ( نوڈ * جڑ ) {اگر ( بائنری_ٹری ) {
ڈسپلے_ان_آرڈر ( جڑ -> بائیں ) ;
printf ( '%d \n ' ، جڑ -> ڈیٹا ) ;
ڈسپلے_ان_آرڈر ( جڑ -> صحیح ) ;
}
}
مرحلہ 5: بائنری ٹری میں ڈیلیٹ کرنا
ہم تخلیق کو حذف کر سکتے ہیں۔ بائنری درخت مندرجہ ذیل طور پر C میں پیرنٹ نوڈ فنکشن والے دونوں بچوں کو حذف کرکے۔
باطل حذف_ٹی ( نوڈ * جڑ ) {اگر ( جڑ ) {
حذف_ٹی ( جڑ -> بائیں ) ;
حذف_ٹی ( جڑ -> صحیح ) ;
مفت ( جڑ ) ;
}
}
بائنری سرچ ٹری کا سی پروگرام
سی پروگرامنگ میں بائنری سرچ ٹری کا مکمل نفاذ درج ذیل ہے۔
# شامل کریں# شامل کریں
ساخت نوڈ {
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 ( بائنری سرچ ٹری کا C نفاذ! \n \n ' ) ;
ساخت نوڈ * والدین = خالی ;
والدین = insert_node ( والدین ، 10 ) ;
insert_node ( والدین ، 4 ) ;
insert_node ( والدین ، 66 ) ;
insert_node ( والدین ، چار پانچ ) ;
insert_node ( والدین ، 9 ) ;
insert_node ( والدین ، 7 ) ;
پرنٹ کریں ( والدین ) ;
واپسی 0 ;
}
مندرجہ بالا کوڈ میں، ہم پہلے اعلان کرتے ہیں a نوڈ استعمال کرتے ہوئے ساخت . پھر ہم ایک نیا نوڈ شروع کرتے ہیں جیسے ' نوڈ 1 اور متحرک طور پر استعمال کرتے ہوئے میموری کو مختص کریں۔ malloc() ڈیٹا اور دو پوائنٹرز کے ساتھ C میں اعلان کردہ نوڈ کا استعمال کرتے ہوئے بچوں کو ٹائپ کریں۔ اس کے بعد، ہم نوڈ کو بذریعہ ظاہر کرتے ہیں۔ printf() فنکشن کریں اور اسے میں کال کریں۔ مرکزی() فنکشن پھر insertion_node() فنکشن بنایا گیا ہے، جہاں اگر نوڈ ڈیٹا NULL ہے تو نوڈ 1 ریٹائرڈ ہے، ورنہ ڈیٹا میں رکھا جاتا ہے۔ نوڈ (والدین) بائیں اور دائیں بچے کے۔ پروگرام سے عمل درآمد شروع ہوتا ہے۔ مرکزی() فنکشن، جو بچوں کے طور پر چند نمونہ نوڈس کا استعمال کرتے ہوئے ایک نوڈ تیار کرتا ہے اور پھر نوڈ کے مواد کو پرنٹ کرنے کے لیے ان آرڈر ٹراورسل طریقے استعمال کرتا ہے۔
آؤٹ پٹ
نتیجہ
اعداد و شمار کو غیر لکیری شکل میں رکھنے کے لیے درختوں کو اکثر استعمال کیا جاتا ہے۔ بائنری درخت درختوں کی وہ اقسام ہیں جہاں ہر نوڈ (والدین) کی دو اولادیں ہوتی ہیں بائیں بچہ اور دایاں بچہ۔ اے بائنری درخت ڈیٹا کی منتقلی اور ذخیرہ کرنے کا ایک ورسٹائل طریقہ ہے۔ یہ سی میں لنکڈ لسٹ کے مقابلے میں زیادہ کارآمد ہے۔ مذکورہ مضمون میں، ہم نے ایک کے تصور کو دیکھا ہے۔ بائنری درخت a کے مرحلہ وار نفاذ کے ساتھ بائنری تلاش درخت سی میں