[Powered by Google Translate] [دفعہ 7] [کم آرام دہ اور پرسکون] [نیٹ Hardison] [ہارورڈ یونیورسٹی] [یہ CS50 ہے.] [CS50.TV] 

دفعہ 7 میں آپ کا استقبال ہے. سمندری طوفان کے لئے سینڈی پر آپ کا شکریہ، اس ہفتے ایک عام سیکشن ہونے کے بجائے، ہم اس واک کے ذریعے کر رہے ہیں سوالات کے سیکشن کے ذریعے،. میں کے مسائل کے ساتھ ساتھ مندرجہ ذیل 6 تفصیلات قائم کیا جائے جا رہا ہوں، اور میں سوالات کے سب سے گزر رہا سوالات کے سیکشن کے ایک حصے. اگر اس کے ذہن میں کوئی سوالات ہیں، برائے مہربانی CS50 بحث پر ان پوسٹ. 

ٹھیک ہے. شروع کرنے کے دو ٹھیک ہے اب میں مسئلہ سیٹ کی تفصیلات کے صفحہ 3 میں دیکھ رہا ہوں. ہم سب سے پہلے بائنری درختوں کے بارے میں بات کر شروع کرنے جا رہے ہیں کے بعد ان کا اس ہفتے کا مسئلہ سیٹ کی مطابقت کا ایک بہت ہے - Huffman درخت انکوڈنگ. بہت پہلے ڈیٹا ڈھانچے میں سے ایک ہم نے CS50 پر کے بارے میں بات کی تھی صف تھا. یاد رکھیں کہ عناصر میں سے ایک صف میں ایک ہی تسلسل ہے - اسی قسم کی - یاد داشت میں ایک دوسرے کے ساتھ دیئے گئے حق محفوظ ہے. اگر میں ایک عددی صف ہے کہ میں اس انداز باکس تعداد integers کا استعمال کرتے ہوئے اپنی طرف متوجہ کر سکتے ہیں ہے - چلو کا کہنا ہے کہ میں پہلی باکس میں 5 ہے، میں نے دوسری میں 7 ہے، تو میں 8، 10، اور آخری خانے میں 20 ہے. اس صف کے بارے میں یاد رکھیں، دو تو واقعی اچھی چیزیں ہے کہ ہم اس مسلسل وقت کسی خاص عنصر کو رسائی حاصل ہے  صف میں اگر ہم اس کے انڈیکس کو جانتے ہیں. مثال کے طور پر، اگر میں صف میں تیسرے عنصر پر قبضہ کرنا چاہتے ہیں - انڈیکس میں 2 ہماری صفر کی بنیاد پر تخکرمن کے نظام کا استعمال کرتے ہوئے - میں لفظی صرف ایک آسان حساب کا حساب کرنے کے لئے ہے، صف میں اس پوزیشن کو ہاپ، 8 کہ وہاں محفوظ ہے ھیںچو، اور میں اسے اچھی طرح ہوں. 

اس صف کے بارے میں بری چیزوں کی ایک - کہ ہم کے بارے میں بات کی تھی ہم منسلک فہرستوں پر تبادلہ خیال کیا - کہ اگر میں اس صف میں ایک عنصر داخل کرنا چاہتے ہیں، میں کچھ کے ارد گرد منتقل کرنے کے لئے کی ضرورت کے لئے جا رہا ہوں. مثال کے طور پر، یہ یہیں صف کے مطابق ترتیب میں ہے - صعودی میں کے مطابق - 5، پھر 7، تو 8، تو 10، اور پھر 20 - لیکن اگر میں اس صف میں 9 نمبر داخل کرنا چاہتے ہیں، میں کے کچھ عناصر کے لئے کی جگہ بنانے کے لئے منتقل کی ضرورت کے لئے جا رہا ہوں. ہم اس طرف متوجہ یہاں سے باہر جا سکتا ہے. میں 5، 7 کو منتقل کرنے کے لئے جا رہا ہوں، اور اس کے بعد 8؛ وقفے جہاں میں 9 رکھ سکتے ہیں بنانے کے، اور پھر 10 اور 20 9 کا حق میں جا سکتے ہیں. یہ درد کی طرح ہے کیونکہ بدترین حالات کی صورت میں - ہم داخل جب شروع میں یا آخر میں دشواری ہو رہی ہے یا تو صف، ہم کس طرح پر منحصر منتقل کر رہے ہیں - ہم نے ختم عناصر کے سب منتقل کرنے کر سکتے ہیں کہ ہم فی الحال صف میں ذخیرہ کرنے کر رہے ہیں. 

تو، اس کے ارد گرد کیا طریقہ تھا؟ اس کے ارد گرد اور طریقہ یہ ہے کہ ہمارے سے منسلک فہرست طریقہ ہے جہاں میں جانا تھا - عناصر 5، 7، 8، 10، اور 20 یاد میں ایک دوسرے کے ساتھ ذخیرہ کرنے کی بجائے - جو ہم بجائے جہاں کہیں بھی ہم ان سے محفوظ کرنا چاہتا تھا ان قسم ذخیرہ ان سے منسلک فہرست نوڈس میں جو میں نے یہاں سے باہر ڈرائنگ رہا ہوں، ایڈہاک کی طرح. اور پھر ہم نے انہیں مربوط مل کر ان اگلے اشارہ کا استعمال کرتے ہوئے. میں 5 سے 7 پوائنٹر کر سکتے ہیں، 7 سے 8 پوائنٹر 8 سے 10 پوائنٹر اور آخر میں، 10 سے 20 تک ایک پوائنٹر اور پھر 20، شہوت انگیز null پوائنٹر اشارہ ہے کہ کچھ بھی نہیں بچا ہے. ٹریڈ آف ہے کہ ہم یہاں ہیں کہ اب اگر ہم ہمارے کے مطابق کی فہرست میں 9 نمبر داخل کرنا چاہتے ہیں، ہم سب پر واجب ہے 9 کے ساتھ ایک نیا نوڈ بنانے کے، اسے مناسب جگہ پر کی طرف اشارہ، تار اور اس کے بعد دوبارہ تار 8 9 نیچے کی طرف اشارہ ہے. یہ بہت تیز ہے، سنبھالنے ہم بالکل پتہ ہے کہ جہاں ہم 9 کو شامل کرنے کے لئے چاہتے ہیں. لیکن اس کے بدلے میں تجارت بند یہ ہے کہ ہم اب تک رسائی مسلسل وقت کھو دیا ہے ہمارے اعداد و شمار کے ڈھانچے میں کسی خاص عنصر. مثال کے طور پر، اگر میں اس سے منسلک فہرست میں چوتھا عنصر تلاش کرنا چاہتے ہیں، میں کی فہرست کے شروع میں شروع کرنے کے لئے کی ضرورت کے لئے جا رہا ہوں اور نوڈ کی طرف سے نوڈ گنتی کے ذریعے اپنے راستے کو کام جب تک میں چوتھے ایک ملے. 

کے لئے ایک لنک کی فہرست سے بہتر تک رسائی کی کارکردگی کو حاصل کرنے کے لئے - بلکہ فوائد کہ ہم نے کچھ کو برقرار رکھنے - کے اندراج کے وقت کی شرائط میں ایک لنک کی فہرست سے ایک بائنری درخت تھوڑا اور میموری کو استعمال کرنے کی ضرورت پر کی جا رہی ہے. خاص طور پر، صرف ایک بائنری درخت نوڈ میں ایک پوائنٹر ہونے کے بجائے میں سب کچھ - فہرست سے منسلک کی طرح نوڈ ہے - ہم بائنری درخت نوڈ پر ایک دوسرے پوائنٹر کو شامل کرنے جا رہے ہیں. کی بجائے صرف اگلے عنصر ایک پوائنٹر ہے، ہم ایک بائیں بچے اور ایک صحیح بچے کو ایک پوائنٹر کے لئے جا رہے ہیں. 

کی ایک تصویر دیکھ کر اپنی طرف متوجہ کیا ہے کہ اصل کی طرح لگتا ہے. ایک بار پھر، میں ان باکس اور تیر کو استعمال کرنے کے لئے جا رہا ہوں. ایک بائنری درخت نوڈ صرف ایک سادہ باکس کے ساتھ شروع کر دیں گے. یہ قیمت کے لئے ایک جگہ ہے جا رہا ہے، اور پھر یہ بھی بائیں بچے اور دائیں بچے کے لئے ایک جگہ ہے جا رہا ہے. میں نے ان سے یہاں لیبل جا رہا ہوں. ہم بائیں بچہ جا رہے ہیں، اور پھر ہم صحیح بچے کے لئے جا رہے ہیں. ایسا کرنے کے بہت سے مختلف طریقے ہیں. ، کی جگہ اور سہولت کے لئے کبھی کبھی میں یہ اصل میں اپنی طرف متوجہ کی طرح میں نیچے پر یہاں کیا کر رہا ہوں گے جہاں میں سب سے اوپر کی قیمت میں جا رہا ہوں، اور پھر نیچے دائیں دائیں بچے، نیچے بائیں اور بائیں بچہ. ، اس کے سب سے اوپر تصویر پر واپس جانا ہم سب سے اوپر کی قیمت میں ہے، تو ہم بائیں بچے پوائنٹر ہے، اور پھر ہم پوائنٹر صحیح بچے ہے. 

مسئلہ سیٹ کی تفصیلات میں، ہم ایک نوڈ جو 7 قدر ہے ڈرائنگ کے بارے میں بات کرتے ہیں، اور پھر پوائنٹر بائیں بچے شہوت انگیز null ہے، اور حق بچے پوائنٹر شہوت انگیز null ہے. ہم نے خلا میں دارالحکومت نل یا تو کے لئے لکھ سکتے ہیں دونوں بائیں بچے اور دائیں بچے یا ہم اس اخترن سلیش کو اپنی طرف متوجہ کر سکتے ہیں باکس میں سے ہر ایک کے ذریعے اس بات کی نشاندہی کرتا ہے کہ یہ شہوت انگیز null ہے. میں ہے کہ صرف اس وجہ سے کہ آسان ہے کے لئے جا رہا ہوں. تم یہاں کیا دیکھ ایک بہت سادہ بائنری درخت نوڈ diagramming کے دو طریقے ہیں ہم 7 قدر اور جہاں اتارنا null بچے اشارہ ہے. 

ہمارے کس طرح منسلک کی فہرست کے ساتھ کے بارے میں تفصیلات کے مذاکرات کا دوسرا حصہ - یاد رکھو، ہم صرف ایک کی فہرست میں سب سے پہلا عنصر پر منعقد پڑا مکمل فہرست کو یاد کرنے کی - اور اسی طرح ایک بائنری درخت کے ساتھ، ہم صرف ایک پوائنٹر پر درخت کے انعقاد ہے کے لئے مکمل آنکڑا ڈھانچہ پر کنٹرول برقرار رکھنے کے لئے. درخت کا یہ خصوصی عنصر نے درخت کی جڑ نوڈ کو کہا جاتا ہے. مثال کے طور پر، اگر یہ ایک نوڈ - 7 قیمت پر مشتمل نوڈ شہوت انگیز null بائیں اور دائیں بچے اشارہ کے ساتھ - ہمارے درخت میں صرف قیمت تھے، تو یہ ہمارا روٹ نوڈ ہو جائے گی. یہ ہمارے درخت کی بہت آغاز ہے. ہم اس چھوٹے سے زیادہ واضح طور پر دیکھ کر ایک بار ہم نے ہماری درخت زیادہ نوڈس انہوں نے مزید کہا شروع کر سکتے ہیں. چلو، مجھے ایک نئے صفحے سے ھیںچ لیں. 

