1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [المادة 7: أكثر مريحة]

2
00:00:02,770 --> 00:00:05,090
[روب بودين] [جامعة هارفارد]

3
00:00:05,090 --> 00:00:07,930
[هذا CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
حسنا. مثل ذلك قلت في البريد الإلكتروني الخاص بي،

5
00:00:10,110 --> 00:00:14,060
هذا سيكون جزء ثنائي شجرة كثيفة.

6
00:00:14,060 --> 00:00:16,820
ولكن هناك العديد من الأسئلة التي لا.

7
00:00:16,820 --> 00:00:18,920
لذلك نحن ذاهبون لمحاولة استخلاص كل سؤال

8
00:00:18,920 --> 00:00:25,430
والخوض في التفاصيل المؤلمة من الطرق أفضل للقيام بهذه الأمور كافة.

9
00:00:25,430 --> 00:00:31,200
الحق في ذلك في البداية، نذهب من خلال رسومات عينة من الأشجار الثنائية والاشياء.

10
00:00:31,200 --> 00:00:35,970
حتى هنا، "تذكر أن لديه شجرة ثنائية مشابهة لتلك العقد من قائمة مرتبطة،

11
00:00:35,970 --> 00:00:38,150
بدلا من واحدة إلا مؤشر هناك اثنين: واحد ل 'الطفل' اليسار

12
00:00:38,150 --> 00:00:41,950
واحد لل"الطفل" الحق ".

13
00:00:41,950 --> 00:00:45,630
حتى شجرة ثنائية هو تماما مثل قائمة مرتبط،

14
00:00:45,630 --> 00:00:47,910
ما عدا البنية يجري لاثنين من المؤشرات.

15
00:00:47,910 --> 00:00:51,390
هناك أشجار trinary، والتي تسير على ثلاثة مؤشرات،

16
00:00:51,390 --> 00:00:56,540
هناك N-ARY الأشجار، والتي يكون مجرد مؤشر عام

17
00:00:56,540 --> 00:01:00,320
ثم أن لديك لmalloc أن تكون كبيرة بما يكفي ليكون

18
00:01:00,320 --> 00:01:04,840
يكفي مؤشرات إلى جميع الأطفال ممكن.

19
00:01:04,840 --> 00:01:08,200
حتى شجرة ثنائية يحدث لمجرد أن يكون لها عدد ثابت من اثنين.

20
00:01:08,200 --> 00:01:11,260
إذا كنت تريد، يمكنك ان تعطي قائمة مرتبطة مثل شجرة أحادي،

21
00:01:11,260 --> 00:01:15,360
لكنني لا أعتقد أن أحدا يسميها ذلك.

22
00:01:15,360 --> 00:01:18,060
"رسم مخطط مربعات و-سهام عقدة شجرة ثنائية

23
00:01:18,060 --> 00:01:24,110
تحتوي على عدد نيت المفضل، 7، حيث كل طفل مؤشر فارغة. "

24
00:01:24,110 --> 00:01:27,780
باد حتى واسطة.

25
00:01:27,780 --> 00:01:30,280
>> انها سوف تكون واضحة جدا.

26
00:01:30,280 --> 00:01:36,150
ونحن في طريقنا لمجرد الحصول على عقدة، وأنا رسم بأنها مربع.

27
00:01:36,150 --> 00:01:38,730
وسوف يوجه القيم هنا.

28
00:01:38,730 --> 00:01:41,090
لذلك سوف تذهب في القيمة هنا،

29
00:01:41,090 --> 00:01:44,770
ثم إلى هنا سيكون لدينا مؤشر اليسار على اليسار واليمين مؤشر على اليمين.

30
00:01:44,770 --> 00:01:50,430
وإلى حد كبير حتى أن نسميها اتفاقية اليسار واليمين، وأسماء المؤشر.

31
00:01:50,430 --> 00:01:52,460
كل من هذه ستكون فارغة.

32
00:01:52,460 --> 00:01:57,870
وأن يكون مجرد فارغة، والتي من شأنها أن يكون مجرد فارغة.

33
00:01:57,870 --> 00:02:03,630
حسنا. ذلك لدعم هنا.

34
00:02:03,630 --> 00:02:05,700
"مع قائمة مرتبطة، كان لدينا فقط لتخزين مؤشر

35
00:02:05,700 --> 00:02:09,639
إلى العقدة الأولى في القائمة من أجل أن نتذكر اللائحة بأكملها مرتبطة، أو اللائحة بأكملها.

36
00:02:09,639 --> 00:02:11,650
وبالمثل، مع الأشجار، لدينا فقط لتخزين مؤشر

37
00:02:11,650 --> 00:02:13,420
لعقدة واحدة من أجل أن نتذكر الشجرة كلها.

38
00:02:13,420 --> 00:02:15,980
هذه العقدة هي كالي 'جذور' من شجرة.

39
00:02:15,980 --> 00:02:18,320
بناء على الرسم البياني الخاص بك من قبل أو رسم جديد

40
00:02:18,320 --> 00:02:21,690
مثل أن يكون لديك تصوير مربعات و-سهام شجرة ثنائية

41
00:02:21,690 --> 00:02:25,730
مع قيمة 7، 3 ثم في اليسار،

42
00:02:25,730 --> 00:02:32,760
9 وعلى اليمين، ومن ثم 6 على يمين 3. "

43
00:02:32,760 --> 00:02:34,810
دعونا نرى ما اذا كان يمكنني تذكر كل ذلك في رأسي.

44
00:02:34,810 --> 00:02:37,670
ولذلك فإن هذا سيكون لدينا هنا الجذر.

45
00:02:37,670 --> 00:02:41,600
سيكون لدينا بعض مؤشر مكان ما، وهو الأمر الذي سنقوم استدعاء الجذر،

46
00:02:41,600 --> 00:02:45,140
وانها تشير الى هذا الرجل.

47
00:02:45,140 --> 00:02:48,490
الآن لجعل عقدة جديدة،

48
00:02:48,490 --> 00:02:52,870
ماذا لدينا، 3 على اليسار؟

49
00:02:52,870 --> 00:02:57,140
حتى عقدة جديدة مع 3، ويشير في البداية فارغة.

50
00:02:57,140 --> 00:02:59,190
أنا فقط وضعت N.

51
00:02:59,190 --> 00:03:02,250
الآن نحن نريد أن نجعل التي تذهب إلى يسار 7.

52
00:03:02,250 --> 00:03:06,840
حتى نغير هذا المؤشر للإشارة إلى هذا الرجل الآن.

53
00:03:06,840 --> 00:03:12,420
ونحن نفعل نفس الشيء. نريد أكثر من 9 هنا

54
00:03:12,420 --> 00:03:14,620
في البداية يقول عادل الذي فارغة.

55
00:03:14,620 --> 00:03:19,600
ونحن في طريقنا لتغيير هذا المؤشر، وأشر إلى 9،

56
00:03:19,600 --> 00:03:23,310
ونحن الآن نريد أن نضع 6 إلى حق 3.

57
00:03:23,310 --> 00:03:32,170
لذلك سيكون ل- تقديم 6.

58
00:03:32,170 --> 00:03:34,310
وسوف نشير أن الرجل هناك.

59
00:03:34,310 --> 00:03:38,320
حسنا. ذلك أن كل ما يطلب منا القيام به.

60
00:03:38,320 --> 00:03:42,770
>> الآن دعونا نذهب أكثر من بعض المصطلحات.

61
00:03:42,770 --> 00:03:46,690
تحدثنا بالفعل عن كيفية جذر الشجرة هي العقدة معظم العليا في الشجرة.

62
00:03:46,690 --> 00:03:54,720
واحد يحتوي على 7. ويطلق على العقد في الجزء السفلي من الشجرة الأوراق.

63
00:03:54,720 --> 00:04:01,240
أي عقدة التي لديها فقط فارغة وأبنائها هو ورقة.

64
00:04:01,240 --> 00:04:03,680
لذلك فمن الممكن، إذا شجرة ثنائية لدينا هو مجرد عقدة واحدة،

65
00:04:03,680 --> 00:04:10,130
أن الشجرة هي ورقة، وهذا كل شيء.

66
00:04:10,130 --> 00:04:12,060
"إن 'ارتفاع' من شجرة هو عدد القفزات لديك لجعل

67
00:04:12,060 --> 00:04:16,620
للحصول على من أعلى إلى ورقة ".

68
00:04:16,620 --> 00:04:18,640
سوف نصل إلى، في الثانية، والفرق

69
00:04:18,640 --> 00:04:21,940
بين أشجار ثنائي متوازنة وغير متوازنة،

70
00:04:21,940 --> 00:04:29,470
لكن في الوقت الراهن، والارتفاع الكلي لهذه الشجرة

71
00:04:29,470 --> 00:04:34,520
وأود أن أقول هو 3، ولكن إذا كنت تعول عدد من القفزات

72
00:04:34,520 --> 00:04:39,710
عليك ان تجعل من اجل الحصول على ل9، ثم انها حقا فقط على ارتفاع 2.

73
00:04:39,710 --> 00:04:43,340
الآن هذا هو شجرة ثنائية غير متوازنة،

74
00:04:43,340 --> 00:04:49,840
ولكن سوف نتحدث عن التوازن عندما يحصل أن تكون ذات صلة.

75
00:04:49,840 --> 00:04:52,040
حتى الآن يمكن أن نتحدث عن العقد في شجرة من حيث

76
00:04:52,040 --> 00:04:54,700
بالنسبة إلى العقد الأخرى في الشجرة.

77
00:04:54,700 --> 00:04:59,730
حتى الآن لدينا الآباء والأطفال والأشقاء والأجداد، وأحفاد.

78
00:04:59,730 --> 00:05:05,650
فهي جميلة الحس السليم، وما فيها من معاني.

79
00:05:05,650 --> 00:05:09,610
إذا نطلب - الآباء الامر.

80
00:05:09,610 --> 00:05:12,830
فما هو أصل 3؟

81
00:05:12,830 --> 00:05:16,090
[الطلاب] 7. نعم >>. الأصل هو الذهاب لمجرد أن يكون ما يشير لك.

82
00:05:16,090 --> 00:05:20,510
ثم ما هي الأطفال من 7؟

83
00:05:20,510 --> 00:05:23,860
[الطلاب] 3 و 9. نعم >>.

84
00:05:23,860 --> 00:05:26,460
لاحظت أن "الأطفال" تعني حرفيا الأطفال،

85
00:05:26,460 --> 00:05:31,010
وحتى 6 لا تطبق، لأنها مثل الحفيد.

86
00:05:31,010 --> 00:05:35,540
ولكن بعد ذلك اذا ذهبنا نسل، لذلك ما هي أحفاد 7؟

87
00:05:35,540 --> 00:05:37,500
[الطلاب] 3 و 6 و 9. نعم >>.

88
00:05:37,500 --> 00:05:42,330
المتحدرين من عقدة الجذر سيكون كل شيء في الشجرة،

89
00:05:42,330 --> 00:05:47,950
ربما باستثناء عقدة الجذر نفسه، إذا كنت لا ترغب في النظر في أن أحد أحفاد.

90
00:05:47,950 --> 00:05:50,750
وأخيرا، الأجداد، لذلك فمن الاتجاه المعاكس.

91
00:05:50,750 --> 00:05:55,740
فما هي أسلاف 6؟

92
00:05:55,740 --> 00:05:58,920
[الطلاب] 3 و 7. نعم >>. لم يتم تضمين 9.

93
00:05:58,920 --> 00:06:02,520
انها مجرد العودة النسب المباشر إلى جذر

94
00:06:02,520 --> 00:06:13,230
ستكون أسلافك.

95
00:06:13,230 --> 00:06:16,300
>> "نحن نقول ان هو 'أمر' شجرة ثنائية إذا لكل عقدة في الشجرة،

96
00:06:16,300 --> 00:06:19,530
كل نسله على اليسار يكون أقل القيم

97
00:06:19,530 --> 00:06:22,890
وجميع من هم على الحق قدر أكبر من القيم.

98
00:06:22,890 --> 00:06:27,060
على سبيل المثال، أمر شجرة أعلاه ولكنها ليست الوحيدة الممكنة للترتيب أمر ".

99
00:06:27,060 --> 00:06:30,180
قبل أن نصل إلى ذلك،

100
00:06:30,180 --> 00:06:36,420
وكما هو معروف شجرة ثنائية كما أمرت شجرة البحث الثنائية.

101
00:06:36,420 --> 00:06:38,660
نحن هنا يحدث ليكون اصفا اياه بانه شجرة ثنائية أمر،

102
00:06:38,660 --> 00:06:41,850
ولكن لم يسبق لي أن سمعت يطلق عليه اسم شجرة ثنائية أمر من قبل،

103
00:06:41,850 --> 00:06:46,650
وعلى مسابقة نحن أكثر من ذلك بكثير من المرجح أن تضع ثنائي شجرة البحث.

104
00:06:46,650 --> 00:06:49,250
انهم احدة واحدة،

105
00:06:49,250 --> 00:06:54,580
ومن المهم تتعرف على التمييز بين شجرة ثنائية وثنائي شجرة البحث.

106
00:06:54,580 --> 00:06:58,830
شجرة ثنائية هو مجرد شجرة يشير إلى أمرين.

107
00:06:58,830 --> 00:07:02,120
كل عقدة يشير إلى أمرين.

108
00:07:02,120 --> 00:07:06,310
لا يوجد أي منطق حول القيم يشير إلى.

109
00:07:06,310 --> 00:07:11,370
مثل ذلك أكثر من هنا، لأنه شجرة البحث الثنائية،

110
00:07:11,370 --> 00:07:14,030
ونحن نعلم أنه إذا نذهب يسار 7،

111
00:07:14,030 --> 00:07:16,670
بعد ذلك كل من القيم التي يمكن ان نصل ربما

112
00:07:16,670 --> 00:07:19,310
عن طريق الذهاب غادر من 7 يجب أن تكون أقل من 7.

113
00:07:19,310 --> 00:07:24,070
لاحظت أن جميع القيم هي أقل من 7 3 و 6.

114
00:07:24,070 --> 00:07:26,040
تلك كلها على يسار 7.

115
00:07:26,040 --> 00:07:29,020
إذا ذهبنا إلى يمين 7، كل شيء يجب أن تكون أكبر من 7،

116
00:07:29,020 --> 00:07:33,220
حتى 9 هو الحق من 7، لذلك نحن في حالة جيدة.

117
00:07:33,220 --> 00:07:36,150
ليست هذه هي الحال بالنسبة لشجرة ثنائية،

118
00:07:36,150 --> 00:07:40,020
لشجرة ثنائية منتظمة يمكن أن لدينا فقط 3 في القمة، من 7 إلى اليسار،

119
00:07:40,020 --> 00:07:47,630
9 إلى يسار 7؛ ليس هناك ترتيب القيم على الإطلاق.

120
00:07:47,630 --> 00:07:56,140
الآن، ونحن لن نفعل هذا لأنه فعلا أمر يبعث على الملل وغير ضرورية،

121
00:07:56,140 --> 00:07:59,400
ولكن "محاولة لرسم ما يصل الأشجار كما أمرت يمكن ان يخطر لك

122
00:07:59,400 --> 00:08:01,900
باستخدام الأرقام 7، 3، 9، و 6.

123
00:08:01,900 --> 00:08:06,800
عدد الترتيبات المتميزة هناك؟ ما هو ارتفاع كل واحدة؟ "

124
00:08:06,800 --> 00:08:10,480
>> سنفعل زوجين، ولكن هي الفكرة الرئيسية،

125
00:08:10,480 --> 00:08:16,530
هذا هو بأي حال من الأحوال تمثيل فريد من شجرة ثنائية تحتوي على هذه القيم.

126
00:08:16,530 --> 00:08:22,760
كل ما نحتاجه هو بعض شجرة ثنائية الذي يحتوي 7، 3، 6، و 9.

127
00:08:22,760 --> 00:08:25,960
وآخر واحد ممكن تكون صالحة الجذر هو 3،

128
00:08:25,960 --> 00:08:30,260
انتقل إلى اليسار وانها 6، يذهب إلى اليسار وانها 7،

129
00:08:30,260 --> 00:08:32,730
انتقل إلى اليسار وانها 9.

130
00:08:32,730 --> 00:08:36,169
وهذا هو البحث الثنائي صالح تماما شجرة.

131
00:08:36,169 --> 00:08:39,570
انها ليست مفيدة جدا، لأنها تماما مثل قائمة مرتبطة

132
00:08:39,570 --> 00:08:43,750
وجميع هذه المؤشرات تعتبر لاغية فقط.

133
00:08:43,750 --> 00:08:48,900
وإنما هو شجرة صالحة. نعم؟

134
00:08:48,900 --> 00:08:51,310
[طالب] لا القيم يجب أن تكون أكبر على الحق؟

135
00:08:51,310 --> 00:08:56,700
أم أن هذا -؟ هذه >> يعني أن أذهب في الاتجاه الآخر.

136
00:08:56,700 --> 00:09:00,960
هناك أيضا - نعم، دعونا تبديل ذلك.

137
00:09:00,960 --> 00:09:07,770
9، 7، 6، 3. جيد الصيد.

138
00:09:07,770 --> 00:09:11,730
فإنه لا يزال على طاعة ما يفترض البحث شجرة ثنائية للقيام به.

139
00:09:11,730 --> 00:09:15,650
حيث كل شيء إلى اليسار يجب أن يكون أقل من أي عقدة معينة.

140
00:09:15,650 --> 00:09:23,180
يمكن أن نتحرك فقط، ويقول، وهذا 6 و ضعه هنا.

141
00:09:23,180 --> 00:09:26,880
لا، لا يمكننا ذلك. لماذا تستمر في فعل ذلك؟

142
00:09:26,880 --> 00:09:35,350
دعونا نفعل - هنا هو 6، وهنا 7، 6 نقاط إلى 3.

143
00:09:35,350 --> 00:09:39,290
هذا لا يزال البحث الثنائية صالحة شجرة.

144
00:09:39,290 --> 00:09:49,260
ما هو الخطأ إذا I - دعونا نرى ما اذا كان يمكنني الخروج مع الترتيب.

145
00:09:49,260 --> 00:09:52,280
نعم، حسنا. ما هو الخطأ في ذلك هذه الشجرة؟

146
00:09:52,280 --> 00:10:08,920
اعتقد انني قد قدمت فعلا لك وإشارة إلى أن هناك شيئا خطأ في ذلك.

147
00:10:08,920 --> 00:10:14,430
لماذا تستمر في فعل ذلك؟

148
00:10:14,430 --> 00:10:18,510
حسنا. هذا يبدو معقولا.

149
00:10:18,510 --> 00:10:22,590
إذا نظرنا إلى كل عقدة، مثل 7، ثم إلى يسار 7 هو 3.

150
00:10:22,590 --> 00:10:24,960
لذلك لدينا 3، الشيء إلى يمين 3 هو 6.

151
00:10:24,960 --> 00:10:27,750
واذا نظرتم الى 6، الشيء إلى اليمين من 6 هو 9.

152
00:10:27,750 --> 00:10:30,910
فلماذا هذا ليس بحثا ثنائي صالحة الشجرة؟

153
00:10:30,910 --> 00:10:36,330
[الطلاب] 9 لا يزال على يسار 7. نعم >>.

154
00:10:36,330 --> 00:10:43,710
يجب أن يكون صحيحا أن جميع القيم التي يمكن أن تصل إلى ربما من خلال الذهاب الى اليسار من 7 هي أقل من 7.

155
00:10:43,710 --> 00:10:49,120
اذا ذهبنا تبقى من 7، نصل الى 3 و يمكننا الحصول على ما زالت إلى 6،

156
00:10:49,120 --> 00:10:52,520
يمكننا الحصول على ما زالت إلى 9، ولكن بعد أن ذهب أقل من 7،

157
00:10:52,520 --> 00:10:55,070
لا ينبغي لنا أن تكون قادرة على الحصول على عدد أكبر من هذا 7.

158
00:10:55,070 --> 00:10:59,830
لذلك هذه ليست صالحة شجرة البحث الثنائية.

159
00:10:59,830 --> 00:11:02,330
>> أخي كان في الواقع مسألة مقابلة

160
00:11:02,330 --> 00:11:07,760
كان ذلك في الأساس هذا، رمز للتو شيئا للتحقق من صحة

161
00:11:07,760 --> 00:11:10,500
سواء شجرة هي شجرة البحث الثنائية،

162
00:11:10,500 --> 00:11:13,580
وهكذا كان أول شيء فعله انظروا فقط لرؤية

163
00:11:13,580 --> 00:11:17,020
إذا كان اليسار واليمين صحيحة، وتكرار ثم الى هناك.

164
00:11:17,020 --> 00:11:19,700
ولكن لا يمكنك فعل ذلك فقط، عليك أن تتبع

165
00:11:19,700 --> 00:11:22,550
لكون ذلك الآن لقد ذهبت يسار 7،

166
00:11:22,550 --> 00:11:26,340
يجب أن كل شيء في هذا الشجرة الفرعية تكون أقل من 7.

167
00:11:26,340 --> 00:11:28,430
الخوارزمية الصحيح يحتاج إلى تتبع

168
00:11:28,430 --> 00:11:35,970
من حدود القيم التي يمكن أن تقع فيها ربما

169
00:11:35,970 --> 00:11:38,360
ونحن لن نذهب من خلال كل منهم.

170
00:11:38,360 --> 00:11:41,630
هناك علاقة تكرار لطيفة،

171
00:11:41,630 --> 00:11:44,810
على الرغم من أننا لم نصل إلى تلك، أو أننا لن نصل إلى تلك،

172
00:11:44,810 --> 00:11:47,030
تحديد عدد وهناك بالفعل.

173
00:11:47,030 --> 00:11:53,180
لذلك هناك 14 منهم.

174
00:11:53,180 --> 00:11:56,020
فكرة كيف سيكون ذلك هو رياضيا مثل،

175
00:11:56,020 --> 00:11:59,770
يمكنك اختيار أي واحد واحدة لتكون عقدة الجذر،

176
00:11:59,770 --> 00:12:03,160
ثم إذا كنت اختيار 7 لتكون العقدة الجذر،

177
00:12:03,160 --> 00:12:08,150
ثم هناك، مثلا، بعض الأرقام التي يمكن أن تذهب تكون عقدة يساري،

178
00:12:08,150 --> 00:12:10,440
وهناك بعض الأرقام التي يمكن أن تكون عقدة حقي،

179
00:12:10,440 --> 00:12:15,090
ولكن إذا كنت قد ن العدد الإجمالي، ثم المبلغ الذي يمكن أن تذهب إلى اليسار

180
00:12:15,090 --> 00:12:18,820
بالإضافة إلى المبلغ الذي يمكن أن تذهب إلى اليمين هو ن - 1.

181
00:12:18,820 --> 00:12:26,130
لذلك من الأرقام المتبقية، فإنها يجب أن تكون قادرا على الذهاب إما إلى اليسار أو اليمين.

182
00:12:26,130 --> 00:12:31,580
يبدو من الصعب أن، إذا وضعت 3 الأولى ثم كل شيء يجب أن يذهب إلى اليسار،

183
00:12:31,580 --> 00:12:35,080
ولكن إذا وضعت 7، ثم يمكن أن تسير الأمور على بعض اليسار وبعض الأشياء يمكن أن تذهب إلى اليمين.

184
00:12:35,080 --> 00:12:39,570
و'3 'أول يعني كل شيء يمكن أن تذهب إلى اليمين.

185
00:12:39,570 --> 00:12:42,350
انها حقا، عليك أن تفكر في ذلك كما،

186
00:12:42,350 --> 00:12:47,980
كيف تسير الأمور في كثير من المستوى التالي من شجرة.

187
00:12:47,980 --> 00:12:50,420
ويتعلق الأمر إلى أن تكون 14؛ أو يمكنك رسم كل منهم،

188
00:12:50,420 --> 00:12:54,650
وبعد ذلك سوف تحصل على 14.

189
00:12:54,650 --> 00:13:01,120
>> العودة هنا،

190
00:13:01,120 --> 00:13:03,510
"أشجار الثنائية أمرت هي باردة لأننا يمكن البحث من خلالها

191
00:13:03,510 --> 00:13:06,910
بطريقة مشابهة جدا لتبحث على مجموعة فرزها.

192
00:13:06,910 --> 00:13:10,120
للقيام بذلك، ونحن نبدأ في جذور والعمل طريقنا إلى أسفل الشجرة

193
00:13:10,120 --> 00:13:13,440
نحو الأوراق، والتحقق من القيم كل عقدة ضد القيم التي تبحث عنها.

194
00:13:13,440 --> 00:13:15,810
إذا قيمة العقدة الحالية هي أقل من القيمة التي تبحث عنها،

195
00:13:15,810 --> 00:13:18,050
تذهب بجوار الطفل العقدة اليمنى.

196
00:13:18,050 --> 00:13:20,030
خلاف ذلك، تذهب إلى الأطفال للعقدة اليسار.

197
00:13:20,030 --> 00:13:22,800
في مرحلة ما، ستجد إما القيمة التي تبحث عنها، أو عليك أن تصل الى قيمة خالية،

198
00:13:22,800 --> 00:13:28,520
تشير القيمة ليست في الشجرة. "

199
00:13:28,520 --> 00:13:32,450
لا بد لي من إعادة رسم شجرة كان لدينا من قبل؛ التي سوف تأخذ ثانية.

200
00:13:32,450 --> 00:13:38,280
لكننا نريد للبحث عن ما إذا كان 6، 10، و 1 في الشجرة.

201
00:13:38,280 --> 00:13:49,180
ذلك ما كان عليه، 7، 9، 3، 6. حسنا.

202
00:13:49,180 --> 00:13:52,730
الأرقام التي تريد البحث عنها، ونحن نريد للبحث عن 6.

203
00:13:52,730 --> 00:13:55,440
كيف يعمل هذا الخوارزمية؟

204
00:13:55,440 --> 00:14:03,040
حسنا، لدينا أيضا بعض مؤشر الجذر إلى شجرة لدينا.

205
00:14:03,040 --> 00:14:12,460
وكنا نذهب إلى جذر ويقولون، هو هذه القيمة مساوية لقيمة ونحن تبحث عن؟

206
00:14:12,460 --> 00:14:15,000
لذلك نحن نبحث عن 6، حتى انها ليست متساوية.

207
00:14:15,000 --> 00:14:20,140
لذلك نحن نستمر، ونحن الآن نقول، حسنا، لذلك 6 هو أقل من 7.

208
00:14:20,140 --> 00:14:23,940
هل يعني هذا أننا نريد أن يذهب إلى اليسار، أو لا نريد أن نذهب إلى اليمين؟

209
00:14:23,940 --> 00:14:27,340
[طالب] بقي. نعم >>.

210
00:14:27,340 --> 00:14:33,340
انه من الاسهل بكثير، كل ما عليك القيام به هو رسم عقدة واحدة ممكن من شجرة

211
00:14:33,340 --> 00:14:37,760
ثم مش - بدلا من محاولة التفكير في رأسك،

212
00:14:37,760 --> 00:14:40,020
حسنا، إذا كان أقل من ذلك، لم أذهب إلى اليسار أو الذهاب الحق،

213
00:14:40,020 --> 00:14:43,030
مجرد النظر في هذه الصورة، من الواضح جدا أن لدي للذهاب إلى اليسار

214
00:14:43,030 --> 00:14:47,700
إذا كانت هذه العقدة هي أكبر من القيمة التي أنا أبحث عن.

215
00:14:47,700 --> 00:14:52,600
حتى تذهب إلى اليسار، والآن أنا في 3.

216
00:14:52,600 --> 00:14:57,770
أريد أن - 3 هو أقل من القيمة أنا أبحث عن الذي هو 6.

217
00:14:57,770 --> 00:15:03,420
لذلك نحن نذهب إلى اليمين، والآن أنا في نهاية المطاف في 6،

218
00:15:03,420 --> 00:15:07,380
وهي القيمة أنا أبحث عن، لذلك أعود صحيح.

219
00:15:07,380 --> 00:15:15,760
القيمة التالية انا ذاهب للبحث عن هو 10.

220
00:15:15,760 --> 00:15:23,230
حسنا. حتى 10، الآن، هو الذهاب الى - قطع ذلك - سوف تتبع جذورها.

221
00:15:23,230 --> 00:15:27,670
الآن، 10 ستكون أكبر من 7، لذلك أريد أن ننظر إلى اليمين.

222
00:15:27,670 --> 00:15:31,660
أنا سوف يأتي إلى هنا، 10 ستكون أكبر من 9،

223
00:15:31,660 --> 00:15:34,520
لذلك أنا ذاهب الى تريد أن تبدو إلى اليمين.

224
00:15:34,520 --> 00:15:42,100
لقد جئت إلى هنا، ولكن أكثر من هنا الآن أنا في فارغة.

225
00:15:42,100 --> 00:15:44,170
ماذا أفعل إذا ضرب فارغة؟

226
00:15:44,170 --> 00:15:47,440
[طالب] عودة كاذبة؟ نعم >>. لم أجد 10.

227
00:15:47,440 --> 00:15:49,800
1 لن تكون قضية مماثلة تقريبا،

228
00:15:49,800 --> 00:15:51,950
إلا انه سيكون مجرد أن يكون انقلبت، وبدلا من البحث

229
00:15:51,950 --> 00:15:56,540
أسفل الجانب الأيمن، وأنا ذاهب إلى النظر إلى أسفل الجانب الأيسر.

230
00:15:56,540 --> 00:16:00,430
>> الآن أعتقد أننا في الواقع الحصول على التعليمات البرمجية.

231
00:16:00,430 --> 00:16:04,070
هنا المكان - فتح الجهاز والتنقل CS50 طريقك هناك،

232
00:16:04,070 --> 00:16:07,010
ولكن يمكنك أيضا القيام بذلك فقط في الفضاء.

233
00:16:07,010 --> 00:16:09,170
انها على الارجح مثالية للقيام بذلك في الفضاء،

234
00:16:09,170 --> 00:16:13,760
لأنه لا يمكن أن نعمل في الفضاء.

235
00:16:13,760 --> 00:16:19,170
"أولا سنحتاج إلى تعريف نوع جديد للعقدة شجرة ثنائية تحتوي على قيم كثافة العمليات.

236
00:16:19,170 --> 00:16:21,400
باستخدام النمطي typedef أدناه،

237
00:16:21,400 --> 00:16:24,510
إنشاء تعريف نوع جديد للعقدة في شجرة ثنائية.

238
00:16:24,510 --> 00:16:27,930
إذا واجهتك مشكلة. . . "بلاه، بلاه، بلاه. حسنا.

239
00:16:27,930 --> 00:16:30,380
لذلك دعونا نضع المتداول هنا،

240
00:16:30,380 --> 00:16:41,630
typedef العقدة البنية، وعقدة. نعم، حسنا.

241
00:16:41,630 --> 00:16:44,270
فما هي المجالات ونحن في طريقنا لدينا عقدة تريد في؟

242
00:16:44,270 --> 00:16:46,520
[طالب] وكثافة العمليات ثم اثنين مؤشرات؟

243
00:16:46,520 --> 00:16:49,700
الباحث >> القيمة، وهما المؤشرات؟ كيف أكتب المؤشرات؟

244
00:16:49,700 --> 00:16:58,440
[طالب] البنية. وأرجو >> تكبير. نعم، لذلك البنية عقدة * اليسار،

245
00:16:58,440 --> 00:17:01,320
والبنية عقدة * الحق.

246
00:17:01,320 --> 00:17:03,460
وتذكر المناقشة من وقت الماضي،

247
00:17:03,460 --> 00:17:15,290
أن هذا لا معنى له، وهذا لا معنى له،

248
00:17:15,290 --> 00:17:18,270
هذا لا معنى له.

249
00:17:18,270 --> 00:17:25,000
تحتاج كل شيء هناك من أجل تحديد هذه البنية العودية.

250
00:17:25,000 --> 00:17:27,970
حسنا، حتى في ما يجري لدينا شجرة لتبدو وكأنها.

251
00:17:27,970 --> 00:17:37,670
إذا فعلنا شجرة trinary، ثم قد تبدو وكأنها عقدة B2، B1، B3 * البنية عقدة،

252
00:17:37,670 --> 00:17:43,470
حيث هي فرع ب - في الواقع، لقد سمعت أنه ترك أكثر،، والحق الأوسط، ولكن أيا كان.

253
00:17:43,470 --> 00:17:55,610
نحن نهتم فقط عن ثنائي، الحق في ذلك، غادر.

254
00:17:55,610 --> 00:17:59,110
"تعلن الآن على عقدة العالمية * متغير لجذر الشجرة."

255
00:17:59,110 --> 00:18:01,510
لذلك نحن لن نفعل ذلك.

256
00:18:01,510 --> 00:18:08,950
من أجل جعل الأمور أكثر صعوبة قليلا ومعممة أكثر من ذلك،

257
00:18:08,950 --> 00:18:11,570
لن يكون لدينا متغير عقدة العالمية.

258
00:18:11,570 --> 00:18:16,710
بدلا من ذلك، سوف الرئيسي في نعلن بكل ما نملك من الأشياء العقدة،

259
00:18:16,710 --> 00:18:20,500
وهذا يعني أن أدناه، عندما نبدأ تشغيل

260
00:18:20,500 --> 00:18:23,130
لدينا يحتوي على وظيفة وظيفة لدينا إدراج،

261
00:18:23,130 --> 00:18:27,410
بدلا من الدالة باستخدام لدينا يحتوي هذا المتغير فقط عقدة العالمية،

262
00:18:27,410 --> 00:18:34,280
نحن ذاهبون الى انها قد تأخذ كوسيطة الشجرة التي نريد لها أن معالجة.

263
00:18:34,280 --> 00:18:36,650
وجود المتغير العالمي كان من المفترض أن تجعل الأمور أسهل.

264
00:18:36,650 --> 00:18:42,310
ونحن في طريقنا لجعل الامور اكثر صعوبة.

265
00:18:42,310 --> 00:18:51,210
تتخذ الآن لمدة دقيقة أو نحو ذلك لمجرد قيام بذلك النوع من الشيء،

266
00:18:51,210 --> 00:18:57,690
حيث من داخل الرئيسية التي تريد إنشاء هذه الشجرة، وهذا كل ما تريد القيام به.

267
00:18:57,690 --> 00:19:04,530
محاولة وبناء هذه الشجرة في وظيفة الرئيسي الخاص بك.

268
00:19:42,760 --> 00:19:47,610
>> حسنا. لذلك أنت لا تملك حتى أن الشجرة التي شيدت الطريق بأكمله حتى الآن.

269
00:19:47,610 --> 00:19:49,840
ولكن أي شخص على شيء أنا يمكن سحب ما يصل

270
00:19:49,840 --> 00:20:03,130
لاظهار كيف يمكن للمرء أن يبدأ بناء مثل هذه الشجرة؟

271
00:20:03,130 --> 00:20:08,080
[طالب] شخص ما ضجيجا، في محاولة للخروج.

272
00:20:08,080 --> 00:20:13,100
[بودين] مريحة مع أي شخص بناء على شجرة؟

273
00:20:13,100 --> 00:20:15,520
[طالب] بالتأكيد. انها لم تفعل ذلك. أنها على ما يرام >>. يمكن أن ننتهي فقط -

274
00:20:15,520 --> 00:20:26,860
يا، هل يمكنك حفظه؟ الصيحة.

275
00:20:26,860 --> 00:20:32,020
حتى هنا لدينا - أوه، أنا قطعت قليلا قبالة.

276
00:20:32,020 --> 00:20:34,770
أنا كنت أسرع في؟

277
00:20:34,770 --> 00:20:37,730
تكبير، انتقل بها. >> لدي سؤال. نعم >>؟

278
00:20:37,730 --> 00:20:44,410
[طالب] عند تعريف البنية، هي أشياء مثل تهيئة إلى أي شيء؟

279
00:20:44,410 --> 00:20:47,160
[بودين] رقم >> حسنا. لذلك سيكون لديك لتهيئة -

280
00:20:47,160 --> 00:20:50,450
[بودين] رقم عند تعريف، أو عندما تعلن لك والبنية،

281
00:20:50,450 --> 00:20:55,600
لم يتم تهيئة بشكل افتراضي، بل مجرد مثل إذا قمت بتعريف الباحث.

282
00:20:55,600 --> 00:20:59,020
انها بالضبط نفس الشيء. انها مثل كل من حقولها الفردية

283
00:20:59,020 --> 00:21:04,460
يمكن أن يكون لها قيمة القمامة في ذلك. و>> هل من الممكن تحديد - أو لتعلن البنية

284
00:21:04,460 --> 00:21:07,740
بطريقة يفعل تهيئة لهم؟

285
00:21:07,740 --> 00:21:13,200
[بودين] نعم. ذلك تهيئة الاختصار، جملة

286
00:21:13,200 --> 00:21:18,660
سوف تبدو وكأنها -

287
00:21:18,660 --> 00:21:22,200
هناك طريقتان يمكننا أن نفعل هذا. أعتقد أننا يجب أن ترجمة عليه

288
00:21:22,200 --> 00:21:25,840
لجعل متأكد من ضجيج أيضا لا هذا.

289
00:21:25,840 --> 00:21:28,510
ترتيب الحجج التي تأتي في البنية،

290
00:21:28,510 --> 00:21:32,170
وضع لكم وترتيب الحجج داخل هذه الأقواس المتعرجة.

291
00:21:32,170 --> 00:21:35,690
حتى إذا كنت ترغب في تهيئة إلى 9 و ترك لاغية وباطلة ثم يكون على حق،

292
00:21:35,690 --> 00:21:41,570
سيكون من 9، فارغة، فارغة.

293
00:21:41,570 --> 00:21:47,890
البديل هو، والمحرر لا يحب هذا النحو،

294
00:21:47,890 --> 00:21:50,300
ويعتقد أريد كتلة جديدة،

295
00:21:50,300 --> 00:22:01,800
لكن البديل هو شيء من هذا القبيل -

296
00:22:01,800 --> 00:22:04,190
هنا، وأنا وضعه في سطر جديد.

297
00:22:04,190 --> 00:22:09,140
يمكنك القول صراحة، انسى بناء الجملة بالضبط.

298
00:22:09,140 --> 00:22:13,110
حتى تتمكن من معالجة صراحة منهم بالاسم، ويقول:

299
00:22:13,110 --> 00:22:21,570
ج، أو قيمة = 9. NULL = اليسار.

300
00:22:21,570 --> 00:22:24,540
انا التخمين هذه الحاجة إلى أن تكون الفواصل.

301
00:22:24,540 --> 00:22:29,110
. الحق = NULL، لذلك هذا الأسلوب الذي لا

302
00:22:29,110 --> 00:22:33,780
تحتاج بالفعل لمعرفة ترتيب البنية،

303
00:22:33,780 --> 00:22:36,650
وعندما كنت في هذه القراءة، انها أكثر من ذلك بكثير صريح

304
00:22:36,650 --> 00:22:41,920
حول ما يتم تهيئة القيمة إلى.

305
00:22:41,920 --> 00:22:44,080
>> هذا يحدث ليكون واحدا من الأشياء التي -

306
00:22:44,080 --> 00:22:49,100
لذلك، بالنسبة للجزء الأكبر، C + + هو شاملة من C.

307
00:22:49,100 --> 00:22:54,160
يمكنك أن تأخذ كود C، نقله الى C + +، وينبغي أن تجمع.

308
00:22:54,160 --> 00:22:59,570
هذا هو واحد من الأشياء التي C + + لا يعتمد، لذلك الناس في الغالب لا تفعل ذلك.

309
00:22:59,570 --> 00:23:01,850
أنا لا أعرف إذا كان هذا هو السبب الوحيد الناس لا يميلون للقيام بذلك،

310
00:23:01,850 --> 00:23:10,540
ولكن هناك حاجة الحالة حيث كنت بحاجة لاستخدامه للعمل مع C + + وحتى أتمكن من عدم استخدام هذا.

311
00:23:10,540 --> 00:23:14,000
مثال آخر على ما لا يعمل مع C + + هو

312
00:23:14,000 --> 00:23:16,940
كيف malloc بإرجاع "* الفراغ،" من الناحية الفنية،

313
00:23:16,940 --> 00:23:20,200
لكن هل يمكن أن نقول فقط تشار * X = malloc مهما،

314
00:23:20,200 --> 00:23:22,840
وسوف يكون تلقائيا إلى * يلقي شار.

315
00:23:22,840 --> 00:23:25,450
أن يلقي التلقائي لا يحدث في C + +.

316
00:23:25,450 --> 00:23:28,150
ومن شأن ذلك أن لا ترجمة، وكنت في حاجة للقول صراحة

317
00:23:28,150 --> 00:23:34,510
* شار، malloc، أيا كان، لصبغه ل* شار.

318
00:23:34,510 --> 00:23:37,270
هناك الكثير من الامور التي لا C + + C ونختلف على،

319
00:23:37,270 --> 00:23:40,620
ولكن هذه هي اثنين.

320
00:23:40,620 --> 00:23:43,120
وهكذا لن نذهب مع هذه الجملة.

321
00:23:43,120 --> 00:23:46,150
ولكن حتى لو لم نذهب مع ذلك التركيب،

322
00:23:46,150 --> 00:23:49,470
ما هو - قد يكون الخطأ في هذا؟

323
00:23:49,470 --> 00:23:52,170
[طالب] I لا تحتاج إلى إلغاء مرجعية ذلك؟ نعم >>.

324
00:23:52,170 --> 00:23:55,110
تذكر أن السهم لديه إلغاء مرجعية ضمنية،

325
00:23:55,110 --> 00:23:58,230
وذلك عندما نتعامل فقط مع البنية،

326
00:23:58,230 --> 00:24:04,300
نريد للاستخدام. للحصول على في داخل مجال البنية.

327
00:24:04,300 --> 00:24:07,200
والمرة الوحيدة التي نستخدمها السهم عندما نريد القيام به -

328
00:24:07,200 --> 00:24:13,450
حسنا، ما يعادل سهم -

329
00:24:13,450 --> 00:24:17,020
هذا ما كان يمكن أن يكون المقصود إذا كنت السهم.

330
00:24:17,020 --> 00:24:24,600
جميع وسائل السهم، إلغاء مرجعية هذا، والآن أنا في البنية، ويمكنني الحصول على هذا المجال.

331
00:24:24,600 --> 00:24:28,040
الحصول إما مباشرة أو إلغاء مرجعية الميدان والحصول على الميدان -

332
00:24:28,040 --> 00:24:30,380
أعتقد أن هذا يجب أن يكون القيمة.

333
00:24:30,380 --> 00:24:33,910
ولكن هنا انا التعامل مع البنية وفقط، وليس مؤشر إلى البنية،

334
00:24:33,910 --> 00:24:38,780
وهكذا لا أستطيع أن استخدم السهم.

335
00:24:38,780 --> 00:24:47,510
ولكن هذا النوع من الاشياء يمكننا أن نفعل كافة العقد.

336
00:24:47,510 --> 00:24:55,790
يا إلهي.

337
00:24:55,790 --> 00:25:09,540
هذا هو 6 و 7 و 3.

338
00:25:09,540 --> 00:25:16,470
ثم يمكننا إعداد فروع في شجرة لدينا، فإننا يمكن أن يكون 7 -

339
00:25:16,470 --> 00:25:21,650
فإننا يمكن أن يكون، يجب أن يشير يساره إلى 3.

340
00:25:21,650 --> 00:25:25,130
فكيف نفعل ذلك؟

341
00:25:25,130 --> 00:25:29,320
[طلاب، غير مفهومة] >> نعم. عنوان node3،

342
00:25:29,320 --> 00:25:34,170
وإذا لم يكن لديك عنوان، ثم أنه ليس فقط تجميع.

343
00:25:34,170 --> 00:25:38,190
ولكن تذكر أن هذه هي مؤشرات إلى العقد المقبل.

344
00:25:38,190 --> 00:25:44,930
وينبغي الإشارة الحق إلى 9،

345
00:25:44,930 --> 00:25:53,330
وينبغي 3 نقطة على الحق إلى 6.

346
00:25:53,330 --> 00:25:58,480
وأعتقد أن هذا هو كل مجموعة. أي تعليقات أو أسئلة؟

347
00:25:58,480 --> 00:26:02,060
[طالبة، غير مفهومة] جذر ستكون 7.

348
00:26:02,060 --> 00:26:08,210
نستطيع أن نقول مجرد عقدة * PTR =

349
00:26:08,210 --> 00:26:14,160
أو الجذر، و= node7.

350
00:26:14,160 --> 00:26:20,730
>> لأغراضنا، ونحن في طريقنا إلى أن التعامل مع إدراج،

351
00:26:20,730 --> 00:26:25,490
لذلك نحن ذاهبون الى تريد كتابة دالة لتضاف الى هذه الشجرة الثنائية

352
00:26:25,490 --> 00:26:34,230
ويجري إدراج حتما إلى استدعاء malloc لإنشاء عقدة جديدة لهذه الشجرة.

353
00:26:34,230 --> 00:26:36,590
حتى تسير الامور للحصول فوضى مع حقيقة أن بعض العقد

354
00:26:36,590 --> 00:26:38,590
حاليا على كومة

355
00:26:38,590 --> 00:26:43,680
والعقد الأخرى تسير في نهاية المطاف على كومة عندما كنا إدراجها.

356
00:26:43,680 --> 00:26:47,640
هذا صحيح تماما، ولكن السبب الوحيد

357
00:26:47,640 --> 00:26:49,600
ونحن قادرون على القيام بذلك على المكدس

358
00:26:49,600 --> 00:26:51,840
لأنه مثل هذا المثال المفتعلة التي نعرفها

359
00:26:51,840 --> 00:26:56,360
ومن المفترض الشجرة التي يتم بناؤها من 7، 3، 6، 9.

360
00:26:56,360 --> 00:27:02,970
إذا لم يكن لدينا هذا، ثم لما كان لنا لmalloc في المقام الأول.

361
00:27:02,970 --> 00:27:06,160
كما سنرى قليلا في وقت لاحق، ينبغي لنا أن malloc'ing.

362
00:27:06,160 --> 00:27:08,570
الآن انها معقولة تماما لوضعه على كومة،

363
00:27:08,570 --> 00:27:14,750
ولكن دعونا تغيير هذا إلى تنفيذ malloc.

364
00:27:14,750 --> 00:27:17,160
لذلك كل هذه سوف تكون الآن إلى شيء من هذا القبيل

365
00:27:17,160 --> 00:27:24,240
* العقدة = node9 malloc (sizeof (عقدة)).

366
00:27:24,240 --> 00:27:28,040
والآن ونحن في طريقنا إلى القيام به لدينا الاختيار.

367
00:27:28,040 --> 00:27:34,010
إذا كان (node9 == NULL) - لم أكن أريد أن -

368
00:27:34,010 --> 00:27:40,950
العودة 1، ومن ثم يمكننا القيام به node9-> الآن حان لأن مؤشر،

369
00:27:40,950 --> 00:27:45,300
قيمة = 6، node9-> غادر = NULL،

370
00:27:45,300 --> 00:27:48,930
node9-> الحق = NULL،

371
00:27:48,930 --> 00:27:51,410
ونحن ستكون لدينا للقيام بذلك لكل من تلك العقد.

372
00:27:51,410 --> 00:27:57,490
بدلا من ذلك، دعونا وضعها داخل وظيفة منفصلة.

373
00:27:57,490 --> 00:28:00,620
دعنا نسميها عقدة * build_node،

374
00:28:00,620 --> 00:28:09,050
وهذا يشبه إلى حد ما واجهات برمجة التطبيقات التي نقدمها لترميز هوفمان.

375
00:28:09,050 --> 00:28:12,730
نقدم لكم وظائف مهيئ لشجرة

376
00:28:12,730 --> 00:28:20,520
وdeconstructor "وظائف" لتلك الأشجار ومثلها للغابات.

377
00:28:20,520 --> 00:28:22,570
>> حتى هنا ونحن في طريقنا إلى مهيئ لها وظيفة

378
00:28:22,570 --> 00:28:25,170
لمجرد بناء عقدة بالنسبة لنا.

379
00:28:25,170 --> 00:28:29,320
وانها سوف ننظر الى حد كبير تماما مثل هذا.

380
00:28:29,320 --> 00:28:32,230
وانا ذاهب حتى على الكسل وعدم تغيير اسم المتغير،

381
00:28:32,230 --> 00:28:34,380
على الرغم من node9 لا معنى له بعد الآن.

382
00:28:34,380 --> 00:28:38,610
أوه، أعتقد قيمة node9 لا ينبغي أن يكون 6.

383
00:28:38,610 --> 00:28:42,800
الآن يمكننا العودة node9.

384
00:28:42,800 --> 00:28:49,550
وهنا يجب علينا أن نعود فارغة.

385
00:28:49,550 --> 00:28:52,690
الجميع يتفق على أن وظيفة بناء واحد في عقدة؟

386
00:28:52,690 --> 00:28:59,780
حتى الآن يمكن أن نسميه فقط لبناء أي عقدة مع قيمة معينة ومؤشرات فارغة.

387
00:28:59,780 --> 00:29:09,750
الآن يمكننا أن نسمي ذلك، يمكننا أن نفعل عقدة * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
ودعونا نفعل. . .

389
00:29:25,810 --> 00:29:33,980
6، 3، 7، 6، 3، 7.

390
00:29:33,980 --> 00:29:39,330
والآن نريد أن إعداد مؤشرات نفسه،

391
00:29:39,330 --> 00:29:42,470
الآن كل شيء ما عدا بالفعل من حيث مؤشرات

392
00:29:42,470 --> 00:29:48,480
لذلك لم يعد في حاجة إلى عنوان.

393
00:29:48,480 --> 00:29:56,300
حسنا. إذن ما هو آخر شيء أريد القيام به؟

394
00:29:56,300 --> 00:30:03,850
هناك خطأ تدقيق أن أنا لا أفعل.

395
00:30:03,850 --> 00:30:06,800
ماذا بناء عودة العقدة؟

396
00:30:06,800 --> 00:30:11,660
[طالبة، غير مفهومة] >> نعم. إذا فشل malloc، وأنها سوف تعود فارغة.

397
00:30:11,660 --> 00:30:16,460
لذلك أنا ذاهب لوضع بتكاسل عليه هنا بدلا من القيام شرط لكل منها.

398
00:30:16,460 --> 00:30:22,320
إذا كان (node9 == NULL، أو - حتى أبسط،

399
00:30:22,320 --> 00:30:28,020
وهذا يعادل node9 إن لم يكن فقط.

400
00:30:28,020 --> 00:30:38,310
حتى إن لم يكن node9، أو لا node6، أو لا node3، أو لا node7، والعودة 1.

401
00:30:38,310 --> 00:30:42,850
ربما ينبغي لنا أن فشلت طباعة malloc، أو شيء من هذا.

402
00:30:42,850 --> 00:30:46,680
[طالب] هل كاذبة فارغة يساوي أيضا؟

403
00:30:46,680 --> 00:30:51,290
[بودين] أي قيمة الصفر هو زائف.

404
00:30:51,290 --> 00:30:53,920
ذلك هو قيمة فارغة صفر.

405
00:30:53,920 --> 00:30:56,780
صفر هو قيمة صفر. كاذبة هي قيمة صفر.

406
00:30:56,780 --> 00:31:02,130
أي - الى حد كبير فقط 2 صفر القيم لاغية والصفر،

407
00:31:02,130 --> 00:31:07,900
كاذبة هي مجرد تجزئة على النحو المحدد صفر.

408
00:31:07,900 --> 00:31:13,030
الذي ينطبق أيضا إذا كنا لا نعلن متغير عمومي.

409
00:31:13,030 --> 00:31:17,890
إذا لم لدينا عقدة الجذر * هنا،

410
00:31:17,890 --> 00:31:24,150
ثم - والشيء الجميل في المتغيرات العالمية هو أن لديهم دائما قيمة أولية.

411
00:31:24,150 --> 00:31:27,500
هذا ليس صحيحا من وظائف، وكيف داخل من هنا،

412
00:31:27,500 --> 00:31:34,870
اذا كان لدينا، مثل، * عقدة أو عقدة X.

413
00:31:34,870 --> 00:31:37,380
ليس لدينا أي فكرة عما x.value، x.whatever،

414
00:31:37,380 --> 00:31:40,700
أو يمكننا طباعتها وأنها يمكن أن تكون تعسفية.

415
00:31:40,700 --> 00:31:44,980
هذا ليس صحيحا من المتغيرات العالمية.

416
00:31:44,980 --> 00:31:47,450
عقدة الجذر أو حتى العاشر العقدة.

417
00:31:47,450 --> 00:31:53,410
بشكل افتراضي، كل ما هو عالمي، إذا لم يتم تهيئة صراحة إلى بعض القيمة،

418
00:31:53,410 --> 00:31:57,390
يحتوي على قيمة الصفر كقيمة لها.

419
00:31:57,390 --> 00:32:01,150
حتى هنا، عقدة الجذر *، نحن لا تهيئة صراحة إلى أي شيء،

420
00:32:01,150 --> 00:32:06,350
لذلك سوف تكون قيمته الافتراضية فارغة، والذي هو القيمة صفر من المؤشرات.

421
00:32:06,350 --> 00:32:11,870
القيمة الافتراضية X هو الذهاب الى يعني أن x.value صفر،

422
00:32:11,870 --> 00:32:14,260
x.left فارغة، وx.right فارغة.

423
00:32:14,260 --> 00:32:21,070
منذ ذلك هو البنية، فإن كل من مجالات البنية تكون قيم الصفر.

424
00:32:21,070 --> 00:32:24,410
نحن لسنا بحاجة لاستخدام ذلك هنا، وإن كان.

425
00:32:24,410 --> 00:32:27,320
[طالب] والبنيات مختلفة من المتغيرات الأخرى، وهي المتغيرات الأخرى

426
00:32:27,320 --> 00:32:31,400
القيم القمامة، وهذه هي الأصفار؟

427
00:32:31,400 --> 00:32:36,220
[بودين] قيم أخرى أيضا. حتى في س س سوف يكون صفرا.

428
00:32:36,220 --> 00:32:40,070
اذا كان في نطاق عالمي، ولديه القيمة الأولية. حسنا >>.

429
00:32:40,070 --> 00:32:48,950
[بودين] إما القيمة الأولية التي اعطتها أو صفر.

430
00:32:48,950 --> 00:32:53,260
أعتقد أن يعتني كل هذا.

431
00:32:53,260 --> 00:32:58,390
>> حسنا. وبالتالي فإن الجزء التالي من سؤال يسأل،

432
00:32:58,390 --> 00:33:01,260
"الآن نريد أن كتابة دالة دعا يحتوي على

433
00:33:01,260 --> 00:33:04,930
مع نموذج أولي من قيمة BOOL يحتوي على كثافة العمليات. "

434
00:33:04,930 --> 00:33:08,340
نحن لن تفعل BOOL يحتوي على القيمة الصحيحة.

435
00:33:08,340 --> 00:33:15,110
نموذجنا هو الذهاب لتبدو وكأنها

436
00:33:15,110 --> 00:33:22,380
BOOL يحتوي على (قيمة كثافة العمليات.

437
00:33:22,380 --> 00:33:24,490
ثم ونحن في طريقنا أيضا إلى نقله الشجرة

438
00:33:24,490 --> 00:33:28,870
أنه ينبغي أن يكون التحقق لمعرفة إذا كان لديه تلك القيمة.

439
00:33:28,870 --> 00:33:38,290
* عقدة حتى شجرة). حسنا.

440
00:33:38,290 --> 00:33:44,440
ومن ثم يمكن أن نطلق عليه مع شيء من هذا القبيل،

441
00:33:44,440 --> 00:33:46,090
ربما سوف نريد إلى printf أو شيء.

442
00:33:46,090 --> 00:33:51,040
تحتوي على 6، وجذر لدينا.

443
00:33:51,040 --> 00:33:54,300
يجب أن تعود واحدة، أو صحيحا،

444
00:33:54,300 --> 00:33:59,390
في حين يحتوي الجذر 5 ينبغي أن عودة كاذبة.

445
00:33:59,390 --> 00:34:02,690
حتى تأخذ ثانية لتنفيذ ذلك.

446
00:34:02,690 --> 00:34:06,780
يمكنك أن تفعل ذلك إما تكراري أو بشكل متكرر.

447
00:34:06,780 --> 00:34:09,739
والشيء الجميل في الطريقة التي قد وضع الامور هو أن

448
00:34:09,739 --> 00:34:12,300
فإنه يفسح المجال لدينا الحل أسهل بكثير العودية

449
00:34:12,300 --> 00:34:14,719
من الطريقة العالمي المتغير فعلت.

450
00:34:14,719 --> 00:34:19,750
لأنه إذا كان لدينا فقط يحتوي على القيمة الصحيحة، ثم لدينا أي وسيلة لأسفل الأشجار الفرعية recursing.

451
00:34:19,750 --> 00:34:24,130
كان علينا أن لها وظيفة مساعد منفصلة recurses أسفل الأشجار الفرعية بالنسبة لنا.

452
00:34:24,130 --> 00:34:29,610
ولكن بما أننا قد غيرت من اتخاذ الشجرة كوسيطة،

453
00:34:29,610 --> 00:34:32,760
الذي كان ينبغي أن يكون دائما في المقام الأول،

454
00:34:32,760 --> 00:34:35,710
يمكن الآن إعادة لعنة علينا بسهولة أكبر.

455
00:34:35,710 --> 00:34:38,960
حتى تكرارية أو متكررة، سوف نذهب أكثر على حد سواء،

456
00:34:38,960 --> 00:34:46,139
ولكن سوف نرى أن ينتهي به الأمر إلى العودية غاية السهولة.

457
00:34:59,140 --> 00:35:02,480
حسنا. هل لديها شيء يمكننا العمل معها؟

458
00:35:02,480 --> 00:35:12,000
>> [طالب] أنا عندي حل تكرارية. >> حسنا، تكرارية.

459
00:35:12,000 --> 00:35:16,030
حسنا، هذا يبدو جيدا.

460
00:35:16,030 --> 00:35:18,920
لذلك، تريد السير لنا من خلال ذلك؟

461
00:35:18,920 --> 00:35:25,780
[طالب] بالتأكيد. تعيين لذلك أنا متغير TEMP للحصول على العقدة الأولى من شجرة.

462
00:35:25,780 --> 00:35:28,330
وبعد ذلك فقط من خلال يحلق في حين لا TEMP فارغة على قدم المساواة،

463
00:35:28,330 --> 00:35:31,700
وذلك في حين كان لا يزال في الشجرة، وأنا أعتقد.

464
00:35:31,700 --> 00:35:35,710
وإذا كانت القيمة تساوي القيمة التي يتم الإشارة إلى درجة الحرارة،

465
00:35:35,710 --> 00:35:37,640
ثم تقوم بإرجاع هذه القيمة.

466
00:35:37,640 --> 00:35:40,210
خلاف ذلك، فإنه يتحقق ما اذا كان على الجانب الأيمن أو الجانب الأيسر.

467
00:35:40,210 --> 00:35:43,400
اذا كان لديك أي وقت مضى حالة حيث لم يكن هناك مزيد من الشجرة،

468
00:35:43,400 --> 00:35:47,330
ثم تقوم بإرجاع - خروجها من حلقة وترجع كاذبة.

469
00:35:47,330 --> 00:35:52,190
[بودين] حسنا. بحيث يبدو جيدا.

470
00:35:52,190 --> 00:35:58,470
أي شخص لديه أي تعليق على أي شيء؟

471
00:35:58,470 --> 00:36:02,400
ليس لدي اي تعليق صحة على الإطلاق.

472
00:36:02,400 --> 00:36:11,020
شيء واحد يمكننا القيام به هو هذا الرجل.

473
00:36:11,020 --> 00:36:21,660
أوه، أنها سوف تقطع طويل قليلا قليلا.

474
00:36:21,660 --> 00:36:33,460
سوف أقوم بإصلاح ما يصل. حسنا.

475
00:36:33,460 --> 00:36:37,150
>> يجب على الجميع يتذكر كيف يعمل الثلاثي.

476
00:36:37,150 --> 00:36:38,610
هناك بالتأكيد تم المسابقات في الماضي

477
00:36:38,610 --> 00:36:41,170
التي تعطيك وظيفة مع المشغل الثلاثي،

478
00:36:41,170 --> 00:36:45,750
ويقول ترجمة هذا، أن تفعل شيئا لا يستخدم الثلاثي.

479
00:36:45,750 --> 00:36:49,140
لذلك هذا هو الحال شائع جدا من عندما كنت تفكر في استخدام الثلاثي،

480
00:36:49,140 --> 00:36:54,610
حيث إذا وضع بعض حالة متغير إلى شيء،

481
00:36:54,610 --> 00:36:58,580
تعيين متغير آخر أن نفس إلى شيء آخر.

482
00:36:58,580 --> 00:37:03,390
هذا شيء كثيرا جدا يمكن أن تتحول إلى هذا النوع من الاشياء

483
00:37:03,390 --> 00:37:14,420
حيث وضع هذا المتغير لهذا - أو، حسنا، هل هذا صحيح؟ ثم هذا، وإلا هذا.

484
00:37:14,420 --> 00:37:18,550
[طالب] أول واحد هو إذا كان هذا صحيحا، أليس كذلك؟

485
00:37:18,550 --> 00:37:25,570
[بودين] نعم. الطريق قرأت دائما هو عليه، درجة الحرارة يساوي قيمة أكبر من قيمة درجة الحرارة،

486
00:37:25,570 --> 00:37:30,680
ثم هذا، وإلا هذا. انها بطرح سؤال.

487
00:37:30,680 --> 00:37:35,200
هو أكبر؟ قم أول شيء. آخر يفعل الشيء الثاني.

488
00:37:35,200 --> 00:37:41,670
كنت دائما تقريبا - القولون، أنا فقط - في رأسي، وأنا أقرأ آخر باسم.

489
00:37:41,670 --> 00:37:47,180
>> هل لديها حل العودية؟

490
00:37:47,180 --> 00:37:49,670
حسنا. هذا واحد ونحن في طريقنا ل- يمكن أن يكون بالفعل كبيرة،

491
00:37:49,670 --> 00:37:53,990
ولكن ونحن في طريقنا لجعله أفضل.

492
00:37:53,990 --> 00:37:58,720
هذا هو الى حد كبير نفس الفكرة بالضبط.

493
00:37:58,720 --> 00:38:03,060
انها مجرد، حسنا، هل تريد أن أشرح؟

494
00:38:03,060 --> 00:38:08,340
[طالب] بالتأكيد. لذلك نحن مع التأكد من أن الشجرة ليست فارغة الأولى،

495
00:38:08,340 --> 00:38:13,380
لأنه إذا كان شجرة فارغة ثم انه سيكون لعودة كاذبة لأننا لم نجد ذلك.

496
00:38:13,380 --> 00:38:19,200
وإذا كان لا يزال هناك شجرة، نذهب إلى - نحن أولا التحقق إذا كانت القيمة هي العقدة الحالية.

497
00:38:19,200 --> 00:38:23,740
العودة الحقيقية إذا كان، وإذا لم يكن لنا إعادة لعنة على اليسار أو اليمين.

498
00:38:23,740 --> 00:38:25,970
هل هذا الصوت المناسب؟ هم >> MM-. (الاتفاق)

499
00:38:25,970 --> 00:38:33,880
تلاحظ ذلك أن هذا هو تقريبا - هيكليا مشابهة جدا لحل تكرارية.

500
00:38:33,880 --> 00:38:38,200
انها مجرد أنه بدلا من recursing، كان لدينا حلقة من الوقت.

501
00:38:38,200 --> 00:38:40,840
والقضية هنا حيث قاعدة الشجرة فارغة لا تساوي

502
00:38:40,840 --> 00:38:44,850
وكان الشرط الذي بموجبه نحن اندلعت من الحلقة الوقت.

503
00:38:44,850 --> 00:38:50,200
انهم متشابهة جدا. ولكن نحن ذاهبون الى اتخاذ هذه الخطوة واحدة أخرى.

504
00:38:50,200 --> 00:38:54,190
الآن، ونحن نفعل نفس الشيء هنا.

505
00:38:54,190 --> 00:38:57,680
لاحظت نحن العودة نفس الشيء في كل من هذه الخطوط،

506
00:38:57,680 --> 00:39:00,220
باستثناء واحد هو حجة مختلفة.

507
00:39:00,220 --> 00:39:07,950
لذلك نحن ذاهبون لجعل ذلك في الثلاثي.

508
00:39:07,950 --> 00:39:13,790
أنا ضربت شيئا الخيار، وانها حققت الرمز. حسنا.

509
00:39:13,790 --> 00:39:21,720
لذلك نحن في طريقنا للعودة على ذلك.

510
00:39:21,720 --> 00:39:28,030
هذا هو الحصول على خطوط متعددة، وأيضا، في أسرع من ذلك.

511
00:39:28,030 --> 00:39:31,060
عادة، كشيء الأسلوبية، وأنا لا أعتقد كثير من الناس

512
00:39:31,060 --> 00:39:38,640
وضع مسافة بعد السهم، ولكن أعتقد إذا كنت متسقة، أنه بخير.

513
00:39:38,640 --> 00:39:44,320
إذا كانت القيمة أقل من قيمة شجرة، ونحن نريد لإعادة لعنة على اليسار شجرة،

514
00:39:44,320 --> 00:39:53,890
آخر ونحن نريد أن إعادة لعنة على حق شجرة.

515
00:39:53,890 --> 00:39:58,610
لذلك هذه الخطوة واحدة من صنع هذا تبدو أصغر.

516
00:39:58,610 --> 00:40:02,660
الخطوة الثانية لجعل هذا تبدو أصغر -

517
00:40:02,660 --> 00:40:09,150
يمكننا فصل هذه لعدة أسطر.

518
00:40:09,150 --> 00:40:16,500
حسنا. الخطوة الثانية من مما جعلها تبدو أصغر هنا،

519
00:40:16,500 --> 00:40:25,860
حتى يساوي قيمة الإرجاع قيمة شجرة، أو يحتوي أيا كان.

520
00:40:25,860 --> 00:40:28,340
>> هذا هو الشيء المهم.

521
00:40:28,340 --> 00:40:30,860
أنا لست متأكدا مما إذا كان ذلك قال صراحة في الصف،

522
00:40:30,860 --> 00:40:34,740
ولكن يطلق عليه دائرة قصر التقييم.

523
00:40:34,740 --> 00:40:41,060
والفكرة هنا هي القيمة == قيمة شجرة.

524
00:40:41,060 --> 00:40:49,960
إذا كان هذا صحيحا، فإن هذا صحيح، ونحن نريد أن 'أو' انه مع كل ما هو أكثر من هنا.

525
00:40:49,960 --> 00:40:52,520
ذلك دون حتى التفكير بكل ما هو أكثر من هنا،

526
00:40:52,520 --> 00:40:55,070
ما هو التعبير بالكامل سيعودون؟

527
00:40:55,070 --> 00:40:59,430
[طالب] صحيح؟ نعم >>، وذلك لأن الصحيح من أي شيء،

528
00:40:59,430 --> 00:41:04,990
or'd - or'd أو حقيقية مع أي شيء صحيح بالضرورة.

529
00:41:04,990 --> 00:41:08,150
ذلك في أقرب وقت كما نرى قيمة الإرجاع = قيمة الشجرة،

530
00:41:08,150 --> 00:41:10,140
ونحن في طريقنا إلى العودة الحقيقية فقط.

531
00:41:10,140 --> 00:41:15,710
لن يذهبوا حتى للإعادة لعنة يحتوي على مزيد من أسفل الخط.

532
00:41:15,710 --> 00:41:20,980
يمكننا اتخاذ هذه الخطوة واحدة أخرى.

533
00:41:20,980 --> 00:41:29,490
شجرة العودة لا تساوي فارغة وكل هذا.

534
00:41:29,490 --> 00:41:32,650
جعل من ذلك وظيفة من سطر واحد.

535
00:41:32,650 --> 00:41:36,790
وهذا هو أيضا مثال على دائرة قصر التقييم.

536
00:41:36,790 --> 00:41:40,680
ولكن الآن انها نفس الفكرة -

537
00:41:40,680 --> 00:41:47,320
بدلا من - إذا كان الأمر كذلك شجرة فارغة لا تساوي - أو، حسنا،

538
00:41:47,320 --> 00:41:49,580
إذا شجرة لا يساوي فارغة، والذي هو حالة سيئة،

539
00:41:49,580 --> 00:41:54,790
إذا شجرة يساوي فارغة، ثم الشرط الأول ستكون خاطئة.

540
00:41:54,790 --> 00:42:00,550
كاذبة حتى anded مع أي شيء سيكون ماذا؟

541
00:42:00,550 --> 00:42:04,640
[طالب] خطأ. نعم >>. هذا هو النصف الآخر من دائرة قصر التقييم،

542
00:42:04,640 --> 00:42:10,710
حيث إذا شجرة لا فارغة لا تساوي، ثم نحن لن نذهب حتى -

543
00:42:10,710 --> 00:42:14,930
أو إذا شجرة لا يساوي فارغة، فإننا لن نفعل قيمة == قيمة شجرة.

544
00:42:14,930 --> 00:42:17,010
ونحن في طريقنا للعودة على الفور فقط كاذبة.

545
00:42:17,010 --> 00:42:20,970
وهو أمر مهم، لأنه إذا لم يفعل ذلك دائرة قصر تقييم،

546
00:42:20,970 --> 00:42:25,860
ثم إذا شجرة لا يساوي فارغة، هذا الشرط الثاني هو الذهاب الى خطأ SEG،

547
00:42:25,860 --> 00:42:32,510
لأن شجرة> قيمة ويعتبر إلغاء مرجعية فارغة.

548
00:42:32,510 --> 00:42:40,490
ولهذا ذلك. يمكن أن تجعل هذا - تحويل أكثر من مرة واحدة.

549
00:42:40,490 --> 00:42:44,840
هذا أمر شائع جدا أيضا، لا يجعل هذا الخط واحدة مع هذا،

550
00:42:44,840 --> 00:42:49,000
ولكن هذا أمر شائع في ظروف، ربما ليس هنا،

551
00:42:49,000 --> 00:42:59,380
ولكن إذا (شجرة! NULL =، == والقيمة شجرة> القيمة)، تفعل ما.

552
00:42:59,380 --> 00:43:01,560
هذه هي حالة شائعة جدا، حيث بدلا من الاضطرار

553
00:43:01,560 --> 00:43:06,770
لكسر هذه إلى قسمين IFS، حيث تريد، هو باطل الشجرة؟

554
00:43:06,770 --> 00:43:11,780
حسنا، انها ليست فارغة، وحتى الآن هي القيمة مساوية لقيمة الشجرة؟ القيام بذلك.

555
00:43:11,780 --> 00:43:17,300
بدلا من ذلك، هذا الشرط، وهذا خطأ أبدا SEG

556
00:43:17,300 --> 00:43:21,220
لأنها سوف تندلع إذا كانت هذه يحدث أن تكون فارغة.

557
00:43:21,220 --> 00:43:24,000
حسنا، أعتقد إذا شجرة الخاص بك هو مؤشر غير صالح تماما، ويمكن ان يزال SEG خطأ،

558
00:43:24,000 --> 00:43:26,620
ولكن لا يمكن أن SEG خطأ إذا شجرة فارغة.

559
00:43:26,620 --> 00:43:32,900
لو كانت فارغة، فإنه الخروج من أي وقت مضى قبل أن ألغى الإشارة القيمة المؤشر في المقام الأول.

560
00:43:32,900 --> 00:43:35,000
[طالب] هل هذا التقييم يسمى كسول؟

561
00:43:35,000 --> 00:43:40,770
>> التقييم [بودين] كسول هو شيء منفصل.

562
00:43:40,770 --> 00:43:49,880
تقييم كسول هو أشبه تسأل عن قيمة،

563
00:43:49,880 --> 00:43:54,270
كنت أسأل لحساب قيمة، نوع من، ولكنك لا تحتاج على الفور.

564
00:43:54,270 --> 00:43:59,040
لذلك حتى كنت في حاجة فعلا، لا يتم تقييم ذلك.

565
00:43:59,040 --> 00:44:03,920
هذه ليست بالضبط نفس الشيء، ولكن، في pset هوفمان

566
00:44:03,920 --> 00:44:06,520
تقول أننا "بتكاسل" الكتابة.

567
00:44:06,520 --> 00:44:08,670
السبب في أننا نفعل ذلك لأننا في الواقع كنت التخزين المؤقت للكتابة -

568
00:44:08,670 --> 00:44:11,820
نحن لا نريد لكتابة بت الفردية في كل مرة،

569
00:44:11,820 --> 00:44:15,450
أو الفردية بايت في كل مرة، بدلا نريد للحصول على قطعة من وحدات البايت.

570
00:44:15,450 --> 00:44:19,270
ثم مرة واحدة لدينا قطعة من بايت، ثم سوف نكتب بها.

571
00:44:19,270 --> 00:44:22,640
على الرغم من أن تسأل لكتابة - وfwrite وfread تفعل نفس الشيء.

572
00:44:22,640 --> 00:44:26,260
أنها عازلة يقرأ ويكتب لكم.

573
00:44:26,260 --> 00:44:31,610
على الرغم من أن تسأل لكتابة على الفور، وربما لن.

574
00:44:31,610 --> 00:44:34,540
وأنت لا تستطيع أن تتأكد من أن الأمور تسير على أن تكون مكتوبة

575
00:44:34,540 --> 00:44:37,540
حتى استدعاء hfclose أو أيا كان،

576
00:44:37,540 --> 00:44:39,620
ثم التي تقول، حسنا، أنا إغلاق ملف بلدي،

577
00:44:39,620 --> 00:44:43,450
وهذا يعني أنني أفضل الكتابة كل شيء أنا لم تكتب بعد.

578
00:44:43,450 --> 00:44:45,770
فقد لا تحتاج لكتابة كل شيء

579
00:44:45,770 --> 00:44:49,010
حتى كنت إغلاق الملف، ومن ثم فإنه يحتاج إلى.

580
00:44:49,010 --> 00:44:56,220
ولهذا فقط ما كسول - ينتظر حتى يجب أن يحدث.

581
00:44:56,220 --> 00:44:59,990
هذا - اتخاذ 51 و كنت سأذهب فيه بمزيد من التفصيل،

582
00:44:59,990 --> 00:45:05,470
لأن كل شيء في وOCaml 51، كل شيء على ما العودية.

583
00:45:05,470 --> 00:45:08,890
هناك تكرارية أي حلول، أساسا.

584
00:45:08,890 --> 00:45:11,550
كل شيء العودية، وتقييم كسول

585
00:45:11,550 --> 00:45:14,790
وسيكون من المهم بالنسبة للكثير من الظروف

586
00:45:14,790 --> 00:45:19,920
حيث، إذا لم يتم تقييم بتكاسل، فهل يعني -

587
00:45:19,920 --> 00:45:24,760
ومثال على ذلك هو تيارات، والتي هي بلا حدود طويلة.

588
00:45:24,760 --> 00:45:30,990
من الناحية النظرية، يمكنك التفكير في الأعداد الطبيعية وتيار من 1-2-3-4-5-6-7،

589
00:45:30,990 --> 00:45:33,090
الأشياء بتكاسل ذلك تقييم ما يرام.

590
00:45:33,090 --> 00:45:37,210
إذا قلت أريد أن عدد العاشرة، ثم لا أستطيع تقييم ما يصل الى عدد العاشرة.

591
00:45:37,210 --> 00:45:40,300
إذا كنت تريد رقم مائة، ثم لا أستطيع تقييم ما يصل الى مئة عدد.

592
00:45:40,300 --> 00:45:46,290
دون تقييم كسول، ثم انه سيكون في محاولة لتقييم كل الأرقام على الفور.

593
00:45:46,290 --> 00:45:50,000
كنت تقييم العديد من الأرقام متناهيه، وهذا غير ممكن تماما.

594
00:45:50,000 --> 00:45:52,080
لذلك هناك الكثير من الظروف التي تكون فيها كسول التقييم

595
00:45:52,080 --> 00:45:57,840
من الضروري الحصول على الأشياء فقط لللعمل.

596
00:45:57,840 --> 00:46:05,260
>> الآن نريد أن يكتب فيها إدراج إدراج ستكون

597
00:46:05,260 --> 00:46:08,430
تغيير مشابه في تعريفه.

598
00:46:08,430 --> 00:46:10,470
حتى الآن انها إدراج BOOL (القيمة الباحث).

599
00:46:10,470 --> 00:46:23,850
ونحن في طريقنا لتغيير هذا إلى إدراج BOOL (الباحث القيمة، شجرة * العقدة).

600
00:46:23,850 --> 00:46:29,120
ونحن في طريقنا لتغيير الواقع مرة أخرى في أن قليلا، وسنرى ماذا.

601
00:46:29,120 --> 00:46:32,210
ودعونا نقل build_node، لمجرد هيك منه،

602
00:46:32,210 --> 00:46:36,730
إدراج أعلاه بحيث لم يكن لدينا نموذج أولي لكتابة وظيفة.

603
00:46:36,730 --> 00:46:42,450
وهو إشارة إلى أن وأنت تسير إلى استخدام build_node في إدراج.

604
00:46:42,450 --> 00:46:49,590
حسنا. يستغرق دقيقة لذلك.

605
00:46:49,590 --> 00:46:52,130
أعتقد أنني أنقذت مراجعة إذا كنت ترغب في سحب من ذلك،

606
00:46:52,130 --> 00:47:00,240
أو، على الأقل، أنا فعلت الآن.

607
00:47:00,240 --> 00:47:04,190
كنت أرغب في كسر طفيف للتفكير في منطق إدراج،

608
00:47:04,190 --> 00:47:08,750
إذا كنت لا تستطيع التفكير في الأمر.

609
00:47:08,750 --> 00:47:12,860
في الأساس، وسوف يتم إدراج أي وقت مضى فقط في الأوراق.

610
00:47:12,860 --> 00:47:18,640
مثل، إذا كنت إدراج 1، ثم أنا ذاهب لا محالة إلى أن إدراج 1 -

611
00:47:18,640 --> 00:47:21,820
أنا تغيير إلى الأسود - I'll أن إدراج 1 فوق هنا.

612
00:47:21,820 --> 00:47:28,070
أو إذا كنت إدراج 4، أريد أن إدراج أكثر من 4 هنا.

613
00:47:28,070 --> 00:47:32,180
لذلك لا يهم ما تفعله، وأنت تسير أن يكون إدراج في ورقة.

614
00:47:32,180 --> 00:47:36,130
كل ما عليك القيام به هو تكرار أسفل الشجرة حتى تحصل إلى العقدة

615
00:47:36,130 --> 00:47:40,890
ينبغي أن يكون الأصل للعقدة، عقدة الأم الجديدة،

616
00:47:40,890 --> 00:47:44,560
ثم قم بتغيير المؤشر في اليمين أو اليسار، اعتمادا على ما إذا

617
00:47:44,560 --> 00:47:47,060
انها أكبر من أو أقل من العقدة الحالية.

618
00:47:47,060 --> 00:47:51,180
تغيير هذا المؤشر للإشارة إلى العقدة الجديدة.

619
00:47:51,180 --> 00:48:05,490
تكرار ذلك أسفل شجرة، وجعل نقطة أوراق إلى عقدة جديدة.

620
00:48:05,490 --> 00:48:09,810
أعتقد أيضا حول سبب الذي يمنع النوع من الحالات من قبل،

621
00:48:09,810 --> 00:48:17,990
حيث شيدت I الشجرة الثنائية حيث كان صحيحا

622
00:48:17,990 --> 00:48:19,920
إذا كنت تتطلع فقط في عقدة واحدة،

623
00:48:19,920 --> 00:48:24,830
ولكن كان 9 إلى اليسار من 7 إذا كنت يتحرك إلى أسفل على طول الطريق.

624
00:48:24,830 --> 00:48:29,770
بحيث من المستحيل في هذا السيناريو، منذ -

625
00:48:29,770 --> 00:48:32,530
أعتقد إدراج حوالي 9 أو شيء؛ في عقدة الأولى،

626
00:48:32,530 --> 00:48:35,350
أنا ذاهب لرؤية 7 و انا ذاهب للذهاب فقط إلى اليمين.

627
00:48:35,350 --> 00:48:38,490
لذلك لا يهم ما أقوم به، إذا أنا من خلال الذهاب الى إدراج ورقة،

628
00:48:38,490 --> 00:48:40,790
ورقة باستخدام خوارزمية مناسبة،

629
00:48:40,790 --> 00:48:43,130
انه سيكون من المستحيل بالنسبة لي أن إدراج 9 إلى اليسار من 7

630
00:48:43,130 --> 00:48:48,250
لأن بمجرد أن تصل إلى 7 أنا ذاهب للذهاب إلى اليمين.

631
00:48:59,740 --> 00:49:02,070
هل لديها شيء لتبدأ؟

632
00:49:02,070 --> 00:49:05,480
[طالب] أفعل. >> متأكد.

633
00:49:05,480 --> 00:49:09,200
[طالبة، غير مفهومة]

634
00:49:09,200 --> 00:49:14,390
[طالب آخر، غير مفهومة]

635
00:49:14,390 --> 00:49:18,330
[بودين] انها أعربت عن تقديرها. حسنا. أريد أن أشرح؟

636
00:49:18,330 --> 00:49:20,690
>> [طالب] وبما أننا نعرف أن كنا إدراج

637
00:49:20,690 --> 00:49:24,060
العقد الجديد في نهاية الشجرة،

638
00:49:24,060 --> 00:49:28,070
I يحلق من خلال شجرة تكراري

639
00:49:28,070 --> 00:49:31,360
حتى وصلت إلى عقدة التي أشارت إلى قيمة خالية.

640
00:49:31,360 --> 00:49:34,220
وقررت بعد ذلك لوضعها إما على الجانب الأيمن أو الجانب الأيسر

641
00:49:34,220 --> 00:49:37,420
باستخدام هذا المتغير الحق؛ قيل لي أين وضعه.

642
00:49:37,420 --> 00:49:41,850
وبعد ذلك، أساسا، أنا الذي أدلى به للتو مشاركة -

643
00:49:41,850 --> 00:49:47,520
هذه النقطة عقدة إلى عقدة مؤقت جديد أنها خلق،

644
00:49:47,520 --> 00:49:50,770
إما على الجانب الأيسر أو على الجانب الأيمن، اعتمادا على ما قيمة كان على حق.

645
00:49:50,770 --> 00:49:56,530
وأخيرا، أنا وضعت القيمة عقدة جديدة إلى قيمة تجاربها.

646
00:49:56,530 --> 00:49:59,550
[بودين] حسنا، لذلك أرى هنا مسألة واحدة.

647
00:49:59,550 --> 00:50:02,050
هذا هو مثل 95٪ من الطريق إلى هناك.

648
00:50:02,050 --> 00:50:07,550
مسألة واحدة أن أرى، أيضا، لا ترى أي شخص آخر قضية؟

649
00:50:07,550 --> 00:50:18,400
ما هو الظرف بموجبها الخروج من الحلقة؟

650
00:50:18,400 --> 00:50:22,100
[طالب] إذا TEMP فارغة؟ نعم >>. فكيف لك الخروج من الحلقة إذا TEMP فارغة.

651
00:50:22,100 --> 00:50:30,220
ولكن ماذا أفعل هنا؟

652
00:50:30,220 --> 00:50:35,410
I مؤقت إلغاء مرجعية، وهو باطل لا محالة.

653
00:50:35,410 --> 00:50:39,840
وبالتالي فإن الشيء الآخر الذي عليك القيام به هو لا تبقي فقط المسار حتى TEMP فارغة،

654
00:50:39,840 --> 00:50:45,590
كنت تريد أن تتبع الأم في جميع الأوقات.

655
00:50:45,590 --> 00:50:52,190
نريد أيضا العقدة الأصل *، أعتقد أننا يمكن أن تبقي في أن فارغة في البداية.

656
00:50:52,190 --> 00:50:55,480
هذا وستكون لدينا السلوك غريبة لجذر من شجرة،

657
00:50:55,480 --> 00:50:59,210
ولكن سوف نصل الى ذلك.

658
00:50:59,210 --> 00:51:03,950
إذا كانت القيمة أكبر من أيا كان، ثم TEMP = TEMP الحق.

659
00:51:03,950 --> 00:51:07,910
ولكن قبل أن نفعل ذلك، الوالد = TEMP.

660
00:51:07,910 --> 00:51:14,500
أو الآباء دائما ما يساوي درجة الحرارة؟ هو أن هذه القضية؟

661
00:51:14,500 --> 00:51:19,560
إذا درجة الحرارة ليست فارغة، ثم أنا ذاهب للانتقال إلى الأسفل، مهما كانت،

662
00:51:19,560 --> 00:51:24,030
إلى عقدة درجة الحرارة التي هي الأصل.

663
00:51:24,030 --> 00:51:27,500
حتى الأم ستكون درجة الحرارة، ودرجة الحرارة ثم أنتقل إلى أسفل.

664
00:51:27,500 --> 00:51:32,410
الآن TEMP فارغة، ولكن نقطة الأصل إلى الأصل الشيء الذي فارغة.

665
00:51:32,410 --> 00:51:39,110
حتى هنا إلى أسفل، وأنا لا تريد تعيين يساوي حق 1.

666
00:51:39,110 --> 00:51:41,300
حتى انتقلت إلى اليمين، إذا كان الأمر كذلك الحق = 1،

667
00:51:41,300 --> 00:51:45,130
واعتقد انك تحتاج أيضا إلى القيام به -

668
00:51:45,130 --> 00:51:48,530
إذا قمت بنقل إلى اليسار، وتريد أن تعيين يساوي الحق إلى 0.

669
00:51:48,530 --> 00:51:55,950
وإلا إذا نقلت أي وقت مضى إلى اليمين.

670
00:51:55,950 --> 00:51:58,590
الحق في ذلك = 0. إذا 1 = الحق،

671
00:51:58,590 --> 00:52:04,260
الآن نحن نريد أن نجعل مؤشر الرئيسي newnode الحق،

672
00:52:04,260 --> 00:52:08,520
آخر ونحن نريد أن نجعل newnode الأم المؤشر الأيسر.

673
00:52:08,520 --> 00:52:16,850
الأسئلة على ذلك؟

674
00:52:16,850 --> 00:52:24,880
حسنا. لذلك هذا هو الطريق ونحن - حسنا، في الواقع، بدلا من القيام بذلك،

675
00:52:24,880 --> 00:52:29,630
كنا نتوقع منك استخدام 1/2 build_node.

676
00:52:29,630 --> 00:52:40,450
ثم إذا newnode يساوي فارغة، عودة كاذبة.

677
00:52:40,450 --> 00:52:44,170
هذا هو ذلك. الآن، وهذا هو ما كنا نتوقعه منك القيام به.

678
00:52:44,170 --> 00:52:47,690
>> هذا هو ما فعله حلول الموظفين.

679
00:52:47,690 --> 00:52:52,360
أنا لا أتفق مع هذا باعتباره السبيل "الحق" لتحقيق ذلك

680
00:52:52,360 --> 00:52:57,820
ولكن هذا على ما يرام تماما وأنها ستعمل.

681
00:52:57,820 --> 00:53:02,840
شيء واحد وهذا هو الحق غريب قليلا الآن

682
00:53:02,840 --> 00:53:08,310
إذا الشجرة يبدأ لاغيا، نحن نمر في شجرة فارغة.

683
00:53:08,310 --> 00:53:12,650
اعتقد ان ذلك يعتمد على كيفية تعريف سلوك المارة في شجرة فارغة.

684
00:53:12,650 --> 00:53:15,490
وأعتقد أنه إذا كنت تمر في شجرة فارغة،

685
00:53:15,490 --> 00:53:17,520
ثم إدراج قيمة فارغة إلى شجرة

686
00:53:17,520 --> 00:53:23,030
يجب فقط العودة شجرة حيث القيمة الوحيدة هي أن عقدة واحدة.

687
00:53:23,030 --> 00:53:25,830
الناس توافق على ذلك؟ هل يمكن، إذا أردت،

688
00:53:25,830 --> 00:53:28,050
إذا كنت تمر في شجرة فارغة

689
00:53:28,050 --> 00:53:31,320
وتريد إدراج قيمة في ذلك، عودة كاذبة.

690
00:53:31,320 --> 00:53:33,830
والامر متروك لكم لتحديد ذلك.

691
00:53:33,830 --> 00:53:38,320
للقيام أول شيء قلته وبعد ذلك -

692
00:53:38,320 --> 00:53:40,720
حسنا، كنت ستكون لدينا مشكلة يفعل ذلك، لأن

693
00:53:40,720 --> 00:53:44,090
سيكون من الأسهل لو كان لدينا مؤشر العالمية إلى الشيء،

694
00:53:44,090 --> 00:53:48,570
لكننا لا، لذلك إذا شجرة فارغة، لا يوجد شيء يمكننا القيام به حيال ذلك.

695
00:53:48,570 --> 00:53:50,960
يمكننا العودة فقط كاذبة.

696
00:53:50,960 --> 00:53:52,840
لذلك أنا ذاهب الى تغيير إدراج.

697
00:53:52,840 --> 00:53:56,540
أننا يمكن أن مجرد تغيير من الناحية الفنية هذا الحق هنا،

698
00:53:56,540 --> 00:53:58,400
كيف انها بالتكرار عبر الأشياء،

699
00:53:58,400 --> 00:54:04,530
ولكن انا ذاهب الى تغيير إدراج لاتخاذ عقدة ** شجرة.

700
00:54:04,530 --> 00:54:07,510
مؤشرات ضعف.

701
00:54:07,510 --> 00:54:09,710
ماذا يعني هذا؟

702
00:54:09,710 --> 00:54:12,330
بدلا من التعامل مع مؤشرات إلى العقد،

703
00:54:12,330 --> 00:54:16,690
الشيء انا ذاهب الى أن التلاعب هو هذا المؤشر.

704
00:54:16,690 --> 00:54:18,790
انا ذاهب الى أن هذا المؤشر التلاعب.

705
00:54:18,790 --> 00:54:21,770
انا ذاهب الى أن التلاعب مؤشرات مباشرة.

706
00:54:21,770 --> 00:54:25,760
هذا الأمر يبدو معقولا تماما منذ، والتفكير في أسفل -

707
00:54:25,760 --> 00:54:33,340
حسنا، الآن هذا يشير إلى قيمة خالية.

708
00:54:33,340 --> 00:54:38,130
ما أريد القيام به هو التلاعب هذا المؤشر للإشارة إلى غير فارغة.

709
00:54:38,130 --> 00:54:40,970
أريد أن أشير إلى عقدة بلدي جديد.

710
00:54:40,970 --> 00:54:44,870
إذا كنت تبقي فقط تتبع المؤشرات إلى مؤشرات بلدي،

711
00:54:44,870 --> 00:54:47,840
ثم أنا لست بحاجة إلى تتبع مؤشر الرئيسي.

712
00:54:47,840 --> 00:54:52,640
ويمكنني أن تبقي فقط المسار الصحيح لمعرفة ما اذا كان المؤشر يشير إلى قيمة خالية،

713
00:54:52,640 --> 00:54:54,580
وإذا كان المؤشر يشير إلى قيمة خالية،

714
00:54:54,580 --> 00:54:57,370
تغييره للإشارة إلى عقدة أريد.

715
00:54:57,370 --> 00:55:00,070
ويمكنني تغييره منذ لدي مؤشر إلى المؤشر.

716
00:55:00,070 --> 00:55:02,040
دعونا نرى هذا الحق الآن.

717
00:55:02,040 --> 00:55:05,470
يمكنك أن تفعل فعلا بشكل متكرر بسهولة جدا.

718
00:55:05,470 --> 00:55:08,080
نريد أن نفعل ذلك؟

719
00:55:08,080 --> 00:55:10,980
نعم، ونحن نفعل.

720
00:55:10,980 --> 00:55:16,790
>> دعونا نرى ذلك بشكل متكرر.

721
00:55:16,790 --> 00:55:24,070
أولا، ما هو قضيتنا الأساسية ستكون؟

722
00:55:24,070 --> 00:55:29,140
دائما تقريبا حالتنا قاعدة، ولكن في الواقع، وهذا هو نوع من صعبة.

723
00:55:29,140 --> 00:55:34,370
أول الأشياء أولا، إذا (== NULL شجرة)

724
00:55:34,370 --> 00:55:37,550
أعتقد أننا ذاهبون فقط للعودة كاذبة.

725
00:55:37,550 --> 00:55:40,460
هذا يختلف عن شجرة خالية جودكم.

726
00:55:40,460 --> 00:55:44,510
هذا هو مؤشر إلى مؤشر الجذر يتم فارغة

727
00:55:44,510 --> 00:55:48,360
وهو ما يعني أن المؤشر الجذر غير موجود.

728
00:55:48,360 --> 00:55:52,390
حتى هنا إلى أسفل، إذا كنت تفعل

729
00:55:52,390 --> 00:55:55,760
* عقدة - دعونا فقط إعادة استخدام هذا.

730
00:55:55,760 --> 00:55:58,960
* عقدة الجذر = NULL،

731
00:55:58,960 --> 00:56:00,730
ومن ثم أنا ذاهب للدعوة عن طريق القيام إدراج شيء من هذا القبيل،

732
00:56:00,730 --> 00:56:04,540
إدراج 4 في والجذر.

733
00:56:04,540 --> 00:56:06,560
وذلك الجذر، إذا هو الجذر * العقدة

734
00:56:06,560 --> 00:56:11,170
ثم والجذر وستكون ** العقدة.

735
00:56:11,170 --> 00:56:15,120
هذا صحيح. في هذه الحالة، شجرة، هنا،

736
00:56:15,120 --> 00:56:20,120
الشجرة ليست فارغة - أو إدراج.

737
00:56:20,120 --> 00:56:24,630
هنا. الشجرة ليست فارغة؛ * شجرة فارغة، التي على ما يرام

738
00:56:24,630 --> 00:56:26,680
لأنه إذا شجرة * فارغة، ثم لا أستطيع التلاعب به

739
00:56:26,680 --> 00:56:29,210
للإشارة الآن إلى ما أريد أن أشير إليه.

740
00:56:29,210 --> 00:56:34,750
ولكن إذا شجرة باطل، وهذا يعني جئت إلى هنا فقط وقال فارغة.

741
00:56:34,750 --> 00:56:42,710
لا معنى له. لا أستطيع أن أفعل أي شيء في ذلك.

742
00:56:42,710 --> 00:56:45,540
إذا شجرة فارغة، عودة كاذبة.

743
00:56:45,540 --> 00:56:48,220
لذلك أنا بالفعل أساسا ما قال حالتنا الحقيقية هي قاعدة.

744
00:56:48,220 --> 00:56:50,580
وما أن سيكون؟

745
00:56:50,580 --> 00:56:55,030
[طالبة، غير مفهومة]

746
00:56:55,030 --> 00:57:00,000
[بودين] نعم. إذا كان الأمر كذلك (* شجرة == NULL).

747
00:57:00,000 --> 00:57:04,520
هذه القضية تتعلق أكثر من هنا

748
00:57:04,520 --> 00:57:09,640
حيث إذا ضعي أحمر المؤشر هو مؤشر تركيزي ينصب على،

749
00:57:09,640 --> 00:57:12,960
ذلك مثل تركيزي ينصب على هذا المؤشر، والآن تركيزي ينصب على هذا المؤشر.

750
00:57:12,960 --> 00:57:15,150
الآن تركيزي ينصب على هذا المؤشر.

751
00:57:15,150 --> 00:57:18,160
إذا كان الأمر كذلك مؤشر ضعي أحمر، وهو عقدة ** بلدي،

752
00:57:18,160 --> 00:57:22,880
من أي وقت مضى - إذا *، ضعي أحمر المؤشر، فارغة من أي وقت مضى،

753
00:57:22,880 --> 00:57:28,470
وهذا يعني أنني في حال أنا مع التركيز على مؤشر يشير -

754
00:57:28,470 --> 00:57:32,530
هذا هو المؤشر الذي ينتمي إلى ورقة.

755
00:57:32,530 --> 00:57:41,090
أريد تغيير هذا المؤشر للإشارة إلى عقدة بلدي جديد.

756
00:57:41,090 --> 00:57:45,230
العودة إلى هنا.

757
00:57:45,230 --> 00:57:56,490
وسوف يكون مجرد بلدي newnode عقدة * ن = build_node (القيمة)

758
00:57:56,490 --> 00:58:07,300
ثم ن، ن = إذا NULL، عودة كاذبة.

759
00:58:07,300 --> 00:58:12,600
آخر ونحن نريد لتغيير ما يشير المؤشر حاليا

760
00:58:12,600 --> 00:58:17,830
للإشارة إلى عقدة لدينا الآن بنيت حديثا.

761
00:58:17,830 --> 00:58:20,280
يمكننا أن نفعل ذلك هنا في الواقع.

762
00:58:20,280 --> 00:58:30,660
بدلا من أن تقول لا، ونحن نقول * = شجرة شجرة * إذا.

763
00:58:30,660 --> 00:58:35,450
الجميع يفهم ذلك؟ أنه من خلال التعامل مع المؤشرات إلى مؤشرات،

764
00:58:35,450 --> 00:58:40,750
يمكننا تغيير مؤشرات فارغة للإشارة إلى الأشياء التي تريد لهم للإشارة إلى.

765
00:58:40,750 --> 00:58:42,820
هذا حالتنا القاعدة.

766
00:58:42,820 --> 00:58:45,740
>> الآن لدينا تكرار، أو العودية لدينا،

767
00:58:45,740 --> 00:58:51,430
ستكون مشابهة جدا لجميع recursions أخرى كنا نقوم به.

768
00:58:51,430 --> 00:58:55,830
نحن ذاهبون الى تريد إدراج القيمة،

769
00:58:55,830 --> 00:58:59,040
والآن انا ذاهب الى استخدام الثلاثي مرة أخرى، ولكن ما هي حالتنا ستكون؟

770
00:58:59,040 --> 00:59:05,180
ما هو نحن نبحث عن لتقرر ما إذا كنا نريد أن يذهب إلى اليمين أو اليسار؟

771
00:59:05,180 --> 00:59:07,760
دعونا نفعل ذلك في خطوات منفصلة.

772
00:59:07,760 --> 00:59:18,850
إذا (القيمة <) ماذا؟

773
00:59:18,850 --> 00:59:23,200
[طالب] القيمة الشجرة؟

774
00:59:23,200 --> 00:59:27,490
[بودين] لذا تذكر أن أنا حاليا -

775
00:59:27,490 --> 00:59:31,260
[طلاب، غير مفهومة]

776
00:59:31,260 --> 00:59:34,140
[بودين] نعم، لذلك هنا، دعنا نقول أن هذا السهم الأخضر

777
00:59:34,140 --> 00:59:39,050
هو مثال على ما شجرة حاليا، هو مؤشر إلى هذا المؤشر.

778
00:59:39,050 --> 00:59:46,610
وهذا يعني انا مؤشر إلى مؤشر إلى 3.

779
00:59:46,610 --> 00:59:48,800
وبدا مرتين إلغاء مرجعية جيدة.

780
00:59:48,800 --> 00:59:51,010
ماذا I - كيف أفعل ذلك؟

781
00:59:51,010 --> 00:59:53,210
[طالب] إلغاء مرجعية واحدة، ومن ثم القيام سهم بهذه الطريقة؟

782
00:59:53,210 --> 00:59:58,420
[بودين] لذلك (* شجرة) هو إلغاء مرجعية واحدة، -> قيمة

783
00:59:58,420 --> 01:00:05,960
سوف تعطيني قيمة العقدة التي أنا مشيرا بشكل غير مباشر إلى.

784
01:00:05,960 --> 01:00:11,980
حتى أتمكن من الكتابة أيضا tree.value ** إذا كنت تفضل ذلك.

785
01:00:11,980 --> 01:00:18,490
إما يعمل.

786
01:00:18,490 --> 01:00:26,190
إذا كان هذا هو الحال، ثم أريد أن أدعو إدراج مع القيمة.

787
01:00:26,190 --> 01:00:32,590
وما هو عقدة بلدي تحديث ** ستكون؟

788
01:00:32,590 --> 01:00:39,440
أريد أن أذهب إلى اليسار، لذلك ** tree.left ستكون يساري.

789
01:00:39,440 --> 01:00:41,900
وأريد المؤشر إلى هذا الشيء

790
01:00:41,900 --> 01:00:44,930
بحيث إذا كان اليسار ينتهي به الأمر على مؤشر فارغة،

791
01:00:44,930 --> 01:00:48,360
يمكنني تعديله للإشارة إلى عقدة بلدي جديد.

792
01:00:48,360 --> 01:00:51,460
>> ويمكن للحالة أخرى تكون مشابهة جدا.

793
01:00:51,460 --> 01:00:55,600
دعونا جعل الواقع أن الثلاثي بلدي في الوقت الحالي.

794
01:00:55,600 --> 01:01:04,480
إدراج قيمة إذا القيمة <(** شجرة). القيمة.

795
01:01:04,480 --> 01:01:11,040
ثم نريد أن تحديث ** لدينا إلى اليسار،

796
01:01:11,040 --> 01:01:17,030
آخر تحديث نريد أن ** لدينا إلى اليمين.

797
01:01:17,030 --> 01:01:22,540
[طالب] هل الحصول على هذا المؤشر إلى مؤشر؟

798
01:01:22,540 --> 01:01:30,940
[بودين] تذكر أن - ** tree.right هو نجم العقدة.

799
01:01:30,940 --> 01:01:35,040
[طالبة، غير مفهومة] >> نعم.

800
01:01:35,040 --> 01:01:41,140
tree.right ** مثل هذا المؤشر أو شيء.

801
01:01:41,140 --> 01:01:45,140
ذلك عن طريق أخذ مؤشر إلى ذلك، أن يعطيني ما أريد

802
01:01:45,140 --> 01:01:50,090
من المؤشر لهذا الرجل.

803
01:01:50,090 --> 01:01:54,260
[طالب] ويمكننا أن نذهب من جديد لماذا نحن نستخدم مؤشرات اثنين؟

804
01:01:54,260 --> 01:01:58,220
[بودين] نعم. لذلك - لا، يمكنك، والحل الذي قبل

805
01:01:58,220 --> 01:02:04,540
كان وسيلة للقيام بذلك دون القيام اثنين المؤشرات.

806
01:02:04,540 --> 01:02:08,740
عليك أن تكون قادرا على فهم باستخدام اثنين من المؤشرات،

807
01:02:08,740 --> 01:02:11,660
وهذا هو الحل الأكثر نظافة.

808
01:02:11,660 --> 01:02:16,090
أيضا، لاحظ أن، ماذا يحدث إذا شجرة بلدي -

809
01:02:16,090 --> 01:02:24,480
ماذا يحدث إذا الجذر بلدي لاغ؟ ماذا يحدث إذا كنت تفعل هذه الحالة هنا أليس كذلك؟

810
01:02:24,480 --> 01:02:30,540
حتى عقدة الجذر * = NULL، أدخل 4 في والجذر.

811
01:02:30,540 --> 01:02:35,110
ما لدي الآن هو جذور سيكون بعد ذلك؟

812
01:02:35,110 --> 01:02:37,470
[طالبة، غير مفهومة] >> نعم.

813
01:02:37,470 --> 01:02:41,710
قيمة الجذر ستكون 4.

814
01:02:41,710 --> 01:02:45,510
اليسار الجذري ستكون باطلة، والحق الجذر ستكون فارغة.

815
01:02:45,510 --> 01:02:49,490
وفي حالة ما إذا لم نكن تمرير الجذر حسب العنوان،

816
01:02:49,490 --> 01:02:52,490
لم نتمكن من تعديل الجذر.

817
01:02:52,490 --> 01:02:56,020
في الحالة التي يكون فيها شجرة - الجذر حيث لاغ،

818
01:02:56,020 --> 01:02:58,410
كان لدينا فقط لعودة كاذبة. لا يوجد شيء يمكننا القيام به.

819
01:02:58,410 --> 01:03:01,520
لا يمكننا إدراج عقدة في شجرة فارغة.

820
01:03:01,520 --> 01:03:06,810
ولكن يمكن الآن لدينا، ونحن جعل مجرد شجرة إلى شجرة فارغة واحدة العقدة.

821
01:03:06,810 --> 01:03:13,400
التي عادة ما تكون الطريقة المتوقعة التي من المفترض أن تعمل.

822
01:03:13,400 --> 01:03:21,610
>> وعلاوة على ذلك، وهذا هو أقصر بكثير من

823
01:03:21,610 --> 01:03:26,240
حفظ المسار أيضا من الأم، وحتى تتمكن تكرار أسفل على طول الطريق.

824
01:03:26,240 --> 01:03:30,140
الآن لدي والدي، وأنا فقط مؤشر حقي الأصل إلى غير ذلك.

825
01:03:30,140 --> 01:03:35,640
بدلا من ذلك، إذا فعلنا هذا تكراري، ويهمني أن يكون نفس الفكرة مع حلقة من الوقت.

826
01:03:35,640 --> 01:03:38,100
ولكن بدلا من الاضطرار إلى التعامل مع المؤشر والدي،

827
01:03:38,100 --> 01:03:40,600
وبدلا من ذلك مؤشر بلدي الحالي يكون الشيء

828
01:03:40,600 --> 01:03:43,790
انني تعديل مباشرة للإشارة إلى عقدة بلدي جديد.

829
01:03:43,790 --> 01:03:46,090
ليس لدي للتعامل مع سواء كان ذلك يشير إلى اليسار.

830
01:03:46,090 --> 01:03:48,810
ليس لدي للتعامل مع سواء كان ذلك يشير إلى اليمين.

831
01:03:48,810 --> 01:04:00,860
انها مجرد ما هذا المؤشر، وانا ذاهب لتعيين أنه للإشارة إلى عقدة بلدي جديد.

832
01:04:00,860 --> 01:04:05,740
الجميع يفهم كيف يعمل؟

833
01:04:05,740 --> 01:04:09,460
إذا لماذا لا نريد أن نفعل ذلك بهذه الطريقة،

834
01:04:09,460 --> 01:04:14,920
ولكن على الأقل أن يعمل هذا كحل؟

835
01:04:14,920 --> 01:04:17,110
[طالب] أين نعود صحيح؟

836
01:04:17,110 --> 01:04:21,550
[بودين] وربما كان هنا.

837
01:04:21,550 --> 01:04:26,690
إذا كان لنا أن إدراج بشكل صحيح، والعودة الحقيقية.

838
01:04:26,690 --> 01:04:32,010
آخر، إلى هنا ونحن في طريقنا إلى العودة يريدون العودة إدراج أيا كان.

839
01:04:32,010 --> 01:04:35,950
>> وما هو خاص حول هذا ظيفة العودية؟

840
01:04:35,950 --> 01:04:43,010
انها متكررة الذيل، وذلك دمنا ترجمة مع بعض التحسين،

841
01:04:43,010 --> 01:04:48,060
سوف ندرك أن وأنك لن تحصل على تجاوز سعة مكدس من هذا،

842
01:04:48,060 --> 01:04:53,230
حتى لو لديها شجرة على ارتفاع 10،000 أو 10 مليون.

843
01:04:53,230 --> 01:04:55,630
[طالبة، غير مفهومة]

844
01:04:55,630 --> 01:05:00,310
[بودين] أعتقد أنه يفعل ذلك في داش - أو ما هو مستوى التحسين

845
01:05:00,310 --> 01:05:03,820
مطلوب لالعودية ذيل ليتم الاعتراف بها.

846
01:05:03,820 --> 01:05:09,350
أعتقد أنها تعترف - دول مجلس التعاون الخليجي وضجيج

847
01:05:09,350 --> 01:05:12,610
أيضا معاني مختلفة لمستويات التحسين الخاصة بهم.

848
01:05:12,610 --> 01:05:17,870
أريد أن أقول انها داشو 2، لعلى يقين من أنه سوف تعترف العودية الذيل.

849
01:05:17,870 --> 01:05:27,880
ولكننا - هل يمكن أن بناء مثل Fibonocci سبيل المثال أو شيء.

850
01:05:27,880 --> 01:05:30,030
انها ليست سهلة لاختبار مع هذا، لأنه من الصعب لبناء

851
01:05:30,030 --> 01:05:32,600
شجرة ثنائية هذا كبيرة جدا.

852
01:05:32,600 --> 01:05:37,140
ولكن نعم، اعتقد انه من داشو 2، أن

853
01:05:37,140 --> 01:05:40,580
إذا كنت ترجمة مع داشو 2، فإنه سيتم البحث عن العودية ذيل

854
01:05:40,580 --> 01:05:54,030
وأنه من الأمثل.

855
01:05:54,030 --> 01:05:58,190
دعونا نعود إلى - إدراج حرفيا وآخر شيء تحتاجه.

856
01:05:58,190 --> 01:06:04,900
دعونا نعود إلى إدراج أكثر من هنا

857
01:06:04,900 --> 01:06:07,840
أين نحن في طريقنا للقيام نفس الفكرة.

858
01:06:07,840 --> 01:06:14,340
وأنها سوف لا تزال لديها عيب من عدم القدرة على التعامل مع تماما

859
01:06:14,340 --> 01:06:17,940
عندما الجذر نفسه لاغيا، أو دخول الماضية فارغة،

860
01:06:17,940 --> 01:06:20,060
ولكن بدلا من التعامل مع مؤشر الرئيسي،

861
01:06:20,060 --> 01:06:27,430
دعونا تطبيق نفس المنطق من المؤشرات لحفظ المؤشرات.

862
01:06:27,430 --> 01:06:35,580
إذا واصلنا هنا لدينا عقدة ** الحالي،

863
01:06:35,580 --> 01:06:37,860
ونحن لسنا بحاجة لتتبع الحق بعد الآن،

864
01:06:37,860 --> 01:06:47,190
ولكن عقدة الحالي ** = & شجرة.

865
01:06:47,190 --> 01:06:54,800
والآن لدينا حلقة في حين ستكون في حين الحالي * هل غير فارغة متساوية.

866
01:06:54,800 --> 01:07:00,270
لا تحتاج إلى تتبع الآباء بعد الآن.

867
01:07:00,270 --> 01:07:04,180
لا تحتاج إلى تتبع اليسار واليمين.

868
01:07:04,180 --> 01:07:10,190
وسوف أسميها مؤقت، لأننا بالفعل باستخدام مؤقت.

869
01:07:10,190 --> 01:07:17,200
حسنا. إذا كان الأمر كذلك (القيمة> * مؤقت)،

870
01:07:17,200 --> 01:07:24,010
ثم و(* TEMP) -> الحق

871
01:07:24,010 --> 01:07:29,250
آخر TEMP = & (* TEMP) -> اليسار.

872
01:07:29,250 --> 01:07:32,730
والآن، في هذه المرحلة، وبعد هذه الحلقة من الوقت،

873
01:07:32,730 --> 01:07:36,380
أفعل هذا فقط لأنه ربما يكون من الأسهل على التفكير بشكل متكرر من تكراري عن،

874
01:07:36,380 --> 01:07:39,010
ولكن بعد هذه الحلقة من الوقت،

875
01:07:39,010 --> 01:07:43,820
* درجة الحرارة هو مؤشر نريد للتغيير.

876
01:07:43,820 --> 01:07:48,960
>> كان لدينا قبل الوالدين، وكنا نرغب في تغيير إما اليسار الوالدين أو الوالدين الحق،

877
01:07:48,960 --> 01:07:51,310
ولكن إذا أردنا تغيير حق الوالدين،

878
01:07:51,310 --> 01:07:54,550
* ثم TEMP هو حق الوالدين، ويمكننا تغييره مباشرة.

879
01:07:54,550 --> 01:08:05,860
حتى هنا إلى أسفل، يمكننا أن نفعل * TEMP = newnode، وهذا كل شيء.

880
01:08:05,860 --> 01:08:09,540
حتى إشعار، كل ما فعلناه هو في هذا إخراج الأسطر من التعليمات البرمجية.

881
01:08:09,540 --> 01:08:14,770
من أجل تتبع الأصل في كل ما هو جهد إضافي.

882
01:08:14,770 --> 01:08:18,689
هنا، إذا كنا نستمر مسار المؤشر إلى المؤشر،

883
01:08:18,689 --> 01:08:22,990
وحتى لو أردنا أن نتخلص من كل هذه الأقواس المتعرجة الآن،

884
01:08:22,990 --> 01:08:27,170
جعلها تبدو أقصر.

885
01:08:27,170 --> 01:08:32,529
هذا هو الحل الآن بالضبط نفس،

886
01:08:32,529 --> 01:08:38,210
لكن أقل الأسطر من التعليمات البرمجية.

887
01:08:38,210 --> 01:08:41,229
بمجرد البدء في الاعتراف بهذه كحل صالح،

888
01:08:41,229 --> 01:08:43,529
كما أنه من الأسهل لسبب من مجرد مثل، حسنا،

889
01:08:43,529 --> 01:08:45,779
لماذا لدي هذه العلامة في حق الباحث؟

890
01:08:45,779 --> 01:08:49,290
ماذا يعني ذلك؟ أوه، أنها مما يدل على أن

891
01:08:49,290 --> 01:08:51,370
في كل مرة أذهب الحق، ولست بحاجة لتعيين أنه،

892
01:08:51,370 --> 01:08:53,819
آخر إذا ذهبت تركت تحتاج إلى تعيين إلى صفر.

893
01:08:53,819 --> 01:09:04,060
هنا، وأنا لم يكن لديك سبب لعن ذلك، بل من الأسهل لمجرد التفكير فيها.

894
01:09:04,060 --> 01:09:06,710
الأسئلة؟

895
01:09:06,710 --> 01:09:16,290
[طالبة، غير مفهومة] >> نعم.

896
01:09:16,290 --> 01:09:23,359
حسنا، وذلك في الجزء الأخير -

897
01:09:23,359 --> 01:09:28,080
أعتقد وظيفة واحدة سريعة وسهلة يمكننا القيام به هو،

898
01:09:28,080 --> 01:09:34,910
let's - معا، وأعتقد، ومحاولة إرسال بريد يحتوي على وظيفة

899
01:09:34,910 --> 01:09:38,899
الذي لا يهمه ما إذا كان من شجرة البحث الثنائية.

900
01:09:38,899 --> 01:09:43,770
هذا يتضمن وظيفة يجب العودة الحقيقية

901
01:09:43,770 --> 01:09:58,330
إذا في أي مكان في هذه الشجرة الثنائية العام هو القيمة التي تبحث عنها.

902
01:09:58,330 --> 01:10:02,520
لذلك دعونا نفعل لأول مرة بشكل متكرر وبعد ذلك نحن سوف نفعل ذلك تكرارا.

903
01:10:02,520 --> 01:10:07,300
يمكننا في الواقع مجرد القيام بذلك معا، لأن هذا سيكون حقا قصيرة.

904
01:10:07,300 --> 01:10:11,510
>> ما حالتي قاعدة ستكون؟

905
01:10:11,510 --> 01:10:13,890
[طالبة، غير مفهومة]

906
01:10:13,890 --> 01:10:18,230
[بودين] حتى إذا (== شجرة NULL)، ثم ماذا؟

907
01:10:18,230 --> 01:10:22,740
[طالب] عودة كاذبة.

908
01:10:22,740 --> 01:10:26,160
[بودين] أخرى، حسنا، أنا لا يحتاجون إلى آخر.

909
01:10:26,160 --> 01:10:30,250
إذا كان حالتي قاعدة أخرى.

910
01:10:30,250 --> 01:10:32,450
[طالب] شجرة في القيمة؟ نعم >>.

911
01:10:32,450 --> 01:10:36,430
إذا كان الأمر كذلك (القيمة == شجرة> القيمة.

912
01:10:36,430 --> 01:10:39,920
تلاحظ نعود إلى * العقدة، عقدة لا ** ق؟

913
01:10:39,920 --> 01:10:42,990
سوف يحتوي أبدا إلى استخدام ** العقدة،

914
01:10:42,990 --> 01:10:45,480
بما أننا لا تعديل المؤشرات.

915
01:10:45,480 --> 01:10:50,540
نحن يجتاز منهم فقط.

916
01:10:50,540 --> 01:10:53,830
اذا ما حدث ذلك، ثم نريد أن العودة الحقيقية.

917
01:10:53,830 --> 01:10:58,270
آخر ونحن نريد أن تجتاز الأطفال.

918
01:10:58,270 --> 01:11:02,620
حتى نتمكن من ليس سببا حول ما إذا كان كل شيء على يسار أقل

919
01:11:02,620 --> 01:11:05,390
وكل شيء إلى اليمين أكبر.

920
01:11:05,390 --> 01:11:09,590
فما هي حالتنا ستكون هنا - أو، ماذا نحن فاعلون؟

921
01:11:09,590 --> 01:11:11,840
[طالبة، غير مفهومة] >> نعم.

922
01:11:11,840 --> 01:11:17,400
عودة يحتوي على (القيمة، شجرة> يسار)

923
01:11:17,400 --> 01:11:26,860
أو يحتوي على (القيمة، شجرة> الحق). وهذا كل شيء.

924
01:11:26,860 --> 01:11:29,080
وتلاحظ وجود بعض التقييم دائرة قصر،

925
01:11:29,080 --> 01:11:32,520
حيث إذا كنا يحدث لتجد القيمة في شجرة اليسار،

926
01:11:32,520 --> 01:11:36,820
نحن لا نحتاج إلى النظر في الشجرة الحق.

927
01:11:36,820 --> 01:11:40,430
هذا هو وظيفة كاملة.

928
01:11:40,430 --> 01:11:43,690
الآن دعونا نفعل ذلك تكرارا،

929
01:11:43,690 --> 01:11:48,060
التي ستكون أقل لطيفة.

930
01:11:48,060 --> 01:11:54,750
سوف نأخذ بداية من المعتاد الحالي * العقدة = شجرة.

931
01:11:54,750 --> 01:12:03,250
في حين أن (الحالي! = NULL).

932
01:12:03,250 --> 01:12:08,600
الذهاب بسرعة لرؤية المشكلة.

933
01:12:08,600 --> 01:12:12,250
إذا الحالي - من هنا، إذا ما تم كسر أي وقت مضى للخروج من هذا،

934
01:12:12,250 --> 01:12:16,020
ثم قمنا ينفد من الاشياء لننظر، حتى يعود كاذبة.

935
01:12:16,020 --> 01:12:24,810
إذا (الحالي> == قيمة القيمة)، والعودة الحقيقية.

936
01:12:24,810 --> 01:12:32,910
حتى الآن، ونحن في مكان -

937
01:12:32,910 --> 01:12:36,250
نحن لا نعرف ما إذا كنا نريد أن يذهب إلى اليمين أو اليسار.

938
01:12:36,250 --> 01:12:44,590
تعسفي لذا، دعونا فقط يتجه يسارا.

939
01:12:44,590 --> 01:12:47,910
لقد تشغيل I الواضح أن مسألة حيث كنت التخلي تماما كل شيء -

940
01:12:47,910 --> 01:12:50,760
وسوف تحقق فقط من أي وقت مضى على الجانب الأيسر من شجرة.

941
01:12:50,760 --> 01:12:56,050
أنا لن تحقق أي شيء للطفل الحق في أي شيء.

942
01:12:56,050 --> 01:13:00,910
كيف يمكنني تصحيح هذا؟

943
01:13:00,910 --> 01:13:05,260
[طالب] عليك أن تتبع اليسار واليمين في كومة.

944
01:13:05,260 --> 01:13:13,710
[بودين] نعم. لذلك دعونا تجعل من

945
01:13:13,710 --> 01:13:32,360
البنية القائمة، عقدة * N، والعقدة ثم ** القادمة؟

946
01:13:32,360 --> 01:13:40,240
أعتقد أن يعمل بشكل جيد.

947
01:13:40,240 --> 01:13:45,940
نريد أن يذهب أكثر من اليسار، أو let's - حتى هنا.

948
01:13:45,940 --> 01:13:54,350
= قائمة البنية القائمة، أنها سوف تبدأ

949
01:13:54,350 --> 01:13:58,170
من هذه القائمة في البنية.

950
01:13:58,170 --> 01:14:04,040
* قائمة = NULL. بحيث سيكون لدينا قائمة مرتبطة

951
01:14:04,040 --> 01:14:08,430
من الأشجار الفرعية أن لدينا أكثر من تخطي.

952
01:14:08,430 --> 01:14:13,800
نحن نذهب لاجتياز غادر الآن،

953
01:14:13,800 --> 01:14:17,870
ولكن بما أننا في حاجة حتما إلى العودة إلى الحق،

954
01:14:17,870 --> 01:14:26,140
ونحن في طريقنا للحفاظ على الجانب الأيمن من قائمة داخل البنية دينا.

955
01:14:26,140 --> 01:14:32,620
فلن تكون لدينا new_list أو البنية،

956
01:14:32,620 --> 01:14:41,080
* البنية القائمة، new_list = malloc (sizeof (قائمة)).

957
01:14:41,080 --> 01:14:44,920
انا ذاهب الى تجاهل الأخطاء التدقيق ذلك، ولكن يجب أن تحقق لمعرفة ما إذا كان لاغيا.

958
01:14:44,920 --> 01:14:50,540
New_list العقدة انه سيكون للإشارة إلى -

959
01:14:50,540 --> 01:14:56,890
أوه، هذا هو السبب في أنني أرغب في ذلك هنا. انه سيكون للإشارة إلى قائمة البنية الثانية.

960
01:14:56,890 --> 01:15:02,380
هذه هي الطريقة فقط مرتبطة قوائم العمل.

961
01:15:02,380 --> 01:15:04,810
هذا هو نفس قائمة الباحث مرتبطة

962
01:15:04,810 --> 01:15:06,960
إلا أننا مجرد استبدال الباحث مع * العقدة.

963
01:15:06,960 --> 01:15:11,040
انها بالضبط نفس الشيء.

964
01:15:11,040 --> 01:15:15,100
new_list ذلك، فإن قيمة عقدة new_list لدينا،

965
01:15:15,100 --> 01:15:19,120
ستكون الحالي> الحق.

966
01:15:19,120 --> 01:15:24,280
قيمة لدينا new_list-> التالي ستكون لدينا قائمة الأصلي،

967
01:15:24,280 --> 01:15:30,760
ثم ونحن في طريقنا لاستكمال قائمتنا للإشارة إلى new_list.

968
01:15:30,760 --> 01:15:33,650
>> الآن نحن بحاجة نوعا من طريقة لسحب الأشياء،

969
01:15:33,650 --> 01:15:37,020
لقد قطعنا مثل الشجرة الفرعية بالكامل اليسار.

970
01:15:37,020 --> 01:15:40,480
الآن نحن بحاجة لسحب الاشياء للخروج منه،

971
01:15:40,480 --> 01:15:43,850
مثل الحالي باطل، ونحن لا نريد العودة فقط كاذبة.

972
01:15:43,850 --> 01:15:50,370
نريد الآن لسحب خارج في قائمتنا الجديدة.

973
01:15:50,370 --> 01:15:53,690
وهناك طريقة مريحة للقيام بذلك - حسنا، في الواقع، هناك عدة طرق للقيام بذلك.

974
01:15:53,690 --> 01:15:56,680
أي شخص يحصل على الاقتراح؟

975
01:15:56,680 --> 01:15:58,790
حيث يجب أن أفعل هذا أو كيف يجب أن تفعل ذلك؟

976
01:15:58,790 --> 01:16:08,010
ليس لدينا سوى بضع دقائق، ولكن أي اقتراحات؟

977
01:16:08,010 --> 01:16:14,750
بدلا من - طريقة واحدة، بدلا من حالة جودنا في حين،

978
01:16:14,750 --> 01:16:17,090
ما نحن نبحث حاليا ليست في فارغة،

979
01:16:17,090 --> 01:16:22,340
بدلا من ذلك نحن ذاهبون الى مواصلة للذهاب حتى قائمتنا نفسها هي فارغة.

980
01:16:22,340 --> 01:16:25,680
إذا كان الأمر كذلك قائمتنا ينتهي به الأمر فارغة،

981
01:16:25,680 --> 01:16:30,680
ثم قمت بتشغيل نحن من الأشياء للبحث عن، للبحث أكثر.

982
01:16:30,680 --> 01:16:39,860
ولكن هذا يعني أن أول شيء في قائمتنا هو مجرد الذهاب الى تكون العقدة الأولى.

983
01:16:39,860 --> 01:16:49,730
فإن أول شيء جدا أن تكون - لم نعد بحاجة الى ان نرى ذلك.

984
01:16:49,730 --> 01:16:58,710
حتى قائمة> ن ستكون لدينا شجرة.

985
01:16:58,710 --> 01:17:02,860
قائمة> القادمة ستكون فارغة.

986
01:17:02,860 --> 01:17:07,580
والآن بينما لا قائمة فارغة متساوية.

987
01:17:07,580 --> 01:17:11,610
الحالي هو الذهاب الى سحب شيء من قائمتنا.

988
01:17:11,610 --> 01:17:13,500
حتى الحالي هو الذهاب الى قائمة متساوية> ن.

989
01:17:13,500 --> 01:17:20,850
ومن ثم يتم الانتقال إلى قائمة المساواة القائمة>-N، أو قائمة>. المقبل

990
01:17:20,850 --> 01:17:23,480
حتى إذا كانت القيمة تساوي قيمة الحالي.

991
01:17:23,480 --> 01:17:28,790
الآن يمكننا أن نضيف على حد سواء لدينا مؤشر ومؤشر لدينا الحق اليسار

992
01:17:28,790 --> 01:17:32,900
طالما انهم غير فارغة.

993
01:17:32,900 --> 01:17:36,390
إلى هنا، وأنا أعتقد أننا يجب أن نفعل ذلك في المقام الأول.

994
01:17:36,390 --> 01:17:44,080
إذا (الحالي> الحق! = NULL)

995
01:17:44,080 --> 01:17:56,380
ثم نحن نذهب لادخال تلك العقدة في قائمتنا.

996
01:17:56,380 --> 01:17:59,290
إذا (الحالي> اليسار)، وهذا هو القليل من العمل الاضافي، ولكن هذا ما يرام.

997
01:17:59,290 --> 01:18:02,690
إذا (الحالي> اليسار! = NULL)،

998
01:18:02,690 --> 01:18:14,310
ونحن في طريقنا لإدراج اليسار إلى قائمتنا المرتبطة،

999
01:18:14,310 --> 01:18:19,700
وينبغي أن يكون عليه.

1000
01:18:19,700 --> 01:18:22,670
نحن تكرار - ما دام لدينا شيء في قائمتنا،

1001
01:18:22,670 --> 01:18:26,640
لدينا عقدة أخرى للنظر في.

1002
01:18:26,640 --> 01:18:28,920
لذلك نحن ننظر إلى تلك العقدة،

1003
01:18:28,920 --> 01:18:31,390
نحن نتقدم قائمتنا إلى المرحلة التالية.

1004
01:18:31,390 --> 01:18:34,060
إذا كان هذا هو قيمة عقدة نحن تبحث عنه، يمكننا العودة الحقيقية.

1005
01:18:34,060 --> 01:18:37,640
إدراج كل الأشجار الفرعية آخر لدينا اليسار واليمين،

1006
01:18:37,640 --> 01:18:40,510
طالما انهم غير فارغة، إلى قائمتنا

1007
01:18:40,510 --> 01:18:43,120
بحيث نذهب حتما عليها.

1008
01:18:43,120 --> 01:18:45,160
إذا كان الأمر كذلك لم تكن فارغة،

1009
01:18:45,160 --> 01:18:47,950
فإذا قال لدينا مؤشر الجذر إلى أمرين،

1010
01:18:47,950 --> 01:18:51,670
ثم انسحبت في البداية شيء من ذلك ونحن لدينا قائمة ينتهي به الأمر فارغة.

1011
01:18:51,670 --> 01:18:56,890
ثم نضع نحن أمرين مرة أخرى، وحتى الآن لدينا قائمة من حجم 2.

1012
01:18:56,890 --> 01:19:00,030
ثم ونحن في طريقنا إلى حلقة احتياطية ونحن مجرد الذهاب الى سحب،

1013
01:19:00,030 --> 01:19:04,250
دعنا نقول، المؤشر الأيسر من عقدة الجذر لدينا.

1014
01:19:04,250 --> 01:19:07,730
وسوف نستمر أن يحدث، ونحن سوف ينتهي حلقات على كل شيء.

1015
01:19:07,730 --> 01:19:11,280
>> لاحظ أن هذا كان أكثر تعقيدا بكثير

1016
01:19:11,280 --> 01:19:14,160
في حل العودية.

1017
01:19:14,160 --> 01:19:17,260
ولقد قلت عدة مرات

1018
01:19:17,260 --> 01:19:25,120
أن الحل متكررة عادة الكثير من القواسم المشتركة مع تكرارية الحل.

1019
01:19:25,120 --> 01:19:30,820
هنا هذا هو بالضبط ما الحل متكررة يقوم به.

1020
01:19:30,820 --> 01:19:36,740
التغيير الوحيد هو أنه بدلا من استخدام ضمنا المكدس، مكدس البرنامج،

1021
01:19:36,740 --> 01:19:40,840
كما طريقك لمتابعة ما كنت لا تزال بحاجة العقد للزيارة،

1022
01:19:40,840 --> 01:19:45,430
الآن لديك لاستخدام قائمة مرتبطة بشكل واضح.

1023
01:19:45,430 --> 01:19:49,070
في كلتا الحالتين كنت تتبع ما العقدة لا تزال بحاجة إلى زيارتها.

1024
01:19:49,070 --> 01:19:51,790
في حالة العودية أنه من الأسهل لمجرد كومة

1025
01:19:51,790 --> 01:19:57,100
وينفذ لك ومكدس البرنامج.

1026
01:19:57,100 --> 01:19:59,550
تلاحظ أن هذه القائمة مرتبطة، بل هو مكدس.

1027
01:19:59,550 --> 01:20:01,580
مهما وضعنا فقط على المكدس

1028
01:20:01,580 --> 01:20:09,960
هو على الفور ما نحن ذاهبون لسحب قبالة كومة لزيارة المقبل.

1029
01:20:09,960 --> 01:20:14,380
نحن في الخارج من الوقت، ولكن أي أسئلة؟

1030
01:20:14,380 --> 01:20:23,530
[طالبة، غير مفهومة]

1031
01:20:23,530 --> 01:20:27,790
[بودين] نعم. إذا كان الأمر كذلك لدينا قائمتنا مرتبط،

1032
01:20:27,790 --> 01:20:30,150
يجري حاليا للإشارة إلى هذا الرجل،

1033
01:20:30,150 --> 01:20:34,690
ونحن الآن تقدم فقط قائمتنا مرتبط إلى التركيز على هذا الرجل.

1034
01:20:34,690 --> 01:20:44,200
نحن العبور على قائمة مرتبطة في هذا الخط.

1035
01:20:44,200 --> 01:20:51,200
ومن ثم أعتقد أننا ينبغي تحرير قائمتنا المرتبطة والاشياء

1036
01:20:51,200 --> 01:20:53,880
مرة واحدة قبل أن يعود صحيحة أو خاطئة، ونحن بحاجة إلى

1037
01:20:53,880 --> 01:20:57,360
تكرار عبر قائمتنا مرتبطة دائما أسفل وهنا، أعتقد،

1038
01:20:57,360 --> 01:21:03,900
إذا كنا الحالي هو حق لا يساوي، إضافته، وحتى الآن نحن نريد لتحرير

1039
01:21:03,900 --> 01:21:09,600
لأن الحالي، حسنا، نحن لم ننسى تماما عن القائمة؟ نعم.

1040
01:21:09,600 --> 01:21:12,880
وهذا ما نريد أن نفعله هنا.

1041
01:21:12,880 --> 01:21:16,730
أين المؤشر؟

1042
01:21:16,730 --> 01:21:23,320
كان الحالي ثم - نحن نريد أن قائمة البنية * 10 يساوي القائمة التالي.

1043
01:21:23,320 --> 01:21:29,240
قائمة حرة، قائمة = TEMP.

1044
01:21:29,240 --> 01:21:32,820
وفي حالة ما إذا نعود صحيح، ونحن بحاجة إلى تكرار

1045
01:21:32,820 --> 01:21:37,050
طوال ما تبقى من قائمتنا المرتبطة تحرير الأشياء.

1046
01:21:37,050 --> 01:21:39,700
والشيء الجميل في حل العودية وتحرير الأشياء

1047
01:21:39,700 --> 01:21:44,930
يعني فقط factorings ظهرت قبالة كومة الذي سيحدث لك.

1048
01:21:44,930 --> 01:21:50,720
حتى لقد ذهبنا من شيء مثل 3 خطوط من يصعب التفكير حول رمز

1049
01:21:50,720 --> 01:21:57,520
إلى ما هو أكثر بكثير كثير يصعب التفكير حول الأسطر من التعليمات البرمجية.

1050
01:21:57,520 --> 01:22:00,620
أي أسئلة أخرى؟

1051
01:22:00,620 --> 01:22:08,760
حسنا. نحن في حالة جيدة. وداعا!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]