[Powered by Google Translate] [المادة 7: أكثر مريحة] [روب بودين] [جامعة هارفارد] [هذا CS50] [CS50.TV] حسنا. مثل ذلك قلت في البريد الإلكتروني الخاص بي، هذا سيكون جزء ثنائي شجرة كثيفة. ولكن هناك العديد من الأسئلة التي لا. لذلك نحن ذاهبون لمحاولة استخلاص كل سؤال والخوض في التفاصيل المؤلمة من الطرق أفضل للقيام بهذه الأمور كافة. الحق في ذلك في البداية، نذهب من خلال رسومات عينة من الأشجار الثنائية والاشياء. حتى هنا، "تذكر أن لديه شجرة ثنائية مشابهة لتلك العقد من قائمة مرتبطة، بدلا من واحدة إلا مؤشر هناك اثنين: واحد ل 'الطفل' اليسار واحد لل"الطفل" الحق ". حتى شجرة ثنائية هو تماما مثل قائمة مرتبط، ما عدا البنية يجري لاثنين من المؤشرات. هناك أشجار trinary، والتي تسير على ثلاثة مؤشرات، هناك N-ARY الأشجار، والتي يكون مجرد مؤشر عام ثم أن لديك لmalloc أن تكون كبيرة بما يكفي ليكون يكفي مؤشرات إلى جميع الأطفال ممكن. حتى شجرة ثنائية يحدث لمجرد أن يكون لها عدد ثابت من اثنين. إذا كنت تريد، يمكنك ان تعطي قائمة مرتبطة مثل شجرة أحادي، لكنني لا أعتقد أن أحدا يسميها ذلك. "رسم مخطط مربعات و-سهام عقدة شجرة ثنائية تحتوي على عدد نيت المفضل، 7، حيث كل طفل مؤشر فارغة. " باد حتى واسطة. 

انها سوف تكون واضحة جدا. ونحن في طريقنا لمجرد الحصول على عقدة، وأنا رسم بأنها مربع. وسوف يوجه القيم هنا. لذلك سوف تذهب في القيمة هنا، ثم إلى هنا سيكون لدينا مؤشر اليسار على اليسار واليمين مؤشر على اليمين. وإلى حد كبير حتى أن نسميها اتفاقية اليسار واليمين، وأسماء المؤشر. كل من هذه ستكون فارغة. وأن يكون مجرد فارغة، والتي من شأنها أن يكون مجرد فارغة. حسنا. ذلك لدعم هنا. "مع قائمة مرتبطة، كان لدينا فقط لتخزين مؤشر إلى العقدة الأولى في القائمة من أجل أن نتذكر اللائحة بأكملها مرتبطة، أو اللائحة بأكملها. وبالمثل، مع الأشجار، لدينا فقط لتخزين مؤشر لعقدة واحدة من أجل أن نتذكر الشجرة كلها. هذه العقدة هي كالي 'جذور' من شجرة. بناء على الرسم البياني الخاص بك من قبل أو رسم جديد مثل أن يكون لديك تصوير مربعات و-سهام شجرة ثنائية مع قيمة 7، 3 ثم في اليسار، 9 وعلى اليمين، ومن ثم 6 على يمين 3. " دعونا نرى ما اذا كان يمكنني تذكر كل ذلك في رأسي. ولذلك فإن هذا سيكون لدينا هنا الجذر. سيكون لدينا بعض مؤشر مكان ما، وهو الأمر الذي سنقوم استدعاء الجذر، وانها تشير الى هذا الرجل. الآن لجعل عقدة جديدة، ماذا لدينا، 3 على اليسار؟ حتى عقدة جديدة مع 3، ويشير في البداية فارغة. أنا فقط وضعت N. الآن نحن نريد أن نجعل التي تذهب إلى يسار 7. حتى نغير هذا المؤشر للإشارة إلى هذا الرجل الآن. ونحن نفعل نفس الشيء. نريد أكثر من 9 هنا في البداية يقول عادل الذي فارغة. ونحن في طريقنا لتغيير هذا المؤشر، وأشر إلى 9، ونحن الآن نريد أن نضع 6 إلى حق 3. لذلك سيكون ل- تقديم 6. وسوف نشير أن الرجل هناك. حسنا. ذلك أن كل ما يطلب منا القيام به. 

الآن دعونا نذهب أكثر من بعض المصطلحات. تحدثنا بالفعل عن كيفية جذر الشجرة هي العقدة معظم العليا في الشجرة. واحد يحتوي على 7. ويطلق على العقد في الجزء السفلي من الشجرة الأوراق. أي عقدة التي لديها فقط فارغة وأبنائها هو ورقة. لذلك فمن الممكن، إذا شجرة ثنائية لدينا هو مجرد عقدة واحدة، أن الشجرة هي ورقة، وهذا كل شيء. "إن 'ارتفاع' من شجرة هو عدد القفزات لديك لجعل للحصول على من أعلى إلى ورقة ". سوف نصل إلى، في الثانية، والفرق بين أشجار ثنائي متوازنة وغير متوازنة، لكن في الوقت الراهن، والارتفاع الكلي لهذه الشجرة وأود أن أقول هو 3، ولكن إذا كنت تعول عدد من القفزات عليك ان تجعل من اجل الحصول على ل9، ثم انها حقا فقط على ارتفاع 2. الآن هذا هو شجرة ثنائية غير متوازنة، ولكن سوف نتحدث عن التوازن عندما يحصل أن تكون ذات صلة. حتى الآن يمكن أن نتحدث عن العقد في شجرة من حيث بالنسبة إلى العقد الأخرى في الشجرة. حتى الآن لدينا الآباء والأطفال والأشقاء والأجداد، وأحفاد. فهي جميلة الحس السليم، وما فيها من معاني. إذا نطلب - الآباء الامر. فما هو أصل 3؟ [الطلاب] 7. نعم >>. الأصل هو الذهاب لمجرد أن يكون ما يشير لك. ثم ما هي الأطفال من 7؟ [الطلاب] 3 و 9. نعم >>. لاحظت أن "الأطفال" تعني حرفيا الأطفال، وحتى 6 لا تطبق، لأنها مثل الحفيد. ولكن بعد ذلك اذا ذهبنا نسل، لذلك ما هي أحفاد 7؟ [الطلاب] 3 و 6 و 9. نعم >>. المتحدرين من عقدة الجذر سيكون كل شيء في الشجرة، ربما باستثناء عقدة الجذر نفسه، إذا كنت لا ترغب في النظر في أن أحد أحفاد. وأخيرا، الأجداد، لذلك فمن الاتجاه المعاكس. فما هي أسلاف 6؟ [الطلاب] 3 و 7. نعم >>. لم يتم تضمين 9. انها مجرد العودة النسب المباشر إلى جذر ستكون أسلافك. 

"نحن نقول ان هو 'أمر' شجرة ثنائية إذا لكل عقدة في الشجرة، كل نسله على اليسار يكون أقل القيم وجميع من هم على الحق قدر أكبر من القيم. على سبيل المثال، أمر شجرة أعلاه ولكنها ليست الوحيدة الممكنة للترتيب أمر ". قبل أن نصل إلى ذلك، وكما هو معروف شجرة ثنائية كما أمرت شجرة البحث الثنائية. نحن هنا يحدث ليكون اصفا اياه بانه شجرة ثنائية أمر، ولكن لم يسبق لي أن سمعت يطلق عليه اسم شجرة ثنائية أمر من قبل، وعلى مسابقة نحن أكثر من ذلك بكثير من المرجح أن تضع ثنائي شجرة البحث. انهم احدة واحدة، ومن المهم تتعرف على التمييز بين شجرة ثنائية وثنائي شجرة البحث. شجرة ثنائية هو مجرد شجرة يشير إلى أمرين. كل عقدة يشير إلى أمرين. لا يوجد أي منطق حول القيم يشير إلى. مثل ذلك أكثر من هنا، لأنه شجرة البحث الثنائية، ونحن نعلم أنه إذا نذهب يسار 7، بعد ذلك كل من القيم التي يمكن ان نصل ربما عن طريق الذهاب غادر من 7 يجب أن تكون أقل من 7. لاحظت أن جميع القيم هي أقل من 7 3 و 6. تلك كلها على يسار 7. إذا ذهبنا إلى يمين 7، كل شيء يجب أن تكون أكبر من 7، حتى 9 هو الحق من 7، لذلك نحن في حالة جيدة. ليست هذه هي الحال بالنسبة لشجرة ثنائية، لشجرة ثنائية منتظمة يمكن أن لدينا فقط 3 في القمة، من 7 إلى اليسار، 9 إلى يسار 7؛ ليس هناك ترتيب القيم على الإطلاق. الآن، ونحن لن نفعل هذا لأنه فعلا أمر يبعث على الملل وغير ضرورية، ولكن "محاولة لرسم ما يصل الأشجار كما أمرت يمكن ان يخطر لك باستخدام الأرقام 7، 3، 9، و 6. عدد الترتيبات المتميزة هناك؟ ما هو ارتفاع كل واحدة؟ " 