اب ہم ایک درخت ہے جو جڑ 7 ہے اپنی طرف متوجہ کرنے کے لئے جا رہے ہیں، اور بائیں، بچے، اور صحیح بچے کی 9 اندر اندر 3. ایک بار پھر، یہ بہت آسان ہے. ہم نے 7 ملی ہے، 3 کے لئے ایک نوڈ، 9 کے لئے ایک نوڈ سے اپنی طرف متوجہ کریں، اور میں 7 پوائنٹر بائیں بچے 3 مشتمل نوڈ کی طرف اشارہ مقرر کرنے جا رہا ہوں، اور 9 پر مشتمل نوڈ 7 مشتمل نوڈ کے دائیں بچے پوائنٹر. اب 3 اور 9 کے بعد سے کسی بھی بچے نہیں ہے، ہم اپنے بچے کے اشارہ کے تمام لوڈ، اتارنا null قائم کرنے جا رہے ہیں. یہاں، ہمارے درخت کی جڑ نمبر 7 پر مشتمل نوڈ کے مساوی ہے. تم نے یہ دیکھا کر سکتے ہیں اگر ہم نے اس روٹ نوڈ پوائنٹر ہے، تو ہم اپنے درخت کے ذریعے چل سکتے ہیں اور دونوں بچے نوڈس تک رسائی حاصل کر سکتے ہیں - دونوں 3 اور 9. درخت پر ہر ایک نوڈ پر اشارہ کو برقرار رکھنے کی ضرورت ہے نہیں ہے. ٹھیک ہے. اب ہم اس آریھ پر دوسری نوڈ پر شامل کرنے کے لئے جا رہے ہیں. ہم 6 مشتمل نوڈ کو شامل کرنے کے لئے جا رہے ہیں، اور ہم 3 مشتمل نوڈ کے دائیں بچے کے طور پر شامل کرنے جا رہے ہیں. ایسا کرنے کے لیے، میں 3 نوڈ میں کہ شہوت انگیز null پوائنٹر مٹانے کے لئے جا رہا ہوں اور یہ تار 6 مشتمل نوڈ کی طرف اشارہ ہے. ٹھیک ہے. 

اس وقت، اصطلاحات کا ایک تھوڑا سا پر. ، وجہ ہے کہ یہ خاص طور پر ایک بائنری درخت کہا جاتا ہے شروع یہ ہے کہ یہ دو بچے اشارہ ہے. کے دیگر قسم کے درخت ہے کہ زیادہ بچے اشارہ ہے ہیں. خاص طور پر، آپ کو ایک مسئلہ 5 سیٹ میں کی کوشش کرو 'کیا. آپ اس کوشش میں ہے کہ محسوس کریں گے، آپ کو مختلف بچوں کے 27 مختلف اشارہ تھا - انگریزی حروف تہجی میں 26 حروف میں سے ہر ایک کے لئے ایک، اور پھر apostrophe کے لئے 27th - ایسا ہے، تو وہ درخت کی ایک قسم کے لئے اسی طرح کی ہے. لیکن یہاں، یہ بائنری کے بعد سے، ہم صرف دو بچے اشارہ ہے. 

اس روٹ نوڈ ہے کہ ہم کے بارے میں بات کرنے کے علاوہ میں، ہم بھی کیا گیا ہے اس لفظ کے ارد گرد پھینک 'بچے. کیا اس کا مطلب یہ ہے کے لئے ایک نوڈ دوسرے نوڈ کا ایک بچہ ہے؟ یہ لفظی مطلب یہ ہے کہ ایک بچے نوڈ کو دوسرے نوڈ کا ایک بچہ ہے جب کہ دوسرے نوڈ اس کے بچے کو اس نوڈ پر کی طرف اشارہ مقرر اشارہ میں سے ایک ہے. کنکریٹ کی شرائط میں یہ ڈال، اگر 3 7 کا بچہ اشارہ کی ایک کی طرف سے نشاندہی کی ہے، اس وقت 3 7 ایک بچہ ہے. اگر ہم اعداد و شمار کیا 7 بچے ہیں - اچھا، ہم دیکھتے ہیں، کہ 7 3 پوائنٹر اور 9 پوائنٹر ہے، تو 9 اور 3 7 بچے ہیں. نو کوئی بچے نہیں ہیں کیونکہ اس کے بچے اشارہ شہوت انگیز null ہیں، اور صرف 3 ایک بچہ، 6 ہے. چھ بھی کوئی بچے نہیں ہیں کیونکہ اس کے اشارہ کے دونوں شہوت انگیز null، جو ہم نے ابھی اپنی طرف متوجہ کریں گے. 

کے علاوہ، ہم ایک خاص نوڈ کے والدین کے بارے میں بھی بات کرتے ہیں، اور یہ ہے، جیسا کہ آپ کی توقع چاہتے ہیں، تو اس بچے کو وضاحت کی الٹ ہے. دو کی بجائے جیسا کہ آپ انسانوں کے ساتھ کی توقع کر سکتے ہیں - ہر نوڈ صرف ایک والدین ہیں. مثال کے طور پر، 3 والدین 7 ہے. 9 کے والدین بھی 7 ہے، اور والدین کا 6 3 ہے. زیادہ نہیں. ہم دادا دادی اور پوتے کے بارے میں بات کرنے کے لئے بھی شرائط ہیں، اور عام طور پر ہم پتروں کے بارے میں بات کرتے ہیں اور ایک خاص نوڈ کی سنتان. نوڈ کے پرکھا - یا باپ دادا کو ایک نوڈ سے، بلکہ - ہیں نوڈس ہے کہ جڑ سے اس نوڈ کے راستے پر جھوٹ. مثال کے طور پر، اگر میں نوڈ 6 بجے دیکھ رہا ہوں، تو باپ دادا دونوں 3 اور 7 کے لئے جا رہے ہیں. 9 کی آباؤ اجداد، مثال کے طور پر، کر رہے ہیں - اگر میں نوڈ 9 بجے دیکھ رہا ہوں - تو 9 پرکھا 7 ہے. اور اولاد بالکل ریورس ہیں. اگر میں 7 کے خاندان کے تمام کو دیکھنے کے لئے چاہتے ہیں، تو میں اس کے نیچے نوڈس کے تمام کو دیکھنے کے لئے ہے. لہذا، میں 3، 9، اور 6 7 کے خاندان کے طور پر تمام ہے. 

آخری مدت کہ ہم کے بارے میں بات کریں گے، ایک بھائی ہونے کا یہ تصور ہے. بھائی بہن کی تعداد - خاندان کے ان شرائط پر ساتھ بعد کی قسم - نوڈس جو درخت میں ایک ہی سطح پر ہیں. تو، 3 اور 9 بہن بھائیوں ہیں کیونکہ وہ درخت میں ایک ہی سطح پر ہیں. وہ دونوں ایک ہی والدین، 7 ہے. 6 بھائی بہن ہے کیونکہ 9 کسی بھی بچے نہیں ہے. اور 7 کسی بھی بہن بھائیوں کو نہیں ہے کیونکہ یہ ہمارے درخت کی جڑ ہے، اور کبھی صرف 1 جڑ ہے. کے لئے 7 بہن بھائیوں وہاں 7 اوپر ایک نوڈ ہوگا. 7 کے والدین، جس میں 7 کیس درخت کی جڑ اب نہیں ہو گی ہو گی. اس کے بعد 7 نئے والدین ایک بچہ بھی ہوگا، اور یہ کہ بچے کو 7 بھائی ہو جائے گی. 

ٹھیک ہے. پر جا رہے ہیں. ، جب ہم ہمارے بائنری درختوں کی بحث کا آغاز کیا ہم کہ ہم کس طرح ان کے لئے استعمال کرنے کے لئے جا رہے تھے کے بارے میں بات کی arrays اور منسلک فہرستوں پر دونوں کا فائدہ حاصل کریں. اور جس طرح سے ہم ایسا کرنے کے لئے جا رہے ہیں اس کا حکم جائیداد کے ساتھ ہے. ہم کا کہنا ہے کہ ایک بائنری درخت حکم دیا جاتا ہے تفصیلات کے مطابق، اگر ہمارے درخت میں ہر نوڈ کے لئے، بائیں جانب اس کی اولاد کے سب - بائیں بچے اور بائیں بچے کی اولاد کے تمام - کم اقدار، اور دائیں جانب نوڈس - صحیح بچے اور صحیح بچے کی اولاد کے تمام - موجودہ نوڈ کی قدر ہے کہ ہم دیکھ رہے ہیں سے زیادہ نوڈس ہے. بس سادگی کے لئے، ہم یہ فرض ہے کہ ہمارے درخت میں کوئی ڈوپلیکیٹ نوڈس نہیں ہیں جا رہے ہیں. مثال کے طور پر، ہم نے اس درخت میں کیس سے نمٹنے کے نہیں کر رہے ہیں ہم جڑ جہاں 7 قدر ہے  اور پھر ہم بھی قدر دوسری جگہوں پر درخت میں 7 ہے. اس صورت میں، آپ کو نوٹس، گے کہ اس درخت کو واقعی حکم دیا جاتا ہے. ہم نے جڑ 7 قدر ہے. 7 بائیں کو سب کچھ - اگر میں ان بہت کم نمبروں کی سب یہاں کالعدم - 7 بائیں سب کچھ - 3 اور 6 - ان اقدار دونوں 7 سے کم اور صحیح سب کچھ - - جس میں صرف 9 ہے 7 سے بڑا ہے. 

یہ صرف حکم دیا ان اقدار پر مشتمل درخت نہیں ہے، لیکن ان میں سے چند اپنی طرف متوجہ. اصل میں ہے طریقوں کہ ہم یہ کر سکتے ہیں کی ایک پوری گچرچھا ہے. میں آشلپی صرف چیزوں کو آسان جہاں رکھنے کے لئے استعمال کرنے کے لئے جا رہا ہوں - بلکہ پوری باکس اور تیر ڈرائنگ سے میں سب کچھ - میں صرف تعداد کو اپنی طرف متوجہ کرنے اور ان سے منسلک تیر شامل کی جا رہی ہوں. ، ہم اپنے اصل درخت پھر لکھیں گے جہاں ہم 7 سال کی تھی شروع، اور پھر 3، اور پھر 3 6 کا حق واپس کی طرف اشارہ کیا، اور 7 ایک صحیح بچے کہ 9 سال کی تھی. ٹھیک ہے. ایک اور طریقہ ہے کہ ہم اس درخت کو لکھ سکتے ہیں کیا کیا ہے؟ کی بجائے 3 7 کے بائیں بچے، ہم بھی 6 7 کے بائیں بچے کر سکتے ہیں، اور پھر 3 6 کے بائیں بچے. اس درخت کی طرح ابھی یہاں دیکھو جہاں میں 7 ہے، تو 6، تو 3، اور حق پر 9. ہم نے ہماری جڑ نوڈ کے طور پر 7 کی ضرورت نہیں ہے. ہم نے ہماری جڑ نوڈ کے طور پر 6 بھی کر سکتے ہیں. کیا اس طرح نظر آئے گا؟ اگر ہم نے اس کا حکم دیا ملکیت کو برقرار رکھنے کے لئے جا رہے ہیں، 6 بائیں کو سب کچھ اس سے کم ہونا ہے. صرف ایک امکان ہے، اور یہ کہ 3. لیکن اس وقت 6 کے دائیں بچے کے طور پر، ہم نے دو امکانات ہیں. سب سے پہلے، ہم 7 ہے اور پھر سکتا ہے 9، یا ہم اسے اپنی طرف متوجہ کر سکتے ہیں - جیسا کہ میں یہاں کیا کر رہا ہوں - ، جہاں ہم نے 6 کے دائیں بچے کے طور پر 9 ہے اور پھر 9 کے بائیں بچے کے طور پر 7. 

