1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [القسم 7] [أقل راحة]

2
00:00:02,500 --> 00:00:04,890
[نيت Hardison] [جامعة هارفارد]

3
00:00:04,890 --> 00:00:07,000
[هذا CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> مرحبا بكم في القسم 7.

5
00:00:09,080 --> 00:00:11,330
بفضل إعصار ساندي

6
00:00:11,330 --> 00:00:13,440
بدلا من وجود القسم العادي من هذا الأسبوع،

7
00:00:13,440 --> 00:00:17,650
نحن نفعل ذلك من خلال المشي، من خلال قسم من الأسئلة.

8
00:00:17,650 --> 00:00:22,830
انا ذاهب الى أن بعد طول مع مشكلة تعيين 6 مواصفات،

9
00:00:22,830 --> 00:00:25,650
ويمر على جميع الأسئلة في

10
00:00:25,650 --> 00:00:27,770
مقطع من قسم شؤون.

11
00:00:27,770 --> 00:00:30,940
إذا كان هناك أي أسئلة،

12
00:00:30,940 --> 00:00:32,960
الرجاء نشر هذه على ناقش CS50.

13
00:00:32,960 --> 00:00:35,480
>> بخير. دعونا نبدأ.

14
00:00:35,480 --> 00:00:40,780
الآن أنا أبحث في الصفحة 3 من مشكلة مواصفات مجموعة.

15
00:00:40,780 --> 00:00:44,110
ونحن في طريقنا للبدء أولا نتحدث عن الأشجار الثنائية

16
00:00:44,110 --> 00:00:47,850
منذ تلك ديهم الكثير من الأهمية لمجموعة مشكلة هذا الأسبوع -

17
00:00:47,850 --> 00:00:49,950
ترميز هوفمان شجرة.

18
00:00:49,950 --> 00:00:55,000
كان واحدا من هياكل البيانات الأولى تحدثنا عن CS50 على الصفيف.

19
00:00:55,000 --> 00:01:00,170
تذكر أن مجموعة هو سلسلة من العناصر -

20
00:01:00,170 --> 00:01:04,019
جميع من نفس النوع - تخزينها بجوار بعضها البعض في الذاكرة.

21
00:01:04,019 --> 00:01:14,420
إذا كان لدي مجموعة صحيحا أستطيع أن أوجه استخدام هذا النمط صناديق أرقام صحيحة، -

22
00:01:14,420 --> 00:01:20,290
دعنا نقول لدي 5 في المربع الأول، ولدي 7 في الثانية،

23
00:01:20,290 --> 00:01:27,760
ثم لدي 8، 10، و 20 في المربع النهائي.

24
00:01:27,760 --> 00:01:33,000
تذكر، وهما حقا جيدة الأشياء عن هذه المجموعة

25
00:01:33,000 --> 00:01:38,800
هي أن لدينا هذا الوصول المستمر لمرة وإلى أي عنصر معين

26
00:01:38,800 --> 00:01:40,500
 في الصفيف إذا علمنا مؤشره.

27
00:01:40,500 --> 00:01:44,670
على سبيل المثال، إذا كنت ترغب في الاستيلاء على العنصر الثالث في مجموعة -

28
00:01:44,670 --> 00:01:47,870
في مؤشر 2 باستخدام نظامنا الفهرسة الصفرية -

29
00:01:47,870 --> 00:01:52,220
I حرفيا فقط لتفعل عملية حسابية بسيطة الرياضية،

30
00:01:52,220 --> 00:01:56,170
قفز إلى هذا الموقف في الصفيف،

31
00:01:56,170 --> 00:01:57,840
سحب ال 8 التي تم تخزينها هناك،

32
00:01:57,840 --> 00:01:59,260
وأنا على ما يرام.

33
00:01:59,260 --> 00:02:03,350
>> واحدة من أشياء سيئة عن هذه المجموعة - التي تحدثنا عنها

34
00:02:03,350 --> 00:02:05,010
عندما ناقشنا القوائم المرتبطة -

35
00:02:05,010 --> 00:02:09,120
هو أنه إذا كنت تريد إدراج عنصر في هذه المجموعة،

36
00:02:09,120 --> 00:02:11,090
انا ذاهب الى القيام به بعض التحول حولها.

37
00:02:11,090 --> 00:02:12,940
على سبيل المثال، هذه المجموعة هنا

38
00:02:12,940 --> 00:02:16,850
في ترتيب فرزها - غير مصنفة -

39
00:02:16,850 --> 00:02:19,440
5 و 7 ثم، ثم 8، ثم 10، ثم 20 -

40
00:02:19,440 --> 00:02:23,100
ولكن إذا كنت تريد إدراج الرقم 9 في هذه المجموعة،

41
00:02:23,100 --> 00:02:27,460
أنا ذاهب لدينا لتحويل بعض العناصر من أجل جعل الفضاء.

42
00:02:27,460 --> 00:02:30,440
يمكننا رسم هذا هنا.

43
00:02:30,440 --> 00:02:35,650
انا ذاهب الى أن تقوم بتحريك 5، 7، ثم 8؛

44
00:02:35,650 --> 00:02:38,720
خلق فجوة أين يمكنني وضع 9،

45
00:02:38,720 --> 00:02:45,910
وبعد ذلك يمكن لل10 و 20 انتقل إلى يمين 9.

46
00:02:45,910 --> 00:02:49,450
هذا هو نوع من الألم لأنه في أسوأ سيناريو -

47
00:02:49,450 --> 00:02:54,350
في وقت نواجه فيه الحاجة إلى إدراج إما في بداية أو في نهاية

48
00:02:54,350 --> 00:02:56,040
من الصفيف، وهذا يتوقف على مستوى قيامنا تحويل -

49
00:02:56,040 --> 00:02:58,850
ونحن قد ينتهي بعد لتحويل كل العناصر

50
00:02:58,850 --> 00:03:00,750
اننا حاليا في تخزين الصفيف.

51
00:03:00,750 --> 00:03:03,810
>> الأمر كذلك، فما هو السبيل للتغلب على هذه؟

52
00:03:03,810 --> 00:03:09,260
هو السبيل للتغلب على هذه الطريقة للذهاب الى لدينا قائمة مرتبطة-حيث -

53
00:03:09,260 --> 00:03:19,820
بدلا من تخزين العناصر 5 و 7 و 8 و 10 و 20 جميع بجانب بعضها البعض في الذاكرة -

54
00:03:19,820 --> 00:03:25,630
ما فعلته هو بدلا تخزينها نوع من أينما كنا نريد لتخزينها

55
00:03:25,630 --> 00:03:32,470
في هذه العقد القائمة المرتبطة والتي أنا استخلاص هنا، النوع المخصص.

56
00:03:32,470 --> 00:03:42,060
وبعد ذلك توصيلها معا باستخدام هذه المؤشرات القادمة.

57
00:03:42,060 --> 00:03:44,370
الأول يمكن أن يكون مؤشر في الفترة من 5 إلى 7،

58
00:03:44,370 --> 00:03:46,420
مؤشر من 7 إلى 8،

59
00:03:46,420 --> 00:03:47,770
مؤشر من 8 إلى 10،

60
00:03:47,770 --> 00:03:51,220
وأخيرا، مؤشر من 10 إلى 20،

61
00:03:51,220 --> 00:03:54,880
ثم مؤشر فارغة في ال 20 مشيرا إلى أن لا يوجد شيء اليسار.

62
00:03:54,880 --> 00:03:59,690
المفاضلة التي لدينا هنا

63
00:03:59,690 --> 00:04:05,360
الآن هو أن إذا كنا نريد لإدراج رقم 9 الى قائمتنا فرزها،

64
00:04:05,360 --> 00:04:08,270
كل ما عليك القيام به هو إنشاء عقدة جديدة مع 9،

65
00:04:08,270 --> 00:04:12,290
سلك ليصل إلى الإشارة إلى المكان المناسب،

66
00:04:12,290 --> 00:04:20,630
ومن ثم إعادة الأسلاك 8 إلى نقطة وصولا الى 9.

67
00:04:20,630 --> 00:04:25,660
هذا سريع جدا، على افتراض أننا نعرف بالضبط أين نريد أن إدراج 9.

68
00:04:25,660 --> 00:04:32,610
ولكن المفاضلة في مقابل ذلك هو أن فقدنا الآن وصول مستمر في الوقت

69
00:04:32,610 --> 00:04:36,230
إلى أي عنصر معين في بنية البيانات المتوفرة لدينا.

70
00:04:36,230 --> 00:04:40,950
على سبيل المثال، إذا كنت تريد العثور على العنصر الرابع في هذه القائمة المرتبطة،

71
00:04:40,950 --> 00:04:43,510
انا ذاهب الى أن تبدأ في بداية القائمة

72
00:04:43,510 --> 00:04:48,930
والعمل في طريقي من خلال العد عقدة تلو عقدة حتى أجد واحدة الرابع.

73
00:04:48,930 --> 00:04:55,870
>> من أجل الحصول على أفضل أداء من الوصول قائمة مرتبطة -

74
00:04:55,870 --> 00:04:59,360
ولكن أيضا الاحتفاظ بعض الفوائد التي كانت لدينا

75
00:04:59,360 --> 00:05:01,800
من حيث الوقت الإدراج من قائمة مرتبطة -

76
00:05:01,800 --> 00:05:05,750
شجرة ثنائية سوف تحتاج إلى استخدام الذاكرة أكثر من ذلك بقليل.

77
00:05:05,750 --> 00:05:11,460
على وجه الخصوص، بدلا من الاضطرار مؤشر واحد فقط في عقدة شجرة ثنائية -

78
00:05:11,460 --> 00:05:13,350
مثل القائمة المرتبطة عقدة لا -

79
00:05:13,350 --> 00:05:16,950
ونحن في طريقنا لإضافة مؤشر الثاني إلى عقدة شجرة ثنائية.

80
00:05:16,950 --> 00:05:19,950
بدلا من الاضطرار مؤشر واحد فقط إلى العنصر التالي،

81
00:05:19,950 --> 00:05:24,420
نحن ستكون لدينا مؤشر إلى اليسار الطفل وطفل الحق.

82
00:05:24,420 --> 00:05:26,560
>> دعونا رسم صورة لنرى ما الذي يبدو في الواقع مثل.

83
00:05:26,560 --> 00:05:31,350
مرة أخرى، انا ذاهب الى استخدام هذه الصناديق والسهام.

84
00:05:31,350 --> 00:05:37,150
وهناك عقدة شجرة ثنائية تبدأ مع مربع واحد فقط بسيطة.

85
00:05:37,150 --> 00:05:40,940
انها ستكون لدينا مساحة للقيمة،

86
00:05:40,940 --> 00:05:47,280
وبعد ذلك يحدث أيضا أن يكون لها مساحة للطفل الأيسر والطفل الصحيح.

87
00:05:47,280 --> 00:05:49,280
أنا ذاهب لتسمية لهم هنا.

88
00:05:49,280 --> 00:05:57,560
ونحن في طريقنا لجعل الطفل الأيسر، ثم نحن ستكون لدينا الحق للطفل.

89
00:05:57,560 --> 00:05:59,920
هناك العديد من الطرق المختلفة للقيام بذلك.

90
00:05:59,920 --> 00:06:02,050
في بعض الأحيان لالفضاء والراحة،

91
00:06:02,050 --> 00:06:06,460
أنا فعلا مثل رسم أفعله هنا على الجزء السفلي

92
00:06:06,460 --> 00:06:10,910
حيث أنا ذاهب ليكون في أعلى قيمة،

93
00:06:10,910 --> 00:06:14,060
ومن ثم حق الطفل على اليمين أسفل،

94
00:06:14,060 --> 00:06:16,060
والطفل الأيسر على اليسار من الأسفل.

95
00:06:16,060 --> 00:06:20,250
العودة إلى أعلى هذا المخطط،

96
00:06:20,250 --> 00:06:22,560
لدينا قيمة في أعلى جدا،

97
00:06:22,560 --> 00:06:25,560
ثم لدينا مؤشر اليسار الطفل، ومن ثم لدينا مؤشر الماوس الأيمن الأطفال.

98
00:06:25,560 --> 00:06:30,110
>> مشكلة في مواصفات مجموعة،

99
00:06:30,110 --> 00:06:33,110
نتحدث عن رسم العقدة التي لديها قيمة 7،

100
00:06:33,110 --> 00:06:39,750
ثم مؤشر اليسار الأطفال الذي فارغة، ومؤشر الماوس الأيمن الأطفال الذي فارغة.

101
00:06:39,750 --> 00:06:46,040
يمكن أن نكتب إما NULL رأس المال في الفضاء ل

102
00:06:46,040 --> 00:06:51,610
يمكن كل من اليسار والطفل الطفل الحق، أو وضعنا هذه القطع قطري

103
00:06:51,610 --> 00:06:53,750
من خلال كل من مربعات للإشارة إلى أنه من فارغة.

104
00:06:53,750 --> 00:06:57,560
انا ذاهب للقيام بذلك لمجرد أن هذا أكثر بساطة.

105
00:06:57,560 --> 00:07:03,700
ما تراه هنا طريقتان لإنشاء المخططات شجرة ثنائية بسيطة جدا العقدة

106
00:07:03,700 --> 00:07:07,960
حيث لدينا قيمة 7 و الطفل مؤشرات فارغة.

107
00:07:07,960 --> 00:07:15,220
>> الجزء الثاني من المحادثات حول كيفية مواصفات لدينا مع القوائم المرتبطة -

108
00:07:15,220 --> 00:07:18,270
تذكر، كان لدينا فقط على التمسك العنصر الأول في قائمة جدا

109
00:07:18,270 --> 00:07:20,270
أن نتذكر القائمة بأكملها -

110
00:07:20,270 --> 00:07:26,140
وبالمثل، مع شجرة ثنائية، لدينا فقط لعقد واحد على مؤشر إلى شجرة

111
00:07:26,140 --> 00:07:31,120
من أجل الحفاظ على السيطرة على بنية البيانات بالكامل.

112
00:07:31,120 --> 00:07:36,150
ويسمى هذا العنصر الخاص للشجرة عقدة جذر الشجرة.

113
00:07:36,150 --> 00:07:43,360
على سبيل المثال، إذا كانت هذه عقدة واحدة - هذه العقدة التي تحتوي على قيمة 7

114
00:07:43,360 --> 00:07:45,500
مع مؤشرات فارغة اليسار واليمين للأطفال و-

115
00:07:45,500 --> 00:07:47,360
وكانت قيمة فقط في شجرة لدينا،

116
00:07:47,360 --> 00:07:50,390
ثم وهذا سيكون لدينا عقدة الجذر.

117
00:07:50,390 --> 00:07:52,240
انها بداية شجرة لدينا.

118
00:07:52,240 --> 00:07:58,530
يمكننا أن نرى هذا بشكل أكثر وضوحا قليلا مرة واحدة نبدأ إضافة المزيد من العقد إلى شجرة لدينا.

119
00:07:58,530 --> 00:08:01,510
اسمحوا لي سحب ما يصل صفحة جديدة.

120
00:08:01,510 --> 00:08:05,000
>> الآن ونحن في طريقنا لرسم الشجرة التي لديها 7 في الجذر،

121
00:08:05,000 --> 00:08:10,920
و 3 داخل الطفل الأيسر، و 9 داخل الطفل الصحيح.

122
00:08:10,920 --> 00:08:13,500
مرة أخرى، وهذا هو بسيط جدا.

123
00:08:13,500 --> 00:08:26,510
لدينا 7، رسم عقدة ل3، عقدة لمدة 9،

124
00:08:26,510 --> 00:08:32,150
وانا ذاهب لضبط المؤشر الأيسر للطفل من 7 للإشارة إلى العقدة التي تحتوي على 3،

125
00:08:32,150 --> 00:08:37,850
والمؤشر حق الطفل من العقدة التي تحتوي على 7 إلى العقدة التي تحتوي على 9.

126
00:08:37,850 --> 00:08:42,419
الآن، منذ 3 و 9 لم يكن لديك أي أطفال،

127
00:08:42,419 --> 00:08:48,500
ونحن في طريقنا لتعيين كافة مؤشرات الطفل على أن تكون فارغة.

128
00:08:48,500 --> 00:08:56,060
هنا، جذر شجرة لدينا يتوافق مع عقدة تحتوي على رقم 7.

129
00:08:56,060 --> 00:09:02,440
يمكنك أن ترى أن كل ما لدينا إذا هو مؤشر إلى أن العقدة الجذر،

130
00:09:02,440 --> 00:09:07,330
يمكننا المشي من خلال شجرة ثم لدينا والوصول العقد التابعة على حد سواء -

131
00:09:07,330 --> 00:09:10,630
كلا 3 و 9.

132
00:09:10,630 --> 00:09:14,820
لا حاجة للحفاظ على مؤشرات إلى كل عقدة واحدة على الشجرة.

133
00:09:14,820 --> 00:09:22,080
بخير. الآن ونحن في طريقنا لإضافة عقدة أخرى إلى هذا المخطط.

134
00:09:22,080 --> 00:09:25,370
ونحن في طريقنا لإضافة عقدة تحتوي على 6،

135
00:09:25,370 --> 00:09:34,140
ونحن في طريقنا لإضافة هذا الطفل والحق في العقدة التي تحتوي على 3.

136
00:09:34,140 --> 00:09:41,850
للقيام بذلك، وانا ذاهب لمحو أن مؤشر فارغة في عقدة-3

137
00:09:41,850 --> 00:09:47,750
والأسلاك ليصل إلى الإشارة إلى عقدة تحتوي على 6. بخير.

138
00:09:47,750 --> 00:09:53,800
>> في هذه المرحلة، دعونا نذهب أكثر قليلا من المصطلحات.

139
00:09:53,800 --> 00:09:58,230
للبدء، والسبب في أن هذا ما يسمى شجرة ثنائية على وجه الخصوص

140
00:09:58,230 --> 00:10:00,460
هو أن لديها مؤشرات طفل في الثانية.

141
00:10:00,460 --> 00:10:06,020
هناك أنواع أخرى من الأشجار التي لديها مؤشرات أكثر الأطفال.

142
00:10:06,020 --> 00:10:10,930
على وجه الخصوص، هل ل'محاولة' في مجموعة مشكلة 5.

143
00:10:10,930 --> 00:10:19,310
هل كان لديك ستلاحظ أن في ذلك محاولة، 27 مؤشرات مختلفة للأطفال مختلفة -

144
00:10:19,310 --> 00:10:22,410
واحد لكل من 26 حرفا في الأبجدية الإنجليزية،

145
00:10:22,410 --> 00:10:25,410
ثم الفاصلة العليا ل27 -

146
00:10:25,410 --> 00:10:28,900
لذلك، وهذا مماثل لنوع من الأشجار.

147
00:10:28,900 --> 00:10:34,070
ولكن هنا، منذ ذلك ثنائي، لدينا فقط مؤشرات الطفل اثنين.

148
00:10:34,070 --> 00:10:37,880
>> بالإضافة إلى هذه العقدة الجذر الذي تحدثنا عنه،

149
00:10:37,880 --> 00:10:41,470
لقد تم أيضا إلقاء حول هذا المصطلح "الطفل".

150
00:10:41,470 --> 00:10:44,470
ماذا يعني ذلك للعقدة واحدة في أن يكون طفلا من عقدة أخرى؟

151
00:10:44,470 --> 00:10:54,060
وهذا يعني حرفيا أن عقدة الطفل هو الطفل من عقدة أخرى

152
00:10:54,060 --> 00:10:58,760
إذا كان ذلك عقدة أخرى لديها واحد من المؤشرات التابعة لها للإشارة إلى تعيين تلك العقدة.

153
00:10:58,760 --> 00:11:01,230
لوضع هذا في شروط أكثر واقعية،

154
00:11:01,230 --> 00:11:11,170
إذا أشار 3 إلى واحد من المؤشرات الطفل من 7، ثم 3 هو طفل من 7.

155
00:11:11,170 --> 00:11:14,510
إذا كان لنا أن معرفة ما هي الأطفال من 7 -

156
00:11:14,510 --> 00:11:18,510
حسنا، نحن نرى أن 7 ومؤشر إلى 3 و مؤشر إلى 9،

157
00:11:18,510 --> 00:11:22,190
9 بحيث و 3 أطفال من 7.

158
00:11:22,190 --> 00:11:26,650
لا يوجد لديه تسعة أطفال بسبب مؤشرات التابعة لها لاغية،

159
00:11:26,650 --> 00:11:30,940
و 3 لديه طفل واحد فقط، و 6.

160
00:11:30,940 --> 00:11:37,430
ستة أطفال أيضا لا لأن كلا من المؤشرات التي تعتبر لاغية، والتي سوف نستخلص الآن.

161
00:11:37,430 --> 00:11:45,010
>> بالإضافة إلى ذلك، نتحدث أيضا عن والدي عقدة معينة،

162
00:11:45,010 --> 00:11:51,100
وهذا هو، كما كنت تتوقع، عكس هذا الوصف الطفل.

163
00:11:51,100 --> 00:11:58,620
كل عقدة لديه أحد الوالدين فقط - بدلا من اثنين كما قد تتوقع مع البشر.

164
00:11:58,620 --> 00:12:03,390
على سبيل المثال، فإن الوالد من 3 هو 7.

165
00:12:03,390 --> 00:12:10,800
والد 9 هو أيضا 7، والوالد من 6 هو 3. ليس كثيرا لذلك.

166
00:12:10,800 --> 00:12:15,720
لدينا أيضا حيث الحديث عن الأجداد والأحفاد،

167
00:12:15,720 --> 00:12:18,210
وبشكل عام كنا نتحدث عن الأجداد

168
00:12:18,210 --> 00:12:20,960
والمتحدرين من عقدة معينة.

169
00:12:20,960 --> 00:12:25,710
والجد من عقدة - أو الأجداد، بدلا من عقدة -

170
00:12:25,710 --> 00:12:32,730
هي كافة العقد التي تقع على الطريق من جذورها إلى تلك العقدة.

171
00:12:32,730 --> 00:12:36,640
على سبيل المثال، إذا أنا أبحث في ال 6 عقدة،

172
00:12:36,640 --> 00:12:46,430
ثم أسلاف ستكون كل 3 و 7.

173
00:12:46,430 --> 00:12:55,310
أسلاف 9، على سبيل المثال، هي - إذا أنا أبحث في ال 9 عقدة -

174
00:12:55,310 --> 00:12:59,990
ثم الجد من 9 هو فقط 7.

175
00:12:59,990 --> 00:13:01,940
ونسل هي بالضبط عكس ذلك.

176
00:13:01,940 --> 00:13:05,430
إذا كنت تريد أن ننظر إلى كل من أحفاد 7،

177
00:13:05,430 --> 00:13:11,020
ثم لا بد لي من النظر في كافة العقد تحته.

178
00:13:11,020 --> 00:13:16,950
لذلك، لدي 3، 9، و 6 عن باعتبارهم من نسل من 7.

179
00:13:16,950 --> 00:13:24,170
>> على المدى النهائي الذي سنتحدث عنه هو هذه الفكرة من كونها الأخوة.

180
00:13:24,170 --> 00:13:27,980
الأشقاء - نوع من بعد طول هذه الشروط على الأسرة -

181
00:13:27,980 --> 00:13:33,150
هي العقد التي تكون في نفس المستوى في الشجرة.

182
00:13:33,150 --> 00:13:42,230
حتى و 3 و 9 إخوة لأنهم على نفس المستوى في الشجرة.

183
00:13:42,230 --> 00:13:46,190
ديهما نفس الأم، 7.

184
00:13:46,190 --> 00:13:51,400
ال 6 لا يوجد لديه أشقاء ل9 لا يوجد اي الأطفال.

185
00:13:51,400 --> 00:13:55,540
و 7 لا يوجد اي الأشقاء لأنه جذر شجرة لدينا،

186
00:13:55,540 --> 00:13:59,010
وليس هناك سوى نفس الوقت كان 1 الجذر.

187
00:13:59,010 --> 00:14:02,260
لمدة 7 لالأشقاء ويجب أن تكون هناك عقدة فوق 7.

188
00:14:02,260 --> 00:14:07,480
وهناك يجب أن يكون أحد الوالدين من 7، الذي الحالة 7 لن يكون جذر الشجرة.

189
00:14:07,480 --> 00:14:10,480
فهذا هو الأصل الجديد من 7 أيضا لإنجاب طفل،

190
00:14:10,480 --> 00:14:16,480
وسوف يكون هذا الطفل ثم الأخوة من 7.

191
00:14:16,480 --> 00:14:21,040
>> بخير. الانتقال.

192
00:14:21,040 --> 00:14:24,930
عندما بدأنا مناقشاتنا الثنائية من الأشجار،

193
00:14:24,930 --> 00:14:28,790
تحدثنا عن الطريقة التي كانوا في طريقهم لاستخدامها ل

194
00:14:28,790 --> 00:14:32,800
كسب ميزة على حد سواء المصفوفات والقوائم المرتبطة.

195
00:14:32,800 --> 00:14:37,220
والطريقة ونحن في طريقنا للقيام بذلك هي مع هذه الخاصية الطلب.

196
00:14:37,220 --> 00:14:41,080
نقول أن أمر شجرة ثنائية، وفقا لمواصفات،

197
00:14:41,080 --> 00:14:45,740
إذا لكل عقدة في شجرة لدينا، كل من نسله على اليسار -

198
00:14:45,740 --> 00:14:48,670
الطفل الأيسر وجميع أحفاد الطفل اليسار -

199
00:14:48,670 --> 00:14:54,510
يكون أقل القيم، وجميع من العقد على حق -

200
00:14:54,510 --> 00:14:57,770
الطفل والحق كل نسل الطفل الحق في -

201
00:14:57,770 --> 00:15:02,800
يكون العقد أكبر من قيمة العقدة الحالية التي نحن نبحث في.

202
00:15:02,800 --> 00:15:07,850
فقط لبساطة، ونحن في طريقنا لنفترض أن ليس هناك أي عقد مكررة في شجرة لدينا.

203
00:15:07,850 --> 00:15:11,180
على سبيل المثال، في هذه الشجرة ونحن لن تتعامل مع القضية

204
00:15:11,180 --> 00:15:13,680
حيث لدينا قيمة 7 في الجذر

205
00:15:13,680 --> 00:15:16,720
 ثم لدينا أيضا قيمة 7 مكان آخر في الشجرة.

206
00:15:16,720 --> 00:15:24,390
في هذه الحالة، سوف تلاحظ أن أمر الواقع هذه الشجرة.

207
00:15:24,390 --> 00:15:26,510
لدينا قيمة 7 في جذورها.

208
00:15:26,510 --> 00:15:29,720
كل شيء على يسار 7 -

209
00:15:29,720 --> 00:15:35,310
إذا كنت التراجع عن كل هذه علامات قليلا هنا -

210
00:15:35,310 --> 00:15:40,450
كل شيء على يسار 7 - 3 و 6 و-

211
00:15:40,450 --> 00:15:49,410
هذه القيم على حد سواء أقل من 7، وكل شيء إلى اليمين - - الذي هو مجرد هذه 9

212
00:15:49,410 --> 00:15:53,450
هو أكبر من 7.

213
00:15:53,450 --> 00:15:58,650
>> ليست هذه هي شجرة تحتوي على أمر هذه القيم فقط،

214
00:15:58,650 --> 00:16:03,120
ولكن دعونا رسم أكثر عدد قليل منها.

215
00:16:03,120 --> 00:16:05,030
هناك في الواقع مجموعة كاملة من الطرق التي يمكننا أن نفعل هذا.

216
00:16:05,030 --> 00:16:09,380
انا ذاهب الى استخدام الاختزال فقط للحفاظ على الأشياء البسيطة حيث -

217
00:16:09,380 --> 00:16:11,520
بدلا من استخلاص كله مربعات و-السهام -

218
00:16:11,520 --> 00:16:14,220
انا فقط لرسم الأرقام وربطها إضافة السهام.

219
00:16:14,220 --> 00:16:22,920
للبدء، وسنقوم مجرد كتابة شجرة لدينا الأصلي مرة أخرى حيث كان لدينا 7، وبعد ذلك 3،

220
00:16:22,920 --> 00:16:25,590
وأشار ثم 3 عودة إلى الحق في 6،

221
00:16:25,590 --> 00:16:30,890
وكان 7 ألف طفل الحق الذي كان 9.

222
00:16:30,890 --> 00:16:33,860
بخير. ما طريقة أخرى أن نتمكن من كتابة هذه الشجرة؟

223
00:16:33,860 --> 00:16:38,800
بدلا من أن يكون وجود 3 الطفل الأيسر من 7،

224
00:16:38,800 --> 00:16:41,360
يمكن أن لدينا أيضا ال 6 يكون الطفل الأيسر من 7،

225
00:16:41,360 --> 00:16:44,470
وثم 3 يكون الطفل الأيسر من 6.

226
00:16:44,470 --> 00:16:48,520
والتي تبدو وكأنها هذه الشجرة هنا حيث كنت قد حصلت على 7،

227
00:16:48,520 --> 00:16:57,860
6 ثم، ثم 3، و9 على اليمين.

228
00:16:57,860 --> 00:17:01,490
ونحن أيضا لا يكون لدينا (7)، لدينا عقدة الجذر.

229
00:17:01,490 --> 00:17:03,860
يمكن أن لدينا أيضا (6)، لدينا عقدة الجذر.

230
00:17:03,860 --> 00:17:06,470
ماذا تشبه؟

231
00:17:06,470 --> 00:17:09,230
إذا نحن في طريقنا للحفاظ على هذه الخاصية أمر،

232
00:17:09,230 --> 00:17:12,970
كل شيء على يسار ال 6 يجب أن يكون أقل من ذلك.

233
00:17:12,970 --> 00:17:16,540
هناك احتمال واحد فقط، وهذا هو 3.

234
00:17:16,540 --> 00:17:19,869
ولكن بعد ذلك الطفل حق 6، لدينا اثنين من الاحتمالات.

235
00:17:19,869 --> 00:17:25,380
أولا، يمكن أن لدينا 7 و ثم 9،

236
00:17:25,380 --> 00:17:28,850
أو يمكن أن استدراجه - مثل أنا على وشك القيام به هنا -

237
00:17:28,850 --> 00:17:34,790
حيث لدينا 9 كما الطفل الأيمن من 6،

238
00:17:34,790 --> 00:17:39,050
وبعد ذلك (7)، الطفل الأيسر من 9.

239
00:17:39,050 --> 00:17:44,240
>> الآن، 7 و 6 ليست فقط القيم الممكنة لجذر.

240
00:17:44,240 --> 00:17:50,200
يمكن أن لدينا أيضا 3 يكون في الجذر.

241
00:17:50,200 --> 00:17:52,240
ماذا يحدث إذا (3) هي في جذور؟

242
00:17:52,240 --> 00:17:54,390
هنا، الامور قليلا للاهتمام.

243
00:17:54,390 --> 00:17:58,440
ثلاثة ليس لديها أي القيم التي هي أقل من ذلك،

244
00:17:58,440 --> 00:18:02,070
بحيث الجانب الأيسر بأكمله من شجرة هو مجرد الذهاب لاغية.

245
00:18:02,070 --> 00:18:03,230
هناك لن يكون أي شيء هناك.

246
00:18:03,230 --> 00:18:07,220
إلى اليمين، يمكن أن قائمة الأشياء في ترتيب تصاعدي.

247
00:18:07,220 --> 00:18:15,530
يمكن أن لدينا 3، ثم 6، ثم 7، ثم 9.

248
00:18:15,530 --> 00:18:26,710
أو، يمكن أن نفعل 3، ثم 6، ثم 9، ثم 7.

249
00:18:26,710 --> 00:18:35,020
أو، يمكن أن نفعل 3، ثم 7، ثم 6، ثم 9.

250
00:18:35,020 --> 00:18:40,950
أو، 3، 7 - لا في الواقع، لا يمكننا القيام ج 7 بعد الآن.

251
00:18:40,950 --> 00:18:43,330
هذا لدينا شيء واحد هناك.

252
00:18:43,330 --> 00:18:54,710
يمكننا أن نفعل 9، ثم من ال 9 يمكننا القيام به ثم 6 و 7.

253
00:18:54,710 --> 00:19:06,980
أو، يمكننا أن نفعل 3، ثم 9، ثم 7، ثم 6.

254
00:19:06,980 --> 00:19:12,490
>> شيء واحد أن ألفت انتباهكم إلى هنا

255
00:19:12,490 --> 00:19:14,510
أن هذه الأشجار هي غريبة قليلا المظهر.

256
00:19:14,510 --> 00:19:17,840
على وجه الخصوص، إذا نظرنا إلى الأشجار 4 على الجانب الأيمن -

257
00:19:17,840 --> 00:19:20,930
أنا دائرة لهم، وهنا -

258
00:19:20,930 --> 00:19:28,410
هذه الأشجار تبدو تماما تقريبا مثل قائمة مرتبطة.

259
00:19:28,410 --> 00:19:32,670
كل عقدة لديه طفل واحد فقط،

260
00:19:32,670 --> 00:19:38,950
وذلك ليس لدينا أي من هذه البنية شجرة تشبه التي نراها، على سبيل المثال،

261
00:19:38,950 --> 00:19:44,720
 في هذا شجرة واحدة وحيدة أكثر من هنا على اليسار السفلي.

262
00:19:44,720 --> 00:19:52,490
وتسمى هذه الأشجار في الواقع تتحول الأشجار الثنائية،

263
00:19:52,490 --> 00:19:54,170
وسوف نتحدث عن هذه أكثر في المستقبل -

264
00:19:54,170 --> 00:19:56,730
خاصة إذا كنت تذهب على أن يأخذ علوم الحاسب الآلي المقررات الأخرى.

265
00:19:56,730 --> 00:19:59,670
هذه الأشجار هي تتدهور.

266
00:19:59,670 --> 00:20:03,780
انهم ليسوا مفيدة جدا لأنه، في الواقع، هذا الهيكل يفسح المجال

267
00:20:03,780 --> 00:20:08,060
 لبحث مرات مماثلة لتلك التي على قائمة مرتبطة.

268
00:20:08,060 --> 00:20:13,050
نحن لا تحصل على الاستفادة من ذاكرة إضافية - وهذا مؤشر إضافي -

269
00:20:13,050 --> 00:20:18,840
بسبب بنية سيئة جودنا في هذا السبيل.

270
00:20:18,840 --> 00:20:24,700
بدلا من المضي قدما واستخلاص الأشجار الثنائية التي لديها 9 في الجذر،

271
00:20:24,700 --> 00:20:27,220
كما هو الحال النهائية التي سيكون لدينا،

272
00:20:27,220 --> 00:20:32,380
نحن بدلا من ذلك، في هذه المرحلة، بصدد الحديث قليلا عن هذا المصطلح الأخرى

273
00:20:32,380 --> 00:20:36,150
التي نستخدمها عندما نتحدث عن الأشجار، وهو ما يسمى الارتفاع.

274
00:20:36,150 --> 00:20:45,460
>> ارتفاع شجرة هي المسافة من الجذر إلى العقدة الأكثر بعيد المنال،

275
00:20:45,460 --> 00:20:48,370
أو بالأحرى عدد من القفزات التي عملتم لجعل ل

276
00:20:48,370 --> 00:20:53,750
تبدأ من الجذر ثم ينتهي في عقدة معظم البعيد في الشجرة.

277
00:20:53,750 --> 00:20:57,330
إذا كان لنا أن نلقي نظرة على بعض من هذه الأشجار التي كانت لدينا رسمها هنا،

278
00:20:57,330 --> 00:21:07,870
يمكننا أن نرى أن إذا أخذنا هذه الشجرة في أعلى الزاوية اليسرى ونبدأ في 3،

279
00:21:07,870 --> 00:21:14,510
ثم لدينا لجعل 1 هوب للوصول الى 6، قفزة ثانية لتصل إلى 7،

280
00:21:14,510 --> 00:21:20,560
وهوب الثالث لتصل إلى 9.

281
00:21:20,560 --> 00:21:26,120
لذا، فإن ارتفاع هذه الشجرة هو 3.

282
00:21:26,120 --> 00:21:30,640
يمكننا أن نفعل نفس العملية للأشجار الأخرى المبينة في هذا الأخضر،

283
00:21:30,640 --> 00:21:40,100
ونحن نرى أن ارتفاع كل هذه الأشجار هي في الواقع أيضا 3.

284
00:21:40,100 --> 00:21:45,230
هذا جزء من ما يجعلها تتحول -

285
00:21:45,230 --> 00:21:53,750
أن طولهم واحد فقط أقل من عدد العقد في الشجرة بأكملها.

286
00:21:53,750 --> 00:21:58,400
إذا نظرنا إلى هذه الشجرة الأخرى التي المحاصرة مع الأحمر، من ناحية أخرى،

287
00:21:58,400 --> 00:22:03,920
ونحن نرى أن معظم أوراق العقد البعيد هي 6 و 9 و-

288
00:22:03,920 --> 00:22:06,940
ويجري يترك تلك العقد التي ليس لها أطفال.

289
00:22:06,940 --> 00:22:11,760
لذلك، من أجل الحصول على الجذر من العقدة إلى 6 أو 9 إما ل،

290
00:22:11,760 --> 00:22:17,840
لدينا لجعل واحدة هوب للوصول الى (7) وبعد ذلك قفزة ثانية للحصول على ل9،

291
00:22:17,840 --> 00:22:21,240
وبالمثل، فقط هوب الثاني من 7 إلى الوصول إلى 6.

292
00:22:21,240 --> 00:22:29,080
لذا، فإن ارتفاع هذه الشجرة إلى هنا هو 2 فقط.

293
00:22:29,080 --> 00:22:35,330
يمكنك العودة وذلك لجميع الأشجار الأخرى التي ناقشناها سابقا

294
00:22:35,330 --> 00:22:37,380
ابتداء من 7 و 6 و،

295
00:22:37,480 --> 00:22:42,500
وسوف تجد أن ارتفاع كل هذه الأشجار هي أيضا 2.

296
00:22:42,500 --> 00:22:46,320
>> أمرت السبب كنا نتحدث عن الأشجار الثنائية

297
00:22:46,320 --> 00:22:50,250
والسبب في انهم بارد لأن يمكنك البحث من خلالها في

298
00:22:50,250 --> 00:22:53,810
بطريقة مماثلة جدا لتبحث على مجموعة فرزها.

299
00:22:53,810 --> 00:22:58,720
هذا هو المكان الذي نتحدث عن الحصول على هذا الوقت البحث المحسنة

300
00:22:58,720 --> 00:23:02,730
خلال قائمة بسيطة مرتبطة.

301
00:23:02,730 --> 00:23:05,010
مع قائمة مرتبطة - إذا كنت ترغب في العثور على عنصر معين -

302
00:23:05,010 --> 00:23:07,470
كنت في الذهاب الأفضل أن تفعل نوعا من البحث الخطي

303
00:23:07,470 --> 00:23:10,920
حيث تبدأ في بداية قائمة وهوب واحد من جانب واحد -

304
00:23:10,920 --> 00:23:12,620
عقدة واحدة من عقدة واحدة -

305
00:23:12,620 --> 00:23:16,060
من خلال القائمة بأكملها حتى تجد ما كنت تبحث عنه.

306
00:23:16,060 --> 00:23:19,440
في حين، إذا كان لديك شجرة الثنائية التي يتم تخزينها في هذا الشكل لطيف،

307
00:23:19,440 --> 00:23:23,300
يمكنك في الواقع الحصول على أكثر من بحث ثنائية مستمرة

308
00:23:23,300 --> 00:23:25,160
حيث يمكنك فرق تسد

309
00:23:25,160 --> 00:23:29,490
وبحث خلال النصف المناسبة من شجرة في كل خطوة.

310
00:23:29,490 --> 00:23:32,840
دعونا نرى كيف يعمل.

311
00:23:32,840 --> 00:23:38,850
>> اذا كان لدينا - مرة أخرى، والعودة إلى شجرة لدينا الأصلي -

312
00:23:38,850 --> 00:23:46,710
نبدأ في الساعة 7، لدينا 3 على اليسار و 9 على اليمين،

313
00:23:46,710 --> 00:23:51,740
وتحت ال 3 لدينا 6.

314
00:23:51,740 --> 00:24:01,880
إذا كنا نريد للبحث عن الرقم 6 في هذه الشجرة، علينا أن نبادر في جذورها.

315
00:24:01,880 --> 00:24:08,910
وقارنا القيمة التي تبحث عنها، ويقول 6،

316
00:24:08,910 --> 00:24:12,320
إلى القيمة المخزنة في العقدة التي نحن نبحث حاليا في، 7،

317
00:24:12,320 --> 00:24:21,200
وجدت أن 6 هو في الواقع أقل من 7، لذلك كنا نقل إلى اليسار.

318
00:24:21,200 --> 00:24:25,530
إذا كانت القيمة من 6 كان أكبر من 7، وانتقلنا بدلا من ذلك إلى اليمين.

319
00:24:25,530 --> 00:24:29,770
لأننا نعلم أن - بسبب هيكل شجرة لدينا ثنائي أمر -

320
00:24:29,770 --> 00:24:33,910
كافة القيم أقل من 7 سوف تكون مخزنة على يسار 7،

321
00:24:33,910 --> 00:24:40,520
ليس هناك حاجة لعناء حتى النظر من خلال الجانب الأيمن من الشجرة.

322
00:24:40,520 --> 00:24:43,780
مرة واحدة ونحن نتحرك إلى اليسار، ونحن الآن في عقدة تحتوي على 3،

323
00:24:43,780 --> 00:24:48,110
يمكننا أن نفعل ذلك مرة أخرى حيث المقارنة نفسها قارنا 3 و 6 و.

324
00:24:48,110 --> 00:24:52,430
ونجد أنه في حين أن 6 - قيمة ونحن نبحث عن - أكبر من 3،

325
00:24:52,430 --> 00:24:58,580
يمكننا أن نذهب إلى الجانب الأيمن من العقدة التي تحتوي على 3.

326
00:24:58,580 --> 00:25:02,670
ليس هناك الجانب الأيسر هنا، حتى أننا يمكن أن تجاهلوا ذلك.

327
00:25:02,670 --> 00:25:06,510
ولكننا نعرف فقط ذلك لأننا نبحث في الشجرة نفسها،

328
00:25:06,510 --> 00:25:08,660
ويمكننا أن نرى أن الشجرة لا يوجد لديه أطفال.

329
00:25:08,660 --> 00:25:13,640
>> كما انها سهلة جدا للبحث عن 6 في هذه الشجرة إذا نفعله بأنفسنا كبشر،

330
00:25:13,640 --> 00:25:16,890
ولكن دعونا اتبع هذه العملية ميكانيكيا مثل الكمبيوتر ستفعل

331
00:25:16,890 --> 00:25:18,620
لفهم حقا الخوارزمية.

332
00:25:18,620 --> 00:25:26,200
في هذه المرحلة، ونحن نبحث الآن في العقدة التي تحتوي على 6،

333
00:25:26,200 --> 00:25:29,180
ونحن نبحث عن القيمة 6،

334
00:25:29,180 --> 00:25:31,740
لذلك، في الواقع، وجدنا العقدة المناسبة.

335
00:25:31,740 --> 00:25:35,070
وجدنا قيمة 6 في شجرة لدينا، ونحن يمكن أن يوقف البحث.

336
00:25:35,070 --> 00:25:37,330
في هذه المرحلة، اعتمادا على ما يجري،

337
00:25:37,330 --> 00:25:41,870
نستطيع أن نقول، نعم، وجدنا قيمة 6، كان موجودا في شجرة لدينا.

338
00:25:41,870 --> 00:25:47,640
أو، إذا نحن نخطط لإدراج عقدة أو تفعل شيئا، يمكننا أن نفعل ذلك في هذه المرحلة.

339
00:25:47,640 --> 00:25:53,010
>> دعونا نفعل عمليات البحث أكثر زوجين فقط لنرى كيف يعمل هذا.

340
00:25:53,010 --> 00:25:59,390
دعونا ننظر إلى ما يحدث إذا كان لنا أن نحاول والبحث عن القيمة 10.

341
00:25:59,390 --> 00:26:02,970
إذا كان لنا أن البحث عن القيمة 10، ونبدأ في جذورها.

342
00:26:02,970 --> 00:26:07,070
كنا نرى أن 10 هو أكبر من 7، لذلك كنا التحرك إلى اليمين.

343
00:26:07,070 --> 00:26:13,640
كنا نصل إلى المقارنة 9 و 9 إلى ال 10، ويرى في 9 هو في الواقع أقل من 10.

344
00:26:13,640 --> 00:26:16,210
ذلك مرة أخرى، كنا محاولة نقل إلى اليمين.

345
00:26:16,210 --> 00:26:20,350
ولكن في هذه النقطة، لكنا نلاحظ أننا في عقدة فارغة.

346
00:26:20,350 --> 00:26:23,080
لا يوجد شيء هناك. لا يوجد شيء حيث ينبغي أن تكون ال 10.

347
00:26:23,080 --> 00:26:29,360
هذا هو المكان الذي يمكن أن يقدم تقريرا الفشل - أن هناك في الواقع لا 10 في الشجرة.

348
00:26:29,360 --> 00:26:35,420
وأخيرا، دعونا نذهب من خلال الحالة التي نحاول أن ننظر بنسبة 1 في الشجرة.

349
00:26:35,420 --> 00:26:38,790
هذا هو على غرار ما يحدث إذا نظرنا حتى 10، باستثناء بدلا من الذهاب إلى اليمين،

350
00:26:38,790 --> 00:26:41,260
ونحن في طريقنا للذهاب إلى اليسار.

351
00:26:41,260 --> 00:26:46,170
نبدأ في 7 و نرى أن 1 هو أقل من 7، لذلك نحن نتحرك إلى اليسار.

352
00:26:46,170 --> 00:26:51,750
نصل إلى 3 و نرى أن 1 أقل من 3، لذلك مرة أخرى ونحن نحاول التحرك إلى اليسار.

353
00:26:51,750 --> 00:26:59,080
عند هذه النقطة لدينا عقدة فارغة، مرة أخرى حتى نتمكن من تقديم تقرير الفشل.

354
00:26:59,080 --> 00:27:10,260
>> إذا كنت تريد معرفة المزيد عن الأشجار الثنائية،

355
00:27:10,260 --> 00:27:14,420
هناك مجموعة كاملة من المشاكل الصغيرة المتعة التي يمكنك القيام به معها.

356
00:27:14,420 --> 00:27:19,450
أقترح ممارسة الرسم للخروج من هذه المخططات واحدة تلو الأخرى

357
00:27:19,450 --> 00:27:21,910
ومتابعة كافة الخطوات المختلفة،

358
00:27:21,910 --> 00:27:25,060
لأن هذا في متناول اليدين عظمى

359
00:27:25,060 --> 00:27:27,480
ليس فقط عندما كنت تفعل ترميز هوفمان مشكلة مجموعة

360
00:27:27,480 --> 00:27:29,390
ولكن أيضا في الدورات المقبلة -

361
00:27:29,390 --> 00:27:32,220
مجرد تعلم كيفية استخلاص هذه الهياكل البيانات والتفكير في المشاكل

362
00:27:32,220 --> 00:27:38,000
مع القلم والورقة أو، في هذه الحالة، وتطلب الشركة والقلم.

363
00:27:38,000 --> 00:27:41,000
>> في هذه المرحلة على الرغم من أننا في طريقنا للانتقال إلى القيام ببعض الممارسات الترميز

364
00:27:41,000 --> 00:27:44,870
وتلعب هذه الأشجار فعلا مع ثنائي ونرى.

365
00:27:44,870 --> 00:27:52,150
انا ذاهب للعودة الى جهاز الكمبيوتر الخاص بي.

366
00:27:52,150 --> 00:27:58,480
لهذا الجزء من هذا الباب، بدلا من استخدام CS50 CS50 تشغيل أو مسافات،

367
00:27:58,480 --> 00:28:01,500
انا ذاهب الى استخدام الجهاز.

368
00:28:01,500 --> 00:28:04,950
>> بعد طول مشكلة مع مواصفات مجموعة،

369
00:28:04,950 --> 00:28:07,740
وأرى أن من المفترض أن تفتح الجهاز،

370
00:28:07,740 --> 00:28:11,020
انتقل إلى مجلد Dropbox بلدي، إنشاء مجلد يسمى القسم 7،

371
00:28:11,020 --> 00:28:15,730
ثم قم بإنشاء ملف يسمى binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
هنا نذهب. أنا عندي الجهاز مفتوح مسبقا.

373
00:28:22,050 --> 00:28:25,910
أنا ذاهب سحب ما يصل محطة.

374
00:28:25,910 --> 00:28:38,250
انا ذاهب للذهاب إلى مجلد Dropbox، وجعل دليل يسمى section7،

375
00:28:38,250 --> 00:28:42,230
ونرى أنه من فارغة تماما.

376
00:28:42,230 --> 00:28:48,860
الآن انا ذاهب لفتح binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
بخير. هنا نذهب - ملف فارغ.

378
00:28:51,750 --> 00:28:54,330
>> دعونا نعود إلى مواصفات.

379
00:28:54,330 --> 00:28:59,850
مواصفات يسأل لإنشاء تعريف نوع جديد

380
00:28:59,850 --> 00:29:03,080
لعقدة شجرة ثنائية تحتوي على قيم الباحث -

381
00:29:03,080 --> 00:29:07,110
تماما مثل القيم التي نحن في وجه المخططات لدينا من قبل.

382
00:29:07,110 --> 00:29:11,740
ونحن في طريقنا لاستخدام هذا المتداول typedef أن فعلناه هنا

383
00:29:11,740 --> 00:29:14,420
يجب عليك أن تدرك من مجموعة مشكلة 5 -

384
00:29:14,420 --> 00:29:19,190
إذا لم لك الطريق جدول التجزئة من قهر وبرنامج سبيلر.

385
00:29:19,190 --> 00:29:22,540
يجب أن ندرك أيضا أنه من قسم الأسبوع الماضي

386
00:29:22,540 --> 00:29:23,890
حيث تحدثنا عن القوائم المرتبطة.

387
00:29:23,890 --> 00:29:27,870
ونحن قد حصلت على هذا typedef من عقدة البنية،

388
00:29:27,870 --> 00:29:34,430
ولقد أعطيت لنا هذه العقدة اسم هذه البنية عقدة البنية مسبقا

389
00:29:34,430 --> 00:29:39,350
حتى نتمكن من الرجوع إليها منذ ذلك الحين سنقوم تريد أن يكون عقدة مؤشرات البنية

390
00:29:39,350 --> 00:29:45,740
كجزء من البنية لدينا، ولكن لدينا طوق ثم وهذا -

391
00:29:45,740 --> 00:29:47,700
أو بالأحرى، محاطة هذا - في typedef

392
00:29:47,700 --> 00:29:54,600
بحيث، في وقت لاحق في التعليمات البرمجية، يمكننا الرجوع إلى هذه البنية وعقدة فقط بدلا من عقدة البنية.

393
00:29:54,600 --> 00:30:03,120
>> هذه ستكون مشابهة جدا لتعريف قائمة منفردة مرتبطة التي شهدناها الأسبوع الماضي.

394
00:30:03,120 --> 00:30:20,070
للقيام بذلك، دعونا نبدأ من خلال كتابة خارج المتداول.

395
00:30:20,070 --> 00:30:23,840
ونحن نعلم أن علينا أن يكون لها قيمة عدد صحيح،

396
00:30:23,840 --> 00:30:32,170
وهكذا لن نضع في قيمة الباحث، ومن ثم بدلا من أن مؤشر واحد فقط إلى العنصر التالي -

397
00:30:32,170 --> 00:30:33,970
كما فعلنا مع منفردة مرتبطة القوائم -

398
00:30:33,970 --> 00:30:38,110
نحن ستكون لدينا مؤشرات الطفل اليمنى واليسرى.

399
00:30:38,110 --> 00:30:42,880
هذا بسيط جدا جدا - البنية الطفل عقدة * اليسرى.

400
00:30:42,880 --> 00:30:51,190
والبنية عقدة * الطفل اليمنى. بارد.

401
00:30:51,190 --> 00:30:54,740
التي تبدو وكأنها بداية جيدة جدا.

402
00:30:54,740 --> 00:30:58,530
دعونا نعود إلى مواصفات.

403
00:30:58,530 --> 00:31:05,030
>> الآن نحن بحاجة إلى أن يعلن * عقدة العالمية المتغيرة لجذر شجرة.

404
00:31:05,030 --> 00:31:10,590
ونحن في طريقنا لجعل هذا العالم مثلما قدمنا ​​المؤشر الأول في قائمتنا العالمية مرتبطة أيضا.

405
00:31:10,590 --> 00:31:12,690
وكان هذا حتى في الوظائف التي نكتب

406
00:31:12,690 --> 00:31:16,180
ليس لدينا للحفاظ على تمرير حول هذا الجذر -

407
00:31:16,180 --> 00:31:19,620
على الرغم سنرى أنه إذا كنت لا تريد أن أكتب هذه المهام بشكل متكرر،

408
00:31:19,620 --> 00:31:22,830
قد يكون من الأفضل أن لا تمر حتى حولها باعتبارها العالمي في المقام الأول

409
00:31:22,830 --> 00:31:28,090
وبدلا من ذلك تهيئة محليا في وظيفة الرئيسي الخاص بك.

410
00:31:28,090 --> 00:31:31,960
ولكن، سوف نفعل ذلك على الصعيد العالمي لبدء.

411
00:31:31,960 --> 00:31:39,920
مرة أخرى، سوف نقدم اثنين من مسافات، وانا ذاهب لاعلان الجذر * العقدة.

412
00:31:39,920 --> 00:31:46,770
فقط للتأكد من أنني لا اترك هذا غير مهيأ، وانا ذاهب لتعيين أنه يساوي قيمة خالية.

413
00:31:46,770 --> 00:31:52,210
الآن، في المهمة الرئيسية - التي سوف نكتب بسرعة حقا هنا -

414
00:31:52,210 --> 00:32:00,450
الباحث الرئيسي (الباحث argc، تشار * argv CONST []) -

415
00:32:00,450 --> 00:32:10,640
وانا ذاهب لبدء إعلان مجموعة بلدي argv كما CONST فقط لكي أعرف

416
00:32:10,640 --> 00:32:14,550
إن هذه الحجج هي حجج أنني ربما لا تريد تعديلها.

417
00:32:14,550 --> 00:32:18,390
إذا كنت ترغب في تعديلها يجب أن تكون القرارات ربما نسخ منها.

418
00:32:18,390 --> 00:32:21,740
سترى هذا كثيرا في التعليمات البرمجية.

419
00:32:21,740 --> 00:32:25,440
أنه بخير اي من الاتجاهين. أنه بخير لترك الأمر كما - حذفت CONST إذا كنت ترغب.

420
00:32:25,440 --> 00:32:28,630
عادة أضع في ذلك فقط أن أذكر نفسي

421
00:32:28,630 --> 00:32:33,650
 أنني ربما لا ترغب في تعديل تلك الحجج.

422
00:32:33,650 --> 00:32:39,240
>> كما هو الحال دائما، وانا ذاهب لتضمين هذا الخط عودة 0 في نهاية الرئيسي.

423
00:32:39,240 --> 00:32:45,730
هنا، وسوف بلدي تهيئة عقدة الجذر.

424
00:32:45,730 --> 00:32:48,900
كما هو عليه الآن، لقد حصلت على المؤشر الذي تم ضبطه إلى فارغة،

425
00:32:48,900 --> 00:32:52,970
حتى انها لافتا في شيء.

426
00:32:52,970 --> 00:32:57,480
من أجل البدء في بناء الواقع العقدة،

427
00:32:57,480 --> 00:32:59,250
I تحتاج أولا إلى تخصيص ذاكرة لذلك.

428
00:32:59,250 --> 00:33:05,910
انا ذاهب للقيام بذلك بجعل الذاكرة على الكومة باستخدام malloc.

429
00:33:05,910 --> 00:33:10,660
أنا ذاهب لتعيين الجذر يساوي نتيجة malloc،

430
00:33:10,660 --> 00:33:19,550
وانا ذاهب الى استخدام عامل التشغيل sizeof لحساب حجم عقدة.

431
00:33:19,550 --> 00:33:24,990
السبب الذي يمكنني استخدام sizeof عقدة بدلا من، لنقل،

432
00:33:24,990 --> 00:33:37,020
القيام بشيء من هذا القبيل - malloc (4 + 4 +4) أو malloc 12 -

433
00:33:37,020 --> 00:33:40,820
هو لأنني أريد قانون بلدي لتكون متوافقة قدر الإمكان.

434
00:33:40,820 --> 00:33:44,540
أريد أن أكون قادرا على اتخاذ هذا الملف ج.، ترجمة على الجهاز،

435
00:33:44,540 --> 00:33:48,820
وثم ترجمة ذلك على ماك 64-بت بلدي -

436
00:33:48,820 --> 00:33:52,040
أو على بنية مختلفة تماما -

437
00:33:52,040 --> 00:33:54,640
وأريد هذا جميعا أن نعمل نفس الشيء.

438
00:33:54,640 --> 00:33:59,510
>> إذا أنا وضع افتراضات حول حجم المتغيرات -

439
00:33:59,510 --> 00:34:02,070
حجم وكثافة العمليات أو حجم مؤشر -

440
00:34:02,070 --> 00:34:06,070
ثم أنا أيضا جعل افتراضات حول أنواع أبنية

441
00:34:06,070 --> 00:34:10,440
التي يمكن أن قانون بلدي بنجاح ترجمة عند تشغيل.

442
00:34:10,440 --> 00:34:15,030
دائما استخدام sizeof بدلا من تلخيص مجالات البنية يدويا.

443
00:34:15,030 --> 00:34:20,500
والسبب الآخر هو أنه قد يكون هناك أيضا الحشو أن يضع المترجم في البنية.

444
00:34:20,500 --> 00:34:26,570
حتى تلخيص فقط الحقول الفردية ليست شيئا كنت تريد أن تفعل عادة،

445
00:34:26,570 --> 00:34:30,340
لذلك، حذف ذلك السطر.

446
00:34:30,340 --> 00:34:33,090
الآن، لتهيئة حقا هذه العقدة الجذر،

447
00:34:33,090 --> 00:34:36,489
انا ذاهب الى أن سد العجز في القيم لكل من حقولها المختلفة.

448
00:34:36,489 --> 00:34:41,400
على سبيل المثال، لأعرف قيمة أريد أن تهيئة إلى 7،

449
00:34:41,400 --> 00:34:46,920
والآن انا ذاهب لوضع الطفل الأيسر لاغية

450
00:34:46,920 --> 00:34:55,820
والطفل أيضا الحق في أن يكون باطلا. عظيم!

451
00:34:55,820 --> 00:35:02,670
لقد فعلنا ذلك الجزء من المواصفات.

452
00:35:02,670 --> 00:35:07,390
>> مواصفات أسفل في أسفل الصفحة 3 يطلب مني لخلق المزيد من ثلاث عقد -

453
00:35:07,390 --> 00:35:10,600
واحدة تحتوي على 3، واحدة تحتوي على 6، واحد مع 9 -

454
00:35:10,600 --> 00:35:14,210
والأسلاك ثم لهم بحيث يبدو تماما مثل مخطط الشجرة لدينا

455
00:35:14,210 --> 00:35:17,120
أن كنا نتحدث عن السابق.

456
00:35:17,120 --> 00:35:20,450
دعونا نفعل ذلك بسرعة كبيرة هنا.

457
00:35:20,450 --> 00:35:26,270
سترى بسرعة حقا بأنني ذاهب للبدء في كتابة مجموعة من التعليمات البرمجية المتكررة.

458
00:35:26,270 --> 00:35:32,100
أنا ذاهب لخلق عقدة * وانا ذاهب الى نسميها الثلاثة.

459
00:35:32,100 --> 00:35:36,000
انا ذاهب الى تعيين يساوي malloc (sizeof (عقدة)).

460
00:35:36,000 --> 00:35:41,070
انا ذاهب الى تعيين ثلاثة> القيمة = 3.

461
00:35:41,070 --> 00:35:54,780
ثلاثة -> left_child = NULL؛ الثلاث -> الحق NULL = _child؛ كذلك.

462
00:35:54,780 --> 00:36:01,150
التي تبدو مشابهة جدا لتهيئة الجذر، وهذا هو بالضبط ما

463
00:36:01,150 --> 00:36:05,760
انا ذاهب الى القيام به إذا كنت بدء تهيئة 6 و 9 أيضا.

464
00:36:05,760 --> 00:36:20,720
سوف أفعل ذلك حقا هنا بسرعة - في الواقع، انا ذاهب الى القيام نسخة ولصق قليلا،

465
00:36:20,720 --> 00:36:46,140
وتأكد من أن I - على ما يرام.

466
00:36:46,470 --> 00:37:09,900
 الآن، وأنا قد حصلت عليه نسخ وأستطيع أن تمضي قدما وتعيين هذا يساوي 6.

467
00:37:09,900 --> 00:37:14,670
يمكنك أن ترى أن هذا يأخذ لحظة وليس كفاءة فائقة.

468
00:37:14,670 --> 00:37:22,610
في قليلا فقط، وسوف نكتب وظيفة من شأنها أن تفعل هذا بالنسبة لنا.

469
00:37:22,610 --> 00:37:32,890
أريد أن يحل محل هذا مع 9، الاستعاضة عن ذلك مع 6.

470
00:37:32,890 --> 00:37:37,360
>> الآن لدينا كل من العقد وخلق لدينا تهيئة.

471
00:37:37,360 --> 00:37:41,200
لدينا لدينا الجذر تعيين يساوي 7، أو التي تحتوي على قيمة 7،

472
00:37:41,200 --> 00:37:46,510
لدينا عقدة تحتوي على 3، لدينا عقدة تحتوي على 6، والتي تحتوي على عقدة لدينا 9.

473
00:37:46,510 --> 00:37:50,390
في هذه المرحلة، كل ما عليك القيام به هو كل شيء حتى الأسلاك.

474
00:37:50,390 --> 00:37:53,020
السبب في أنني تهيئة جميع المؤشرات إلى أن مجرد فارغة لذلك أنا تأكد من أن

475
00:37:53,020 --> 00:37:56,260
ليس لدي أي مؤشرات غير مهيأ هناك عن طريق الصدفة.

476
00:37:56,260 --> 00:38:02,290
وأيضا منذ ذلك الحين، في هذه المرحلة، وليس لدي سوى للاتصال العقد في الواقع مع بعضها البعض -

477
00:38:02,290 --> 00:38:04,750
لتلك التي كنت متصلا بالفعل إلى أنها - أنا لا يجب أن تمر عبر وجعل

478
00:38:04,750 --> 00:38:08,240
التأكد من أن جميع بلا قيم هي في وجود في الأماكن المناسبة.

479
00:38:08,240 --> 00:38:15,630
>> ابتداء من الجذر، وأنا أعلم أن الطفل الجذر اليسار هو 3.

480
00:38:15,630 --> 00:38:21,250
وأنا أعلم أن الطفل الجذر الحق هو 9.

481
00:38:21,250 --> 00:38:24,880
بعد ذلك، والطفل الوحيد الذي لم يقم أنا ما يدعو للقلق

482
00:38:24,880 --> 00:38:39,080
هو الطفل 3 اليمنى، والتي هي 6.

483
00:38:39,080 --> 00:38:44,670
عند هذه النقطة، يبدو كل شيء جيد جدا.

484
00:38:44,670 --> 00:38:54,210
سنقوم بحذف بعض من هذه الخطوط.

485
00:38:54,210 --> 00:38:59,540
الآن كل شيء يبدو جيدا جدا.

486
00:38:59,540 --> 00:39:04,240
دعونا نعود لمواصفات لدينا ونرى ما يتعين علينا القيام به المقبل.

487
00:39:04,240 --> 00:39:07,610
>> في هذه المرحلة، لدينا لكتابة دالة يسمى 'يحتوي'

488
00:39:07,610 --> 00:39:14,150
مع نموذج أولي من 'يحتوي BOOL (الباحث القيمة).

489
00:39:14,150 --> 00:39:17,060
وهذا يتضمن وظيفة هو الذهاب الى العودة الحقيقية

490
00:39:17,060 --> 00:39:21,200
 فإذا قال شجرة لدينا متغير من الجذر العالمية

491
00:39:21,200 --> 00:39:26,950
 يحتوي على القيمة تمريرها إلى الدالة وغير ذلك كاذب.

492
00:39:26,950 --> 00:39:29,000
دعونا نمضي قدما ونفعل ذلك.

493
00:39:29,000 --> 00:39:35,380
هذا سيكون تماما مثل البحث الذي قمنا به باليد على جهاز آي باد قليلا قبل.

494
00:39:35,380 --> 00:39:40,130
دعونا في إعادة تكبير قليلا وانتقل لأعلى.

495
00:39:40,130 --> 00:39:43,130
ونحن في طريقنا لوضع هذه الوظيفة وظيفة الحق فوق هدفنا الرئيسي

496
00:39:43,130 --> 00:39:48,990
بحيث لم يكن لدينا للقيام بأي نوع من النماذج.

497
00:39:48,990 --> 00:39:55,960
لذلك، يحتوي BOOL (الباحث القيمة).

498
00:39:55,960 --> 00:40:00,330
هناك نذهب. هناك إعلاننا النمطي.

499
00:40:00,330 --> 00:40:02,900
فقط للتأكد من أن هذا سيتم ترجمة،

500
00:40:02,900 --> 00:40:06,820
انا ذاهب الى المضي قدما وانها مجرد مجموعة يساوي عودة كاذبة.

501
00:40:06,820 --> 00:40:09,980
الآن هذه الوظيفة فقط لن تفعل أي شيء ويقدم دائما أن

502
00:40:09,980 --> 00:40:14,010
القيمة التي نبحث عنها ليست في الشجرة.

503
00:40:14,010 --> 00:40:16,280
>> في هذه المرحلة، هو على الأرجح فكرة جيدة -

504
00:40:16,280 --> 00:40:19,600
لقد كتبنا منذ مجموعة كاملة من التعليمات البرمجية، ونحن لم يحاكم حتى اختباره حتى الآن -

505
00:40:19,600 --> 00:40:22,590
للتأكد من أن يقوم بإعداد جميع.

506
00:40:22,590 --> 00:40:27,460
هناك اثنين من الأشياء التي يتعين علينا القيام به للتأكد من أن هذا سيتم ترجمة الواقع.

507
00:40:27,460 --> 00:40:33,530
أولا، معرفة ما إذا كنا باستخدام أية وظائف المكتبات في أي أننا لم تدرج بعد.

508
00:40:33,530 --> 00:40:37,940
وظائف استخدمنا حتى الآن malloc،

509
00:40:37,940 --> 00:40:43,310
ثم قمنا أيضا تم استخدام هذا النوع - هذا النوع غير قياسي يسمى 'bool' -

510
00:40:43,310 --> 00:40:45,750
يتم تضمين التي في ملف الرأس BOOL القياسية.

511
00:40:45,750 --> 00:40:53,250
نحن بالتأكيد نريد أن تشمل bool.h القياسية لنوع BOOL،

512
00:40:53,250 --> 00:40:59,230
ونريد أيضا أن تدرج # lib.h القياسية لمكتبات القياسية

513
00:40:59,230 --> 00:41:03,530
التي تشمل malloc، ومجانا، وذلك كله.

514
00:41:03,530 --> 00:41:08,660
لذلك، تصغير، ونحن في طريقنا إلى الإقلاع عن التدخين.

515
00:41:08,660 --> 00:41:14,190
دعونا نحاول وتأكد من أن هذا فعلا الترجمة.

516
00:41:14,190 --> 00:41:18,150
ونحن نرى أن تفعل ذلك، لذلك نحن على الطريق الصحيح.

517
00:41:18,150 --> 00:41:22,990
>> دعونا فتح binary_tree.c مرة أخرى.

518
00:41:22,990 --> 00:41:34,530
يقوم بإعداد. دعونا نذهب إلى أسفل والتأكد من أننا إدراج بعض المكالمات للعمل لدينا يحتوي على -

519
00:41:34,530 --> 00:41:40,130
فقط للتأكد من أن هذا هو كل شيء حسن وجيد.

520
00:41:40,130 --> 00:41:43,170
على سبيل المثال، عندما فعلنا بعض عمليات البحث في شجرة لدينا في وقت سابق،

521
00:41:43,170 --> 00:41:48,500
حاولنا بحث عن القيم 6، 10، و 1، وكنا نعرف أن 6 كان في الشجرة،

522
00:41:48,500 --> 00:41:52,220
كان 10 وليس في الشجرة، و 1 لم يكن في الشجرة سواء.

523
00:41:52,220 --> 00:41:57,230
دعونا نستخدم تلك المكالمات عينة باعتبارها وسيلة لمعرفة ما إذا كان أو لا

524
00:41:57,230 --> 00:41:59,880
لدينا يحتوي على وظيفة تعمل.

525
00:41:59,880 --> 00:42:05,210
من أجل القيام بذلك، أنا ذاهب إلى استخدام الدالة printf،

526
00:42:05,210 --> 00:42:10,280
ونحن في طريقنا للطباعة نتيجة الدعوة إلى يتضمنها.

527
00:42:10,280 --> 00:42:13,280
انا ذاهب الى وضعها في سلسلة "يحتوي على (D٪) = بسبب

528
00:42:13,280 --> 00:42:20,470
 ونحن في طريقنا إلى سد العجز في القيمة التي نحن في طريقنا للبحث عن،

529
00:42:20,470 --> 00:42:27,130
و=٪ S \ N "واستخدام ذلك كسلسلة تنسيق لدينا.

530
00:42:27,130 --> 00:42:30,720
ونحن في طريقنا لمجرد أن نرى - حرفيا طباعة على الشاشة -

531
00:42:30,720 --> 00:42:32,060
ما يشبه استدعاء دالة.

532
00:42:32,060 --> 00:42:33,580
هذه ليست في الواقع استدعاء دالة.

533
00:42:33,580 --> 00:42:36,760
 هذا هو مجرد سلسلة مصممة لتبدو وكأنها استدعاء دالة.

534
00:42:36,760 --> 00:42:41,140
>> الآن، ونحن في طريقنا إلى سد العجز في القيم.

535
00:42:41,140 --> 00:42:43,580
ونحن في طريقنا لمحاولة يحتوي على 6،

536
00:42:43,580 --> 00:42:48,340
ثم ما نحن بصدد القيام به هنا هو استخدام هذا المشغل الثلاثي.

537
00:42:48,340 --> 00:42:56,340
دعونا نرى - يحتوي على 6 - حتى الآن، لقد الواردة 6 و إذا تحتوي على 6 صحيحا،

538
00:42:56,340 --> 00:43:01,850
السلسلة التي نحن في طريقنا لإرسالها إلى الطابع تنسيق٪ S

539
00:43:01,850 --> 00:43:04,850
ستكون السلسلة "الحقيقية".

540
00:43:04,850 --> 00:43:07,690
دعونا تمرير أكثر من قليلا.

541
00:43:07,690 --> 00:43:16,210
خلاف ذلك، ونحن نريد لإرسال سلسلة "كاذبة" إذا يحتوي على 6 بإرجاع FALSE.

542
00:43:16,210 --> 00:43:19,730
هذا هو أحمق قليلا المظهر، ولكن الرقم الأول قد كذلك توضيح

543
00:43:19,730 --> 00:43:23,780
ما المشغل الثلاثي يبدو أننا لم يطلعوا عليه لحظة.

544
00:43:23,780 --> 00:43:27,670
سيكون هذا لطيف، طريقة سهلة لمعرفة ما اذا كان لدينا يحتوي على وظيفة تعمل.

545
00:43:27,670 --> 00:43:30,040
انا ذاهب للتمرير إلى أكثر إلى اليسار،

546
00:43:30,040 --> 00:43:39,900
وانا ذاهب لنسخ ولصق هذا الخط عدة مرات.

547
00:43:39,900 --> 00:43:44,910
تغيرت بعض هذه القيم حولها،

548
00:43:44,910 --> 00:43:59,380
ولذلك فإن هذا سيكون 1، وهذا سيكون 10.

549
00:43:59,380 --> 00:44:02,480
>> في هذه المرحلة لدينا وظيفة يحتوي على لطيفة.

550
00:44:02,480 --> 00:44:06,080
لدينا بعض الاختبارات، وسنرى ما إذا كان هذا جميع الأعمال.

551
00:44:06,080 --> 00:44:08,120
عند هذه النقطة لقد كتبنا رمز بعض أكثر.

552
00:44:08,120 --> 00:44:13,160
الوقت لإنهاء وتأكد من أن كل شيء لا يزال يجمع.

553
00:44:13,160 --> 00:44:20,360
إنهاء خارج، والآن دعونا نحاول جعل شجرة ثنائية مرة أخرى.

554
00:44:20,360 --> 00:44:22,260
حسنا، يبدو أننا قد حصلت على خطأ،

555
00:44:22,260 --> 00:44:26,930
ونحن قد حصلت على هذا الإعلان صراحة وظيفة مكتبة printf.

556
00:44:26,930 --> 00:44:39,350
يبدو أننا في حاجة للذهاب في وتشمل # standardio.h.

557
00:44:39,350 --> 00:44:45,350
ومع ذلك، ينبغي تجميع كل شيء. نحن جميعا جيدة.

558
00:44:45,350 --> 00:44:50,420
الآن دعونا حاول تشغيل شجرة ثنائية ونرى ما سيحدث.

559
00:44:50,420 --> 00:44:53,520
نحن هنا،. / binary_tree،

560
00:44:53,520 --> 00:44:55,190
ونحن نرى أنه، كما كنا نتوقع -

561
00:44:55,190 --> 00:44:56,910
لأننا لم تنفذ حتى الآن يحتوي على،

562
00:44:56,910 --> 00:44:59,800
أو بدلا من ذلك، قد وضعت للتو في المقابل كاذبة -

563
00:44:59,800 --> 00:45:03,300
ونحن نرى أن مجرد انها كاذبة العودة لجميع من لهم،

564
00:45:03,300 --> 00:45:06,180
بحيث انها جميعها تعمل في معظمها جيدة إلى حد ما.

565
00:45:06,180 --> 00:45:11,860
>> دعونا نعود في الواقع وتنفيذ يحتوي على هذه النقطة.

566
00:45:11,860 --> 00:45:17,490
أنا ذاهب إلى التمرير لأسفل، في التكبير، و-

567
00:45:17,490 --> 00:45:22,330
تذكر، وكان الخوارزمية التي استخدمناها أن بدأنا في عقدة الجذر

568
00:45:22,330 --> 00:45:28,010
وبعد ذلك في كل عقدة التي نواجهها، ونحن نفعل مقارنة،

569
00:45:28,010 --> 00:45:32,380
وبناء على هذه المقارنة أن ننتقل إما إلى اليسار أو الطفل للطفل الحق.

570
00:45:32,380 --> 00:45:39,670
هذا هو الذهاب الى نظرة مشابهة جدا لثنائي رمز البحث التي كتبنا في وقت سابق من هذا المصطلح.

571
00:45:39,670 --> 00:45:47,810
عندما نبدأ قبالة، ونحن نعلم أننا نريد أن نتمسك العقدة الحالية

572
00:45:47,810 --> 00:45:54,050
أننا نبحث في، والعقدة الحالية ستكون تهيئة إلى عقدة الجذر.

573
00:45:54,050 --> 00:45:56,260
والآن، ونحن في طريقنا للحفاظ يمر الشجرة،

574
00:45:56,260 --> 00:45:58,140
وتذكر أن لدينا حالة وقف -

575
00:45:58,140 --> 00:46:01,870
 عندما عملنا في الواقع من خلال المثال باليد -

576
00:46:01,870 --> 00:46:03,960
عندما واجهناها كانت عقدة فارغة،

577
00:46:03,960 --> 00:46:05,480
لا عندما نظرنا في طفل فارغة،

578
00:46:05,480 --> 00:46:09,620
بل عندما انتقلنا فعلا إلى عقدة في شجرة

579
00:46:09,620 --> 00:46:12,640
ووجدت أننا في عقدة فارغة.

580
00:46:12,640 --> 00:46:20,720
ونحن في طريقنا لتكرار حتى الحالي لا تساوي قيمة خالية.

581
00:46:20,720 --> 00:46:22,920
وما نحن ذاهبون للقيام؟

582
00:46:22,920 --> 00:46:31,610
ونحن في طريقنا لمعرفة ما إذا (الحالي - قيمة ==> القيمة)،

583
00:46:31,610 --> 00:46:35,160
ثم نحن نعلم أن لدينا فعلا وجدت العقدة التي نحن تبحث عنه.

584
00:46:35,160 --> 00:46:40,450
حتى هنا، يمكننا العودة الحقيقية.

585
00:46:40,450 --> 00:46:49,830
خلاف ذلك، ونحن نريد أن نرى ما إذا كان أو لم يكن هو قيمة أقل من القيمة.

586
00:46:49,830 --> 00:46:53,850
إذا قيمة العقدة الحالية هي أقل من القيمة التي تبحث عنها،

587
00:46:53,850 --> 00:46:57,280
ونحن في طريقنا للتحرك إلى اليمين.

588
00:46:57,280 --> 00:47:10,600
لذلك، الحالي = الحالي -> right_child، وغير ذلك، ونحن في طريقنا للانتقال إلى اليسار.

589
00:47:10,600 --> 00:47:17,480
= الحالي الحالي -> left_child؛ بسيط جدا.

590
00:47:17,480 --> 00:47:22,830
>> ربما كنت تعترف الحلقة التي تبدو مشابهة جدا لهذا من

591
00:47:22,830 --> 00:47:27,580
البحث الثنائية في وقت سابق من هذا المصطلح، إلا بعد ذلك كنا نتعامل مع منتصف، وانخفاض وارتفاع.

592
00:47:27,580 --> 00:47:30,000
هنا، علينا فقط أن ننظر إلى القيمة الحالية،

593
00:47:30,000 --> 00:47:31,930
لذلك فمن طيفة وبسيطة.

594
00:47:31,930 --> 00:47:34,960
دعونا نتأكد من هذا الرمز هو العمل.

595
00:47:34,960 --> 00:47:42,780
أولا، تأكد من أنه يجمع. يبدو أنه لا.

596
00:47:42,780 --> 00:47:47,920
دعونا نحاول تشغيله.

597
00:47:47,920 --> 00:47:50,160
وبالفعل، فإنه يطبع من كل ما كنا نتوقع.

598
00:47:50,160 --> 00:47:54,320
يجدها 6 في الشجرة، لا العثور على 10 لأن 10 ليست في الشجرة،

599
00:47:54,320 --> 00:47:57,740
ولا العثور على 1 إما لأن 1 أيضا ليس في الشجرة.

600
00:47:57,740 --> 00:48:01,420
بارد الاشياء.

601
00:48:01,420 --> 00:48:04,470
>> بخير. دعونا نعود لمواصفات لدينا ونرى ما هي الخطوة التالية.

602
00:48:04,470 --> 00:48:07,990
الآن، انها تريد إضافة المزيد من العقد إلى شجرة لدينا.

603
00:48:07,990 --> 00:48:11,690
انها تريد لإضافة 5، 2، و 8، وتأكد من أن لدينا يحتوي على رمز

604
00:48:11,690 --> 00:48:13,570
لا يزال يعمل كما هو متوقع.

605
00:48:13,570 --> 00:48:14,900
دعونا نذهب نفعل ذلك.

606
00:48:14,900 --> 00:48:19,430
في هذه المرحلة، بدلا من القيام بذلك نسخة مزعج ولصق مرة أخرى،

607
00:48:19,430 --> 00:48:23,770
دعونا كتابة دالة لإنشاء عقدة في الواقع.

608
00:48:23,770 --> 00:48:27,740
إذا كان لنا أن انتقل لأسفل على طول الطريق الرئيسي ل، ونحن نرى أن كنا نفعل ذلك

609
00:48:27,740 --> 00:48:31,210
مشابهة جدا رمز مرارا وتكرارا في كل مرة أننا نريد لإنشاء عقدة.

610
00:48:31,210 --> 00:48:39,540
>> دعونا كتابة دالة التي من شأنها فعلا بناء عقدة بالنسبة لنا وإعادته.

611
00:48:39,540 --> 00:48:41,960
انا ذاهب الى نسميها build_node.

612
00:48:41,960 --> 00:48:45,130
انا ذاهب لبناء عقدة مع قيمة معينة.

613
00:48:45,130 --> 00:48:51,040
تكبير هنا.

614
00:48:51,040 --> 00:48:56,600
أول شيء أنا بصدد القيام به هو خلق مساحة للفي الواقع عقدة على الكومة.

615
00:48:56,600 --> 00:49:05,400
لذلك، عقدة * ن = malloc (sizeof (عقدة))، ن -> قيمة = القيمة؛

616
00:49:05,400 --> 00:49:14,960
ثم هنا، وانا ذاهب فقط لتهيئة كافة الحقول لتكون القيم المناسبة.

617
00:49:14,960 --> 00:49:22,500
وفي النهاية، سوف نعود لدينا عقدة.

618
00:49:22,500 --> 00:49:28,690
بخير. شيء واحد هو أن نلاحظ أن هذه الوظيفة هنا

619
00:49:28,690 --> 00:49:34,320
هو الذهاب الى العودة مؤشر إلى الذاكرة التي تم تخصيصها كومة.

620
00:49:34,320 --> 00:49:38,880
ما هو الجميل في هذا هو أن هذه العقدة الآن -

621
00:49:38,880 --> 00:49:42,420
علينا أن نعلن ذلك على كومة لأنه إذا أعلنا ذلك على المكدس

622
00:49:42,420 --> 00:49:45,050
ونحن لن تكون قادرة على القيام بذلك في هذه الوظيفة مثل هذا.

623
00:49:45,050 --> 00:49:47,690
ومن شأن ذلك أن الذاكرة الخروج من نطاق

624
00:49:47,690 --> 00:49:51,590
وسيكون باطلا إذا حاولنا الوصول إليه في وقت لاحق.

625
00:49:51,590 --> 00:49:53,500
نحن نعلن منذ كومة-تخصيص الذاكرة،

626
00:49:53,500 --> 00:49:55,830
نحن ستكون لدينا لرعاية تحرير في وقت لاحق

627
00:49:55,830 --> 00:49:58,530
لبرنامجنا للا يتسرب أي الذاكرة.

628
00:49:58,530 --> 00:50:01,270
كنا التسيير على أن لكل شيء آخر في التعليمات البرمجية

629
00:50:01,270 --> 00:50:02,880
فقط للتبسيط في ذلك الوقت،

630
00:50:02,880 --> 00:50:05,610
ولكن إذا كنت من أي وقت مضى وظيفة الكتابة التي تبدو مثل هذا

631
00:50:05,610 --> 00:50:10,370
حيث كنت قد حصلت - بعض تسميتها malloc أو داخل realloc -

632
00:50:10,370 --> 00:50:14,330
تريد للتأكد من أن كنت وضعت بعض النوع من التعليقات هنا أن يقول:

633
00:50:14,330 --> 00:50:29,970
مهلا، أنت تعرف، والعودة عقدة كومة تخصيصها تهيئة مع قيمة تم تمريرها في.

634
00:50:29,970 --> 00:50:33,600
ثم كنت تريد للتأكد من أن كنت وضعت في نوع من المذكرة التي تقول

635
00:50:33,600 --> 00:50:41,720
يجب على المتصل تحرير الذاكرة إرجاعها.

636
00:50:41,720 --> 00:50:45,450
وبهذه الطريقة، إذا كان شخص ما من أي وقت مضى يذهب ويستخدم تلك الوظيفة،

637
00:50:45,450 --> 00:50:48,150
أنهم يعرفون أن كل ما نعود من تلك الوظيفة

638
00:50:48,150 --> 00:50:50,870
وعند نقطة ما يجب أن يتم اطلاق سراحهم.

639
00:50:50,870 --> 00:50:53,940
>> على افتراض أن كل شيء على ما يرام وجيدة هنا،

640
00:50:53,940 --> 00:51:02,300
يمكننا أن نذهب إلى أسفل في نظامنا واستبدال كل هذه الخطوط هنا

641
00:51:02,300 --> 00:51:05,410
مع دعوات لدينا وظيفة العقدة الإنشاء.

642
00:51:05,410 --> 00:51:08,170
دعونا نفعل ذلك بسرعة حقا.

643
00:51:08,170 --> 00:51:15,840
والجزء الأول أننا لن يحل محل هذا الجزء هو أسفل هنا

644
00:51:15,840 --> 00:51:18,520
في الجزء السفلي حيث أننا سلك فعليا حتى العقد للإشارة إلى بعضها البعض،

645
00:51:18,520 --> 00:51:21,030
لأن ذلك لا نستطيع أن نفعل في وظيفتنا.

646
00:51:21,030 --> 00:51:37,400
ولكن، دعونا نفعل الجذر = build_node (7)؛ العقدة = * ثلاثة build_node (3)؛

647
00:51:37,400 --> 00:51:47,980
* ستة عقدة = build_node (6)؛ العقدة * تسعة = build_node (9)؛

648
00:51:47,980 --> 00:51:52,590
والآن، ونحن أيضا عن رغبته في إضافة العقد ل-

649
00:51:52,590 --> 00:52:03,530
* خمسة عقدة = build_node (5)؛ العقدة * ثمانية = build_node (8)؛

650
00:52:03,530 --> 00:52:09,760
وما هو عقدة أخرى؟ دعونا نرى هنا. أردنا أن تضيف أيضا 2 -

651
00:52:09,760 --> 00:52:20,280
* اثنين = عقدة build_node (2)؛

652
00:52:20,280 --> 00:52:26,850
بخير. في هذه المرحلة، ونحن نعلم أننا قد حصلت على 7، 3، 9، و 6 في

653
00:52:26,850 --> 00:52:30,320
كل ما يصل السلكية مناسب، ولكن ماذا عن 5، 8، و 2 من؟

654
00:52:30,320 --> 00:52:33,550
للحفاظ على كل شيء في الترتيب المناسب،

655
00:52:33,550 --> 00:52:39,230
ونحن نعلم أن الأطفال الثلاثة، وهو الحق هو 6.

656
00:52:39,230 --> 00:52:40,890
لذا، إذا نحن في طريقنا لإضافة 5،

657
00:52:40,890 --> 00:52:46,670
ال 5 ينتمي أيضا في الجانب الأيمن من شجرة منها 3 هو الجذر،

658
00:52:46,670 --> 00:52:50,440
5 حتى ينتمي والطفل الأيسر من 6.

659
00:52:50,440 --> 00:52:58,650
يمكننا القيام بذلك عن طريق قائلا، ستة -> left_child = الخمسة؛

660
00:52:58,650 --> 00:53:10,790
ومن ثم ال 8 وينتمي الطفل الأيسر من 9، 9 حتى -> left_child = 8؛

661
00:53:10,790 --> 00:53:22,190
وثم 2 هو الطفل الأيسر من 3، ولذا فإننا يمكن أن نفعل ذلك هنا حتى - اليك -> left_child = اثنين؛

662
00:53:22,190 --> 00:53:27,730
إذا كنت لا تتبع تماما إلى جانب ذلك، أقترح عليك استدراجه من نفسك.

663
00:53:27,730 --> 00:53:35,660
>> بخير. دعونا حفظ هذا. دعونا نذهب الى هناك وتأكد من أنه لا يجمع،

664
00:53:35,660 --> 00:53:40,760
ومن ثم يمكننا أن نضيف في المكالمات يحتوي دينا.

665
00:53:40,760 --> 00:53:44,120
كل شيء يبدو وكأنه لا يزال يجمع.

666
00:53:44,120 --> 00:53:51,790
دعونا نذهب في وإضافة في بعض يحتوي المكالمات.

667
00:53:51,790 --> 00:53:59,640
مرة أخرى، انا ذاهب للقيام قليلا من النسخ واللصق.

668
00:53:59,640 --> 00:54:15,860
الآن دعونا بحث عن 8، 5، و 2. بخير.

669
00:54:15,860 --> 00:54:28,330
دعونا نتأكد من أن هذا يبدو كل شيء لا تزال جيدة. عظيم! حفظ والإقلاع عن التدخين.

670
00:54:28,330 --> 00:54:33,220
الآن دعونا جعل وتجميع، والآن دعونا تشغيل.

671
00:54:33,220 --> 00:54:37,540
من نتائج، يبدو أن كل شيء يعمل فقط لطيفة وجيدة.

672
00:54:37,540 --> 00:54:41,780
عظيم! حتى الآن لدينا الدالة مكتوبة على لدينا.

673
00:54:41,780 --> 00:54:46,160
دعونا نمضي قدما وبدء العمل على كيفية إدراج العقد في الشجرة

674
00:54:46,160 --> 00:54:50,000
منذ ذلك الحين، ونحن نفعل ذلك الآن، الأمور ليست جميلة جدا.

675
00:54:50,000 --> 00:54:52,280
>> إذا عدنا للمواصفات،

676
00:54:52,280 --> 00:55:00,540
ما يطلب منا كتابة دالة يسمى إدراج - مرة أخرى، إرجاع BOOL

677
00:55:00,540 --> 00:55:04,400
لأم لا يمكننا إدراج فعلا عقدة في شجرة -

678
00:55:04,400 --> 00:55:07,710
ومن ثم يتم تحديد القيمة لتضاف الى الشجرة كما

679
00:55:07,710 --> 00:55:11,060
والحجة الوحيدة لإدراج دالة لدينا.

680
00:55:11,060 --> 00:55:18,180
سوف نعود صحيح لو تمكنا من إدراج قيمة في الواقع تحتوي على عقدة في الشجرة،

681
00:55:18,180 --> 00:55:20,930
وهو ما يعني أننا، واحد، كان ذاكرة كافية،

682
00:55:20,930 --> 00:55:24,840
ومن ثم اثنين، تلك العقدة لم تكن موجودة من قبل في الشجرة منذ -

683
00:55:24,840 --> 00:55:32,170
نتذكر، ونحن لن يكون لها قيم مكررة في شجرة، فقط لجعل الامور بسيطة.

684
00:55:32,170 --> 00:55:35,590
بخير. عودة إلى التعليمات البرمجية.

685
00:55:35,590 --> 00:55:44,240
فتحه. تكبير قليلا، انتقل بعد ذلك إلى أسفل.

686
00:55:44,240 --> 00:55:47,220
لنضع إدراج دالة الحق فوق يحتوي عليها.

687
00:55:47,220 --> 00:55:56,360
مرة أخرى، فإنه سيكون من دعا إدراج BOOL (الباحث القيمة).

688
00:55:56,360 --> 00:56:01,840
إعطائها مساحة أكثر من ذلك بقليل، وبعد ذلك، كإعداد افتراضي،

689
00:56:01,840 --> 00:56:08,870
دعونا نضع في المقابل كاذبة في النهاية.

690
00:56:08,870 --> 00:56:22,620
الآن إلى أسفل في قاع، دعونا نمضي قدما وبدلا من بناء يدويا العقد

691
00:56:22,620 --> 00:56:27,900
في أنفسنا والأسلاك الرئيسية لهم حتى للإشارة إلى بعضها البعض مثل نقوم به،

692
00:56:27,900 --> 00:56:30,600
سوف نعتمد على إدراج دالة لدينا للقيام بذلك.

693
00:56:30,600 --> 00:56:35,510
لن نعتمد على إدراج دالة لدينا لبناء شجرة بأكملها من الصفر فقط حتى الآن،

694
00:56:35,510 --> 00:56:39,970
بل سوف نتخلص من هذه الخطوط - we'll التعليق خارج هذه الأسطر -

695
00:56:39,970 --> 00:56:43,430
أن بناء العقد 5، 8، و 2.

696
00:56:43,430 --> 00:56:55,740
وبدلا من ذلك، سنقوم بإدراج المكالمات إلى إدراج دالة لدينا

697
00:56:55,740 --> 00:57:01,280
للتأكد من أن الذي يعمل في الواقع.

698
00:57:01,280 --> 00:57:05,840
هنا نذهب.

699
00:57:05,840 --> 00:57:09,300
>> الآن لدينا تعليق الخروج هذه الخطوط.

700
00:57:09,300 --> 00:57:13,700
ليس لدينا سوى 7، 3، 9، و 6 في شجرة لدينا في هذه المرحلة.

701
00:57:13,700 --> 00:57:18,870
للتأكد من أن هذا هو كل عمل،

702
00:57:18,870 --> 00:57:25,050
يمكننا تصغير، وجعل شجرة لدينا ثنائي،

703
00:57:25,050 --> 00:57:30,750
تشغيله، ويمكننا أن نرى أن يحتوي تقول لنا الآن أننا على حق تماما -

704
00:57:30,750 --> 00:57:33,110
5، 8، و 2 لم تعد موجودة في الشجرة.

705
00:57:33,110 --> 00:57:37,960
العودة إلى رمز،

706
00:57:37,960 --> 00:57:41,070
وكيف نحن ذاهبون لإدراج؟

707
00:57:41,070 --> 00:57:46,290
تذكر ما فعلناه عندما كنا في الواقع إدراج 5، 8، و 2 سابقا.

708
00:57:46,290 --> 00:57:50,100
لعبنا هذه المباراة Plinko حيث بدأنا في الجذر،

709
00:57:50,100 --> 00:57:52,780
ذهب إلى أسفل شجرة واحدة تلو الأخرى من جانب واحد

710
00:57:52,780 --> 00:57:54,980
حتى وجدنا الفجوة المناسبة،

711
00:57:54,980 --> 00:57:57,570
السلكية وبعد ذلك نحن في عقدة في البقعة المناسبة.

712
00:57:57,570 --> 00:57:59,480
ونحن في طريقنا لفعل الشيء نفسه.

713
00:57:59,480 --> 00:58:04,070
هذا هو في الأساس مثل كتابة التعليمات البرمجية التي كنا في وظيفة يحتوي على

714
00:58:04,070 --> 00:58:05,910
العثور على المكان الذي يجب أن تكون العقدة،

715
00:58:05,910 --> 00:58:10,560
ثم ونحن في طريقنا فقط لإدراج عقدة هناك.

716
00:58:10,560 --> 00:58:17,000
لنبدأ القيام بذلك.

717
00:58:17,000 --> 00:58:24,200
>> لذلك لدينا عقدة الجذر = * الحالي، ونحن في طريقنا لمجرد اتباع يحتوي على رمز

718
00:58:24,200 --> 00:58:26,850
حتى نجد أنه لا يعمل تماما بالنسبة لنا.

719
00:58:26,850 --> 00:58:32,390
ونحن في طريقنا للذهاب من خلال شجرة في حين أن العنصر الحالي هو غير فارغة،

720
00:58:32,390 --> 00:58:45,280
وإذا وجدنا أن قيمة الحالي هو يساوي القيمة التي نحاول إدراج -

721
00:58:45,280 --> 00:58:49,600
حسنا، هذا هو واحد من الحالات التي لم نتمكن من إدراج فعلا عقدة

722
00:58:49,600 --> 00:58:52,730
في شجرة لأن هذا يعني لدينا قيمة مكررة.

723
00:58:52,730 --> 00:58:59,010
هنا ونحن في طريقنا للعودة في الواقع زائفة.

724
00:58:59,010 --> 00:59:08,440
الآن، الا اذا قيمة الحالي هو أقل من القيمة،

725
00:59:08,440 --> 00:59:10,930
نحن نعرف الآن أن نتحرك إلى اليمين

726
00:59:10,930 --> 00:59:17,190
 لأن القيمة ينتمي في النصف الأيمن من الشجرة الحالي.

727
00:59:17,190 --> 00:59:30,110
خلاف ذلك، ونحن في طريقنا للانتقال إلى اليسار.

728
00:59:30,110 --> 00:59:37,980
وهذا في الأساس لدينا تعمل على حق هناك.

729
00:59:37,980 --> 00:59:41,820
>> عند هذه النقطة، مرة واحدة لقد أكملنا هذه الحلقة من الوقت،

730
00:59:41,820 --> 00:59:47,350
المؤشر الحالي لدينا سوف يتم الإشارة إلى قيمة خالية

731
00:59:47,350 --> 00:59:51,540
إذا لم الدالة عادوا بالفعل.

732
00:59:51,540 --> 00:59:58,710
نحن لها بالتالي الحالي في المكان الذي نريد إدراج عقدة جديدة.

733
00:59:58,710 --> 01:00:05,210
ما زال يتعين القيام به هو بناء في الواقع عقدة جديدة،

734
01:00:05,210 --> 01:00:08,480
والتي يمكن أن نقوم به بسهولة جدا.

735
01:00:08,480 --> 01:00:14,930
يمكننا استخدام لدينا عقدة بناء فائقة مفيد وظيفة،

736
01:00:14,930 --> 01:00:17,210
وشيء لم نفعل سابقا -

737
01:00:17,210 --> 01:00:21,400
نحن فقط نوع من تولى أمرا مفروغا منه ولكن الآن سنفعل فقط للتأكد من -

738
01:00:21,400 --> 01:00:27,130
سنقوم اختبار للتأكد من أن القيمة التي تم إرجاعها بواسطة عقدة جديدة في الواقع

739
01:00:27,130 --> 01:00:33,410
غير فارغة، لأننا لا نريد لبدء الوصول إلى تلك الذاكرة إذا كان لاغيا.

740
01:00:33,410 --> 01:00:39,910
يمكننا اختبار للتأكد من أن عقدة جديدة لا تساوي فارغة.

741
01:00:39,910 --> 01:00:42,910
أو بدلا من ذلك، يمكننا أن نرى فقط إذا كان هو في الواقع باطلة،

742
01:00:42,910 --> 01:00:52,120
وإذا كانت فارغة، ثم يمكن أن نعود فقط كاذبة في وقت مبكر.

743
01:00:52,120 --> 01:00:59,090
>> في هذه المرحلة، علينا أن سلك عقدة جديدة إلى المركز المناسب لها في الشجرة.

744
01:00:59,090 --> 01:01:03,510
إذا نظرنا إلى الوراء في الرئيسية وأين كنا فعلا الأسلاك في القيم من قبل،

745
01:01:03,510 --> 01:01:08,470
ونحن نرى أن الطريقة كنا نفعل عندما كنا نرغب في وضع 3 في شجرة

746
01:01:08,470 --> 01:01:11,750
ونحن الوصول إلى الطفل الأيسر من جذورها.

747
01:01:11,750 --> 01:01:14,920
كان لدينا عندما نضع 9 في الشجرة، للوصول إلى حق الطفل جذورها.

748
01:01:14,920 --> 01:01:21,030
كان علينا أن يكون مؤشر إلى الوالدين من أجل وضع قيمة جديدة في الشجرة.

749
01:01:21,030 --> 01:01:24,430
التمرير مرة أخرى إلى إدراج، وهذا لن تعمل تماما هنا

750
01:01:24,430 --> 01:01:27,550
لأننا لم يكن لديك مؤشر الرئيسي.

751
01:01:27,550 --> 01:01:31,650
ما نريد أن تكون قادرة على القيام به هو، في هذه المرحلة،

752
01:01:31,650 --> 01:01:37,080
تحقق قيمة الأصل وانظر - حسنا، يا الهي،

753
01:01:37,080 --> 01:01:41,990
إذا قيمة الأصل هو أقل من القيمة الحالية،

754
01:01:41,990 --> 01:01:54,440
ثم يجب الطفل الأم الحق يكون عقدة جديدة؛

755
01:01:54,440 --> 01:02:07,280
خلاف ذلك، يجب الطفل الأم اليسار يكون عقدة جديدة.

756
01:02:07,280 --> 01:02:10,290
ولكن، لم يكن لدينا هذا المؤشر الرئيسي تماما حتى الآن.

757
01:02:10,290 --> 01:02:15,010
>> من أجل الحصول على ذلك، ونحن في طريقنا في الواقع لدينا لتتبع ذلك ونحن نمضي من خلال شجرة

758
01:02:15,010 --> 01:02:18,440
والعثور على بقعة مناسبة في حلقة اعلاه.

759
01:02:18,440 --> 01:02:26,840
يمكننا القيام بذلك عن طريق التمرير لأعلى مرة أخرى إلى أعلى إدراج دالة لدينا

760
01:02:26,840 --> 01:02:32,350
وتتبع مؤشر متغير آخر يسمى الأصل.

761
01:02:32,350 --> 01:02:39,340
ونحن في طريقنا لتعيين أنه يساوي فارغة في البداية،

762
01:02:39,340 --> 01:02:43,640
ثم في كل مرة نذهب من خلال الشجرة،

763
01:02:43,640 --> 01:02:51,540
ونحن في طريقنا لتعيين المؤشر الرئيسي لتتناسب مع مؤشر الحالية.

764
01:02:51,540 --> 01:02:59,140
تعيين الأصل تساوي الحالي.

765
01:02:59,140 --> 01:03:02,260
بهذه الطريقة، في كل مرة نمر بها،

766
01:03:02,260 --> 01:03:05,550
ونحن في طريقنا لضمان أن ما يحصل مؤشر الحالية زيادة

767
01:03:05,550 --> 01:03:12,640
المؤشر الرئيسي يلي ذلك - فقط مستوى واحد أعلى من المؤشر الحالي في الشجرة.

768
01:03:12,640 --> 01:03:17,370
أن جميع تبدو جيدة.

769
01:03:17,370 --> 01:03:22,380
>> أعتقد أن الشيء الوحيد الذي سنقوم ترغب في ضبط هذا هو بناء فارغة عقدة العودة.

770
01:03:22,380 --> 01:03:25,380
من أجل الحصول على عقدة لبناء الواقع بنجاح العودة فارغة،

771
01:03:25,380 --> 01:03:31,060
سيكون لدينا لتعديل هذا الرمز،

772
01:03:31,060 --> 01:03:37,270
لأن هنا، ونحن لم اختبارها للتأكد من أن malloc عاد مؤشر صالح.

773
01:03:37,270 --> 01:03:53,390
لذا، إذا (ن = NULL!)، ثم -

774
01:03:53,390 --> 01:03:55,250
إذا malloc عاد مؤشر صالحة، ثم سنقوم تهيئة ذلك؛

775
01:03:55,250 --> 01:04:02,540
خلاف ذلك، سوف نعود فقط والتي في نهاية المطاف العودة فارغة بالنسبة لنا.

776
01:04:02,540 --> 01:04:13,050
الآن يبدو كل شيء جيد جدا. دعونا نتأكد من هذا الواقع يجمع.

777
01:04:13,050 --> 01:04:22,240
جعل شجرة ثنائية، وأوه، لقد حصلت على بعض الاشياء يجري هنا.

778
01:04:22,240 --> 01:04:29,230
>> ونحن قد حصلت على وظيفة إعلان ضمني بناء العقدة.

779
01:04:29,230 --> 01:04:31,950
مرة أخرى، مع هذه المجمعات، ونحن في طريقنا للبدء في الأعلى.

780
01:04:31,950 --> 01:04:36,380
ما يعني أنه يجب أن ادعو بناء العقدة قبل لقد أعلن فعلا.

781
01:04:36,380 --> 01:04:37,730
دعونا نعود إلى رمز بسرعة حقا.

782
01:04:37,730 --> 01:04:43,510
انتقل لأسفل، والمؤكد، وأعلن مهامي إدراج

783
01:04:43,510 --> 01:04:47,400
أعلاه وظيفة العقدة إنشاء،

784
01:04:47,400 --> 01:04:50,070
ولكنني أحاول أن استخدام بناء عقدة داخل إدراج.

785
01:04:50,070 --> 01:05:06,610
انا ذاهب للذهاب في ونسخة - ثم لصق وظيفة العقدة بناء الطريق حتى هنا في الأعلى.

786
01:05:06,610 --> 01:05:11,750
وبهذه الطريقة، نأمل أن تعمل. دعونا نعطي هذا آخر الذهاب.

787
01:05:11,750 --> 01:05:18,920
الآن يقوم بإعداد جميع. كل شيء جيد.

788
01:05:18,920 --> 01:05:21,640
>> ولكن في هذه المرحلة، ونحن في الواقع لم يسمى وظيفتنا إدراج.

789
01:05:21,640 --> 01:05:26,510
نحن نعرف فقط أنه يجمع، لذلك دعونا نذهب في بعض المكالمات ووضع فيها

790
01:05:26,510 --> 01:05:28,240
دعونا نفعل ذلك في وظيفة الرئيسية لدينا.

791
01:05:28,240 --> 01:05:32,390
هنا، نحن من علق 5، 8، و 2،

792
01:05:32,390 --> 01:05:36,680
ومن ثم لم نكن سلك عنها هنا إلى أسفل.

793
01:05:36,680 --> 01:05:41,640
دعونا جعل بعض المكالمات لإدراج،

794
01:05:41,640 --> 01:05:46,440
ودعونا أيضا استخدام نفس النوع من الاشياء التي كنا

795
01:05:46,440 --> 01:05:52,810
عندما قدمنا ​​هذه الدعوات printf للتأكد من أن كل شيء لم يحصل إدراج بشكل صحيح.

796
01:05:52,810 --> 01:06:00,550
أنا ذاهب إلى نسخ ولصق،

797
01:06:00,550 --> 01:06:12,450
وبدلا من يحتوي نحن في طريقنا للقيام إدراج.

798
01:06:12,450 --> 01:06:30,140
وبدلا من 10، 6، و 1، ونحن في طريقنا لاستخدام 5، 8، و 2.

799
01:06:30,140 --> 01:06:37,320
وينبغي إدراج هذه نأمل 5، 8، و 2 في الشجرة.

800
01:06:37,320 --> 01:06:44,050
ترجمة. كل شيء جيد. الآن سنقوم بتشغيل برنامجنا في الواقع.

801
01:06:44,050 --> 01:06:47,330
>> عاد كل شيء زائف.

802
01:06:47,330 --> 01:06:53,830
لذلك، لم 5، 8، و 2 لا تذهب، ويبدو أن لا يحتوي على العثور عليها أيضا.

803
01:06:53,830 --> 01:06:58,890
ما الذي يحدث؟ دعونا تصغير.

804
01:06:58,890 --> 01:07:02,160
كانت المشكلة الأولى التي يبدو أن إدراج عودة كاذبة،

805
01:07:02,160 --> 01:07:08,750
ويبدو أن هذا هو لأننا في ترك الدعوة عودتنا كاذبة،

806
01:07:08,750 --> 01:07:14,590
ونحن في الواقع لم يعد صحيحا.

807
01:07:14,590 --> 01:07:17,880
يمكننا إعداد ذلك.

808
01:07:17,880 --> 01:07:25,290
والمشكلة الثانية هي، الآن حتى لو كنا نفعل - حفظ هذا، إنهاء هذا،

809
01:07:25,290 --> 01:07:34,530
جعل تشغيل مرة أخرى، وأنه ترجمة، ثم تشغيله -

810
01:07:34,530 --> 01:07:37,670
ونحن نرى أن هناك شيئا آخر يحدث هنا.

811
01:07:37,670 --> 01:07:42,980
ومازال 5 و 8، و 2 لم يتم العثور في الشجرة.

812
01:07:42,980 --> 01:07:44,350
الأمر كذلك، فما الذي يحدث؟

813
01:07:44,350 --> 01:07:45,700
>> دعونا نلقي نظرة على هذا في التعليمات البرمجية.

814
01:07:45,700 --> 01:07:49,790
دعونا نرى ما اذا كنا نستطيع هذا الرقم.

815
01:07:49,790 --> 01:07:57,940
نبدأ مع الوالد لا يتم فارغة.

816
01:07:57,940 --> 01:07:59,510
وضعنا المؤشر الحالي يساوي مؤشر الجذر،

817
01:07:59,510 --> 01:08:04,280
ونحن في طريقنا للعمل طريقنا إلى أسفل من خلال الشجرة.

818
01:08:04,280 --> 01:08:08,650
إذا كانت العقدة الحالية ليست فارغة، ثم نحن نعلم أننا يمكن أن تتحرك إلى أسفل قليلا.

819
01:08:08,650 --> 01:08:12,330
وضعنا المؤشر الرئيسي لدينا ليكون مساويا لمؤشر الحالية،

820
01:08:12,330 --> 01:08:15,420
التحقق من قيمة - إذا كانت القيم هي نفسها عدنا كاذبة.

821
01:08:15,420 --> 01:08:17,540
إذا كانت القيم هي أقل انتقلنا إلى اليمين؛

822
01:08:17,540 --> 01:08:20,399
خلاف ذلك، انتقلنا إلى اليسار.

823
01:08:20,399 --> 01:08:24,220
ثم نبني عقدة. أنا تكبير قليلا.

824
01:08:24,220 --> 01:08:31,410
وهنا، ونحن في طريقنا لمحاولة سلك عن القيم أن تكون هي نفسها.

825
01:08:31,410 --> 01:08:37,250
ما الذي يحدث؟ دعونا نرى ما اذا كان ربما Valgrind يمكن أن تعطينا لمحة.

826
01:08:37,250 --> 01:08:43,910
>> أود أن استخدام Valgrind فقط لأن Valgrind بسرعة حقا يدير

827
01:08:43,910 --> 01:08:46,729
ويخبرك إذا كان هناك أي أخطاء الذاكرة.

828
01:08:46,729 --> 01:08:48,300
عندما ندير Valgrind على المدونه،

829
01:08:48,300 --> 01:08:55,859
كما ترون الحق here--Valgrind./binary_tree--and ضرب أدخل.

830
01:08:55,859 --> 01:09:03,640
ترى أن لم يكن لدينا أي خطأ الذاكرة، بحيث يبدو مثل كل شيء على ما يرام حتى الآن.

831
01:09:03,640 --> 01:09:07,529
لدينا بعض التسريبات الذاكرة، التي نعرف، لأننا لسنا

832
01:09:07,529 --> 01:09:08,910
يحدث لتحرير أي من العقد لدينا.

833
01:09:08,910 --> 01:09:13,050
دعونا نحاول تشغيل GDB لمعرفة ما يجري في الواقع على.

834
01:09:13,050 --> 01:09:20,010
سنفعل GDB / binary_tree. تمهيد الامر على ما يرام.

835
01:09:20,010 --> 01:09:23,670
دعونا تعيين نقطة فاصل على إدراج.

836
01:09:23,670 --> 01:09:28,600
دعونا تشغيل.

837
01:09:28,600 --> 01:09:31,200
يبدو أننا في الواقع لا يسمى إدراج.

838
01:09:31,200 --> 01:09:39,410
يبدو أن المشكلة هي أن مجرد تغيير عندما كنت هنا في أسفل الرئيسية -

839
01:09:39,410 --> 01:09:44,279
كل هذه المكالمات من printf يحتوي على -

840
01:09:44,279 --> 01:09:56,430
لم أكن في الواقع تغيير هذه الدعوة إدراج.

841
01:09:56,430 --> 01:10:01,660
الآن دعونا يعطي هو محاولة. دعونا ترجمة.

842
01:10:01,660 --> 01:10:09,130
جميع تبدو جيدة هناك. الآن دعونا نحاول تشغيله، ونرى ما سيحدث.

843
01:10:09,130 --> 01:10:13,320
بخير! كل شيء يبدو جيدا جدا هناك.

844
01:10:13,320 --> 01:10:18,130
>> الشيء النهائية للتفكير هو، هل هناك أي حالات لهذا حافة إدراج؟

845
01:10:18,130 --> 01:10:23,170
وتبين أن، أيضا، حالة واحدة أن يكون حافة دائما مثيرة للاهتمام للتفكير

846
01:10:23,170 --> 01:10:26,250
هو، ماذا يحدث إذا شجرة الخاص بك فارغة واستدعاء هذه الدالة إدراج؟

847
01:10:26,250 --> 01:10:30,330
وسوف يعمل؟ حسنا، دعونا محاولة إعطائها.

848
01:10:30,330 --> 01:10:32,110
- binary_tree ج -

849
01:10:32,110 --> 01:10:35,810
الطريق ونحن في طريقنا لاختبار هذا، ونحن في طريقنا للذهاب الى وظيفتنا الرئيسية،

850
01:10:35,810 --> 01:10:41,690
وبدلا من الأسلاك هذه العقد حتى مثل هذا،

851
01:10:41,690 --> 01:10:56,730
ونحن في طريقنا لمجرد التعليق خارج الشيء بأكمله،

852
01:10:56,730 --> 01:11:02,620
وبدلا من الأسلاك حتى العقد أنفسنا،

853
01:11:02,620 --> 01:11:09,400
يمكننا فعلا اذهبوا الى الامام وحذف كل هذا.

854
01:11:09,400 --> 01:11:17,560
ونحن في طريقنا لجعل كل شيء دعوة للإدراج.

855
01:11:17,560 --> 01:11:49,020
لذلك، دعونا نفعل - بدلا من 5، 8، و 2، ونحن في طريقنا لإدراج 7، 3، و 9.

856
01:11:49,020 --> 01:11:58,440
وبعد ذلك سوف نريد أيضا لإدراج (6)، أيضا.

857
01:11:58,440 --> 01:12:05,190
حفظ. الإقلاع عن التدخين. جعل شجرة ثنائية.

858
01:12:05,190 --> 01:12:08,540
يقوم بإعداد جميع.

859
01:12:08,540 --> 01:12:10,320
يمكننا فقط تشغيله كما هو ونرى ما سيحدث،

860
01:12:10,320 --> 01:12:12,770
لكنه سيحتاج أيضا إلى أن تكون مهمة حقا للتأكد من أن

861
01:12:12,770 --> 01:12:14,740
ليس لدينا أي أخطاء الذاكرة،

862
01:12:14,740 --> 01:12:16,840
وبما أن هذا هو واحد من الحالات تفوقنا التي نعرفها عنه.

863
01:12:16,840 --> 01:12:20,150
>> دعونا تأكد من أنه يعمل بشكل جيد تحت Valgrind،

864
01:12:20,150 --> 01:12:28,310
الذي سوف نقوم به فقط عن طريق تشغيل Valgrind / binary_tree.

865
01:12:28,310 --> 01:12:31,110
يبدو في الواقع لدينا خطأ واحد من سياق -

866
01:12:31,110 --> 01:12:33,790
لدينا هذا الخطأ تجزئة.

867
01:12:33,790 --> 01:12:36,690
ماذا حدث؟

868
01:12:36,690 --> 01:12:41,650
يقول لنا الواقع Valgrind حيث هو.

869
01:12:41,650 --> 01:12:43,050
تصغير قليلا.

870
01:12:43,050 --> 01:12:46,040
يبدو أنه يحدث في إدراج دالة لدينا،

871
01:12:46,040 --> 01:12:53,420
حيث لدينا غير صالحة للقراءة من حجم 4 في إدراج، خط 60.

872
01:12:53,420 --> 01:13:03,590
دعونا نعود ونرى ما يجري هنا.

873
01:13:03,590 --> 01:13:05,350
تصغير سريع حقا.

874
01:13:05,350 --> 01:13:14,230
أريد أن تأكد من أنه لا يذهب إلى حافة الشاشة حتى نتمكن من رؤية كل شيء.

875
01:13:14,230 --> 01:13:18,760
سحب في أن قليلا. بخير.

876
01:13:18,760 --> 01:13:35,030
انتقل لأسفل، والمشكلة هنا هي الحق.

877
01:13:35,030 --> 01:13:40,120
ماذا يحدث إذا كان لنا أن ننكب وعقدة الحالية لدينا بالفعل فارغة،

878
01:13:40,120 --> 01:13:44,010
عقدة لدينا الأم باطل، إذا كان الأمر كذلك فإننا البصر على أعلى جدا هنا الحق، -

879
01:13:44,010 --> 01:13:47,340
إذا كانت هذه حلقة في حين لم ينفذ فعليا

880
01:13:47,340 --> 01:13:52,330
لأن القيمة الحالية لدينا باطل - باطل الجذر لدينا حتى الحالي باطل -

881
01:13:52,330 --> 01:13:57,810
ثم لدينا الوالد لم يحصل على تعيين الحالي أو إلى قيمة صالحة،

882
01:13:57,810 --> 01:14:00,580
لذلك، سوف تكون الأم أيضا فارغة.

883
01:14:00,580 --> 01:14:03,700
علينا أن نتذكر أن للتحقق من

884
01:14:03,700 --> 01:14:08,750
بحلول الوقت الذي نبدأ هنا، ونبدأ الوصول إلى قيمة الأصل.

885
01:14:08,750 --> 01:14:13,190
لذلك، ماذا يحدث؟ حسنا، إذا كان الوالد هو باطل -

886
01:14:13,190 --> 01:14:17,990
إذا كان (الوالد == NULL) - ثم نحن نعلم أن

887
01:14:17,990 --> 01:14:19,530
يجب أن لا يكون هناك أي شيء في الشجرة.

888
01:14:19,530 --> 01:14:22,030
يجب أن تكون محاولة لإدراجها في جذورها.

889
01:14:22,030 --> 01:14:32,570
يمكننا أن نفعل ذلك فقط من خلال وضع الجذر يساوي عقدة جديدة.

890
01:14:32,570 --> 01:14:40,010
ثم في هذه المرحلة، ونحن لا نريد في الواقع أن يذهب من خلال هذه الأشياء الأخرى.

891
01:14:40,010 --> 01:14:44,780
بدلا من ذلك، والحق هنا، يمكننا أن نفعل إما آخر، IF-آخر،

892
01:14:44,780 --> 01:14:47,610
أو يمكن أن الجمع بين كل شيء هنا في آخر،

893
01:14:47,610 --> 01:14:56,300
ولكن هنا سنستخدم فقط آخر، وتفعل ذلك بهذه الطريقة.

894
01:14:56,300 --> 01:14:59,030
الآن، ونحن في طريقنا لاختبار للتأكد من أن الأم لدينا ليست فارغة

895
01:14:59,030 --> 01:15:02,160
قبل ذلك في الواقع محاولة للوصول إلى الحقول الخاصة به.

896
01:15:02,160 --> 01:15:05,330
وسيساعدنا هذا خطأ تجنب تجزئة.

897
01:15:05,330 --> 01:15:14,740
لذلك، فإننا الإقلاع عن التدخين، تصغير، تجميع، تشغيل.

898
01:15:14,740 --> 01:15:18,130
>> عدم وجود أخطاء، ولكن لا يزال لدينا مجموعة من التسرب في الذاكرة

899
01:15:18,130 --> 01:15:20,650
لأننا لم سراح أي من العقد لدينا.

900
01:15:20,650 --> 01:15:24,350
ولكن، إذا كان لنا أن ترتفع هنا ونحن ننظر إلى النسخة المطبوعة لدينا،

901
01:15:24,350 --> 01:15:30,880
ونحن نرى أنه، حسنا، يبدو كل إدراج لدينا كانوا عائدين الحقيقية، وهو أمر جيد.

902
01:15:30,880 --> 01:15:33,050
يدرج كلها صحيحة،

903
01:15:33,050 --> 01:15:36,670
وبعد ذلك مناسبا يحتوي على المكالمات صحيح أيضا.

904
01:15:36,670 --> 01:15:41,510
>> عمل جيد! يبدو أننا قد كتبت بنجاح إدراج.

905
01:15:41,510 --> 01:15:47,430
هذا كل ما لدينا لهذا الأسبوع مشكلة مواصفات مجموعة.

906
01:15:47,430 --> 01:15:51,720
أحد التحديات متعة للتفكير هو كيف لك أن تذهب فعلا في

907
01:15:51,720 --> 01:15:55,340
والافراج عن كل من العقد في هذه الشجرة.

908
01:15:55,340 --> 01:15:58,830
يمكننا أن نفعل ذلك بعدة طرق مختلفة،

909
01:15:58,830 --> 01:16:01,930
ولكن سأترك ذلك متروك لكم لتجربة،

910
01:16:01,930 --> 01:16:06,080
وباعتبارها تحديا متعة، ومحاولة التأكد من أن يمكنك التأكد من

911
01:16:06,080 --> 01:16:09,490
أن هذا التقرير Valgrind إرجاع أية أخطاء والتسريبات لا.

912
01:16:09,490 --> 01:16:12,880
>> حظا سعيدا في هذا الأسبوع مجموعة هوفمان مشكلة الترميز،

913
01:16:12,880 --> 01:16:14,380
وسنرى في الأسبوع القادم!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]