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
מלבד struct הולך להיות שני מצביעים.

15
00:00:47,910 --> 00:00:51,390
יש עצי trinary, שהולכים להיות שלשות,

16
00:00:51,390 --> 00:00:56,540
יש עצי N-ארי, שפשוט יש להם מצביע גנרי

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
"צייר תרשים תיבות-and-חצים של צומת בעץ בינארי

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
פסק זו היא calle 'השורש' של העץ.

39
00:02:15,980 --> 00:02:18,320
לבנות על התרשים שלך מקודם או לצייר אחד חדש

40
00:02:18,320 --> 00:02:21,690
כזה שיש לך תיאור תיבות-and-חצים של עץ בינארי

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, וזה בתחילה מצביע null.

50
00:02:57,140 --> 00:02:59,190
אני פשוט אשים את נ

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
מה לא בסדר אם אני - בא נראה אם ​​אני יכול לבוא עם הסדר.

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
אבל אם יש לי n מספרי סך הכל, אזי הסכום שיכול ללכת לשמאל

180
00:12:15,090 --> 00:12:18,820
בתוספת הסכום שיכול ללכת לימין הוא n - 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
יש לי לשרטט מחדש את העץ שהיינו לנו לפני; שייקח 2.

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
"קודם כול צריכים הגדרת סוג חדשה לצומת בעץ בינארי שמכיל ערכי int.

236
00:16:19,170 --> 00:16:21,400
שימוש boilerplate 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
אז בואו נשים boilerplate כאן,

240
00:16:30,380 --> 00:16:41,630
צומת typedef struct, וצומת. כן, בסדר.

241
00:16:41,630 --> 00:16:44,270
אז מה הם את השדות שאנחנו הולכים רוצים בצומת שלנו?

242
00:16:44,270 --> 00:16:46,520
[סטודנטים] Int ולאחר מכן שני מצביעים?

243
00:16:46,520 --> 00:16:49,700
>> Int ערך, שני מצביעים? כיצד תאכל לכתוב את המצביעים?

244
00:16:49,700 --> 00:16:58,440
[סטודנטים] struct. >> אני צריך להתמקד פנימה כן, אז struct צומת * עזבה,

245
00:16:58,440 --> 00:17:01,320
וstruct צומת * נכון.

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
אתה צריך כל מה שיש על מנת להגדיר struct רקורסיבית זה.

250
00:17:25,000 --> 00:17:27,970
אוקיי, אז זה מה שהעץ שלנו הולך להיראות.

251
00:17:27,970 --> 00:17:37,670
אם הייתי עושה כך עץ trinary, אז צומת עשויה להיראות כמו B1, B2, B3 * struct צומת,

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
[סטודנטים] כשאתה מגדיר struct, הם דברים כמו אותחל לכל דבר?

279
00:20:44,410 --> 00:20:47,160
[אודן] מס >> אוקיי. אז היית צריך לאתחל -

280
00:20:47,160 --> 00:20:50,450
[אודן] מס כשאתה מגדיר, או כאשר אתה מצהיר על struct,

281
00:20:50,450 --> 00:20:55,600
זה אינו מאותחל כברירת מחדל; זה בדיוק כמו אם תכריז int.

282
00:20:55,600 --> 00:20:59,020
זה בדיוק אותו הדבר. זה כמו כל אחד מהתחומים הבודדים שלה

283
00:20:59,020 --> 00:21:04,460
יכול להיות בעל ערך באשפתו. >> והאם ניתן להגדיר - או להכריז struct

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
סדר הטיעונים שמגיע בstruct,

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, null, null.

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
באמת צריך לדעת את הסדר של struct,

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 היא על של ג

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 char,

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
* Char, 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
[סטודנטים] אני לא צריך dereference זה? >> כן.

324
00:23:52,170 --> 00:23:55,110
זכור שיש חץ dereference משתמע,

325
00:23:55,110 --> 00:23:58,230
ולכן כאשר אנחנו עוסקים רק בstruct,

326
00:23:58,230 --> 00:24:04,300
אנחנו רוצים להשתמש. כדי לקבל בבתוך שדה של struct.

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
כל אמצעי החץ, dereference זה, עכשיו אני בstruct, ואני יכול לקבל את השטח.

331
00:24:24,600 --> 00:24:28,040
או שיזיז את השדה באופן ישיר או dereference ולקבל את השדה -

332
00:24:28,040 --> 00:24:30,380
אני מניח שזה צריך להיות ערך.

333
00:24:30,380 --> 00:24:33,910
אבל כאן אני מתמודד עם רק struct, לא מצביע ל struct,

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
וזה דומה במקצת לממשקי API שאנו מספקים לאפמן קידוד.

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
וכאן אנחנו צריכים להחזיר null.