اب، 7 اور 6 جڑ کے لئے ہی ممکن اقدار نہیں ہیں. ہم نے 3 جڑ کر سکتے ہیں. اگر 3 جڑ ہے تو کیا ہوتا ہے؟ یہاں چیزیں تھوڑا سا دلچسپ ملتا ہے. تین کوئی اقدار نہیں کرتا ہے جو اس سے کم ہے، درخت کی کہ پوری بائیں جانب اتارنا null جا رہا ہے. آمدید کچھ وہاں جا نہیں ہے. صعودی میں صحیح کرنے کے لئے، ہم چیزوں کی فہرست کر سکتے ہیں. ہم نے 3، پھر 6، تو 7، تو 9 کر سکتے ہیں. یا، ہم 3 کرتے ہیں، تو 6، کر سکتے ہیں تو 9، 7 تو. یا، ہم 3 کرتے ہیں، تو 7، کر سکتے ہیں تو 6، 9 تو. یا، 3، 7 - نہیں، اصل، ہم 7 نہیں کر سکتا. کہ وہاں ہمارے ایک بات ہے. ہم 9 کرتے ہیں، اور پھر 9 سے ہم 6 کرتے ہیں اور پھر 7 سکتے ہیں کر سکتے ہیں. یا، ہم 3 کرتے ہیں، تو 9، کر سکتے ہیں تو 7، اور پھر 6. 

ایک بات یہ ہے کہ یہاں آپ کی توجہ اپنی طرف متوجہ ہے کہ ان درختوں کو ایک چھوٹا سا عجیب نظر آنے والے ہیں. اگر خاص طور پر، ہم دائیں جانب 4 درختوں پر دیکھو - میں ان کے سرکل یہاں کریں گے - ان درختوں کو ایک لنک کی فہرست کی طرح تقریبا بالکل نظر آتے ہو. ہر نوڈ صرف ایک بچہ ہے، اور اسی طرح ہم نے مثال کے طور پر اس ڈھانچے پیڑ کی طرح ہے کہ ہم دیکھتے ہیں کے کسی بھی نہیں،  یہاں یہ ایک نیچے بائیں واحد درخت میں. یہ درخت اصل میں بائنری درخت degenerate کہا جاتا ہے، اور ہم مستقبل میں ان کے بارے میں بات کریں گے - خاص طور پر اگر آپ پر دوسرے کمپیوٹر سائنس کورس کرنے کے لئے جانا. یہ درخت degenerate ہیں. وہ بہت ہی مفید نہیں ہو کیونکہ، یقینا، یہ ساخت خود فراہم کرتا ہے  ایک لنک کی فہرست کے لئے اسی طرح کی اوقات تلاش کرنے کے لئے. ہم اضافی میموری کا فائدہ اٹھا کر حاصل نہیں ہے - یہ اضافی پوائنٹر - ہماری ساخت کی وجہ سے اس طرح سے خراب ہے. بجائے جاؤ اور بائنری درخت ہے جو جڑ 9 ہے اپنی طرف متوجہ، جس میں آخری مقدمہ ہے کہ ہم ہوگا، ہم بجائے ہیں، اس وقت، یہ دوسری مدت کے بارے میں تھوڑا بہت بات کرنے جا کہ ہم استعمال کرتے ہیں جب درخت، جو اونچائی کہا جاتا ہے کے بارے میں بات کر رہی ہے. 

ایک درخت کی اونچائی جڑ سے سب سے زیادہ دور نوڈ دوری ہے، بلکہ hops کی تعداد ہے کہ آپ کے لئے کرنا ہوگا جڑ سے شروع کرتے ہیں اور پھر درخت میں نوڈ سب سے زیادہ دور میں ختم. اگر ہم ان درختوں میں سے کچھ ہے کہ ہم یہیں تیار کیا ہے، دیکھو، ہم نے 3 میں دیکھ رہا ہوں کہ اگر ہم نے سب سے اوپر بائیں کونے میں اس درخت کو لے اور ہم شروع کر سکتے ہیں، تو ہم 1 ہاپ 6 حاصل کرنے کے لئے، 7 حاصل کرنے کے لئے ایک دوسرے ہاپ بنانے کے لئے ہے، اور ایک تہائی ہاپ 9 حاصل کرنے کے لئے. تو، اس درخت کی اونچائی 3 ہے. ہم نے اس سبز کے ساتھ بیان کردہ دوسرے درخت کے لئے ایک ہی مشق کر سکتے ہیں، اور ہم دیکھتے ہیں کہ ان درختوں کی سب سے اونچائی بھی ہے یقینا 3. یہ کیا کرتا ہے ان degenerate کا حصہ ہے - کہ ان کی اونچائی صرف ایک پورے درخت میں مراکز کی تعداد کے مقابلے میں کم ہے. اگر ہم دوسری طرف اس دوسرے درخت ہے کہ لال کا گھرا ہے، میں دیکھتا ہوں، ہم دیکھتے ہیں کہ سب سے زیادہ دور پتی نوڈس 6 اور 9 ہیں - چھوڑ دیتا ہے وہ نوڈس کہ کوئی بچے ہیں کیا جا رہا ہے. تو، کے لئے جڑ نوڈ سے کسی بھی 6 یا 9 حاصل کرنے کے لئے، ہم ایک ہاپ 7 سے حاصل کرنے کے لئے تو اور 9 حاصل کرنے کے لئے ایک دوسرے ہاپ، اور اسی طرح، 7 سے صرف ایک دوسرے ہاپ 6 حاصل کرنے کے لئے. تو، یہاں اس درخت کی اونچائی صرف 2 ہے. تم واپس جاؤ اور دوسرے درخت میں سے سب کے لئے کر سکتے ہیں کہ ہم نے پہلے بات چیت کی 7 اور 6 کے ساتھ شروع آپ کو تلاش کریں گے اور یہ کہ ان پیڑوں میں سے سب سے اونچائی بھی ہے 2. 

وجہ ہے ہم کے بارے میں بات کر رہے بائنری درخت کو حکم دیا اور کیوں ہے وہ ڈاؤن لوڈ، اتارنا ہیں کیونکہ آپ ان کے ذریعے تلاش کر سکتے ہیں ایک بہت ہی کے مطابق صف پر تلاش کرنے کا ایک طریقہ ہے. یہی وہ جگہ ہے جہاں ہم کہ بہتر تلاش وقت حاصل کرنے کے بارے میں بات کرتے ہیں سادہ منسلک فہرست پر. ایک لنک کی فہرست کے ساتھ - - اگر آپ کو ایک مخصوص عنصر کو تلاش کرنا چاہتے ہیں تم بہترین لکیری تلاش کے کچھ کیا کرنے جا رہے ہو آپ کو ایک فہرست اور ہاپ ایک کی طرف سے ایک کے آغاز میں کہاں سے شروع - ایک نوڈ کی طرف سے ایک نوڈ - مکمل فہرست ہے جب تک کہ آپ جو کچھ بھی آپ کے لئے تلاش کر رہے ہیں کے ذریعے. جبکہ، اگر آپ کو ایک بائنری درخت ہے کہ اس اچھی شکل میں محفوظ ہے، آپ کو ایک بائنری جا تلاش کے بھی حاصل کر سکتے ہیں ہے آپ اور کہاں فتح تقسیم اور ہر قدم پر درخت کی مناسب نصف کے ذریعے تلاش. چلو، یہ کیسے کام کرتا ہے کو دیکھنے کے. 

اگر ہم - پھر ہماری اصل درخت واپس جا - ہم 7 بجے شروع ہم نے بائیں جانب 3 ہے، دائیں طرف کے 9، اور ہم نے 3 کے نیچے 6 ہے. اگر ہم اس پیڑ میں 6 نمبر کے لئے تلاش کرنا چاہتے ہیں ہیں، ہم جڑ میں شروع کروں گا. ہم قدر ہم کے لئے، 6 کہنا تلاش کر رہے ہیں کا آپس میں موازنہ کریں گے، نوڈ کہ ہم فی الحال میں، 7 تلاش کر رہے ہیں میں ذخیرہ کی قیمت، تلاش کہ 6 یقینا سے کم 7 ہے، تو ہم بائیں منتقل کریں گے. اگر 6 کی قیمت 7 سے بڑا رہا تھا، ہم اس کی بجائے حق پر کریں گے میں منتقل کردیا گیا ہے. چونکہ ہم جانتے ہیں کہ - ہمارے حکم دیا بائنری درخت کی ساخت کی وجہ سے - 7 سے کم اقدار کی سب 7 بائیں سے محفوظ رکھا جائے جا رہے ہیں، کوئی فکر کرنے کی بھی درخت کی دائیں جانب کے ذریعے تلاش کرنے کی ضرورت ہے. ایک بار جب ہم بائیں منتقل اور اب ہم 3 مشتمل نوڈ میں ہیں، ہم اس ایک ہی موازنہ پھر سے کرتے ہیں جہاں ہم نے 3 اور 6 کا آپس میں موازنہ کر سکتے ہیں. اور ہم یہ محسوس کرتے ہیں کہ جبکہ 6 - قدر ہم کے لئے تلاش کر رہے ہیں - 3 سے بڑھ کر ہے، ہم 3 مشتمل نوڈ کے دائیں جانب جا سکتے ہیں. کوئی بائیں جانب ہے، تو ہم اس کو نظرانداز کیا جا سکتا ہے. لیکن ہم صرف یہ جانتے ہیں کہ کیونکہ ہم خود درخت کی طرف دیکھ رہے ہیں، ہم دیکھتے ہیں اور یہ کہ درخت کوئی بچے نہیں ہیں کر سکتے ہیں. 

یہ بھی بہت آسان ہے اس درخت میں سے 6 دیکھو، اگر ہم یہ کام کر رہے خود کر رہے ہیں انسان کے طور پر، لیکن ایک کمپیوٹر کی طرح اس عمل میکانکی کی پیروی کرے گا واقعی الگورتھم کو سمجھتے ہیں. اس وقت، اب ہم ایک نوڈ کہ 6 پر مشتمل ہے میں تلاش کر رہے ہیں، اور ہم 6 قیمت کے لئے تلاش کر رہے ہیں، ایسا ہے، تو بے شک، ہم مناسب نوڈ تلاش کر لیا ہے. ہم درخت میں 6 قیمت مل گیا ہے، اور ہم اپنی تلاش کو روکنا کر سکتے ہیں. اس وقت کیا ہو رہا ہے پر منحصر ہے، ہم کہہ سکتے ہیں، جی ہاں، ہم 6 قیمت مل گیا ہے، یہ ہمارے درخت میں موجود ہے. یا، اگر ہم ایک نوڈ کو شامل کرنے کے لئے یا کچھ کی منصوبہ بندی کر رہے ہیں، ہم اس وقت ایسا کر سکتے ہیں. 

چلو ایک جوڑے lookups صرف یہ کس طرح کام کرتا ہے دیکھنے کے لئے. چلو، کیا ہوا اگر ہم اور 10 قیمت تلاش کرنے کی کوشش کر رہے تھے ہوتا ہے کو دیکھو. اگر ہم 10 قیمت پر نظر تھے، ہم جڑ میں شروع ہو جائے گی. ہم دیکھتے ہیں کہ 7 سے 10 بڑی اور عظیم چیز ہے، تو ہم کو درست کرنے میں منتقل ہوتا ہے. ہم 9 10 9 موازنہ اور چاہتے ہیں دیکھتے ہیں کہ یقینا 9 سے کم 10 ہے. تو پھر، ہم حق میں منتقل کرنے کی کوشش کریں گے. لیکن ہم اس وقت محسوس کرتے ہیں، چاہتے ہیں کہ ہم شہوت انگیز null نوڈ میں ہیں. وہاں کچھ بھی نہیں ہے. وہاں کچھ بھی نہیں ہے 10 کہاں ہونا چاہئے. اس کا ہے جہاں ہم ناکامی کی رپورٹ کر سکتے ہیں - ہے کہ واقعی کوئی درخت میں 10. اور آخر میں، صورت میں جہاں ہم نے درخت میں سے 1 نظر کرنے کی کوشش کر رہے ہیں کے ذریعے جانا. یہ کیا اگر ہم نے 10 نظر آتے کو درست کرنے کے بجائے کے علاوہ ہوتا ہے، اسی طرح ہے، ہم بائیں طرف جانے کے لئے جا رہے ہیں. ہم نے 7 بجے شروع کرتے ہیں اور دیکھتے ہیں کہ 1 7 سے کم ہے، تو ہم بائیں منتقل کریں. ہم نے 3 سے ملتا ہے اور دیکھتے ہیں کہ 1 3 سے کم ہے، تو پھر ہم بائیں طرف منتقل کرنے کے لئے کی کوشش کرتے ہیں. اس وقت ہم نے ایک لوڈ، اتارنا null نوڈ ہے، تو پھر ہم ناکامی کی رپورٹ کر سکتے ہیں. 