سنفعل زوجين، ولكن هي الفكرة الرئيسية، هذا هو بأي حال من الأحوال تمثيل فريد من شجرة ثنائية تحتوي على هذه القيم. كل ما نحتاجه هو بعض شجرة ثنائية الذي يحتوي 7، 3، 6، و 9. وآخر واحد ممكن تكون صالحة الجذر هو 3، انتقل إلى اليسار وانها 6، يذهب إلى اليسار وانها 7، انتقل إلى اليسار وانها 9. وهذا هو البحث الثنائي صالح تماما شجرة. انها ليست مفيدة جدا، لأنها تماما مثل قائمة مرتبطة وجميع هذه المؤشرات تعتبر لاغية فقط. وإنما هو شجرة صالحة. نعم؟ [طالب] لا القيم يجب أن تكون أكبر على الحق؟ أم أن هذا -؟ هذه >> يعني أن أذهب في الاتجاه الآخر. هناك أيضا - نعم، دعونا تبديل ذلك. 9، 7، 6، 3. جيد الصيد. فإنه لا يزال على طاعة ما يفترض البحث شجرة ثنائية للقيام به. حيث كل شيء إلى اليسار يجب أن يكون أقل من أي عقدة معينة. يمكن أن نتحرك فقط، ويقول، وهذا 6 و ضعه هنا. لا، لا يمكننا ذلك. لماذا تستمر في فعل ذلك؟ دعونا نفعل - هنا هو 6، وهنا 7، 6 نقاط إلى 3. هذا لا يزال البحث الثنائية صالحة شجرة. ما هو الخطأ إذا I - دعونا نرى ما اذا كان يمكنني الخروج مع الترتيب. نعم، حسنا. ما هو الخطأ في ذلك هذه الشجرة؟ اعتقد انني قد قدمت فعلا لك وإشارة إلى أن هناك شيئا خطأ في ذلك. لماذا تستمر في فعل ذلك؟ حسنا. هذا يبدو معقولا. إذا نظرنا إلى كل عقدة، مثل 7، ثم إلى يسار 7 هو 3. لذلك لدينا 3، الشيء إلى يمين 3 هو 6. واذا نظرتم الى 6، الشيء إلى اليمين من 6 هو 9. فلماذا هذا ليس بحثا ثنائي صالحة الشجرة؟ [الطلاب] 9 لا يزال على يسار 7. نعم >>. يجب أن يكون صحيحا أن جميع القيم التي يمكن أن تصل إلى ربما من خلال الذهاب الى اليسار من 7 هي أقل من 7. اذا ذهبنا تبقى من 7، نصل الى 3 و يمكننا الحصول على ما زالت إلى 6، يمكننا الحصول على ما زالت إلى 9، ولكن بعد أن ذهب أقل من 7، لا ينبغي لنا أن تكون قادرة على الحصول على عدد أكبر من هذا 7. لذلك هذه ليست صالحة شجرة البحث الثنائية. 

أخي كان في الواقع مسألة مقابلة كان ذلك في الأساس هذا، رمز للتو شيئا للتحقق من صحة سواء شجرة هي شجرة البحث الثنائية، وهكذا كان أول شيء فعله انظروا فقط لرؤية إذا كان اليسار واليمين صحيحة، وتكرار ثم الى هناك. ولكن لا يمكنك فعل ذلك فقط، عليك أن تتبع لكون ذلك الآن لقد ذهبت يسار 7، يجب أن كل شيء في هذا الشجرة الفرعية تكون أقل من 7. الخوارزمية الصحيح يحتاج إلى تتبع من حدود القيم التي يمكن أن تقع فيها ربما ونحن لن نذهب من خلال كل منهم. هناك علاقة تكرار لطيفة، على الرغم من أننا لم نصل إلى تلك، أو أننا لن نصل إلى تلك، تحديد عدد وهناك بالفعل. لذلك هناك 14 منهم. فكرة كيف سيكون ذلك هو رياضيا مثل، يمكنك اختيار أي واحد واحدة لتكون عقدة الجذر، ثم إذا كنت اختيار 7 لتكون العقدة الجذر، ثم هناك، مثلا، بعض الأرقام التي يمكن أن تذهب تكون عقدة يساري، وهناك بعض الأرقام التي يمكن أن تكون عقدة حقي، ولكن إذا كنت قد ن العدد الإجمالي، ثم المبلغ الذي يمكن أن تذهب إلى اليسار بالإضافة إلى المبلغ الذي يمكن أن تذهب إلى اليمين هو ن - 1. لذلك من الأرقام المتبقية، فإنها يجب أن تكون قادرا على الذهاب إما إلى اليسار أو اليمين. يبدو من الصعب أن، إذا وضعت 3 الأولى ثم كل شيء يجب أن يذهب إلى اليسار، ولكن إذا وضعت 7، ثم يمكن أن تسير الأمور على بعض اليسار وبعض الأشياء يمكن أن تذهب إلى اليمين. و'3 'أول يعني كل شيء يمكن أن تذهب إلى اليمين. انها حقا، عليك أن تفكر في ذلك كما، كيف تسير الأمور في كثير من المستوى التالي من شجرة. ويتعلق الأمر إلى أن تكون 14؛ أو يمكنك رسم كل منهم، وبعد ذلك سوف تحصل على 14. 

العودة هنا، "أشجار الثنائية أمرت هي باردة لأننا يمكن البحث من خلالها بطريقة مشابهة جدا لتبحث على مجموعة فرزها. للقيام بذلك، ونحن نبدأ في جذور والعمل طريقنا إلى أسفل الشجرة نحو الأوراق، والتحقق من القيم كل عقدة ضد القيم التي تبحث عنها. إذا قيمة العقدة الحالية هي أقل من القيمة التي تبحث عنها، تذهب بجوار الطفل العقدة اليمنى. خلاف ذلك، تذهب إلى الأطفال للعقدة اليسار. في مرحلة ما، ستجد إما القيمة التي تبحث عنها، أو عليك أن تصل الى قيمة خالية، تشير القيمة ليست في الشجرة. " لا بد لي من إعادة رسم شجرة كان لدينا من قبل؛ التي سوف تأخذ ثانية. لكننا نريد للبحث عن ما إذا كان 6، 10، و 1 في الشجرة. ذلك ما كان عليه، 7، 9، 3، 6. حسنا. الأرقام التي تريد البحث عنها، ونحن نريد للبحث عن 6. كيف يعمل هذا الخوارزمية؟ حسنا، لدينا أيضا بعض مؤشر الجذر إلى شجرة لدينا. وكنا نذهب إلى جذر ويقولون، هو هذه القيمة مساوية لقيمة ونحن تبحث عن؟ لذلك نحن نبحث عن 6، حتى انها ليست متساوية. لذلك نحن نستمر، ونحن الآن نقول، حسنا، لذلك 6 هو أقل من 7. هل يعني هذا أننا نريد أن يذهب إلى اليسار، أو لا نريد أن نذهب إلى اليمين؟ [طالب] بقي. نعم >>. انه من الاسهل بكثير، كل ما عليك القيام به هو رسم عقدة واحدة ممكن من شجرة ثم مش - بدلا من محاولة التفكير في رأسك، حسنا، إذا كان أقل من ذلك، لم أذهب إلى اليسار أو الذهاب الحق، مجرد النظر في هذه الصورة، من الواضح جدا أن لدي للذهاب إلى اليسار إذا كانت هذه العقدة هي أكبر من القيمة التي أنا أبحث عن. حتى تذهب إلى اليسار، والآن أنا في 3. أريد أن - 3 هو أقل من القيمة أنا أبحث عن الذي هو 6. لذلك نحن نذهب إلى اليمين، والآن أنا في نهاية المطاف في 6، وهي القيمة أنا أبحث عن، لذلك أعود صحيح. القيمة التالية انا ذاهب للبحث عن هو 10. حسنا. حتى 10، الآن، هو الذهاب الى - قطع ذلك - سوف تتبع جذورها. الآن، 10 ستكون أكبر من 7، لذلك أريد أن ننظر إلى اليمين. أنا سوف يأتي إلى هنا، 10 ستكون أكبر من 9، لذلك أنا ذاهب الى تريد أن تبدو إلى اليمين. لقد جئت إلى هنا، ولكن أكثر من هنا الآن أنا في فارغة. ماذا أفعل إذا ضرب فارغة؟ [طالب] عودة كاذبة؟ نعم >>. لم أجد 10. 1 لن تكون قضية مماثلة تقريبا، إلا انه سيكون مجرد أن يكون انقلبت، وبدلا من البحث أسفل الجانب الأيمن، وأنا ذاهب إلى النظر إلى أسفل الجانب الأيسر. 

الآن أعتقد أننا في الواقع الحصول على التعليمات البرمجية. هنا المكان - فتح الجهاز والتنقل CS50 طريقك هناك، ولكن يمكنك أيضا القيام بذلك فقط في الفضاء. انها على الارجح مثالية للقيام بذلك في الفضاء، لأنه لا يمكن أن نعمل في الفضاء. "أولا سنحتاج إلى تعريف نوع جديد للعقدة شجرة ثنائية تحتوي على قيم كثافة العمليات. باستخدام النمطي typedef أدناه، إنشاء تعريف نوع جديد للعقدة في شجرة ثنائية. إذا واجهتك مشكلة. . . "بلاه، بلاه، بلاه. حسنا. لذلك دعونا نضع المتداول هنا، typedef العقدة البنية، وعقدة. نعم، حسنا. فما هي المجالات ونحن في طريقنا لدينا عقدة تريد في؟ [طالب] وكثافة العمليات ثم اثنين مؤشرات؟ الباحث >> القيمة، وهما المؤشرات؟ كيف أكتب المؤشرات؟ [طالب] البنية. وأرجو >> تكبير. نعم، لذلك البنية عقدة * اليسار، والبنية عقدة * الحق. وتذكر المناقشة من وقت الماضي، أن هذا لا معنى له، وهذا لا معنى له، هذا لا معنى له. تحتاج كل شيء هناك من أجل تحديد هذه البنية العودية. حسنا، حتى في ما يجري لدينا شجرة لتبدو وكأنها. إذا فعلنا شجرة trinary، ثم قد تبدو وكأنها عقدة B2، B1، B3 * البنية عقدة، حيث هي فرع ب - في الواقع، لقد سمعت أنه ترك أكثر،، والحق الأوسط، ولكن أيا كان. نحن نهتم فقط عن ثنائي، الحق في ذلك، غادر. "تعلن الآن على عقدة العالمية * متغير لجذر الشجرة." لذلك نحن لن نفعل ذلك. من أجل جعل الأمور أكثر صعوبة قليلا ومعممة أكثر من ذلك، لن يكون لدينا متغير عقدة العالمية. بدلا من ذلك، سوف الرئيسي في نعلن بكل ما نملك من الأشياء العقدة، وهذا يعني أن أدناه، عندما نبدأ تشغيل لدينا يحتوي على وظيفة وظيفة لدينا إدراج، بدلا من الدالة باستخدام لدينا يحتوي هذا المتغير فقط عقدة العالمية، نحن ذاهبون الى انها قد تأخذ كوسيطة الشجرة التي نريد لها أن معالجة. وجود المتغير العالمي كان من المفترض أن تجعل الأمور أسهل. ونحن في طريقنا لجعل الامور اكثر صعوبة. تتخذ الآن لمدة دقيقة أو نحو ذلك لمجرد قيام بذلك النوع من الشيء، حيث من داخل الرئيسية التي تريد إنشاء هذه الشجرة، وهذا كل ما تريد القيام به. محاولة وبناء هذه الشجرة في وظيفة الرئيسي الخاص بك. 

