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
من به معنای واقعی کلمه فقط برای انجام یک محاسبه ساده ریاضی داشته باشد،

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 و 3 پدر و مادر از 6 است. به آن بسیار نیست.

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
با قلم و کاغذ و یا در این مورد، iPad و قلم.

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
رفتن به پوشه My 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
یک گره درخت باینری حاوی مقادیر نوع int -

381
00:29:03,080 --> 00:29:07,110
درست مثل ارزش هایی که ما را در رسم نمودار ما قبل را به خود جلب کرد.

382
00:29:07,110 --> 00:29:11,740
ما در حال رفتن به استفاده از این boilerplate 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
برای انجام این کار، اجازه دهید فقط با نوشتن boilerplate شروع.

395
00:30:20,070 --> 00:30:23,840
ما می دانیم که ما باید یک مقدار عدد صحیح،

396
00:30:23,840 --> 00:30:32,170
بنابراین ما باید در ارزش داده int قرار داده است، و پس از آن به جای داشتن فقط یک اشاره گر به عنصر بعدی -

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 []) -

415
00:32:00,450 --> 00:32:10,640
و من قصد دارم برای شروع به اعلام آرایه ی argv من به عنوان ثابت به طوری که من می دانم

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
خوب در هر صورت. این خوب است برای ترک آن به عنوان - حذف توایع اگر شما می خواهم.

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
من برای اولین بار نیاز به تخصیص حافظه برای آن.

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
من می خواهم که قادر به گرفتن این فایل C، آن را کامپایل بر روی لوازم خانگی،

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
اندازه یک int و یا به اندازه یک اشاره گر -

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 سه - راست _child = NULL؛ نیز هست.

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
با یک نمونه حاوی بولی (ارزش بین المللی).

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
این امر دقیقا مانند مراجعه به که ما با دست فقط کمی از iPad پیش می شود.

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
بنابراین، بولی شامل (ارزش بین المللی).

498
00:39:55,960 --> 00:40:00,330
وجود دارد بروید. اعلامیه boilerplate ما وجود دارد.

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
است که در فایل هدر بولی استاندارد گنجانده شده است.

511
00:40:45,750 --> 00:40:53,250
ما قطعا می خواهید به bool.h استاندارد برای نوع بولی،

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
بنابراین، گره * N = malloc (sizeof (گره))؛ N -> ارزش = ارزش؛

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
ما شده ایم punting که برای هر چیز دیگری در کد

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 یا بازتخصیص داخل -

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)؛ گره * 8 = 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، پس نه -> left_child = هشت؛

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
حالا اجازه دهید به مدت 5، 8، و 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
از ما می خواهد برای نوشتن یک تابع به نام درج - دوباره، بازگشت بولی

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
باز هم، آن را برای رفتن به درج بولی نامیده می شود (ارزش بین المللی).

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
بنابراین، اگر (n = تهی)، و سپس -

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
و به جای آن از 6، 10، و 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 C -

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
در عوض، درست در اینجا، ما هم می تواند کار دیگری اگر دیگری،

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]