اگر آپ کو بائنری درختوں کے بارے میں کے بارے میں مزید جاننے کے لئے چاہتے ہیں، تفریح ​​بہت کم مسائل ہیں کہ آپ ان کے ساتھ کیا کر سکتے ہیں کی ایک پوری چڑھانے ہیں. میں ان diagrams کی طرف سے ایک ڈرائنگ مشق کا مشورہ دیتے ہیں مختلف اقدامات کے ذریعے بعد کیونکہ یہ سپر ہاتھ میں آئے گا نہ صرف جب تم Huffman انکوڈنگ مسئلہ سیٹ کر رہے ہیں بلکہ مستقبل کے کورسز میں - صرف سیکھنے کس طرح ان اعداد و شمار کے ڈھانچے کو اپنی طرف متوجہ اور مسائل کے ذریعے لگتا ہے کے ساتھ قلم اور کاغذ یا، اس کیس میں رکن، اور stylus. 

اگرچہ اس وقت، ہم کچھ کوڈنگ پریکٹس کرنا منتقل جا رہے ہیں اور اصل میں ان بائنری درخت کے ساتھ ادا کرتے ہیں اور دیکھتے ہیں. میں اپنے کمپیوٹر پر واپس سوئچ جا رہا ہوں. CS50 چلائیں یا CS50 خالی جگہوں کا استعمال کرتے ہوئے کی بجائے سیکشن کے اس حصے کے لئے، میں اس آلے کو استعمال کرنے کے لئے جا رہا ہوں. 

مسئلہ سیٹ کی تفصیلات کے ساتھ ساتھ بعد میں دیکھ رہا ہوں کہ میں نے آلات پر کھولنے والے ہوں، میرے ڈراپ باکس فولڈر کے لئے، ایک دفعہ 7 نامی فولڈر بنائیں، اور پھر کہا جاتا binary_tree.c فائل تشکیل دیں. یہاں ہم چلے. میں آلات پہلے ہی کھلا ہے. میں ایک ٹرمینل ھیںچو جا رہا ہوں. ، میں ڈراپ باکس کے فولڈر میں جانے کے لئے جا رہا ہوں، نامی section7 ڈائریکٹری دیکھتے ہیں اور یہ مکمل طور پر خالی ہے. اب میں نے binary_tree.c کھولنے جا رہا ہوں. ٹھیک ہے. خالی فائل - یہاں ہمیں جانا. 

تفصیلات پر واپس جانے دو. تفصیلات ایک نئی قسم کی تعریف سے بنانے کے لئے کرتے ہیں ایک بائنری درخت int اقدار پر مشتمل نوڈ کے لئے - صرف اقدار کہ ہم نے ہمارے سے پہلے diagramming میں متوجہ کی طرح. ہم یہ boilerplate typedef کہ ہم یہاں کیا ہے استعمال کرنے کے لئے جا رہے ہیں کہ آپ مسئلہ 5 سیٹ سے تسلیم کرنا چاہئے - اگر تم فتح ہجے کنندہ کے پروگرام کے ہیش کی میز کی طرح کیا. تم نے یہ گزشتہ ہفتے کے حصے سے بھی تسلیم کرنا چاہئے جہاں ہم منسلک فہرستوں کے بارے میں بات کی تھی. ہم نے ایک struct نوڈ کے اس typedef ہے، اور ہم اس struct نوڈ کو struct نوڈ کے سے پہلے اس کا نام ہے تاکہ ہم پھر اس کا حوالہ دیتے ہیں کیونکہ ہم struct نوڈ اشارہ کرنا چاہیں گے کر سکتے ہیں ہمارے struct کا حصہ کے طور پر، لیکن ہم تو اس گھرا ہے - typedef میں - یا بلکہ یہ منسلک تاکہ بعد میں کوڈ میں، ہم بجائے struct نوڈ کا ایک نوڈ کے طور پر اس struct رجوع کر سکتے ہیں. 

یہ بہت اکیلے سے تعلق رکھنے والے کی فہرست تعریف اسی طرح گزشتہ ہفتے سے کہ ہم نے دیکھا جا رہا ہے. ایسا کرنے کے لئے، صرف boilerplate لکھنے کی طرف سے شروع کریں. ہم جانتے ہیں کہ ہم ایک عددی قیمت ہے، تو ہم int قدر میں ڈال، اگلے عنصر صرف ایک پوائنٹر ہونے کے بجائے اس وقت گا اور - جیسا کہ ہم اکیلے سے تعلق رکھنے والے کی فہرست کے ساتھ کیا تھا - ہم بائیں اور دائیں بچے اشارہ کر جا رہے ہیں. یہ بہت آسان بھی ہے - struct نوڈ بائیں * بچے؛ اور struct نوڈ * صحیح بچے. ڈاؤن لوڈ، اتارنا. یہ ایک بہت اچھا آغاز کی طرح لگتا ہے. تفصیلات پر واپس جانے دو. 

اب ہم نے ایک درخت کی جڑ کے لئے عالمی سطح پر نوڈ * متغیر کا اعلان کرنے کی ضرورت ہے. ہم جیسا کہ ہم نے ہمارے منسلک بھی عالمی فہرست میں پہلی پوائنٹر نے اس عالمی بنانے کے لئے جا رہے ہیں. تاکہ یہ تھا کام کرتا ہے کہ ہم لکھنے میں ہم اس جڑ کے ارد گرد گزر رہا رکھنے کے لئے کی ضرورت نہیں ہے - اگرچہ ہم دیکھ کہ اگر آپ ایسا کرتے ہیں ان افعال کو تکراری طور پر لکھنا چاہتا ہوں، اسے پہلی جگہ میں بہتر ہو سکتا ہے یہ ایک عالمی طور پر بھی آس پاس نہیں گزر سکتا ہے اور آپ کی مرکزی تقریب میں بجائے مقامی طور پر اس کی ابتدا ہے. لیکن، ہم نے اسے دنیا بھر میں شروع کریں گے. ایک بار پھر، ہم خالی جگہوں کے ایک جوڑے دیتے ہیں، اور میں ایک نوڈ * جڑ کا اعلان کرنے جا رہا ہوں گے. یقین ہے کہ میں نے وہ چھوڑ کر نہیں یہ غیر ابتدا شدہ بنانے کے لئے، میں نے اسے برابر قائم کرنے جا رہا شہوت انگیز null رہا ہوں. اب مرکزی تقریب میں - جو ہم واقعی بہت تیزی سے ٹھیک یہاں لکھیں گے - int اہم (int argc، const حروف * argv []) - اور میں const کے طور پر میری argv صف اعلان شروع کرنے کے لئے صرف اس لئے ہے کہ میں جانتا ہوں کہ جا رہا ہوں کہ ان دلائل کو دلائل کہ میں شاید پر نظر ثانی کرنے کی نہیں کرنا چاہتے ہیں ہیں. اگر میں ان پر نظر ثانی کرنا چاہتے ہیں تو میں شاید ان کی کاپیاں بنانے چاہئے. آپ اس کوڈ میں بہت دیکھ لیں گے. یہ ٹھیک ہے یا تو طریقہ ہے. یہ ٹھیک ہے، اس کے طور پر چھوڑ دیں - اگر آپ چاہیں تو const ترک. میں عام طور پر اس میں صرف اس لئے پیش کیا ہے جس میں اپنے آپ کو یاد دلانے  کہ میں شاید ان دلائل پر نظر ثانی نہیں کرنا چاہتا. 

ہمیشہ کی طرح، میں نے اہم آخر میں اس کی واپسی 0 لائن شامل کرنے کے لئے جا رہا ہوں. یہاں، میں اپنی جڑ نوڈ ابتدا گا. جیسا کہ یہ ابھی کھڑا ہے، میں ایک پوائنٹر شہوت انگیز null مقرر ہے، تو یہ کچھ نہیں طرف اشارہ ہے. حکم میں اصل نوڈ کی تعمیر شروع کرنے کے لئے، میں نے سب سے پہلے اس کے لئے میموری مختص کرنے کی ضرورت ہے. میں malloc کا استعمال کرتے ہوئے ڈھیر پر یاد کرنے کی طرف سے اس کے کرنے جا رہا ہوں. میں malloc کا نتیجہ کے برابر جڑ قائم کرنے جا رہا ہوں، اور میں sizeof آپریٹر ایک نوڈ کے سائز کا حساب کرنے کے لئے استعمال کی جا رہی ہوں. وجہ ہے کہ میں نے sizeof نوڈ کا استعمال کرتے ہیں کے طور پر مخالفت کی، کا کہنا ہے کہ، malloc (4 + 4 +4) یا 12 malloc - اس طرح کچھ کرنے - کیونکہ میں اپنے کوڈ ممکن ہو سکے کے طور پر کے طور پر ہم آہنگ کرنا چاہتے ہیں ہے. میں اس سی فائل. لینے کے قابل بننا چاہتا ہوں، اس آلے پر مرتب، اور پھر یہ میرا میک 64 بٹ پر مرتب - یا ایک مکمل طور پر مختلف ساخت پر - اور میں نے یہ سب ایک ہی کام کرنا چاہتے ہیں. 

اگر میں متغیرات میں سے سائز کے بارے میں مفروضات کر رہا ہوں - ایک int یا ایک پوائنٹر کے سائز کا سائز - تو میں بھی architectures کی قسم کے بارے میں مفروضات بنا رہا ہوں جس پر میرا کوڈ جب چلانے کے کامیابی سے مرتب کر سکتے ہیں. ہمیشہ sizeof استعمال کرنے کے لئے کے طور پر دستی طور پر struct شعبوں میزانی کی مخالفت کی. دوسری وجہ یہ ہے کہ وہاں بھرتی بھی ہو سکتا ہے کہ سنکلک struct میں رکھتا ہے. بھی صرف انفرادی شعبوں میزانی کچھ ہے جو آپ عام طور پر کرنا چاہتے ہیں نہیں ہے، ایسا ہے، تو اس لائن کو ختم کر دیں. اب واقعی میں اس روٹ نوڈ ابتدا، میں اس کے مختلف شعبوں میں سے ہر ایک کے لئے اقدار میں ہونا پڑے جا رہا ہوں. مثال کے طور پر، قیمت کے لئے مجھے پتہ ہے میں 7 سے ابتدا کرنا چاہتے ہیں، اور اب میں بائیں بچے خالی ہو جائے قائم کرنے کے لئے جا رہا ہوں اور صحیح بچہ بھی، شہوت انگیز null. بہت اچھا ہے! ہم نے رپورٹ کے اس حصے نے کیا ہے. 