حسنا. لذلك أنت لا تملك حتى أن الشجرة التي شيدت الطريق بأكمله حتى الآن. ولكن أي شخص على شيء أنا يمكن سحب ما يصل لاظهار كيف يمكن للمرء أن يبدأ بناء مثل هذه الشجرة؟ [طالب] شخص ما ضجيجا، في محاولة للخروج. [بودين] مريحة مع أي شخص بناء على شجرة؟ [طالب] بالتأكيد. انها لم تفعل ذلك. أنها على ما يرام >>. يمكن أن ننتهي فقط - يا، هل يمكنك حفظه؟ الصيحة. حتى هنا لدينا - أوه، أنا قطعت قليلا قبالة. أنا كنت أسرع في؟ تكبير، انتقل بها. >> لدي سؤال. نعم >>؟ [طالب] عند تعريف البنية، هي أشياء مثل تهيئة إلى أي شيء؟ [بودين] رقم >> حسنا. لذلك سيكون لديك لتهيئة - [بودين] رقم عند تعريف، أو عندما تعلن لك والبنية، لم يتم تهيئة بشكل افتراضي، بل مجرد مثل إذا قمت بتعريف الباحث. انها بالضبط نفس الشيء. انها مثل كل من حقولها الفردية يمكن أن يكون لها قيمة القمامة في ذلك. و>> هل من الممكن تحديد - أو لتعلن البنية بطريقة يفعل تهيئة لهم؟ [بودين] نعم. ذلك تهيئة الاختصار، جملة سوف تبدو وكأنها - هناك طريقتان يمكننا أن نفعل هذا. أعتقد أننا يجب أن ترجمة عليه لجعل متأكد من ضجيج أيضا لا هذا. ترتيب الحجج التي تأتي في البنية، وضع لكم وترتيب الحجج داخل هذه الأقواس المتعرجة. حتى إذا كنت ترغب في تهيئة إلى 9 و ترك لاغية وباطلة ثم يكون على حق، سيكون من 9، فارغة، فارغة. البديل هو، والمحرر لا يحب هذا النحو، ويعتقد أريد كتلة جديدة، لكن البديل هو شيء من هذا القبيل - هنا، وأنا وضعه في سطر جديد. يمكنك القول صراحة، انسى بناء الجملة بالضبط. حتى تتمكن من معالجة صراحة منهم بالاسم، ويقول: ج، أو قيمة = 9. NULL = اليسار. انا التخمين هذه الحاجة إلى أن تكون الفواصل. . الحق = NULL، لذلك هذا الأسلوب الذي لا تحتاج بالفعل لمعرفة ترتيب البنية، وعندما كنت في هذه القراءة، انها أكثر من ذلك بكثير صريح حول ما يتم تهيئة القيمة إلى. 

هذا يحدث ليكون واحدا من الأشياء التي - لذلك، بالنسبة للجزء الأكبر، C + + هو شاملة من C. يمكنك أن تأخذ كود C، نقله الى C + +، وينبغي أن تجمع. هذا هو واحد من الأشياء التي C + + لا يعتمد، لذلك الناس في الغالب لا تفعل ذلك. أنا لا أعرف إذا كان هذا هو السبب الوحيد الناس لا يميلون للقيام بذلك، ولكن هناك حاجة الحالة حيث كنت بحاجة لاستخدامه للعمل مع C + + وحتى أتمكن من عدم استخدام هذا. مثال آخر على ما لا يعمل مع C + + هو كيف malloc بإرجاع "* الفراغ،" من الناحية الفنية، لكن هل يمكن أن نقول فقط تشار * X = malloc مهما، وسوف يكون تلقائيا إلى * يلقي شار. أن يلقي التلقائي لا يحدث في C + +. ومن شأن ذلك أن لا ترجمة، وكنت في حاجة للقول صراحة * شار، malloc، أيا كان، لصبغه ل* شار. هناك الكثير من الامور التي لا C + + C ونختلف على، ولكن هذه هي اثنين. وهكذا لن نذهب مع هذه الجملة. ولكن حتى لو لم نذهب مع ذلك التركيب، ما هو - قد يكون الخطأ في هذا؟ [طالب] I لا تحتاج إلى إلغاء مرجعية ذلك؟ نعم >>. تذكر أن السهم لديه إلغاء مرجعية ضمنية، وذلك عندما نتعامل فقط مع البنية، نريد للاستخدام. للحصول على في داخل مجال البنية. والمرة الوحيدة التي نستخدمها السهم عندما نريد القيام به - حسنا، ما يعادل سهم - هذا ما كان يمكن أن يكون المقصود إذا كنت السهم. جميع وسائل السهم، إلغاء مرجعية هذا، والآن أنا في البنية، ويمكنني الحصول على هذا المجال. الحصول إما مباشرة أو إلغاء مرجعية الميدان والحصول على الميدان - أعتقد أن هذا يجب أن يكون القيمة. ولكن هنا انا التعامل مع البنية وفقط، وليس مؤشر إلى البنية، وهكذا لا أستطيع أن استخدم السهم. ولكن هذا النوع من الاشياء يمكننا أن نفعل كافة العقد. يا إلهي. هذا هو 6 و 7 و 3. ثم يمكننا إعداد فروع في شجرة لدينا، فإننا يمكن أن يكون 7 - فإننا يمكن أن يكون، يجب أن يشير يساره إلى 3. فكيف نفعل ذلك؟ [طلاب، غير مفهومة] >> نعم. عنوان node3، وإذا لم يكن لديك عنوان، ثم أنه ليس فقط تجميع. ولكن تذكر أن هذه هي مؤشرات إلى العقد المقبل. وينبغي الإشارة الحق إلى 9، وينبغي 3 نقطة على الحق إلى 6. وأعتقد أن هذا هو كل مجموعة. أي تعليقات أو أسئلة؟ [طالبة، غير مفهومة] جذر ستكون 7. نستطيع أن نقول مجرد عقدة * PTR = أو الجذر، و= node7. 

لأغراضنا، ونحن في طريقنا إلى أن التعامل مع إدراج، لذلك نحن ذاهبون الى تريد كتابة دالة لتضاف الى هذه الشجرة الثنائية ويجري إدراج حتما إلى استدعاء malloc لإنشاء عقدة جديدة لهذه الشجرة. حتى تسير الامور للحصول فوضى مع حقيقة أن بعض العقد حاليا على كومة والعقد الأخرى تسير في نهاية المطاف على كومة عندما كنا إدراجها. هذا صحيح تماما، ولكن السبب الوحيد ونحن قادرون على القيام بذلك على المكدس لأنه مثل هذا المثال المفتعلة التي نعرفها ومن المفترض الشجرة التي يتم بناؤها من 7، 3، 6، 9. إذا لم يكن لدينا هذا، ثم لما كان لنا لmalloc في المقام الأول. كما سنرى قليلا في وقت لاحق، ينبغي لنا أن malloc'ing. الآن انها معقولة تماما لوضعه على كومة، ولكن دعونا تغيير هذا إلى تنفيذ malloc. لذلك كل هذه سوف تكون الآن إلى شيء من هذا القبيل * العقدة = node9 malloc (sizeof (عقدة)). والآن ونحن في طريقنا إلى القيام به لدينا الاختيار. إذا كان (node9 == NULL) - لم أكن أريد أن - العودة 1، ومن ثم يمكننا القيام به node9-> الآن حان لأن مؤشر، قيمة = 6، node9-> غادر = NULL، node9-> الحق = NULL، ونحن ستكون لدينا للقيام بذلك لكل من تلك العقد. بدلا من ذلك، دعونا وضعها داخل وظيفة منفصلة. دعنا نسميها عقدة * build_node، وهذا يشبه إلى حد ما واجهات برمجة التطبيقات التي نقدمها لترميز هوفمان. نقدم لكم وظائف مهيئ لشجرة وdeconstructor "وظائف" لتلك الأشجار ومثلها للغابات. 