385
00:28:49,550 --> 00:28:52,690
כולם מסכימים על כך לתפקוד צמתים לבנות?

386
00:28:52,690 --> 00:28:59,780
אז עכשיו אנחנו יכולים פשוט לקרוא לזה לבנות בכל צומת עם ערך נתון ומצביעי null.

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 נכשלה, זה יחזיר null.

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
[סטודנטים] האם שווא שווה ל null גם?

403
00:30:46,680 --> 00:30:51,290
[אודן] כל ערך אפס הוא שקרי.

404
00:30:51,290 --> 00:30:53,920
אז null הוא ערך אפס.

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
שורש אז צומת או x צומת.

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
אז מכיוון שמדובר בstruct, כל השדות של struct יהיה אפס ערכים.

424
00:32:21,070 --> 00:32:24,410
למרות שאנחנו לא צריכים להשתמש בזה כאן,.

425
00:32:24,410 --> 00:32:27,320
[סטודנטים] בstructs שונה ממשתנים אחרים, ושאר המשתנים

426
00:32:27,320 --> 00:32:31,400
ערכי אשפה, אלו הם אפסים?

427
00:32:31,400 --> 00:32:36,220
[אודן] ערכים אחרים. אז בX, X יהיה אפס.

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 מכיל ערך int. "

434
00:33:04,930 --> 00:33:08,340
אנחנו לא הולכים לעשות bool מכיל ערך int.

435
00:33:08,340 --> 00:33:15,110
אב הטיפוס שלנו הולך להיראות כמו