صفحہ 3 کا سب سے نیچے دیئے گئے تفصیلات کے نیچے مجھ سے پوچھتا مزید تین مراکز بنانے کے لئے - 9 3، 6 پر مشتمل ایک، اور ایک پر مشتمل ایک - اور پھر ان کے تار تو یہ بالکل ہمارے درخت خاکہ کی طرح لگتا ہے کہ ہم پہلے سے بات کر رہے تھے. چلو وہ بہت تیزی سے یہاں کرتے ہیں. تم نے واقعی بہت تیزی سے دیکھتے ہیں کہ میں نقل کوڈ کا ایک گروپ لکھنا شروع کرنے جا رہا ہوں گے. میں ایک نوڈ * بنانے کے لئے جا رہا ہوں اور میں اسے تین کو فون کرنے جا رہا ہوں. میں اسے malloc (sizeof (نوڈ)) کے برابر مقرر کرنے جا رہا ہوں. میں تین> قیمت = 3 قائم کرنے جا رہا ہوں. تین -> left_child = نل، تین -> صحیح _child = نل، کے ساتھ ساتھ. یہ خوبصورت جڑ ابتدا کی طرح لگ رہا ہے، اور یہ کہ بالکل کیا ہے میں اگر میں 6 اور 9 ابتدا کے ساتھ ساتھ شروع کرنا پڑے جا رہا ہوں. مجھے یہ واقعی فوری طور پر یہاں کیا کریں گے - اصل میں، میں نے ایک چھوٹی سی کاپی اور پیسٹ کرنے کے لئے جا رہا ہوں، ٹھیک - اور اس بات کا یقین کر لیں کہ میں.  اب، میں ہے یہ کاپی اور میں آگے بڑھیں اور 6 اس کے برابر مقرر کر سکتے ہیں. آپ دیکھ کر سکتے ہیں کہ یہ کچھ وقت لیتا ہے اور سپر ہنر نہیں ہے. صرف تھوڑا سا میں، ہم نے ایک تقریب ہے جو کہ ہمارے لئے یہ کروں گا لکھیں گے. میں 9 کے ساتھ یہ تبدیل کرنا چاہتے ہیں، کہ 6 کے ساتھ تبدیل کریں. 

اب ہم ہمارے مراکز کی تمام بنایا ہے اور initialized ہے. ہم نے ہماری جڑ 7 کے برابر مقرر کرتے ہیں، ہے یا 7 قیمت پر مشتمل ہے، ہمارے 3 مشتمل نوڈ، ہمارے 6 مشتمل نوڈ، اور ہمارے نوڈ 9 پر مشتمل ہے. اس وقت ہم سب کرنا ہے تار سب کچھ ہے. وجہ ہے کہ میں تمام اشارہ initialized شہوت انگیز null ہے تاکہ میں ہے کہ اس بات کا یقین میں حادثے کی طرف سے میں کوئی غیر ابتدا شدہ اشارہ نہیں ہے. اور کے بعد بھی، اس وقت، میں صرف واقعی میں ایک دوسرے سے نوڈ مربوط ہے - ہیں کہ وہ اصل میں منسلک رہے ہیں - میں کے ذریعے جانے کے لئے اور نہیں ہے اس بات کا یقین کریں کہ ہے کہ تمام nulls مناسب مقامات میں ہیں. 

جڑ میں شروع ہو رہا ہے، میں جانتا ہوں کہ جڑ بائیں بچے 3. میں جانتا ہوں کہ جڑ صحیح بچے 9. اس کے بعد، صرف دوسرے بچے کے بارے میں فکر کرنے کی چھوڑ کر چلے گئے 3 صحیح بچے، جس میں 6 ہے ہے. اس وقت، یہ سب بہت اچھا لگ رہا ہے. ہم نے ان لائنوں میں سے کچھ کو خارج کر دیں گے. اب سب کچھ بہت اچھا لگ رہا ہے. چلو ہماری تفصیلات پر واپس جاؤ اور دیکھو جو ہم اگلے کرنا ہے. 

اس وقت ہم نے لکھ کے نام سے تقریب پر مشتمل ہے ' bool پر مشتمل ہے (int قیمت) کا ایک پروٹوٹائپ کے ساتھ. اور اس پر مشتمل تقریب سچ واپس کرنے کی جا رہی ہے  اگر ہمارے عالمی جڑ متغیر کی طرف سے درخت کی طرف اشارہ  تقریب اور دوسری صورت میں باطل میں منظور کی قیمت پر مشتمل ہے. چلو آگے بڑھو اور ایسا. یہ بالکل تلاش ہے کہ ہم نے پہلے صرف تھوڑا سا iPad پر ہاتھ سے کیا کی طرح بننے جا رہا ہے. چلو تھوڑا سا میں واپس زوم اور سکرال. ہم ہمارے مرکزی تقریب کے اوپر اس تقریب کے لئے جا رہے ہیں تاکہ ہم میں سے کسی قسم کا prototyping کرنے کی ضرورت نہیں ہے. تو، bool پر مشتمل (int قیمت). ہم وہاں جا رہے ہیں. ہمارے boilerplate اعلان ہے. یقین ہے کہ یہ کہ مرتب کریں گے بنانے کے لئے، مجھے آگے جانا ہے اور صرف یہ برابر قائم جھوٹے واپس جا رہا ہوں. اب یہ تقریب کچھ نہیں اور ہمیشہ اس رپورٹ گا قدر کہ ہم کے لئے تلاش کر رہے ہیں درخت میں نہیں ہے. 

اس وقت شاید یہ ایک اچھا خیال ہے - چونکہ ہم نے کوڈ کی ایک پوری چڑھانے لکھا ہے اور ہم اسے ابھی تک جانچ کرنے کی کوشش بھی نہیں - اس بات کا یقین کر لیں کہ ہے کہ یہ سب سے آگاہ کرنے کے لئے. چیزیں ہیں کہ ہم پر واجب ہے اس بات کا یقین کر لیں کہ یہ اصل میں مرتب گا کے ایک جوڑے کی ہیں. سب سے پہلے، دیکھو، اگر ہم کسی بھی لائبریریوں میں کسی بھی کام کرتا ہے کہ ہم ابھی تک شامل نہیں ہے کا استعمال کرتے ہوئے. کام کرتا ہے ہم نے اب تک استعمال کیا ہے malloc ہیں، اور پھر ہم بھی کیا گیا ہے اس قسم کا استعمال کرتے ہوئے - نامی اس غیر معیاری bool' 'کی قسم - جو معیاری bool ہیڈر فائل میں شامل کیا گیا ہے. ہم ضرور bool قسم کے لئے معیاری bool.h کو شامل کرنے کے لئے چاہتے ہیں، اور ہم بھی # معیاری لائبریریوں کے لئے معیاری lib.h شامل کرنا چاہتے ہیں malloc، اور مفت، اور اس کے سب شامل ہیں. تو، باہر زوم، ہم چھوڑ کر جا رہے ہیں. چلو، اور اس بات کا یقین کر لیں کہ یہ اصل میں تالیف کیا کرنے کی کوشش کریں. ہم دیکھتے ہیں کہ اس سے فرق پڑتا ہے، تو ہم صحیح راستے پر ہیں. 

کی اپ binary_tree.c دوبارہ کھول دو. اس سے آگاہ کریں. چلو، نیچے جاؤ اور اس بات کا یقین کر لیں کہ ہم ہمارے پر مشتمل ہے تقریب میں کچھ فون داخل - صرف اس بات کا یقین کر لیں کہ کہ وہ سب ٹھیک اور اچھی ہے. مثال کے طور پر، جب ہم اپنے درخت میں کچھ lookups نے پہلے ہم نے 6 اقدار، 10، اور 1 تلاش کرنے کی کوشش کی، اور ہم جانتے تھے کہ 6 درخت میں تھا، 10 درخت نہیں تھا، اور 1 درخت میں بھی نہیں تھا. کا ایک طریقہ کے طور پر ان لوگوں کو نمونہ کالوں کو جاننے کے لئے استعمال کریں یا نہیں ہمارے پر مشتمل ہے تقریب میں کام کر رہی ہے. کے لئے ایسا کرنے کے لئے، میں printf تقریب کو استعمال کرنے کے لئے جا رہا ہوں، اور ہم پر مشتمل ہے کال کا نتیجہ پرنٹ جا رہے ہیں. میں ایک تار میں ڈال دیا جا رہا ہوں پر مشتمل ہے "(٪ D) کیونکہ =  ہم قدر میں پلگ کرنے جا رہے ہیں کہ ہم نے تلاش کرنے کے لئے جا رہے ہیں، =٪ s کو کریں \ n "اور اس کا استعمال ہماری شکل سٹرنگ کے طور پر. لفظی سکرین پر باہر پرنٹ - ہم تو صرف دیکھ کر جا رہے ہیں - ایک تقریب کال کی طرح کیا لگتا ہے. یہ اصل میں تقریب کال نہیں ہے.  یہ صرف ایک سٹرنگ ایک تقریب کال کی طرح نظر کرنے کے لئے ڈیزائن کیا ہے. 

اب، ہم قیمتوں میں ہونا جا رہے ہیں. ہم 6 مشتمل ہے کرنے کی کوشش کی جا رہے ہیں، اور پھر جو ہم یہاں کیا کرنے جا رہے ہیں کہ تہرا آپریٹر کا استعمال ہے. 6 پر مشتمل ہے - - چلو ایسا ہے، تو اب میں 6 موجود ہے اور اگر 6 مشتمل ہے سچ ہے، سٹرنگ ہے کہ ہم کے٪ فارمیٹ کردار بھیجنے کے لئے جا رہے ہیں سٹرنگ "حقیقی" ہو جائے گا. چلو تھوڑا سا پر سکرال. دوسری صورت میں، ہم سٹرنگ "جھوٹے" اگر 6 جھوٹے واپسی پر مشتمل بھیجنا چاہتے ہیں. یہ تھوڑا مورھ نظر ہے، لیکن مجھے لگتا ہے میں کے طور پر اچھی طرح سے وضاحت کرنا ہو سکتا ہے تہرا آپریٹر کیا کیونکہ ہم تھوڑی دیر کے لئے یہ نہیں دیکھا ہے کی طرح لگتا ہے. یہ ایک اچھا، ہاتھ اگر ہمارے پر مشتمل ہے تقریب میں کام کر رہی ہے پر اعداد و شمار کا ایک طریقہ ہو گا. میں بائیں میں واپس سکرال جا رہا ہوں، اور میں اور اس لائن کو پیسٹ کرنے کی چند بار کی کاپی کرنے جا رہا ہوں. یہ ان اقدار کی کچھ کے ارد گرد کو تبدیل کر دیا گیا، تو یہ 1 جا ہے، اور یہ 10 کی جا رہی ہے. 

اس وقت ہم نے ایک اچھا پر مشتمل ہے تقریب ہے. ہم کچھ ٹیسٹ ہے، اور ہم دیکھتے ہیں اگر یہ سب کام کریں گے ہے. اس وقت ہم نے کچھ اور کوڈ لکھا ہے. باہر چھوڑ اور اس بات کا یقین کر لیں کہ ہے کہ سب کچھ اب بھی آگاہ وقت. باہر چھوڑ اور اب بائنری درخت پھر سے بنانے کی کوشش کریں. ٹھیک ہے، ایسا لگتا ہے جیسے ہم نے ایک غلطی ہے، اور ہم ہے اس کو واضح طور پر لائبریری تقریب printf اعلان. ایسا لگتا ہے جیسے ہم میں جانے کے لئے اور # standardio.h شامل کرنے کی ضرورت ہے. اور اس کے ساتھ سب کچھ مرتب کرنا چاہئے. ہم سب اچھے ہیں. اب بائنری درخت چلانے کی کوشش کرتے ہیں اور دیکھتے ہیں کیا ہوتا ہے. ہم یہاں ہیں، binary_tree /، اور ہم دیکھتے ہیں کہ، جیسا کہ ہم امید کی جاتی ہے - کیونکہ ہم لاگو نہیں کیا ہے ابھی تک پر مشتمل ہوتا ہے، بلکہ، ہم صرف جھوٹے بدلے میں ڈال دیا ہے - ہم دیکھتے ہیں کہ یہ صرف ان میں سے سب کے لئے غلط ہے واپس لوٹنے، تاکہ سب سے زیادہ حصہ کے لئے کافی اچھا کام کر رہا ہے. 