حتى هنا ونحن في طريقنا إلى مهيئ لها وظيفة لمجرد بناء عقدة بالنسبة لنا. وانها سوف ننظر الى حد كبير تماما مثل هذا. وانا ذاهب حتى على الكسل وعدم تغيير اسم المتغير، على الرغم من node9 لا معنى له بعد الآن. أوه، أعتقد قيمة node9 لا ينبغي أن يكون 6. الآن يمكننا العودة node9. وهنا يجب علينا أن نعود فارغة. الجميع يتفق على أن وظيفة بناء واحد في عقدة؟ حتى الآن يمكن أن نسميه فقط لبناء أي عقدة مع قيمة معينة ومؤشرات فارغة. الآن يمكننا أن نسمي ذلك، يمكننا أن نفعل عقدة * node9 = build_node (9). ودعونا نفعل. . . 6، 3، 7، 6، 3، 7. والآن نريد أن إعداد مؤشرات نفسه، الآن كل شيء ما عدا بالفعل من حيث مؤشرات لذلك لم يعد في حاجة إلى عنوان. حسنا. إذن ما هو آخر شيء أريد القيام به؟ هناك خطأ تدقيق أن أنا لا أفعل. ماذا بناء عودة العقدة؟ [طالبة، غير مفهومة] >> نعم. إذا فشل malloc، وأنها سوف تعود فارغة. لذلك أنا ذاهب لوضع بتكاسل عليه هنا بدلا من القيام شرط لكل منها. إذا كان (node9 == NULL، أو - حتى أبسط، وهذا يعادل node9 إن لم يكن فقط. حتى إن لم يكن node9، أو لا node6، أو لا node3، أو لا node7، والعودة 1. ربما ينبغي لنا أن فشلت طباعة malloc، أو شيء من هذا. [طالب] هل كاذبة فارغة يساوي أيضا؟ [بودين] أي قيمة الصفر هو زائف. ذلك هو قيمة فارغة صفر. صفر هو قيمة صفر. كاذبة هي قيمة صفر. أي - الى حد كبير فقط 2 صفر القيم لاغية والصفر، كاذبة هي مجرد تجزئة على النحو المحدد صفر. الذي ينطبق أيضا إذا كنا لا نعلن متغير عمومي. إذا لم لدينا عقدة الجذر * هنا، ثم - والشيء الجميل في المتغيرات العالمية هو أن لديهم دائما قيمة أولية. هذا ليس صحيحا من وظائف، وكيف داخل من هنا، اذا كان لدينا، مثل، * عقدة أو عقدة X. ليس لدينا أي فكرة عما x.value، x.whatever، أو يمكننا طباعتها وأنها يمكن أن تكون تعسفية. هذا ليس صحيحا من المتغيرات العالمية. عقدة الجذر أو حتى العاشر العقدة. بشكل افتراضي، كل ما هو عالمي، إذا لم يتم تهيئة صراحة إلى بعض القيمة، يحتوي على قيمة الصفر كقيمة لها. حتى هنا، عقدة الجذر *، نحن لا تهيئة صراحة إلى أي شيء، لذلك سوف تكون قيمته الافتراضية فارغة، والذي هو القيمة صفر من المؤشرات. القيمة الافتراضية X هو الذهاب الى يعني أن x.value صفر، x.left فارغة، وx.right فارغة. منذ ذلك هو البنية، فإن كل من مجالات البنية تكون قيم الصفر. نحن لسنا بحاجة لاستخدام ذلك هنا، وإن كان. [طالب] والبنيات مختلفة من المتغيرات الأخرى، وهي المتغيرات الأخرى القيم القمامة، وهذه هي الأصفار؟ [بودين] قيم أخرى أيضا. حتى في س س سوف يكون صفرا. اذا كان في نطاق عالمي، ولديه القيمة الأولية. حسنا >>. [بودين] إما القيمة الأولية التي اعطتها أو صفر. أعتقد أن يعتني كل هذا. 

حسنا. وبالتالي فإن الجزء التالي من سؤال يسأل، "الآن نريد أن كتابة دالة دعا يحتوي على مع نموذج أولي من قيمة BOOL يحتوي على كثافة العمليات. " نحن لن تفعل BOOL يحتوي على القيمة الصحيحة. نموذجنا هو الذهاب لتبدو وكأنها BOOL يحتوي على (قيمة كثافة العمليات. ثم ونحن في طريقنا أيضا إلى نقله الشجرة أنه ينبغي أن يكون التحقق لمعرفة إذا كان لديه تلك القيمة. * عقدة حتى شجرة). حسنا. ومن ثم يمكن أن نطلق عليه مع شيء من هذا القبيل، ربما سوف نريد إلى printf أو شيء. تحتوي على 6، وجذر لدينا. يجب أن تعود واحدة، أو صحيحا، في حين يحتوي الجذر 5 ينبغي أن عودة كاذبة. حتى تأخذ ثانية لتنفيذ ذلك. يمكنك أن تفعل ذلك إما تكراري أو بشكل متكرر. والشيء الجميل في الطريقة التي قد وضع الامور هو أن فإنه يفسح المجال لدينا الحل أسهل بكثير العودية من الطريقة العالمي المتغير فعلت. لأنه إذا كان لدينا فقط يحتوي على القيمة الصحيحة، ثم لدينا أي وسيلة لأسفل الأشجار الفرعية recursing. كان علينا أن لها وظيفة مساعد منفصلة recurses أسفل الأشجار الفرعية بالنسبة لنا. ولكن بما أننا قد غيرت من اتخاذ الشجرة كوسيطة، الذي كان ينبغي أن يكون دائما في المقام الأول، يمكن الآن إعادة لعنة علينا بسهولة أكبر. حتى تكرارية أو متكررة، سوف نذهب أكثر على حد سواء، ولكن سوف نرى أن ينتهي به الأمر إلى العودية غاية السهولة. حسنا. هل لديها شيء يمكننا العمل معها؟ 

[طالب] أنا عندي حل تكرارية. >> حسنا، تكرارية. حسنا، هذا يبدو جيدا. لذلك، تريد السير لنا من خلال ذلك؟ [طالب] بالتأكيد. تعيين لذلك أنا متغير TEMP للحصول على العقدة الأولى من شجرة. وبعد ذلك فقط من خلال يحلق في حين لا TEMP فارغة على قدم المساواة، وذلك في حين كان لا يزال في الشجرة، وأنا أعتقد. وإذا كانت القيمة تساوي القيمة التي يتم الإشارة إلى درجة الحرارة، ثم تقوم بإرجاع هذه القيمة. خلاف ذلك، فإنه يتحقق ما اذا كان على الجانب الأيمن أو الجانب الأيسر. اذا كان لديك أي وقت مضى حالة حيث لم يكن هناك مزيد من الشجرة، ثم تقوم بإرجاع - خروجها من حلقة وترجع كاذبة. [بودين] حسنا. بحيث يبدو جيدا. أي شخص لديه أي تعليق على أي شيء؟ ليس لدي اي تعليق صحة على الإطلاق. شيء واحد يمكننا القيام به هو هذا الرجل. أوه، أنها سوف تقطع طويل قليلا قليلا. سوف أقوم بإصلاح ما يصل. حسنا. 

يجب على الجميع يتذكر كيف يعمل الثلاثي. هناك بالتأكيد تم المسابقات في الماضي التي تعطيك وظيفة مع المشغل الثلاثي، ويقول ترجمة هذا، أن تفعل شيئا لا يستخدم الثلاثي. لذلك هذا هو الحال شائع جدا من عندما كنت تفكر في استخدام الثلاثي، حيث إذا وضع بعض حالة متغير إلى شيء، تعيين متغير آخر أن نفس إلى شيء آخر. هذا شيء كثيرا جدا يمكن أن تتحول إلى هذا النوع من الاشياء حيث وضع هذا المتغير لهذا - أو، حسنا، هل هذا صحيح؟ ثم هذا، وإلا هذا. [طالب] أول واحد هو إذا كان هذا صحيحا، أليس كذلك؟ [بودين] نعم. الطريق قرأت دائما هو عليه، درجة الحرارة يساوي قيمة أكبر من قيمة درجة الحرارة، ثم هذا، وإلا هذا. انها بطرح سؤال. هو أكبر؟ قم أول شيء. آخر يفعل الشيء الثاني. كنت دائما تقريبا - القولون، أنا فقط - في رأسي، وأنا أقرأ آخر باسم. 

هل لديها حل العودية؟ حسنا. هذا واحد ونحن في طريقنا ل- يمكن أن يكون بالفعل كبيرة، ولكن ونحن في طريقنا لجعله أفضل. هذا هو الى حد كبير نفس الفكرة بالضبط. انها مجرد، حسنا، هل تريد أن أشرح؟ [طالب] بالتأكيد. لذلك نحن مع التأكد من أن الشجرة ليست فارغة الأولى، لأنه إذا كان شجرة فارغة ثم انه سيكون لعودة كاذبة لأننا لم نجد ذلك. وإذا كان لا يزال هناك شجرة، نذهب إلى - نحن أولا التحقق إذا كانت القيمة هي العقدة الحالية. العودة الحقيقية إذا كان، وإذا لم يكن لنا إعادة لعنة على اليسار أو اليمين. هل هذا الصوت المناسب؟ هم >> MM-. (الاتفاق) تلاحظ ذلك أن هذا هو تقريبا - هيكليا مشابهة جدا لحل تكرارية. انها مجرد أنه بدلا من recursing، كان لدينا حلقة من الوقت. والقضية هنا حيث قاعدة الشجرة فارغة لا تساوي وكان الشرط الذي بموجبه نحن اندلعت من الحلقة الوقت. انهم متشابهة جدا. ولكن نحن ذاهبون الى اتخاذ هذه الخطوة واحدة أخرى. الآن، ونحن نفعل نفس الشيء هنا. لاحظت نحن العودة نفس الشيء في كل من هذه الخطوط، باستثناء واحد هو حجة مختلفة. لذلك نحن ذاهبون لجعل ذلك في الثلاثي. أنا ضربت شيئا الخيار، وانها حققت الرمز. حسنا. لذلك نحن في طريقنا للعودة على ذلك. هذا هو الحصول على خطوط متعددة، وأيضا، في أسرع من ذلك. عادة، كشيء الأسلوبية، وأنا لا أعتقد كثير من الناس وضع مسافة بعد السهم، ولكن أعتقد إذا كنت متسقة، أنه بخير. إذا كانت القيمة أقل من قيمة شجرة، ونحن نريد لإعادة لعنة على اليسار شجرة، آخر ونحن نريد أن إعادة لعنة على حق شجرة. لذلك هذه الخطوة واحدة من صنع هذا تبدو أصغر. الخطوة الثانية لجعل هذا تبدو أصغر - يمكننا فصل هذه لعدة أسطر. حسنا. الخطوة الثانية من مما جعلها تبدو أصغر هنا، حتى يساوي قيمة الإرجاع قيمة شجرة، أو يحتوي أيا كان. 

هذا هو الشيء المهم. أنا لست متأكدا مما إذا كان ذلك قال صراحة في الصف، ولكن يطلق عليه دائرة قصر التقييم. والفكرة هنا هي القيمة == قيمة شجرة. إذا كان هذا صحيحا، فإن هذا صحيح، ونحن نريد أن 'أو' انه مع كل ما هو أكثر من هنا. ذلك دون حتى التفكير بكل ما هو أكثر من هنا، ما هو التعبير بالكامل سيعودون؟ [طالب] صحيح؟ نعم >>، وذلك لأن الصحيح من أي شيء، or'd - or'd أو حقيقية مع أي شيء صحيح بالضرورة. ذلك في أقرب وقت كما نرى قيمة الإرجاع = قيمة الشجرة، ونحن في طريقنا إلى العودة الحقيقية فقط. لن يذهبوا حتى للإعادة لعنة يحتوي على مزيد من أسفل الخط. يمكننا اتخاذ هذه الخطوة واحدة أخرى. شجرة العودة لا تساوي فارغة وكل هذا. جعل من ذلك وظيفة من سطر واحد. وهذا هو أيضا مثال على دائرة قصر التقييم. ولكن الآن انها نفس الفكرة - بدلا من - إذا كان الأمر كذلك شجرة فارغة لا تساوي - أو، حسنا، إذا شجرة لا يساوي فارغة، والذي هو حالة سيئة، إذا شجرة يساوي فارغة، ثم الشرط الأول ستكون خاطئة. كاذبة حتى anded مع أي شيء سيكون ماذا؟ [طالب] خطأ. نعم >>. هذا هو النصف الآخر من دائرة قصر التقييم، حيث إذا شجرة لا فارغة لا تساوي، ثم نحن لن نذهب حتى - أو إذا شجرة لا يساوي فارغة، فإننا لن نفعل قيمة == قيمة شجرة. ونحن في طريقنا للعودة على الفور فقط كاذبة. وهو أمر مهم، لأنه إذا لم يفعل ذلك دائرة قصر تقييم، ثم إذا شجرة لا يساوي فارغة، هذا الشرط الثاني هو الذهاب الى خطأ SEG، لأن شجرة> قيمة ويعتبر إلغاء مرجعية فارغة. ولهذا ذلك. يمكن أن تجعل هذا - تحويل أكثر من مرة واحدة. هذا أمر شائع جدا أيضا، لا يجعل هذا الخط واحدة مع هذا، ولكن هذا أمر شائع في ظروف، ربما ليس هنا، ولكن إذا (شجرة! NULL =، == والقيمة شجرة> القيمة)، تفعل ما. هذه هي حالة شائعة جدا، حيث بدلا من الاضطرار لكسر هذه إلى قسمين IFS، حيث تريد، هو باطل الشجرة؟ حسنا، انها ليست فارغة، وحتى الآن هي القيمة مساوية لقيمة الشجرة؟ القيام بذلك. بدلا من ذلك، هذا الشرط، وهذا خطأ أبدا SEG لأنها سوف تندلع إذا كانت هذه يحدث أن تكون فارغة. حسنا، أعتقد إذا شجرة الخاص بك هو مؤشر غير صالح تماما، ويمكن ان يزال SEG خطأ، ولكن لا يمكن أن SEG خطأ إذا شجرة فارغة. لو كانت فارغة، فإنه الخروج من أي وقت مضى قبل أن ألغى الإشارة القيمة المؤشر في المقام الأول. [طالب] هل هذا التقييم يسمى كسول؟ 

التقييم [بودين] كسول هو شيء منفصل. تقييم كسول هو أشبه تسأل عن قيمة، كنت أسأل لحساب قيمة، نوع من، ولكنك لا تحتاج على الفور. لذلك حتى كنت في حاجة فعلا، لا يتم تقييم ذلك. هذه ليست بالضبط نفس الشيء، ولكن، في pset هوفمان تقول أننا "بتكاسل" الكتابة. السبب في أننا نفعل ذلك لأننا في الواقع كنت التخزين المؤقت للكتابة - نحن لا نريد لكتابة بت الفردية في كل مرة، أو الفردية بايت في كل مرة، بدلا نريد للحصول على قطعة من وحدات البايت. ثم مرة واحدة لدينا قطعة من بايت، ثم سوف نكتب بها. على الرغم من أن تسأل لكتابة - وfwrite وfread تفعل نفس الشيء. أنها عازلة يقرأ ويكتب لكم. على الرغم من أن تسأل لكتابة على الفور، وربما لن. وأنت لا تستطيع أن تتأكد من أن الأمور تسير على أن تكون مكتوبة حتى استدعاء hfclose أو أيا كان، ثم التي تقول، حسنا، أنا إغلاق ملف بلدي، وهذا يعني أنني أفضل الكتابة كل شيء أنا لم تكتب بعد. فقد لا تحتاج لكتابة كل شيء حتى كنت إغلاق الملف، ومن ثم فإنه يحتاج إلى. ولهذا فقط ما كسول - ينتظر حتى يجب أن يحدث. هذا - اتخاذ 51 و كنت سأذهب فيه بمزيد من التفصيل، لأن كل شيء في وOCaml 51، كل شيء على ما العودية. هناك تكرارية أي حلول، أساسا. كل شيء العودية، وتقييم كسول وسيكون من المهم بالنسبة للكثير من الظروف حيث، إذا لم يتم تقييم بتكاسل، فهل يعني - ومثال على ذلك هو تيارات، والتي هي بلا حدود طويلة. من الناحية النظرية، يمكنك التفكير في الأعداد الطبيعية وتيار من 1-2-3-4-5-6-7، الأشياء بتكاسل ذلك تقييم ما يرام. إذا قلت أريد أن عدد العاشرة، ثم لا أستطيع تقييم ما يصل الى عدد العاشرة. إذا كنت تريد رقم مائة، ثم لا أستطيع تقييم ما يصل الى مئة عدد. دون تقييم كسول، ثم انه سيكون في محاولة لتقييم كل الأرقام على الفور. كنت تقييم العديد من الأرقام متناهيه، وهذا غير ممكن تماما. لذلك هناك الكثير من الظروف التي تكون فيها كسول التقييم من الضروري الحصول على الأشياء فقط لللعمل. 

الآن نريد أن يكتب فيها إدراج إدراج ستكون تغيير مشابه في تعريفه. حتى الآن انها إدراج BOOL (القيمة الباحث). ونحن في طريقنا لتغيير هذا إلى إدراج BOOL (الباحث القيمة، شجرة * العقدة). ونحن في طريقنا لتغيير الواقع مرة أخرى في أن قليلا، وسنرى ماذا. ودعونا نقل build_node، لمجرد هيك منه، إدراج أعلاه بحيث لم يكن لدينا نموذج أولي لكتابة وظيفة. وهو إشارة إلى أن وأنت تسير إلى استخدام build_node في إدراج. حسنا. يستغرق دقيقة لذلك. أعتقد أنني أنقذت مراجعة إذا كنت ترغب في سحب من ذلك، أو، على الأقل، أنا فعلت الآن. كنت أرغب في كسر طفيف للتفكير في منطق إدراج، إذا كنت لا تستطيع التفكير في الأمر. في الأساس، وسوف يتم إدراج أي وقت مضى فقط في الأوراق. مثل، إذا كنت إدراج 1، ثم أنا ذاهب لا محالة إلى أن إدراج 1 - أنا تغيير إلى الأسود - I'll أن إدراج 1 فوق هنا. أو إذا كنت إدراج 4، أريد أن إدراج أكثر من 4 هنا. لذلك لا يهم ما تفعله، وأنت تسير أن يكون إدراج في ورقة. كل ما عليك القيام به هو تكرار أسفل الشجرة حتى تحصل إلى العقدة ينبغي أن يكون الأصل للعقدة، عقدة الأم الجديدة، ثم قم بتغيير المؤشر في اليمين أو اليسار، اعتمادا على ما إذا انها أكبر من أو أقل من العقدة الحالية. تغيير هذا المؤشر للإشارة إلى العقدة الجديدة. تكرار ذلك أسفل شجرة، وجعل نقطة أوراق إلى عقدة جديدة. أعتقد أيضا حول سبب الذي يمنع النوع من الحالات من قبل، حيث شيدت I الشجرة الثنائية حيث كان صحيحا إذا كنت تتطلع فقط في عقدة واحدة، ولكن كان 9 إلى اليسار من 7 إذا كنت يتحرك إلى أسفل على طول الطريق. بحيث من المستحيل في هذا السيناريو، منذ - أعتقد إدراج حوالي 9 أو شيء؛ في عقدة الأولى، أنا ذاهب لرؤية 7 و انا ذاهب للذهاب فقط إلى اليمين. لذلك لا يهم ما أقوم به، إذا أنا من خلال الذهاب الى إدراج ورقة، ورقة باستخدام خوارزمية مناسبة، انه سيكون من المستحيل بالنسبة لي أن إدراج 9 إلى اليسار من 7 لأن بمجرد أن تصل إلى 7 أنا ذاهب للذهاب إلى اليمين. هل لديها شيء لتبدأ؟ [طالب] أفعل. >> متأكد. [طالبة، غير مفهومة] [طالب آخر، غير مفهومة] [بودين] انها أعربت عن تقديرها. حسنا. أريد أن أشرح؟ 

[طالب] وبما أننا نعرف أن كنا إدراج العقد الجديد في نهاية الشجرة، I يحلق من خلال شجرة تكراري حتى وصلت إلى عقدة التي أشارت إلى قيمة خالية. وقررت بعد ذلك لوضعها إما على الجانب الأيمن أو الجانب الأيسر باستخدام هذا المتغير الحق؛ قيل لي أين وضعه. وبعد ذلك، أساسا، أنا الذي أدلى به للتو مشاركة - هذه النقطة عقدة إلى عقدة مؤقت جديد أنها خلق، إما على الجانب الأيسر أو على الجانب الأيمن، اعتمادا على ما قيمة كان على حق. وأخيرا، أنا وضعت القيمة عقدة جديدة إلى قيمة تجاربها. [بودين] حسنا، لذلك أرى هنا مسألة واحدة. هذا هو مثل 95٪ من الطريق إلى هناك. مسألة واحدة أن أرى، أيضا، لا ترى أي شخص آخر قضية؟ ما هو الظرف بموجبها الخروج من الحلقة؟ [طالب] إذا TEMP فارغة؟ نعم >>. فكيف لك الخروج من الحلقة إذا TEMP فارغة. ولكن ماذا أفعل هنا؟ I مؤقت إلغاء مرجعية، وهو باطل لا محالة. وبالتالي فإن الشيء الآخر الذي عليك القيام به هو لا تبقي فقط المسار حتى TEMP فارغة، كنت تريد أن تتبع الأم في جميع الأوقات. نريد أيضا العقدة الأصل *، أعتقد أننا يمكن أن تبقي في أن فارغة في البداية. هذا وستكون لدينا السلوك غريبة لجذر من شجرة، ولكن سوف نصل الى ذلك. إذا كانت القيمة أكبر من أيا كان، ثم TEMP = TEMP الحق. ولكن قبل أن نفعل ذلك، الوالد = TEMP. أو الآباء دائما ما يساوي درجة الحرارة؟ هو أن هذه القضية؟ إذا درجة الحرارة ليست فارغة، ثم أنا ذاهب للانتقال إلى الأسفل، مهما كانت، إلى عقدة درجة الحرارة التي هي الأصل. حتى الأم ستكون درجة الحرارة، ودرجة الحرارة ثم أنتقل إلى أسفل. الآن TEMP فارغة، ولكن نقطة الأصل إلى الأصل الشيء الذي فارغة. حتى هنا إلى أسفل، وأنا لا تريد تعيين يساوي حق 1. حتى انتقلت إلى اليمين، إذا كان الأمر كذلك الحق = 1، واعتقد انك تحتاج أيضا إلى القيام به - إذا قمت بنقل إلى اليسار، وتريد أن تعيين يساوي الحق إلى 0. وإلا إذا نقلت أي وقت مضى إلى اليمين. الحق في ذلك = 0. إذا 1 = الحق، الآن نحن نريد أن نجعل مؤشر الرئيسي newnode الحق، آخر ونحن نريد أن نجعل newnode الأم المؤشر الأيسر. الأسئلة على ذلك؟ حسنا. لذلك هذا هو الطريق ونحن - حسنا، في الواقع، بدلا من القيام بذلك، كنا نتوقع منك استخدام 1/2 build_node. ثم إذا newnode يساوي فارغة، عودة كاذبة. هذا هو ذلك. الآن، وهذا هو ما كنا نتوقعه منك القيام به. 

هذا هو ما فعله حلول الموظفين. أنا لا أتفق مع هذا باعتباره السبيل "الحق" لتحقيق ذلك ولكن هذا على ما يرام تماما وأنها ستعمل. شيء واحد وهذا هو الحق غريب قليلا الآن إذا الشجرة يبدأ لاغيا، نحن نمر في شجرة فارغة. اعتقد ان ذلك يعتمد على كيفية تعريف سلوك المارة في شجرة فارغة. وأعتقد أنه إذا كنت تمر في شجرة فارغة، ثم إدراج قيمة فارغة إلى شجرة يجب فقط العودة شجرة حيث القيمة الوحيدة هي أن عقدة واحدة. الناس توافق على ذلك؟ هل يمكن، إذا أردت، إذا كنت تمر في شجرة فارغة وتريد إدراج قيمة في ذلك، عودة كاذبة. والامر متروك لكم لتحديد ذلك. للقيام أول شيء قلته وبعد ذلك - حسنا، كنت ستكون لدينا مشكلة يفعل ذلك، لأن سيكون من الأسهل لو كان لدينا مؤشر العالمية إلى الشيء، لكننا لا، لذلك إذا شجرة فارغة، لا يوجد شيء يمكننا القيام به حيال ذلك. يمكننا العودة فقط كاذبة. لذلك أنا ذاهب الى تغيير إدراج. أننا يمكن أن مجرد تغيير من الناحية الفنية هذا الحق هنا، كيف انها بالتكرار عبر الأشياء، ولكن انا ذاهب الى تغيير إدراج لاتخاذ عقدة ** شجرة. مؤشرات ضعف. ماذا يعني هذا؟ بدلا من التعامل مع مؤشرات إلى العقد، الشيء انا ذاهب الى أن التلاعب هو هذا المؤشر. انا ذاهب الى أن هذا المؤشر التلاعب. انا ذاهب الى أن التلاعب مؤشرات مباشرة. هذا الأمر يبدو معقولا تماما منذ، والتفكير في أسفل - حسنا، الآن هذا يشير إلى قيمة خالية. ما أريد القيام به هو التلاعب هذا المؤشر للإشارة إلى غير فارغة. أريد أن أشير إلى عقدة بلدي جديد. إذا كنت تبقي فقط تتبع المؤشرات إلى مؤشرات بلدي، ثم أنا لست بحاجة إلى تتبع مؤشر الرئيسي. ويمكنني أن تبقي فقط المسار الصحيح لمعرفة ما اذا كان المؤشر يشير إلى قيمة خالية، وإذا كان المؤشر يشير إلى قيمة خالية، تغييره للإشارة إلى عقدة أريد. ويمكنني تغييره منذ لدي مؤشر إلى المؤشر. دعونا نرى هذا الحق الآن. يمكنك أن تفعل فعلا بشكل متكرر بسهولة جدا. نريد أن نفعل ذلك؟ نعم، ونحن نفعل. 

دعونا نرى ذلك بشكل متكرر. أولا، ما هو قضيتنا الأساسية ستكون؟ دائما تقريبا حالتنا قاعدة، ولكن في الواقع، وهذا هو نوع من صعبة. أول الأشياء أولا، إذا (== NULL شجرة) أعتقد أننا ذاهبون فقط للعودة كاذبة. هذا يختلف عن شجرة خالية جودكم. هذا هو مؤشر إلى مؤشر الجذر يتم فارغة وهو ما يعني أن المؤشر الجذر غير موجود. حتى هنا إلى أسفل، إذا كنت تفعل * عقدة - دعونا فقط إعادة استخدام هذا. * عقدة الجذر = NULL، ومن ثم أنا ذاهب للدعوة عن طريق القيام إدراج شيء من هذا القبيل، إدراج 4 في والجذر. وذلك الجذر، إذا هو الجذر * العقدة ثم والجذر وستكون ** العقدة. هذا صحيح. في هذه الحالة، شجرة، هنا، الشجرة ليست فارغة - أو إدراج. هنا. الشجرة ليست فارغة؛ * شجرة فارغة، التي على ما يرام لأنه إذا شجرة * فارغة، ثم لا أستطيع التلاعب به للإشارة الآن إلى ما أريد أن أشير إليه. ولكن إذا شجرة باطل، وهذا يعني جئت إلى هنا فقط وقال فارغة. لا معنى له. لا أستطيع أن أفعل أي شيء في ذلك. إذا شجرة فارغة، عودة كاذبة. لذلك أنا بالفعل أساسا ما قال حالتنا الحقيقية هي قاعدة. وما أن سيكون؟ [طالبة، غير مفهومة] [بودين] نعم. إذا كان الأمر كذلك (* شجرة == NULL). هذه القضية تتعلق أكثر من هنا حيث إذا ضعي أحمر المؤشر هو مؤشر تركيزي ينصب على، ذلك مثل تركيزي ينصب على هذا المؤشر، والآن تركيزي ينصب على هذا المؤشر. الآن تركيزي ينصب على هذا المؤشر. إذا كان الأمر كذلك مؤشر ضعي أحمر، وهو عقدة ** بلدي، من أي وقت مضى - إذا *، ضعي أحمر المؤشر، فارغة من أي وقت مضى، وهذا يعني أنني في حال أنا مع التركيز على مؤشر يشير - هذا هو المؤشر الذي ينتمي إلى ورقة. أريد تغيير هذا المؤشر للإشارة إلى عقدة بلدي جديد. العودة إلى هنا. وسوف يكون مجرد بلدي newnode عقدة * ن = build_node (القيمة) ثم ن، ن = إذا NULL، عودة كاذبة. آخر ونحن نريد لتغيير ما يشير المؤشر حاليا للإشارة إلى عقدة لدينا الآن بنيت حديثا. يمكننا أن نفعل ذلك هنا في الواقع. بدلا من أن تقول لا، ونحن نقول * = شجرة شجرة * إذا. الجميع يفهم ذلك؟ أنه من خلال التعامل مع المؤشرات إلى مؤشرات، يمكننا تغيير مؤشرات فارغة للإشارة إلى الأشياء التي تريد لهم للإشارة إلى. هذا حالتنا القاعدة. 

الآن لدينا تكرار، أو العودية لدينا، ستكون مشابهة جدا لجميع recursions أخرى كنا نقوم به. نحن ذاهبون الى تريد إدراج القيمة، والآن انا ذاهب الى استخدام الثلاثي مرة أخرى، ولكن ما هي حالتنا ستكون؟ ما هو نحن نبحث عن لتقرر ما إذا كنا نريد أن يذهب إلى اليمين أو اليسار؟ دعونا نفعل ذلك في خطوات منفصلة. إذا (القيمة <) ماذا؟ [طالب] القيمة الشجرة؟ [بودين] لذا تذكر أن أنا حاليا - [طلاب، غير مفهومة] [بودين] نعم، لذلك هنا، دعنا نقول أن هذا السهم الأخضر هو مثال على ما شجرة حاليا، هو مؤشر إلى هذا المؤشر. وهذا يعني انا مؤشر إلى مؤشر إلى 3. وبدا مرتين إلغاء مرجعية جيدة. ماذا I - كيف أفعل ذلك؟ [طالب] إلغاء مرجعية واحدة، ومن ثم القيام سهم بهذه الطريقة؟ [بودين] لذلك (* شجرة) هو إلغاء مرجعية واحدة، -> قيمة سوف تعطيني قيمة العقدة التي أنا مشيرا بشكل غير مباشر إلى. حتى أتمكن من الكتابة أيضا tree.value ** إذا كنت تفضل ذلك. إما يعمل. إذا كان هذا هو الحال، ثم أريد أن أدعو إدراج مع القيمة. وما هو عقدة بلدي تحديث ** ستكون؟ أريد أن أذهب إلى اليسار، لذلك ** tree.left ستكون يساري. وأريد المؤشر إلى هذا الشيء بحيث إذا كان اليسار ينتهي به الأمر على مؤشر فارغة، يمكنني تعديله للإشارة إلى عقدة بلدي جديد. 

ويمكن للحالة أخرى تكون مشابهة جدا. دعونا جعل الواقع أن الثلاثي بلدي في الوقت الحالي. إدراج قيمة إذا القيمة <(** شجرة). القيمة. ثم نريد أن تحديث ** لدينا إلى اليسار، آخر تحديث نريد أن ** لدينا إلى اليمين. [طالب] هل الحصول على هذا المؤشر إلى مؤشر؟ [بودين] تذكر أن - ** tree.right هو نجم العقدة. [طالبة، غير مفهومة] >> نعم. tree.right ** مثل هذا المؤشر أو شيء. ذلك عن طريق أخذ مؤشر إلى ذلك، أن يعطيني ما أريد من المؤشر لهذا الرجل. [طالب] ويمكننا أن نذهب من جديد لماذا نحن نستخدم مؤشرات اثنين؟ [بودين] نعم. لذلك - لا، يمكنك، والحل الذي قبل كان وسيلة للقيام بذلك دون القيام اثنين المؤشرات. عليك أن تكون قادرا على فهم باستخدام اثنين من المؤشرات، وهذا هو الحل الأكثر نظافة. أيضا، لاحظ أن، ماذا يحدث إذا شجرة بلدي - ماذا يحدث إذا الجذر بلدي لاغ؟ ماذا يحدث إذا كنت تفعل هذه الحالة هنا أليس كذلك؟ حتى عقدة الجذر * = NULL، أدخل 4 في والجذر. ما لدي الآن هو جذور سيكون بعد ذلك؟ [طالبة، غير مفهومة] >> نعم. قيمة الجذر ستكون 4. اليسار الجذري ستكون باطلة، والحق الجذر ستكون فارغة. وفي حالة ما إذا لم نكن تمرير الجذر حسب العنوان، لم نتمكن من تعديل الجذر. في الحالة التي يكون فيها شجرة - الجذر حيث لاغ، كان لدينا فقط لعودة كاذبة. لا يوجد شيء يمكننا القيام به. لا يمكننا إدراج عقدة في شجرة فارغة. ولكن يمكن الآن لدينا، ونحن جعل مجرد شجرة إلى شجرة فارغة واحدة العقدة. التي عادة ما تكون الطريقة المتوقعة التي من المفترض أن تعمل. 

وعلاوة على ذلك، وهذا هو أقصر بكثير من حفظ المسار أيضا من الأم، وحتى تتمكن تكرار أسفل على طول الطريق. الآن لدي والدي، وأنا فقط مؤشر حقي الأصل إلى غير ذلك. بدلا من ذلك، إذا فعلنا هذا تكراري، ويهمني أن يكون نفس الفكرة مع حلقة من الوقت. ولكن بدلا من الاضطرار إلى التعامل مع المؤشر والدي، وبدلا من ذلك مؤشر بلدي الحالي يكون الشيء انني تعديل مباشرة للإشارة إلى عقدة بلدي جديد. ليس لدي للتعامل مع سواء كان ذلك يشير إلى اليسار. ليس لدي للتعامل مع سواء كان ذلك يشير إلى اليمين. انها مجرد ما هذا المؤشر، وانا ذاهب لتعيين أنه للإشارة إلى عقدة بلدي جديد. الجميع يفهم كيف يعمل؟ إذا لماذا لا نريد أن نفعل ذلك بهذه الطريقة، ولكن على الأقل أن يعمل هذا كحل؟ [طالب] أين نعود صحيح؟ [بودين] وربما كان هنا. إذا كان لنا أن إدراج بشكل صحيح، والعودة الحقيقية. آخر، إلى هنا ونحن في طريقنا إلى العودة يريدون العودة إدراج أيا كان. 

وما هو خاص حول هذا ظيفة العودية؟ انها متكررة الذيل، وذلك دمنا ترجمة مع بعض التحسين، سوف ندرك أن وأنك لن تحصل على تجاوز سعة مكدس من هذا، حتى لو لديها شجرة على ارتفاع 10،000 أو 10 مليون. [طالبة، غير مفهومة] [بودين] أعتقد أنه يفعل ذلك في داش - أو ما هو مستوى التحسين مطلوب لالعودية ذيل ليتم الاعتراف بها. أعتقد أنها تعترف - دول مجلس التعاون الخليجي وضجيج أيضا معاني مختلفة لمستويات التحسين الخاصة بهم. أريد أن أقول انها داشو 2، لعلى يقين من أنه سوف تعترف العودية الذيل. ولكننا - هل يمكن أن بناء مثل Fibonocci سبيل المثال أو شيء. انها ليست سهلة لاختبار مع هذا، لأنه من الصعب لبناء شجرة ثنائية هذا كبيرة جدا. ولكن نعم، اعتقد انه من داشو 2، أن إذا كنت ترجمة مع داشو 2، فإنه سيتم البحث عن العودية ذيل وأنه من الأمثل. دعونا نعود إلى - إدراج حرفيا وآخر شيء تحتاجه. دعونا نعود إلى إدراج أكثر من هنا أين نحن في طريقنا للقيام نفس الفكرة. وأنها سوف لا تزال لديها عيب من عدم القدرة على التعامل مع تماما عندما الجذر نفسه لاغيا، أو دخول الماضية فارغة، ولكن بدلا من التعامل مع مؤشر الرئيسي، دعونا تطبيق نفس المنطق من المؤشرات لحفظ المؤشرات. إذا واصلنا هنا لدينا عقدة ** الحالي، ونحن لسنا بحاجة لتتبع الحق بعد الآن، ولكن عقدة الحالي ** = & شجرة. والآن لدينا حلقة في حين ستكون في حين الحالي * هل غير فارغة متساوية. لا تحتاج إلى تتبع الآباء بعد الآن. لا تحتاج إلى تتبع اليسار واليمين. وسوف أسميها مؤقت، لأننا بالفعل باستخدام مؤقت. حسنا. إذا كان الأمر كذلك (القيمة> * مؤقت)، ثم و(* TEMP) -> الحق آخر TEMP = & (* TEMP) -> اليسار. والآن، في هذه المرحلة، وبعد هذه الحلقة من الوقت، أفعل هذا فقط لأنه ربما يكون من الأسهل على التفكير بشكل متكرر من تكراري عن، ولكن بعد هذه الحلقة من الوقت، * درجة الحرارة هو مؤشر نريد للتغيير. 

كان لدينا قبل الوالدين، وكنا نرغب في تغيير إما اليسار الوالدين أو الوالدين الحق، ولكن إذا أردنا تغيير حق الوالدين، * ثم TEMP هو حق الوالدين، ويمكننا تغييره مباشرة. حتى هنا إلى أسفل، يمكننا أن نفعل * TEMP = newnode، وهذا كل شيء. حتى إشعار، كل ما فعلناه هو في هذا إخراج الأسطر من التعليمات البرمجية. من أجل تتبع الأصل في كل ما هو جهد إضافي. هنا، إذا كنا نستمر مسار المؤشر إلى المؤشر، وحتى لو أردنا أن نتخلص من كل هذه الأقواس المتعرجة الآن، جعلها تبدو أقصر. هذا هو الحل الآن بالضبط نفس، لكن أقل الأسطر من التعليمات البرمجية. بمجرد البدء في الاعتراف بهذه كحل صالح، كما أنه من الأسهل لسبب من مجرد مثل، حسنا، لماذا لدي هذه العلامة في حق الباحث؟ ماذا يعني ذلك؟ أوه، أنها مما يدل على أن في كل مرة أذهب الحق، ولست بحاجة لتعيين أنه، آخر إذا ذهبت تركت تحتاج إلى تعيين إلى صفر. هنا، وأنا لم يكن لديك سبب لعن ذلك، بل من الأسهل لمجرد التفكير فيها. الأسئلة؟ [طالبة، غير مفهومة] >> نعم. حسنا، وذلك في الجزء الأخير - أعتقد وظيفة واحدة سريعة وسهلة يمكننا القيام به هو، let's - معا، وأعتقد، ومحاولة إرسال بريد يحتوي على وظيفة الذي لا يهمه ما إذا كان من شجرة البحث الثنائية. هذا يتضمن وظيفة يجب العودة الحقيقية إذا في أي مكان في هذه الشجرة الثنائية العام هو القيمة التي تبحث عنها. لذلك دعونا نفعل لأول مرة بشكل متكرر وبعد ذلك نحن سوف نفعل ذلك تكرارا. يمكننا في الواقع مجرد القيام بذلك معا، لأن هذا سيكون حقا قصيرة. 

ما حالتي قاعدة ستكون؟ [طالبة، غير مفهومة] [بودين] حتى إذا (== شجرة NULL)، ثم ماذا؟ [طالب] عودة كاذبة. [بودين] أخرى، حسنا، أنا لا يحتاجون إلى آخر. إذا كان حالتي قاعدة أخرى. [طالب] شجرة في القيمة؟ نعم >>. إذا كان الأمر كذلك (القيمة == شجرة> القيمة. تلاحظ نعود إلى * العقدة، عقدة لا ** ق؟ سوف يحتوي أبدا إلى استخدام ** العقدة، بما أننا لا تعديل المؤشرات. نحن يجتاز منهم فقط. اذا ما حدث ذلك، ثم نريد أن العودة الحقيقية. آخر ونحن نريد أن تجتاز الأطفال. حتى نتمكن من ليس سببا حول ما إذا كان كل شيء على يسار أقل وكل شيء إلى اليمين أكبر. فما هي حالتنا ستكون هنا - أو، ماذا نحن فاعلون؟ [طالبة، غير مفهومة] >> نعم. عودة يحتوي على (القيمة، شجرة> يسار) أو يحتوي على (القيمة، شجرة> الحق). وهذا كل شيء. وتلاحظ وجود بعض التقييم دائرة قصر، حيث إذا كنا يحدث لتجد القيمة في شجرة اليسار، نحن لا نحتاج إلى النظر في الشجرة الحق. هذا هو وظيفة كاملة. الآن دعونا نفعل ذلك تكرارا، التي ستكون أقل لطيفة. سوف نأخذ بداية من المعتاد الحالي * العقدة = شجرة. في حين أن (الحالي! = NULL). الذهاب بسرعة لرؤية المشكلة. إذا الحالي - من هنا، إذا ما تم كسر أي وقت مضى للخروج من هذا، ثم قمنا ينفد من الاشياء لننظر، حتى يعود كاذبة. إذا (الحالي> == قيمة القيمة)، والعودة الحقيقية. حتى الآن، ونحن في مكان - نحن لا نعرف ما إذا كنا نريد أن يذهب إلى اليمين أو اليسار. تعسفي لذا، دعونا فقط يتجه يسارا. لقد تشغيل I الواضح أن مسألة حيث كنت التخلي تماما كل شيء - وسوف تحقق فقط من أي وقت مضى على الجانب الأيسر من شجرة. أنا لن تحقق أي شيء للطفل الحق في أي شيء. كيف يمكنني تصحيح هذا؟ [طالب] عليك أن تتبع اليسار واليمين في كومة. [بودين] نعم. لذلك دعونا تجعل من البنية القائمة، عقدة * N، والعقدة ثم ** القادمة؟ أعتقد أن يعمل بشكل جيد. نريد أن يذهب أكثر من اليسار، أو let's - حتى هنا. = قائمة البنية القائمة، أنها سوف تبدأ من هذه القائمة في البنية. * قائمة = NULL. بحيث سيكون لدينا قائمة مرتبطة من الأشجار الفرعية أن لدينا أكثر من تخطي. نحن نذهب لاجتياز غادر الآن، ولكن بما أننا في حاجة حتما إلى العودة إلى الحق، ونحن في طريقنا للحفاظ على الجانب الأيمن من قائمة داخل البنية دينا. فلن تكون لدينا new_list أو البنية، * البنية القائمة، new_list = malloc (sizeof (قائمة)). انا ذاهب الى تجاهل الأخطاء التدقيق ذلك، ولكن يجب أن تحقق لمعرفة ما إذا كان لاغيا. New_list العقدة انه سيكون للإشارة إلى - أوه، هذا هو السبب في أنني أرغب في ذلك هنا. انه سيكون للإشارة إلى قائمة البنية الثانية. هذه هي الطريقة فقط مرتبطة قوائم العمل. هذا هو نفس قائمة الباحث مرتبطة إلا أننا مجرد استبدال الباحث مع * العقدة. انها بالضبط نفس الشيء. new_list ذلك، فإن قيمة عقدة new_list لدينا، ستكون الحالي> الحق. قيمة لدينا new_list-> التالي ستكون لدينا قائمة الأصلي، ثم ونحن في طريقنا لاستكمال قائمتنا للإشارة إلى new_list. 

الآن نحن بحاجة نوعا من طريقة لسحب الأشياء، لقد قطعنا مثل الشجرة الفرعية بالكامل اليسار. الآن نحن بحاجة لسحب الاشياء للخروج منه، مثل الحالي باطل، ونحن لا نريد العودة فقط كاذبة. نريد الآن لسحب خارج في قائمتنا الجديدة. وهناك طريقة مريحة للقيام بذلك - حسنا، في الواقع، هناك عدة طرق للقيام بذلك. أي شخص يحصل على الاقتراح؟ حيث يجب أن أفعل هذا أو كيف يجب أن تفعل ذلك؟ ليس لدينا سوى بضع دقائق، ولكن أي اقتراحات؟ بدلا من - طريقة واحدة، بدلا من حالة جودنا في حين، ما نحن نبحث حاليا ليست في فارغة، بدلا من ذلك نحن ذاهبون الى مواصلة للذهاب حتى قائمتنا نفسها هي فارغة. إذا كان الأمر كذلك قائمتنا ينتهي به الأمر فارغة، ثم قمت بتشغيل نحن من الأشياء للبحث عن، للبحث أكثر. ولكن هذا يعني أن أول شيء في قائمتنا هو مجرد الذهاب الى تكون العقدة الأولى. فإن أول شيء جدا أن تكون - لم نعد بحاجة الى ان نرى ذلك. حتى قائمة> ن ستكون لدينا شجرة. قائمة> القادمة ستكون فارغة. والآن بينما لا قائمة فارغة متساوية. الحالي هو الذهاب الى سحب شيء من قائمتنا. حتى الحالي هو الذهاب الى قائمة متساوية> ن. ومن ثم يتم الانتقال إلى قائمة المساواة القائمة>-N، أو قائمة>. المقبل حتى إذا كانت القيمة تساوي قيمة الحالي. الآن يمكننا أن نضيف على حد سواء لدينا مؤشر ومؤشر لدينا الحق اليسار طالما انهم غير فارغة. إلى هنا، وأنا أعتقد أننا يجب أن نفعل ذلك في المقام الأول. إذا (الحالي> الحق! = NULL) ثم نحن نذهب لادخال تلك العقدة في قائمتنا. إذا (الحالي> اليسار)، وهذا هو القليل من العمل الاضافي، ولكن هذا ما يرام. إذا (الحالي> اليسار! = NULL)، ونحن في طريقنا لإدراج اليسار إلى قائمتنا المرتبطة، وينبغي أن يكون عليه. نحن تكرار - ما دام لدينا شيء في قائمتنا، لدينا عقدة أخرى للنظر في. لذلك نحن ننظر إلى تلك العقدة، نحن نتقدم قائمتنا إلى المرحلة التالية. إذا كان هذا هو قيمة عقدة نحن تبحث عنه، يمكننا العودة الحقيقية. إدراج كل الأشجار الفرعية آخر لدينا اليسار واليمين، طالما انهم غير فارغة، إلى قائمتنا بحيث نذهب حتما عليها. إذا كان الأمر كذلك لم تكن فارغة، فإذا قال لدينا مؤشر الجذر إلى أمرين، ثم انسحبت في البداية شيء من ذلك ونحن لدينا قائمة ينتهي به الأمر فارغة. ثم نضع نحن أمرين مرة أخرى، وحتى الآن لدينا قائمة من حجم 2. ثم ونحن في طريقنا إلى حلقة احتياطية ونحن مجرد الذهاب الى سحب، دعنا نقول، المؤشر الأيسر من عقدة الجذر لدينا. وسوف نستمر أن يحدث، ونحن سوف ينتهي حلقات على كل شيء. 

لاحظ أن هذا كان أكثر تعقيدا بكثير في حل العودية. ولقد قلت عدة مرات أن الحل متكررة عادة الكثير من القواسم المشتركة مع تكرارية الحل. هنا هذا هو بالضبط ما الحل متكررة يقوم به. التغيير الوحيد هو أنه بدلا من استخدام ضمنا المكدس، مكدس البرنامج، كما طريقك لمتابعة ما كنت لا تزال بحاجة العقد للزيارة، الآن لديك لاستخدام قائمة مرتبطة بشكل واضح. في كلتا الحالتين كنت تتبع ما العقدة لا تزال بحاجة إلى زيارتها. في حالة العودية أنه من الأسهل لمجرد كومة وينفذ لك ومكدس البرنامج. تلاحظ أن هذه القائمة مرتبطة، بل هو مكدس. مهما وضعنا فقط على المكدس هو على الفور ما نحن ذاهبون لسحب قبالة كومة لزيارة المقبل. نحن في الخارج من الوقت، ولكن أي أسئلة؟ [طالبة، غير مفهومة] [بودين] نعم. إذا كان الأمر كذلك لدينا قائمتنا مرتبط، يجري حاليا للإشارة إلى هذا الرجل، ونحن الآن تقدم فقط قائمتنا مرتبط إلى التركيز على هذا الرجل. نحن العبور على قائمة مرتبطة في هذا الخط. ومن ثم أعتقد أننا ينبغي تحرير قائمتنا المرتبطة والاشياء مرة واحدة قبل أن يعود صحيحة أو خاطئة، ونحن بحاجة إلى تكرار عبر قائمتنا مرتبطة دائما أسفل وهنا، أعتقد، إذا كنا الحالي هو حق لا يساوي، إضافته، وحتى الآن نحن نريد لتحرير لأن الحالي، حسنا، نحن لم ننسى تماما عن القائمة؟ نعم. وهذا ما نريد أن نفعله هنا. أين المؤشر؟ كان الحالي ثم - نحن نريد أن قائمة البنية * 10 يساوي القائمة التالي. قائمة حرة، قائمة = TEMP. وفي حالة ما إذا نعود صحيح، ونحن بحاجة إلى تكرار طوال ما تبقى من قائمتنا المرتبطة تحرير الأشياء. والشيء الجميل في حل العودية وتحرير الأشياء يعني فقط factorings ظهرت قبالة كومة الذي سيحدث لك. حتى لقد ذهبنا من شيء مثل 3 خطوط من يصعب التفكير حول رمز إلى ما هو أكثر بكثير كثير يصعب التفكير حول الأسطر من التعليمات البرمجية. أي أسئلة أخرى؟ حسنا. نحن في حالة جيدة. وداعا! [CS50.TV]