436
00:33:15,110 --> 00:33:22,380
bool מכיל (ערך int.

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
כי אם רק יש לנו מכיל ערך int, אז אין לנו דרך של recursing את עצי משנה.

451
00:34:19,750 --> 00:34:24,130
היינו צריכים להיות פונקציה נפרדת שעוזרים הרקורסיה את עצי המשנה עבורנו.

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
[סטודנטים] בטח. אז אני מגדיר משתנה זמני כדי לקבל את הצומת הראשונה של העץ.

462
00:35:25,780 --> 00:35:28,330
ואז אני פשוט התפתלתי בעת טמפ אינו null שווה,

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
[סטודנטים] בטח. אז אנחנו מוודאים שהעץ אינו null ראשון,

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
וכאן מקרה הבסיס בו עץ אינו שווה null

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
עץ שבות אינו null שווה וכל זה.

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
אם העץ עושה null שווה, וזה במקרה הרע,

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
או אם העץ עושה null שווה, אז אנחנו לא הולכים לעשות את ערך == ערך עץ.

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
אז אם העץ עושה null שווה, תנאי שני זה הולך אשמת צינוק,

547
00:42:25,860 --> 00:42:32,510
בגלל עצים> ערך ביטול הפנית null.

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, שם תרצו, הוא null העץ?

554
00:43:06,770 --> 00:43:11,780
אוקיי, זה לא ריק, כך שעכשיו הוא ערך העץ שווה ערך? לעשות את זה.

555
00:43:11,780 --> 00:43:17,300
במקום זאת, זה מצב, זה לעולם לא צינוק אשמה

556
00:43:17,300 --> 00:43:21,220
כי זה יהיה לפרוץ אם זה קורה להיות אפס.

557
00:43:21,220 --> 00:43:24,000
ובכן, אני מניח שאם העץ שלך הוא מצביע לחלוטין לא חוקי, הוא עדיין יכול צינוק אשמה,

558
00:43:24,000 --> 00:43:26,620
אבל זה לא יכול צינוק אשמה אם העץ הוא ריק.

559
00:43:26,620 --> 00:43:32,900
אם זה היה ריק, היא הייתה פורצת לפני שאתה בכלל dereferenced המצביע במקום הראשון.

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
אם אני אומר שאני רוצה את המספר 10, אז אני יכול להעריך עד המספר 10.

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 (ערך int).

599
00:46:10,470 --> 00:46:23,850
אנחנו הולכים לשנות את זה כדי להכניס bool (int ערך, צומת * עץ).

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
אני אשנה לשחור - אני אהיה החדרת 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
איפה אני בנוי העץ בינארי שבו היה נכון

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
אני הושחלתי דרך העץ ערוך את

639
00:49:28,070 --> 00:49:31,360
עד שהגעתי לצומת שהצביעה על null.

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
[סטודנטים] אם זמני הוא ריק? >> כן. אז איך אתה לפרוץ את הלולאה הוא אם זמני הוא ריקה.

651
00:50:22,100 --> 00:50:30,220
אבל מה אני עושה כאן?

652
00:50:30,220 --> 00:50:35,410
אני טמפ dereference, שהוא בהכרח בטל.

653
00:50:35,410 --> 00:50:39,840
אז הדבר השני שאתה צריך לעשות הוא לא רק לעקוב עד טמפ הוא ריק,

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 = זכות זמנית.

659
00:51:03,950 --> 00:51:07,910
אבל לפני שאנחנו עושים את זה, הורה = זמני.

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
עכשיו זמני הוא אפס, אבל נקודתי הורה להורה של הדבר שהוא ריק.

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
אנחנו כמעט מצפים לך להשתמש 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
איך זה iterating על דברים,

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
טוב, עכשיו זה נקודות לnull.

708
00:54:33,340 --> 00:54:38,130
מה שאני רוצה לעשות הוא לתפעל את הסמן לנקודה זו לא null.

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
אני רק יכול לעקוב כדי לראות אם המצביע מצביע על null,

713
00:54:52,640 --> 00:54:54,580
ואם המצביע מצביע על null,

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
זה שונה מלהיות null העץ שלך.

726
00:55:40,460 --> 00:55:44,510
זה מצביע למצביע השורש שלך להיות null

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
הוא אי - אם *, המצביע האדום שלי, הוא אי פעם null,

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 יהיה רק ​​צומת * n = build_node (ערך)

758
00:57:56,490 --> 00:58:07,300
אז n, אם n = 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
במקום לומר n, אנחנו אומרים * אם עץ = עץ *.

763
00:58:30,660 --> 00:58:35,450
כולם מבינים את זה? שעל ידי התמודדות עם מצביעים למצביעים,

764
00:58:35,450 --> 00:58:40,750
אנחנו יכולים לשנות את מצביעי null להצביע על דברים שאנחנו רוצים שהם יצביעו.

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
Dereference פעמים נשמע טוב.

780
00:59:48,800 --> 00:59:51,010
מה אני - איך אני עושה את זה?

781
00:59:51,010 --> 00:59:53,210
[סטודנטים] Dereference פעם אחת, ולאחר מכן חץ לעשות ככה?

782
00:59:53,210 --> 00:59:58,420
[אודן] אז (* עץ) הוא dereference פעם אחת, -> ערך

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
אני חושב שהוא מכיר - GCC וקלאנג

847
01:05:09,350 --> 01:05:12,610
גם יש משמעויות שונות לרמות אופטימיזציה שלהם.

848
01:05:12,610 --> 01:05:17,870
אני רוצה לומר שזה DashO 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
אבל כן, אני חושב שזה DashO 2, כי

853
01:05:37,140 --> 01:05:40,580
אם אתה לקמפל עם DashO 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
ועכשיו הלולאה בזמן שלנו הולכת להיות בזמן נוכ * לא null שווה.

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
אז * זמני הוא זכות הורה, ואנחנו יכולים לשנות אותו ישירות.

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
למה אני צריך את הדגל הזה בימין int?

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
בואי - יחד, אני מניח, אנסה לכתוב מכיל פונקציה

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
ברור שאני נתקלתי בבעיה שבה אני כבר נטשתי את הכל לחלוטין -

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
struct רשימה, צומת * n, ולאחר מכן צומת ** הבא?

946
01:13:32,360 --> 01:13:40,240
אני חושב שזה עובד בסדר.

947
01:13:40,240 --> 01:13:45,940
אנחנו רוצים ללכת על צד השמאל, או בואי - עד כאן.

948
01:13:45,940 --> 01:13:54,350
= רשימת רשימת struct, זה יתחיל

949
01:13:54,350 --> 01:13:58,170
יצא ברשימת struct זה.

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
אנחנו מתכוונים להמשיך בצד ימין בתוך רשימת struct שלנו.

955
01:14:26,140 --> 01:14:32,620
אז יהיה לנו new_list או struct,

956
01:14:32,620 --> 01:14:41,080
struct רשימה *, 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
הו, זו הסיבה שאני רוצה אותו כאן. זה הולך להצביע לרשימת struct 2.

960
01:14:56,890 --> 01:15:02,380
זה רק איך שמקושר לרשימות.

961
01:15:02,380 --> 01:15:04,810
זה אותו הדבר כמו רשימה מקושרת int

962
01:15:04,810 --> 01:15:06,960
למעט אנחנו רק החלפה עם int * צומת.

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
אז רשימה-> n יהיה העץ שלנו.

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
אז נוכ הולך שווה רשימה-> n.

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
נוכ כי, ובכן, האם אנחנו שוכחים לגמרי מהרשימה? Yeah.

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
ס היה אז - אנחנו רוצים struct רשימה * 10 שווי רשימה הבאה.

1043
01:21:23,320 --> 01:21:29,240
רשימה חינם, רשימה = זמני.

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]