چلو، میں واپس جانے اور اصل عمل درآمد اس وقت پر مشتمل ہے. میں نیچے سکرال کرنے کے لئے، میں زوم جا رہا ہوں، اور - یاد رکھو، الگورتھم ہے کہ ہم استعمال کیا تھا کہ ہم جڑ نوڈ میں شروع اور پھر ہر نوڈ ہم اس کا سامنا، ہم ایک موازنہ کرتے ہیں، اور ہم اس کے مقابلے پر کی بنیاد پر یا تو بائیں بچے یا صحیح بچے کو منتقل. یہ بائنری تلاش کا کوڈ ہے جو ہم پہلے مدت میں لکھا اسی طرح دیکھنے کے لئے کی جا رہی ہے. جب ہم نے شروع ہو جائیں، ہم جانتے ہیں کہ ہم موجودہ نوڈ پر منعقد کرنا چاہتے ہیں کہ ہم دیکھ رہے ہیں، اور موجودہ نوڈ جڑ نوڈ پر initialized جا رہا ہے. اور اب، ہم نے درخت سے گزر رہا رکھنے کے لئے جا رہے ہیں، اور یہ کہ ہمارے روکنے کی حالت یاد رکھو -  ہم اصل میں جب ہاتھ کی طرف سے مثال کے طور پر کے ذریعے کام - جب ہم نے ایک لوڈ، اتارنا null نوڈ کا سامنا کرنا پڑا تھا، نہیں جب ہم شہوت انگیز null بچے کو دیکھا بلکہ جب ہم اصل درخت میں ایک نوڈ پر منتقل ہو گیا ملا اور یہ کہ ہم شہوت انگیز null نوڈ میں ہیں. ہم iterate جا تک رائج شہوت انگیز null برابر نہیں ہے. اور جو ہم کرنے جا رہے ہیں؟ ہم امتحان جا رہے ہیں اگر - (رائج قیمت> == قیمت) تو ہم جانتے ہیں کہ ہم اصل میں نوڈ کہ ہم کے لئے تلاش کر رہے ہیں تلاش کر لیا ہے. تو یہاں ہم سچ واپس آ سکتے ہیں. دوسری صورت میں، ہم دیکھتے ہیں یا نہیں قیمت کی قیمت سے کم ہے کرنا چاہتے ہیں. اگر موجودہ نوڈ کی قدر قیمت سے کم ہے ہم کے لئے تلاش کر رہے ہیں، ہم حق پر منتقل کرنے کے لئے جا رہے ہیں. لہذا، رائج = رائج -> right_child، اور دوسری صورت میں، ہم بائیں طرف منتقل کرنے کے لئے جا رہے ہیں. رائج = رائج -> left_child؛. بہت آسان ہے. 

تم شاید لوپ ہے جو بہت سے اس کی طرح لگ رہا ہے کو تسلیم بائنری پہلے مدت میں تلاش کرتے ہیں، تو ہم کو چھوڑ کر کم، وسط، اور اعلی سے نمٹنے کر رہے تھے. یہاں، ہم صرف ایک موجودہ قیمت کو دیکھنے کے لئے ہے، تو یہ اچھا اور آسان ہے. چلو اس بات کا یقین کر لیں کہ اس کوڈ کام کر رہا ہے. سب سے پہلے، اس بات کا یقین کر لیں کہ اس سے آگاہ ہے. یہ کرتا ہے ایسا لگتا ہے. کوشش کرتے ہیں یہ چل رہا ہے. اور یقینا، یہ سب کچھ ہے کہ ہم امید پرنٹ. یہ درخت میں 6 پائے، 10 تلاش نہیں ہے کیونکہ 10 درخت میں نہیں ہے، اور 1 تلاش نہیں ہے کیونکہ یا تو 1 بھی درخت میں نہیں ہے. ڈاؤن لوڈ، اتارنا چیزیں. 

ٹھیک ہے. چلو ہماری تفصیلات پر واپس جاؤ اور دیکھو اس کے بعد کیا ہے. اب، یہ ہمارے درخت کچھ نوڈس شامل کرنا چاہتا ہے. 5، 2، اور 8 کو شامل کرنے کے لئے، اور اس بات کا یقین کر لیں کہ کہ ہمارے کوڈ شامل کرنا چاہتا ہے اب بھی کام کرتا ہے کے طور پر امید کی جاتی ہے. چلو ایسا کریں. اس وقت، بلکہ کہ پریشان کاپی اور پیسٹ کر پھر سے ہم اصل میں ایک نوڈ بنانے کی تقریب لکھنے. اگر ہم بنیادی سکرال تمام طرح ہم دیکھتے ہیں کہ ہم یہ کر رہی بار بار ہر وقت آ گیا ہے کہ ہم ایک نوڈ بنانے کے لئے چاہتے ہیں بہت اسی طرح کے کوڈ. 

کی ایک تقریب ہے وہ ہمارے لئے ایک نوڈ اصل اور اس کو واپس تعمیر کریں گے لکھنے دو میں اسے build_node جا رہا ہوں. میں ایک خاص قدر کے ساتھ ایک نوڈ بنانے جا رہا ہوں. یہاں میں زوم. پہلی چیز جو میں کرنے جا رہا ہوں اصل میں ڈھیر پر نوڈ کے لئے جگہ بنانے کے ہے. تو، نوڈ * ن = malloc ((نوڈ) sizeof)؛ N -> قیمت = قیمت. اور یہاں تو، میں تو بس شعبوں کے تمام مناسب اقدار پر ابتدا کی جا رہی ہوں. اور ہم ہی آخر میں اپنے نوڈ کو واپس کریں گے. ٹھیک ہے. ایک بات نوٹ کہ اس تقریب یہیں ہے میموری ڈھیر مختص کر دیا گیا ہے ایک پوائنٹر واپس جا رہے ہیں. کیا اس کے بارے میں اچھی بات ہے یہ ہے کہ یہ نوڈ اب - ہم اس ڈھیر پر کیونکہ اگر ہم اس کے اسٹیک اعلان کیا اعلان ہے ہم اسے اس طرح اس جشن میں کرنے کے قابل نہیں ہو گا. وہ میموری گنجائش سے باہر جائیں گے اور باطل ہو گا اگر ہم اس کے بعد تک رسائی حاصل کرنے کی کوشش کی جائے گی. چونکہ ہم نے ڈھیر مختص میموری کا اعلان کر رہے ہیں، ہم اسے بعد میں آزاد کا خیال رکھنا پڑے جا رہے ہیں ہمارے پروگرام کے لئے کسی بھی میموری لیک نہیں. ہم باقی سب کے لئے کوڈ میں اس پر punting وقت سادگی کے لئے لیکن اگر تم نے کبھی ایک تقریب ہے کہ اس طرح لگتا ہے لکھنے جہاں آپ کو مل گیا ہے - کچھ یہ malloc یا ان کے اندر realloc کہتے ہیں - آپ کو اس بات کا یقین کر لیں کہ آپ کسی قسم کا تبصرہ ڈال جو یہ کہتا ہے بنانے کے لئے چاہتے ہیں، ہے، آپ جانتے ہیں، ایوان میں قدر کے ساتھ initialized ڈھیر مختص نوڈ واپس. اور پھر آپ کو اس بات کا یقین کر لیں کہ آپ نوٹ یہ کہتا ہے کہ کسی قسم میں ڈال دیا بنانا چاہتے ہیں فون کرنے والے سے واپس میموری آزاد کرنا ہوگا. اس طرح، اگر کبھی کسی جاتا ہے اور اس تقریب کا استعمال کرتا ہے، وہ جانتے ہیں کہ جو کچھ بھی وہ اس تقریب سے واپس حاصل کچھ نقطہ پر آزاد کرنے کی ضرورت ہوگی. 

یہ سمجھتے ہوئے کہ سب ٹھیک ہے اور اچھا یہاں ہے، ہم اپنے کوڈ میں نیچے جاؤ اور ان لائنوں کی سب یہیں کی جگہ کر سکتے ہیں ہماری تعمیر نوڈ کی تقریب میں کالوں کے ساتھ. چلو کہ واقعی تیزی سے کرنا چاہے. ایک حصہ ہے کہ ہم جا کے عوض میں نہیں کر رہے ہیں اس حصے کو نیچے یہاں ہے نیچے جہاں ہم واقعی نوڈس تار ایک دوسرے کی طرف اشارہ اس لیے کہ ہم اپنے تقریب میں نہیں کر سکتا. لیکن، جڑ = build_node (7)؛ نوڈ تین * = build_node (3)؛ نوڈ چھ * = build_node (6)؛ نوڈ نو * = build_node (9)؛ اور اب، ہم بھی نوڈس شامل کرنے کے لئے کرنا چاہتا تھا - نوڈ پانچ * = build_node (5)؛ نوڈ آٹھ * = build_node (8)؛ اور دوسری نوڈ تھا؟ چلو یہاں دیکھ. ہم نے بھی 2 میں شامل کرنے کے لئے کرنا چاہتا تھا - نوڈ دو * = build_node (2). ٹھیک ہے. اس وقت، ہم جانتے ہیں کہ ہم 7، 3، 9، اور 6 ہے تمام مناسب طریقے سے منسلک، لیکن جو 5، 8، اور 2؟ ، مناسب ترتیب میں سب کچھ رکھنے کے ہم جانتے ہیں کہ تین صحیح بچے 6. تو، اگر ہم 5 شامل کرنے کے لئے جا رہے ہیں، 5 بھی درخت کی دائیں جانب ہے جن میں سے 3 جڑ ہے میں ہے، تو 5 6 کے بائیں بچے کے طور پر تعلق رکھتا ہے. ہم کہہ رہے ہو، چھ کی طرف سے ایسا کر سکتے ہیں -> left_child پانچ =؛ اور پھر 8 9 کے بائیں بچے کے طور پر ہے، تو نو - آٹھ> left_child =؛ اور پھر 2 3 بائیں بچے، تو ہم ایسا یہاں کر سکتے ہیں - تجھ - دو> left_child =. اگر آپ اس کے ساتھ بہت نہیں کیا کی پیروی، میں تجویز ہے کہ آپ اسے باہر اپنے آپ کو اپنی طرف متوجہ کریں. 

ٹھیک ہے. چلو، اس کو بچانے کے. چلو باہر چلتے ہیں اور اس بات کا یقین کر لیں کہ اس سے آگاہ کریں، اور پھر ہم ہمارے پر مشتمل ہے کالوں میں شامل کر سکتے ہیں. کی طرح سب کچھ اب بھی آگاہ لگتا ہے. چلو میں جاؤ اور کچھ فون پر مشتمل ہے میں شامل ہیں. ایک بار پھر، میں کاپی اور پیسٹ تھوڑا سا میں کیا کرنے جا رہا ہوں. چلو اب 5، 8 اور 2 کے لئے تلاش کریں. ٹھیک ہے. چلو اس بات کا یقین کر لیں کہ ہے کہ یہ سب اچھا اب بھی لگتا ہے. بہت اچھا ہے! محفوظ کریں اور چھوڑ. اب بنانے کی تیاری، اور اب ہم چلانے کے. نتائج سے، ایسا لگتا ہے کہ سب کچھ اچھا اور اچھی طرح کام کر رہا ہے. بہت اچھا ہے! تو اب ہم نے ہمارے پر مشتمل ہے کو لکھا تقریب ہے. چلو منتقل اور کس طرح درخت میں نوڈس داخل کرنے پر کام شروع کے بعد، جیسا کہ ہم یہ کام کر رہے ہو، چیزیں بہت خوبصورت نہیں ہیں. 

اگر ہم تفصیلات پر واپس جانے، یہ ہم سے پوچھتے ہیں کے نام سے داخل تقریب لکھنے - پھر bool واپس لوٹنے یا نہیں ہم درخت میں نوڈ اصل میں داخل کر سکتا ہے - اور پھر درخت میں داخل کرنے کی قیمت کے طور پر مخصوص ہے ہمارے داخل تقریب پر صرف دلیل ہے. ہم سچے واپس اگر ہم درخت میں نوڈ پر مشتمل قیمت واقعی داخل کر سکتا ہے گا، جس کا مطلب یہ ہے کہ ہم، ایک، کافی میموری تھا، اور دو تو، کہ نوڈ کے بعد درخت میں نے پہلے ہی نہیں تھا موجود - یاد رکھو، ہم جا درخت میں نقل اقدار نہیں ہیں، صرف چیزوں کو آسان بنانے کے لئے. ٹھیک ہے. کوڈ پر واپس جائیں. اسے کھولو. تھوڑا سا میں زوم، پھر ذیل میں سکرال. چلو ٹھیک ہے پر مشتمل ہوتا ہے مندرجہ بالا داخل تقریب ڈال. ایک بار پھر، یہ bool داخل کہا جاتا (int قیمت) ہو رہا ہے. ، اس سے تھوڑا زیادہ جگہ دے دو، اور ڈیفالٹ کے طور پر تو، بہت آخر میں جھوٹے بدلے میں ڈال دو. اب نیچے سب سے نیچے دیئے گئے، آگے اور اس کے بجائے دستی طور پر مراکز کی تعمیر کے اہم، خود اور ان کی وائرنگ کا ایک دوسرے سے جیسا کہ ہم کر رہے ہیں کی طرف اشارہ ہم ایسا کرنے کے لئے ہماری داخل تقریب پر انحصار کریں گے. ہم ہماری داخل تقریب پر انحصار نہیں شروع سے پورے درخت کو ابھی تک تعمیر کیا جائے گا، بلکہ ہم ان لائنوں کی چھٹکارا گے - we'll ان لائنوں باہر تبصرہ - 5 نوڈس، 8، اور 2 کی تعمیر. اور اس کے بجائے، ہم ہمارے داخل تقریب کالز داخل کریں گے اس بات کا یقین کر لیں کہ کہ اصل میں کام کرتا ہے بنانے کے لئے. یہاں ہم چلے. 

اب ہم باہر تبصرہ ان لائنوں کو ہے. ہم صرف اس وقت ہمارے درخت میں 7، 3، 9، اور 6 ہے. اس بات کا یقین کر لیں کہ یہ سب کام کر رہی ہے بنانے کے کرنے کے لئے، ہم باہر زوم کر سکتے ہیں، ہماری بائنری درخت، اسے چلاتے ہیں، اور ہم دیکھتے ہیں کہ پر مشتمل ہے اب ہمیں بتا کہ ہم مکمل طور پر درست ہو کر سکتے ہیں - 5، 8، اور 2 درخت میں نہیں ہیں. کوڈ میں واپس جاؤ اور ہم کس طرح داخل کرنے جا رہے ہیں؟ یاد ہے ہم نے کیا کیا جب ہم واقعی 5 داخل کیا گیا تھا، 8 اور 2 پہلے ہے. ہم اس Plinko کھیل کھےلا جہاں ہم جڑ سے شروع، نیچے ایک کے بعد ایک چلا گیا درخت ایک جب تک ہم مناسب فرق پایا جاتا ہے، اور پھر ہم مناسب موقع پر نوڈ میں وائرڈ. ہم ایک ہی بات کرنے جا رہے ہیں. یہ میں کہ ہم کرتے تھے کوڈ لکھنے کی طرح بنیادی طور پر ہے تقریب پر مشتمل ہے جگہ تلاش کرنے کے لئے نوڈ کہاں ہونا چاہئے، اور اس وقت ہم صرف نوڈ وہیں ڈالنے جا رہے ہیں. چلو کہ کر شروع ہو جاتے ہیں. 

تو ہم نے ایک نوڈ * رائج جڑ = ہے، ہم صرف اس کی پیروی کوڈ پر مشتمل ہے کے لئے جا رہے ہیں جب تک ہم محسوس کرتے ہیں کہ یہ ہمارے لئے بہت کام نہیں کرتا. ہم درخت کے ذریعے جانے کے لئے جا رہی جبکہ موجودہ عنصر خالی نہیں ہے، اور اگر ہم دیکھتے ہیں کہ رائج قیمت قدر کہ ہم داخل کرنے کی کوشش کر رہے ہیں کے برابر ہے - ٹھیک ہے، یہ مقدمات میں سے ایک ہے جس میں ہم اصل نوڈ نہیں ڈال سکتا ہے ہے درخت میں کیونکہ اس کا مطلب ہے کہ ہم ڈوپلیکیٹ قدر ہے. یہاں ہم واقعی جھوٹے واپس جا رہے ہیں. اب رائج قیمت اگر کسی قیمت سے کم ہے، اب ہم جانتے ہیں کہ ہم حق میں منتقل  کیونکہ قدر رائج درخت کی دائیں نصف میں تعلق رکھتا ہے. دوسری صورت میں، ہم بائیں طرف منتقل کرنے کے لئے جا رہے ہیں. یہ بنیادی طور پر ہمارے پر مشتمل ہے ٹھیک وہاں کام ہے. 

اس وقت، ایک بار ہم اس دیر لوپ مکمل کرلی ہے، ہمارے رائج پوائنٹر شہوت انگیز null کی طرف اشارہ کرتے ہوئے جا رہا ہے اگر تقریب پہلے ہی واپس نہیں آیا ہے. ہم اس وجہ سے موقع پر رائج ہونے رہے ہیں جہاں ہم نئے نوڈ کو شامل کرنے کے لئے کرنا چاہتے ہیں. کیا کچھ کرنا باقی ہے. میں نئے نوڈ کی تعمیر ہے، جس پر ہم بہت آسانی سے کر سکتے ہیں. ہم اپنے سپر ہاتھ کی تعمیر نوڈ تقریب کا استعمال کر سکتے ہیں، کچھ اور کہ ہم نے پہلے نہیں کیا - ہم صرف طرح حاصل کی جاچکی کے لئے لے گئے لیکن اب ہم صرف اس بات کو یقینی بنانے کے لئے کیا کرنا ہوگا - ہم اس بات کا یقین کر لیں کہ نئے نوڈ کی طرف سے واپس قیمت دراصل آزمائش کریں گے نہیں، شہوت انگیز null، کیونکہ، ہم کہ میموری تک رسائی حاصل اگر وہ شہوت انگیز null ہے شروع کرنے کے لئے نہیں کرنا چاہتا. ہم اس بات کا یقین ہے کہ نئے نوڈ شہوت انگیز null برابر نہیں ہے ٹیسٹ کر سکتے ہیں. یا اس کے بجائے، ہم اگر یہ واقعی اتارنا null ہے دیکھ سکتے ہیں، اور اگر شہوت انگیز null ہے، تو ہم جھوٹے صرف جلد واپس آ سکتے ہیں. 

اس وقت ہم نے اس کے درخت میں مناسب جگہ میں نئے نوڈ تار ہے. اگر ہم اہم میں واپس دیکھو اور جہاں ہم واقعی سے پہلے قیمتوں میں وائرنگ تھے، ہم دیکھتے ہیں کہ جس طرح سے ہم یہ کر رہے تھے جب ہم درخت میں 3 کرنا چاہتے گیا اور ہم جڑ کے بائیں بچے کو حاصل کیا ہے. جب ہم درخت میں 9 ڈالا، ہم جڑ کے دائیں بچے تک رسائی حاصل کی تھی. ہم والدین کو ایک پوائنٹر کے لئے درخت میں ایک نئی قیمت کے لئے تھا. واپس طومار کر ڈالنے کے، کہ بہت کام کرنے کی نہیں ہے یہاں کیونکہ ہم نے والدین پوائنٹر نہیں ہے. ہم کیا کرنے کے قابل کرنا چاہتے ہیں اس وقت ہے، والدین قیمت چیک کریں اور دیکھیں - اچھی طرح بھگوان،، اگر والدین قیمت موجودہ قیمت سے کم ہے، تو والدین کے حق کے بچے کو نئی نوڈ ہونا چاہئے؛ دوسری صورت میں، والدین کے بائیں بچہ نئے نوڈ ہونا چاہئے. لیکن، ہم اس کے والدین پوائنٹر نہیں بہت ابھی تک. 

ہے تاکہ اسے حاصل کرنے کے لئے، ہم اصل میں اس کو ٹریک کرنے کی جا رہے ہیں جیسا کہ ہم نے درخت کے ذریعے جانا اور ہمارے اوپر لوپ میں مناسب جگہ کی تلاش کریں. ہم نے طومار کر کی طرف سے بیک اپ ہمارے داخل تقریب کے سب سے اوپر کر سکتے ہیں اور با خبر رکھنے کے ایک اور پوائنٹر متغیر والدین سے ملاقات کی. ہم اسے برابر قائم کرنے کے لئے ابتدائی طور پر لوڈ، اتارنا null رہے ہیں، اور پھر ہر بار ہم نے درخت کے ذریعے جانا، ہم والدین پوائنٹر موجودہ پوائنٹر سے ملنے کے لئے قائم کرنے کے لئے جا رہے ہیں. رائج برابر والدین مقرر کریں. اس طرح، ہر وقت ہے کہ ہم کے ذریعے جانا، ہم اس بات کا یقین کرنے کے لئے کہ کے طور پر موجودہ پوائنٹر ہو جاتا ہے incremented جا رہے ہیں والدین پوائنٹر مندرجہ ذیل ہے - صرف ایک سطح درخت میں موجودہ پوائنٹر سے زیادہ ہے. کہ تمام بہت اچھا لگ رہا ہے. 

مجھے لگتا ہے کہ ایک بات یہ ہے کہ ہم کو ایڈجسٹ چاہیں گے اس نوڈ واپس لوٹنے شہوت انگیز null کی تعمیر. میں نوڈ اصل کامیابی شہوت انگیز null واپس کی تعمیر کے لئے حاصل کرنے کے لئے، ہم اس کوڈ کو تبدیل کرنے کی ضرورت ہوگی، یہاں کیونکہ ہم نے تجربہ کیا اس بات کا یقین کر لیں کہ malloc ایک درست پوائنٹر واپس کرنے کے لئے کبھی نہیں. لہذا، اگر (ن = نل)، تو - اگر malloc ایک درست پوائنٹر واپس آئے، تو ہم اس کی ابتدا کریں گے؛ دوسری صورت میں، ہم صرف اور یہ کہ آخر ہمارے لئے، شہوت انگیز null واپس لوٹنے واپس کر دیں گے. اب یہ سب بہت اچھا لگ رہا ہے. چلو، اس بات کا یقین کر لیں کہ اس اصل سے آگاہ کرنے کے. بائنری درخت، اور اوہ، ہمیں کچھ ہو رہا ہے یہاں سامان ہے. 

ہم نے تقریب کی ایک انترنہیت اعلان نوڈ کی تعمیر ہے. پھر ان compilers کے ساتھ، ہم نے سب سے اوپر شروع کرنے جا رہے ہیں. کیا اس کا مطلب یہ ضروری ہے یہ ہے کہ میں نوڈ کی تعمیر بلا رہا ہوں اس سے پہلے کہ میں اصل میں یہ اعلان کیا ہے رہا ہوں. چلو کوڈ واپس واقعی جلدی جاؤ. ذیل میں سکرال کریں، اور اس بات کا یقین کے لئے کافی ہے، میرے داخل تقریب کا اعلان کیا ہے تعمیر نوڈ تقریب اوپر لیکن میں داخل کے اندر نوڈ کی تعمیر کے لئے استعمال کرنے کی کوشش کر رہا ہوں. میں کاپی اور میں جانے کے لئے جا رہا ہوں - اور پھر سب سے اوپر تعمیر نوڈ تقریب طرح یہاں چسپاں کر دیں. اس طرح کہ امید ہے کہ یہ کام کرے گا. آو دے جانے دوسرے. اب یہ سب سے آگاہ کریں. سب اچھا ہے. 

لیکن اس وقت، ہم اپنے داخل تقریب اصل میں نہیں ہے کہا جاتا ہے. ہم صرف یہ جانتے ہیں کہ اس سے آگاہ کریں، تو چلو میں جاؤ اور کچھ فون کے اندر ڈال چلو ہمارے مرکزی تقریب میں یہ کرتے ہیں. یہاں، ہم باہر 5، 8، اور 2 تبصرہ، اور پھر ہم انہیں تار نہیں کیا یہاں نیچے. چلو کچھ کالز کو داخل کرنے اور بھی چیزیں ایک ہی قسم ہے کہ ہم استعمال کیا استعمال جب ہم ان printf کالز نے اس بات کو یقینی بنانے کے لئے کہ سب کچھ کرنے کے لئے مناسب طریقے سے کیا داخل کرنے کے لئے. میں کاپی اور پیسٹ کرنے کی جا رہی ہوں، اور بجائے اس کے کہ پر مشتمل ہے ہم داخل کرنے کے لئے جا رہے ہیں. اور 6، 10، اور 1 کے بجائے، ہم نے 5، 8، اور 2 کو استعمال کرنے کے لئے جا رہے ہیں. یہ درخت میں 5، 8، اور 2 امید داخل چاہئے. آرکائیو. سب اچھا ہے. اب ہم ہمارے پروگرام اصل میں چلا کریں گے. 

سب کچھ جھوٹ لوٹ آئے. تو، 5، 8، اور 2 جاتے ہیں، نہیں کیا ہے اور ایسا لگتا ہے کہ پر مشتمل ہے انہیں نہیں ملا یا تو. یہ کیا ہو رہا ہے؟ چلو باہر زوم. پہلا مسئلہ تھا کہ داخل جھوٹے واپس لگ رہا تھا، اور یہ یہ ہے کیونکہ ہم نے ہماری واپسی جھوٹی کال میں چھوڑ دیا کی طرح لگتا ہے اور ہم سچ اصل میں کبھی نہیں واپس. ہم اس سیٹ اپ کر سکتے ہیں. دوسرا مسئلہ یہ ہے، اب یہاں تک کہ اگر ہم کرتے ہیں - اس کو بچانے کے، یہ چھوڑ دوبارہ چلانے، اس، تو مرتب اسے چلانے - ہم دیکھتے ہیں کہ کچھ یہاں ہوا ہے. 5، 8، اور 2 درخت میں اب بھی پائے گئے کبھی نہیں. تو، کیا ہو رہا ہے؟ 

چلو کوڈ میں اس پر ایک نظر لے. چلو دیکھتے ہیں اگر ہم یہ اعداد و شمار کر سکتے ہیں. ہم والدین، شہوت انگیز null نہیں کیا جا رہا ہے کے ساتھ شروع کرتے ہیں. ہم نے موجودہ جڑ پوائنٹر کے برابر پوائنٹر قائم، اور ہم ہماری طرح درخت کے ذریعے نیچے کام پر جا رہے ہیں. اگر موجودہ نوڈ خالی نہیں ہے، تو ہم جانتے ہیں کہ ہم نیچے تھوڑا سا کو منتقل کر سکتے ہیں. ہم اپنے والدین پوائنٹر موجودہ پوائنٹر کے برابر ہو، قیمت کی جانچ پڑتال - اگر اقدار وہی ہیں ہم جھوٹے واپس. اگر اقدار کم ہیں ہم حق میں منتقل کردیا گیا ہے؛ دوسری صورت میں، ہم بائیں طرف منتقل ہو گیا ہے. اس وقت ہم نے ایک نوڈ کی تعمیر. میں تھوڑا سا میں زوم کریں گے. اور یہاں ہم اقدار تار اسی کوشش کرنے کے لئے جا رہے ہیں. یہ کیا ہو رہا ہے؟ چلو دیکھتے ہیں اگر ممکنہ Valgrind ہمیں ایک اشارہ دے سکتے ہیں. 

میں Valgrind استعمال کرنے کے لئے صرف اس لئے کہ واقعی Valgrind تیزی سے چلتا ہے اور آپ کو بتاتا ہے اگر کوئی میموری غلطیاں ہیں. ہم نے کوڈ پر Valgrind جب چلاتے ہیں، دائیں here--Valgrind./binary_tree--and ہٹ میں داخل کریں جیسا کہ آپ دیکھ سکتے ہیں. تم نے دیکھا ہے کہ ہم کسی بھی میموری نقص نہیں تھا، تو ایسا لگتا ہے کہ سب کچھ ٹھیک ہے اب تک. ہم نے کچھ میموری لیک، جو ہم جانتے ہیں کہ ہے، کیونکہ ہم نہیں ہیں ہمارے مراکز کی کسی آزاد ہو رہا ہے. چلو GDB چل رہا ہے جو اصل میں ہو رہا ہے دیکھ کر کرنے کی کوشش کریں. ہم gdb کرنا / binary_tree گے. یہ ٹھیک ہٹا دیا ہے. میں داخل پر ایک بریک پوائنٹ قائم ہوں. چلانے. ایسا لگتا ہے جیسے ہم داخل اصل میں کبھی نہیں کہا جاتا. ایسا لگتا ہے کہ مسئلہ صرف یہ ہے کہ جب میں نیچے اہم میں تبدیل تھا - کے تمام پر مشتمل ہے سے ان printf کالز - میں یہ اصل میں کبھی نہیں تبدیل داخل فون کرنے کی. اب ہم اسے ایک بار آزمائیں. تالیف ہے. سب اچھا لگ رہا ہے. اب کوشش کرتے ہیں چلانا دیکھو، کیا ہوتا ہے. ٹھیک ہے! سب کچھ خوبصورت وہاں اچھا لگ رہا ہے. 

فائنل کے بارے میں سوچنے کی بات یہ ہے کہ، یہ شامل کرنے کے لئے کوئی کنارے مقدمات ہیں؟ اور یہ پتہ چلا ہے کہ، اچھی طرح، ایک کنارے کیس ہے جو ہمیشہ ہے اور کے بارے میں سوچنے کے لئے دلچسپ ہے، اگر آپ کا درخت خالی ہے کیا ہوتا ہے اور آپ اس داخل کی تقریب کہتے ہیں؟ یہ کام کرے گا؟ چلو، کوشش دے. - binary_tree C - جس طرح سے ہم اس کی جانچ کے لئے جا رہے ہیں، ہم کر رہے ہیں ہمارے مرکزی تقریب نیچے جا رہا، بلکہ اس طرح ان مراکز کی وائرنگ اپ سے ہم صرف پوری بات پر تبصرہ کرنے جا رہے ہیں، اور نوڈس خود اپ کی وائرنگ کی بجائے، ہم صرف اصل میں آگے بڑھو اور اس کی سب کو خارج کر سکتے ہیں. ہم داخل کی کال کے سب کچھ کرنے کے لئے جا رہے ہیں. تو، کیا - کے بجائے 5، 8، اور 2، ہم 7 داخل، 3، اور 9 جا رہے ہیں. اور پھر ہم 6 کے طور پر داخل بھی چاہیں گے. محفوظ کریں. بند کرو. بائنری درخت کرو. یہ سب سے آگاہ کریں. ہم اسے صرف چلا سکتے ہیں اور دیکھتے ہیں کیا ہوتا ہے، لیکن یہ بھی بہت ضروری ہونے جا رہا ہے یقین ہے کہ ہم کسی بھی میموری کی غلطیوں کو نہیں ہے، چونکہ یہ ہمارے کنارے مقدمات میں کہا گیا ہے کہ ہم کے بارے میں جانتے ہیں میں سے ایک ہے. 

چلو اس بات کا یقین کر لیں کہ کہ یہ Valgrind کے تحت کام کرتا ہے، جس سے ہم صرف Valgrind binary_tree / چلانے کی طرف سے کر دونگا. ایسا لگتا ہے جیسا کہ ہم نے واقعی ایک سیاق و سباق سے ایک غلطی ہے - ہم اس انقطاع کی غلطی ہے. کیا ہوا ہے؟ Valgrind اصل میں ہمیں بتاتی ہے کہ وہ کہاں ہے. تھوڑا سا زوم. ایسا لگتا ہے جیسے یہ ہمارے داخل تقریب میں کیا ہو رہا ہے، جہاں ہم داخل میں 4 سائز کے ایک جعلی پڑھا ہے، اوپر 60. چلو، واپس جاؤ اور دیکھو یہاں کیا ہو رہا ہے. باہر زوم واقعی جلد. میں اس بات کا یقین کر لیں کہ یہ سکرین کے کنارے نہیں جاتے تاکہ ہم سب کچھ دیکھ سکتے ہیں بنانے کے لئے چاہتے ہیں. تھوڑا سا میں ھیںچو. ٹھیک ہے. ذیل میں سکرال اور مسئلہ یہیں پر ہے. اگر ہم حاصل کرتے ہیں تو کیا ہوتا ہے اور ہماری موجودہ نوڈ پہلے ہی شہوت انگیز null، ہمارے والدین نوڈ خالی ہے، اگر ایسا ہے تو ہم بہت اوپر ہے، یہیں پر دیکھ - اگر یہ دیر لوپ اصل میں کبھی نہیں executes کیونکہ ہماری موجودہ قدر خالی ہے - ہماری جڑ خالی ہے تو رائج شہوت انگیز null ہے - تو ہمارے والدین رائج یا ایک درست قیمت کبھی نہیں قائم ہو جاتا ہے، تو، والدین، شہوت انگیز null بھی ہو جائے گا. ہم اس کے لئے چیک کرنے کے لیے یاد کرنے کی ضرورت ہے وقت تک ہم یہاں ملتا ہے، اور ہم والدین قدر تک رسائی حاصل کرنے شروع. تو کیا ہوتا ہے؟ ٹھیک ہے، اگر والدین شہوت انگیز null ہے - اگر (والدین == نل) - تو ہم جانتے ہیں کہ درخت میں کچھ بھی نہیں ہونا چاہئے. ہم نے اسے جڑ میں داخل کرنے کی کوشش کر رہا ہے. ہم صرف نئے نوڈ کے برابر جڑ قائم کرنے کی طرف سے کر سکتے ہیں. اس کے بعد، ہم اس مقام پر ان دوسری چیزوں کے ذریعے جانے کے لئے اصل میں نہیں چاہتا. اس کے بجائے، ٹھیک ہے یہاں، ہم یا تو ایک کے کسی اور اگر کسی کے کر سکتے ہیں، یا ہم سب کچھ جمع اور ایک یہاں کر سکتے ہیں، لیکن یہاں ہم اور صرف اور اسے اس طرح کرنا استعمال کریں گے. اب، ہم ٹیسٹ اس بات کا یقین کریں کہ ہمارے والدین خالی نہیں ہے کر رہے ہیں اس وقت سے پہلے اصل میں اس کے شعبوں تک رسائی حاصل کرنے کی کوشش کر رہے ہیں. اس سے ہماری مدد انقطاع غلطی سے بچنے کے. تو ہم نے چھوڑ دیا، باہر زوم، مرتب، چلائیں. 

کوئی غلطیاں نہیں، لیکن ہم اب بھی میموری لیک کا ایک گروپ ہے کیونکہ ہم ہمارے مراکز کی کسی بھی آزاد نہیں کیا. لیکن، اگر ہم یہاں جانا اور ہم اپنے پرنٹ آؤٹ پر نظر، ہم دیکھتے ہیں کہ ٹھیک ہے، ہمارے اضافہ طرح لگتا ہے سچ آرہے ہیں، جو اچھا ہے. اضافہ سب سچ ہے، اور پھر مناسب پر مشتمل ہے کالز بھی سچ ہے. 

اچھا کام ہے! ایسا لگتا ہے جیسے ہم نے کامیابی کے ساتھ داخل لکھا ہے. وہ سب ہم اس ہفتے کے مسائل سیٹ تفصیلات کے لئے ہے. ایک تفریح ​​کے بارے میں سوچنے کے لئے چیلنج ہے کہ آپ کس طرح میں اصل گے اور اس پیڑ کے مراکز کی تمام. ہم مختلف طریقوں کی ایک بڑی تعداد کر سکتے ہیں، لیکن مجھے چھوڑ دو تم استفادہ کرنے کے اس تجربے کو کریں گے، اور ایک مذاق کے چیلنج کے طور پر، اور اس بات کا یقین کر لیں کہ آپ اس بات کا یقین کر سکتے ہیں کرنے کی کوشش کہ اس Valgrind رپورٹ غلطیوں اور کوئی لیک واپس. 

گڈ لک، اس ہفتے Huffman کوڈنگ مسئلہ سیٹ پر اور ہم اگلے ہفتے آپ کو نظر آئے گا! [CS50.TV]