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
דברים זכרו, 2 ממש טובים על מערך זה

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
ואז מצביע null ב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 ומצביעי ילד null.

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
עם מצביעי שמאל וימין ילד null -

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
כדי לעשות את זה, אני הולך למחוק שמצביע null ב3-הצומת

137
00:09:41,850 --> 00:09:47,750
ותמלכד אותה כדי להצביע על הצומת המכילה 6. אוקיי.

138
00:09:47,750 --> 00:09:53,800
>> בשלב זה, בואו נלך על קצת טרמינולוגיה.

139
00:09:53,800 --> 00:09:58,230
כדי להתחיל, מהסיבה שזה נקרא עץ בינארי בפרט

140
00:09:58,230 --> 00:10:00,460
הוא כי יש שני מצביעי ילד.

141
00:10:00,460 --> 00:10:06,020
ישנם סוגים אחרים של עצים שיש יותר מצביעי ילד.

142
00:10:06,020 --> 00:10:10,930
בפרט, שעשית "ניסיון" בסט הבעיה 5.

143
00:10:10,930 --> 00:10:19,310
תוכל להבחין כי שבניסיון, שהיה 27 מצביעים שונים לילדים שונים -

144
00:10:19,310 --> 00:10:22,410
אחד לכל אחד מ26 האותיות באלפבית האנגלי,

145
00:10:22,410 --> 00:10:25,410
ולאחר מכן 27 לגרש -

146
00:10:25,410 --> 00:10:28,900
לכן, זה דומה לסוג של עץ.

147
00:10:28,900 --> 00:10:34,070
אבל כאן, שכן בינארי זה, יש לנו שני מצביעים היה בן יחיד.

148
00:10:34,070 --> 00:10:37,880
>> בנוסף לצומת השורש הזה שדברנו עליו,

149
00:10:37,880 --> 00:10:41,470
אנחנו גם כבר לזרוק סביב מונח זה 'הילד'.

150
00:10:41,470 --> 00:10:44,470
מה זה אומר לצומת אחד להיות ילד של צומת אחר?

151
00:10:44,470 --> 00:10:54,060
זה פשוטו כמשמעו שצומת ילד היא ילד של צומת אחרת

152
00:10:54,060 --> 00:10:58,760
אם כי הצומת השנייה יש אחד ממצביעי הבנים שלו שנקבעו כדי להצביע שצומת.

153
00:10:58,760 --> 00:11:01,230
כדי לשים את זה במונחים קונקרטיים יותר,

154
00:11:01,230 --> 00:11:11,170
אם 3 הוא הצביעו על ידי אחד ממצביעי הילד של 7, אז 3 הם ילד של 7.

155
00:11:11,170 --> 00:11:14,510
אם היו עלינו להבין מה הם הילדים בגילי 7 -

156
00:11:14,510 --> 00:11:18,510
כן, אנו רואים כי 7 יש מצביע למצביע 3 ועד 9,

157
00:11:18,510 --> 00:11:22,190
כך 9 ו 3 הם ילדיהם של 7.

158
00:11:22,190 --> 00:11:26,650
תשע אין לו ילדים, כי מצביעי הילד שלה הם ריקים,

159
00:11:26,650 --> 00:11:30,940
ו3 יש רק ילד אחד, 6.

160
00:11:30,940 --> 00:11:37,430
שישה גם אין לו ילדים, כי הן של מצביעיה הן אפס, שאנחנו עושים הגרלה עכשיו.

161
00:11:37,430 --> 00:11:45,010
>> בנוסף, אנחנו גם מדברים על ההורים של צומת מסוימת,

162
00:11:45,010 --> 00:11:51,100
וזה, כפי שהיית מצפה, היפוכו של תיאור הילד הזה.

163
00:11:51,100 --> 00:11:58,620
כל צומת יש הורה אחד בלבד - במקום שניים כפי שהיה אפשר לצפות לו עם בני אדם.

164
00:11:58,620 --> 00:12:03,390
לדוגמה, ההורה של 3 הוא 7.

165
00:12:03,390 --> 00:12:10,800
ההורה של 9 הוא גם 7, וההורה של 6 הוא 3. לא הרבה אליו.

166
00:12:10,800 --> 00:12:15,720
יש לנו גם מבחינת לדבר על סבים ונכדים,

167
00:12:15,720 --> 00:12:18,210
ובאופן כללי אנחנו מדברים על האבות

168
00:12:18,210 --> 00:12:20,960
וצאצאיו של צומת מסוימת.

169
00:12:20,960 --> 00:12:25,710
אב הקדמון של צומת - או אבות, אלא מצומת -

170
00:12:25,710 --> 00:12:32,730
הם כל צומת הנמצאים בדרך מהשורש עד שהצומת.

171
00:12:32,730 --> 00:12:36,640
לדוגמה, אם אני מסתכל על 6 הצומת,

172
00:12:36,640 --> 00:12:46,430
אז האבות הולכים להיות גם 3 ו 7.

173
00:12:46,430 --> 00:12:55,310
אבותיהם של 9, למשל, הם - אם אני מסתכל על 9 הצומת -

174
00:12:55,310 --> 00:12:59,990
אז האב הקדמון של 9 הוא רק 7.

175
00:12:59,990 --> 00:13:01,940
וצאצאים הם בדיוק הפוכים.

176
00:13:01,940 --> 00:13:05,430
אם אני רוצה להסתכל על כל צאצאיו של 7,

177
00:13:05,430 --> 00:13:11,020
אז יש לי להסתכל על כל צומת שמתחתיו.

178
00:13:11,020 --> 00:13:16,950
לכן, יש לי 3, 9, ו 6 הכל כצאצאים של 7.

179
00:13:16,950 --> 00:13:24,170
>> הטווח הסופי שנדברנו על זה רעיון של להיות אח.

180
00:13:24,170 --> 00:13:27,980
אחים - סוג של לאחר יחד בתנאי - המשפחה

181
00:13:27,980 --> 00:13:33,150
הם בלוטות שנמצאות באותה הרמה בעץ.

182
00:13:33,150 --> 00:13:42,230
אז, 3 ו 9 הם אחים כי הם נמצאים באותה הרמה בעץ.

183
00:13:42,230 --> 00:13:46,190
לשניהם יש את אותו הורה, 7.

184
00:13:46,190 --> 00:13:51,400
6 אין אחים כי 9 לא היו לו ילדים.

185
00:13:51,400 --> 00:13:55,540
ו 7 אין שום אחים כי זה השורש של העץ שלנו,

186
00:13:55,540 --> 00:13:59,010
ויש רק פעם 1 שורש.

187
00:13:59,010 --> 00:14:02,260
7 ב ליש אחים שם היה צריך להיות צומת מעל 7.

188
00:14:02,260 --> 00:14:07,480
יהיה צורך בלהיות הורה של 7, ובמקרה זה 7 כבר לא יהיה השורש של העץ.

189
00:14:07,480 --> 00:14:10,480
ואז שההורה החדש של 7 היה צריך גם להביא ילד לעולם,

190
00:14:10,480 --> 00:14:16,480
והילד שהיה אז להיות האח של 7.

191
00:14:16,480 --> 00:14:21,040
>> אוקיי. ימשיך הלאה.

192
00:14:21,040 --> 00:14:24,930
כשהתחלנו הדיון בעצים בינאריים שלנו,

193
00:14:24,930 --> 00:14:28,790
דברנו על איך שאנחנו הולכים להשתמש בם כדי

194
00:14:28,790 --> 00:14:32,800
לזכות ביתרון על שני מערכים ורשימות מקושרות.

195
00:14:32,800 --> 00:14:37,220
והדרך שאנחנו הולכים לעשות את זה הוא ברכוש הזמנה זו.

196
00:14:37,220 --> 00:14:41,080
אנחנו אומרים שעץ בינארי הוא הורה, בהתאם למפרט,

197
00:14:41,080 --> 00:14:45,740
אם לכל צומת בעץ שלנו, כל צאצאיה בצד השמאל -

198
00:14:45,740 --> 00:14:48,670
הילד השמאלי וכל צאצאיו של הילד השמאלי -

199
00:14:48,670 --> 00:14:54,510
יש ערכים פחותים, וכל צומת בימין -

200
00:14:54,510 --> 00:14:57,770
הילד הימני וכל צאצאיו של ילד הזכות -

201
00:14:57,770 --> 00:15:02,800
יש צומת גדולים מהערך של הצומת הנוכחית שאנחנו מסתכלים.

202
00:15:02,800 --> 00:15:07,850
רק לשם פשטות, אנחנו הולכים להניח שאין שום צומת כפולים בעץ שלנו.

203
00:15:07,850 --> 00:15:11,180
לדוגמה, בעץ הזה אנחנו לא מתכוונים להתמודד עם המקרה

204
00:15:11,180 --> 00:15:13,680
שם יש לנו את הערך 7 בשורש

205
00:15:13,680 --> 00:15:16,720
 ואז יש לנו גם את הערך 7 במקום אחר בעץ.

206
00:15:16,720 --> 00:15:24,390
במקרה זה, תוכל להבחין כי העץ הזה הוא הורה אכן.

207
00:15:24,390 --> 00:15:26,510
יש לנו את הערך 7 בשורש.

208
00:15:26,510 --> 00:15:29,720
כל מה שמהשמאל ל7 -

209
00:15:29,720 --> 00:15:35,310
אם אני לבטל את כל הסימנים הקטנים האלה כאן -

210
00:15:35,310 --> 00:15:40,450
כל מה שמהשמאל ל7 - 3 ו - 6

211
00:15:40,450 --> 00:15:49,410
ערכים אלה הם פחות מ 7, והכילו לימין - שהוא פשוט זה 9 -

212
00:15:49,410 --> 00:15:53,450
גדול מ 7.

213
00:15:53,450 --> 00:15:58,650
>> זה לא רק עץ ההורה המכיל את הערכים הללו,

214
00:15:58,650 --> 00:16:03,120
אבל בואו נצייר עוד כמה מהם.

215
00:16:03,120 --> 00:16:05,030
יש למעשה חבורה שלמה של דרכים שאנחנו יכולים לעשות את זה.

216
00:16:05,030 --> 00:16:09,380
אני הולך להשתמש בקצרנות, רק כדי לשמור על דברים פשוטים שבו -

217
00:16:09,380 --> 00:16:11,520
לא ציור את כל תיבות-and-חצים -

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, הופ 2 כדי להגיע ל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
אני מציע תרגול הציור מתוך התרשימים האלה אחד על 1

357
00:27:19,450 --> 00:27:21,910
ובעקבות דרך כל השלבים השונים,

358
00:27:21,910 --> 00:27:25,060
כי זה יבוא בסופר שימושי

359
00:27:25,060 --> 00:27:27,480
לא רק כשאתה עושה את ערכת בעית קידוד האפמן

360
00:27:27,480 --> 00:27:29,390
אלא גם בקורסים עתידיים -

361
00:27:29,390 --> 00:27:32,220
רק לומד איך לצייר את מבני הנתונים האלה ולחשוב דרך הבעיות

362
00:27:32,220 --> 00:27:38,000
עם עט ונייר, או, במקרה זה, אייפד וחרט.

363
00:27:38,000 --> 00:27:41,000
>> בשלב זה אם כי, אנחנו הולכים לעבור על מנת לעשות קצת תרגול קידוד

364
00:27:41,000 --> 00:27:44,870
וממש לשחק עם עצים בינאריים אלה ולראות.

365
00:27:44,870 --> 00:27:52,150
אני הולך לעבור בחזרה אל המחשב שלי.

366
00:27:52,150 --> 00:27:58,480
לחלק זה של הסעיף, במקום להשתמש CS50 הפעלה או CS50 Spaces,

367
00:27:58,480 --> 00:28:01,500
אני הולך להשתמש במכשיר.

368
00:28:01,500 --> 00:28:04,950
>> בעקבות יחד עם מפרט גדר הבעיה,

369
00:28:04,950 --> 00:28:07,740
אני רואה שאני אמור לפתוח את המכשיר,

370
00:28:07,740 --> 00:28:11,020
ללכת לתיקיית ה-Dropbox שלי, ליצור תיקייה בשם הסעיף 7,

371
00:28:11,020 --> 00:28:15,730
ולאחר מכן ליצור קובץ בשם binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
הנה אנחנו מתחילים. יש לי את המכשיר כבר פתוח.

373
00:28:22,050 --> 00:28:25,910
אני הולך למשוך את מסוף.

374
00:28:25,910 --> 00:28:38,250
אני הולך לתיקיית Dropbox, להפוך את ספרייה בשם section7,

375
00:28:38,250 --> 00:28:42,230
ותראה את זה לגמרי ריק.

376
00:28:42,230 --> 00:28:48,860
עכשיו אני הולך לפתוח binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
אוקיי. הנה אנחנו מתחילים - קובץ ריק.

378
00:28:51,750 --> 00:28:54,330
>> בואו נחזור למפרט.

379
00:28:54,330 --> 00:28:59,850
המפרט מבקש ליצור הגדרת סוג חדשה

380
00:28:59,850 --> 00:29:03,080
לצומת בעץ בינארי שמכיל ערכי 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 struct של צומת,

388
00:29:27,870 --> 00:29:34,430
ואנחנו נתנו לי צומת struct זה שמו של צומת struct זה מראש

389
00:29:34,430 --> 00:29:39,350
כדי שאז תוכל להתייחס אליו מאז שנרצה שיהיה לי מצביעי צומת struct

390
00:29:39,350 --> 00:29:45,740
כחלק מstruct שלנו, אבל אז אנחנו כבר הקפנו זה -

391
00:29:45,740 --> 00:29:47,700
או לייתר דיוק, זה סגור - בtypedef

392
00:29:47,700 --> 00:29:54,600
כך, מאוחר יותר בקוד, אנו יכולים להתייחס לזה כפשוט struct צומת במקום צומת struct.

393
00:29:54,600 --> 00:30:03,120
>> זה הולך להיות מאוד דומה להגדרת רשימת ביחידים הצמודה שראינו בשבוע שעבר.

394
00:30:03,120 --> 00:30:20,070
לשם כך, בואו נתחיל על ידי כתיבת הטקסט הסטנדרטי.

395
00:30:20,070 --> 00:30:23,840
אנחנו יודעים שאנחנו צריכים שנהיה לי ערך שלם,

396
00:30:23,840 --> 00:30:32,170
כן אנעל את ערך 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
זה די פשוט מדי - צומת ילד struct * שמאל;

400
00:30:42,880 --> 00:30:51,190
וצומת * ילד struct נכון;. מגניב.

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
רק כדי לוודא שאני לא אעזוב את זה שלא אותחל, אני הולך להגדיר אותו שווה ל null.

413
00:31:46,770 --> 00:31:52,210
כעת, בתפקידו העיקרי - שאנחנו באמת לכתוב במהירות ממש כאן -

414
00:31:52,210 --> 00:32:00,450
int הראשי (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
ואני הולך להתחיל להכריז מערך argv כconst רק כדי שאדע

416
00:32:10,640 --> 00:32:14,550
שהטיעונים האלה הם טיעונים שאני כנראה לא רוצה לשנות.

417
00:32:14,550 --> 00:32:18,390
אם אני רוצה לשנות אותם אני כנראה צריך להיות יצירת עותקים שלהם.

418
00:32:18,390 --> 00:32:21,740
אתה תראה את זה הרבה בקוד.

419
00:32:21,740 --> 00:32:25,440
זה בסדר בכל המקרה. זה בסדר להשאיר אותו כ-- להשמיט const אם תרצה.

420
00:32:25,440 --> 00:32:28,630
אני בדרך כלל לשים את זה רק כדי שאני מזכיר לעצמי

421
00:32:28,630 --> 00:32:33,650
 כי מן הסתם אני לא רוצה לשנות את הטיעונים הללו.

422
00:32:33,650 --> 00:32:39,240
>> כמו תמיד, אני הולך לכולל 0 קו תמורה זו בסופו של ראשי.

423
00:32:39,240 --> 00:32:45,730
הנה, אני יהיה לאתחל צומת השורש שלי.

424
00:32:45,730 --> 00:32:48,900
כפי שהיא עומדת עכשיו, יש לי מצביע אשר מוגדר לnull,

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-bit -

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 בניגוד לסיכום שדות struct באופן ידני.

443
00:34:15,030 --> 00:34:20,500
הסיבה האחרת היא שיש גם עשויה להיות ריפוד שהמהדר מכניס struct.

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
ועכשיו אני הולך להגדיר את הילד השמאלי להיות null

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; 3 -> זכות _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
ולוודא שאני - בסדר.

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
הסיבה שאותחלתי כל המצביעים לnull היא רק כדי שאוכל לוודא כי

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
בטוח שכל הערכים null נמצאים שם במקומות המתאימים.

479
00:38:08,240 --> 00:38:15,630
>> החל בשורש, אני יודע שהילד השמאלי של השורש הוא 3.

480
00:38:15,630 --> 00:38:21,250
אני יודע שהילד הימני של השורש הוא 9.

481
00:38:21,250 --> 00:38:24,880
אחרי זה, הילד היחיד שנשאר לי מה לדאוג

482
00:38:24,880 --> 00:38:39,080
הילד הוא זכותה של 3, שעומד על 6.

483
00:38:39,080 --> 00:38:44,670
בשלב זה, את כל זה נראה די טוב.

484
00:38:44,670 --> 00:38:54,210
אנו מחקנו חלק מהקווים הללו.

485
00:38:54,210 --> 00:38:59,540
עכשיו הכל נראה די טוב.

486
00:38:59,540 --> 00:39:04,240
בואו נחזור למפרט שלנו ולראות מה אנחנו צריכים לעשות הלאה.

487
00:39:04,240 --> 00:39:07,610
>> בנקודה זו, יש לנו לכתוב פונקציה שנקראת 'מכילה'

488
00:39:07,610 --> 00:39:14,150
עם אב טיפוס של "כולל bool (int ערך) '.

489
00:39:14,150 --> 00:39:17,060
וזה מכיל פונקציה הולכת להחזר אמיתי

490
00:39:17,060 --> 00:39:21,200
 אם העץ שאליו מצביע משתנה השורש הגלובלי שלנו

491
00:39:21,200 --> 00:39:26,950
 מכיל את הערך העביר לפונקציה ושקר אחר.

492
00:39:26,950 --> 00:39:29,000
בואו נלך קדימה ולעשות את זה.

493
00:39:29,000 --> 00:39:35,380
זה הולך להיות בדיוק כמו הבדיקה שעשינו ביד על האייפד רק קצת לפני.

494
00:39:35,380 --> 00:39:40,130
בואו נחזור להתמקד במעט ולגלול למעלה.

495
00:39:40,130 --> 00:39:43,130
אנחנו הולכים לשים את הפונקציה הזו בדיוק מעל הפונקציה העיקרית שלנו

496
00:39:43,130 --> 00:39:48,990
כך שאין לנו לעשות כל סוג של אב טיפוס.

497
00:39:48,990 --> 00:39:55,960
אז, bool מכיל (int ערך).

498
00:39:55,960 --> 00:40:00,330
הנה. יש ההצהרה המוכנה מראש שלנו.

499
00:40:00,330 --> 00:40:02,900
רק כדי לוודא שזה יהיה לקמפל,

500
00:40:02,900 --> 00:40:06,820
אני הולך קדימה ופשוט להגדיר אותו שווה לתמורת שווא.

501
00:40:06,820 --> 00:40:09,980
כרגע פונקציה זו פשוט לא לעשות כלום ותמיד מדווחת כי

502
00:40:09,980 --> 00:40:14,010
הערך שאנחנו מחפשים הוא לא בעץ.

503
00:40:14,010 --> 00:40:16,280
>> בשלב זה, זה כנראה רעיון טוב -

504
00:40:16,280 --> 00:40:19,600
מאז שנכתבנו חבורה שלמה של קוד, ואנחנו אפילו לא ניסינו לבדוק את זה עדיין -

505
00:40:19,600 --> 00:40:22,590
כדי לוודא שכל הידור.

506
00:40:22,590 --> 00:40:27,460
יש כמה דברים שאנחנו צריכים לעשות כדי לוודא שזה יהיה ממש לקמפל.

507
00:40:27,460 --> 00:40:33,530
ראשית, לראות אם אנחנו כבר משתמשים בכל פונקציות בכל ספריות שלא נכללו עדיין.

508
00:40:33,530 --> 00:40:37,940
הפונקציות שבם השתמשו עד כה הם malloc,

509
00:40:37,940 --> 00:40:43,310
ואז גם אנחנו משתמשים בסוג זה - הסוג לא הסטנדרטי הזה שנקרא 'bool' -

510
00:40:43,310 --> 00:40:45,750
הנכלל בקובץ כותרת bool הסטנדרטי.

511
00:40:45,750 --> 00:40:53,250
אנחנו בהחלט רוצים לכלול bool.h הסטנדרטי לסוג bool,

512
00:40:53,250 --> 00:40:59,230
ואנחנו גם רוצים # לכלול lib.h הסטנדרטי לספריות הסטנדרטיות

513
00:40:59,230 --> 00:41:03,530
שכולל malloc, וללא תשלום, וכל זה.

514
00:41:03,530 --> 00:41:08,660
לכן, להתרחק, אנחנו מתכוונים לפרוש.

515
00:41:08,660 --> 00:41:14,190
בואו ננסה ולוודא שזה אכן הידור.

516
00:41:14,190 --> 00:41:18,150
אנו רואים שהוא עושה, אז אנחנו בדרך הנכונה.

517
00:41:18,150 --> 00:41:22,990
>> בואו לפתוח binary_tree.c שוב.

518
00:41:22,990 --> 00:41:34,530
זה הידור. בואו נרד ולוודא שאנחנו נכניס כמה שיחות לפונקציה, מכיל -

519
00:41:34,530 --> 00:41:40,130
רק כדי לוודא שזה כל מה שטוב ויפה.

520
00:41:40,130 --> 00:41:43,170
לדוגמה, כשעשינו כמה חיפושים בעץ שלנו קודם לכן,

521
00:41:43,170 --> 00:41:48,500
ניסינו לחפש את הערכים 6, 10, ו 1, וידע שהיו 6 בעץ,

522
00:41:48,500 --> 00:41:52,220
10 לא היו בעץ, ו1 לא היה בעץ אחד.

523
00:41:52,220 --> 00:41:57,230
הבה נשתמש שיחות לדוגמה אלה כדרך להבין אם או לא

524
00:41:57,230 --> 00:41:59,880
הפונקציה, מכיל עובדת.

525
00:41:59,880 --> 00:42:05,210
כדי לעשות את זה, אני הולך להשתמש בפונקצית printf,

526
00:42:05,210 --> 00:42:10,280
ואנחנו הולכים להדפיס את התוצאה של קריאה למכילה.

527
00:42:10,280 --> 00:42:13,280
אני הולך לשים במחרוזת "מכיל (% d) = בגלל

528
00:42:13,280 --> 00:42:20,470
 אנחנו הולכים לחבר את הערך שאנחנו הולכים לחפש,

529
00:42:20,470 --> 00:42:27,130
ו=% s \ n "ולהשתמש בו כמחרוזת התבנית שלנו.

530
00:42:27,130 --> 00:42:30,720
אנחנו רק הולכים לראות - ממש להדפיס על המסך -

531
00:42:30,720 --> 00:42:32,060
מה שנראה כמו קריאה לפונקציה.

532
00:42:32,060 --> 00:42:33,580
זה לא ממש קריאה לפונקציה.

533
00:42:33,580 --> 00:42:36,760
 זה רק חוט שנועד להיראות כמו קריאה לפונקציה.

534
00:42:36,760 --> 00:42:41,140
>> עכשיו, אנחנו הולכים לחבר את הערכים.

535
00:42:41,140 --> 00:42:43,580
אנחנו הולכים לנסות מכילים על 6,

536
00:42:43,580 --> 00:42:48,340
ואז מה שאנחנו הולכים לעשות כאן הוא משתמשים באותו מפעיל משולש.

537
00:42:48,340 --> 00:42:56,340
בואו נראים - מכיל 6 - כך, עכשיו אני כבר הכלתי 6 ואם מכיל 6 הוא נכון,

538
00:42:56,340 --> 00:43:01,850
המחרוזת שאנחנו הולכים לשלוח לאופי פורמט% s

539
00:43:01,850 --> 00:43:04,850
הולך להיות המחרוזת "האמיתית".

540
00:43:04,850 --> 00:43:07,690
בואו לגלול עליו קצת.

541
00:43:07,690 --> 00:43:16,210
אחרת, אנחנו רוצים לשלוח את המחרוזת "מזויפת" אם מכיל 6 חוזר שווא.

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
אנחנו הולכים לחזר עד נוכ אינו שווה null.

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
אנחנו כבר חתירה על זה גם לכל דבר אחר בקוד

629
00:50:01,270 --> 00:50:02,880
רק לשם פשטות באותה העת,

630
00:50:02,880 --> 00:50:05,610
אבל אם אי פעם לכתוב פונקציה שנראית כך

631
00:50:05,610 --> 00:50:10,370
שם יש לך - חלק קורא לזה malloc או realloc בפנים -

632
00:50:10,370 --> 00:50:14,330
אתה רוצה לוודא שאתה מכניס איזו תגובה כאן שאומר,

633
00:50:14,330 --> 00:50:29,970
היי, אתה יודע, מחזיר צומת ערימה מוקצה אותחלה עם הערך מחוסר הכרה ב.

634
00:50:29,970 --> 00:50:33,600
ואז אתה רוצה לוודא שאתה מכניס איזה פתק שאומר

635
00:50:33,600 --> 00:50:41,720
המתקשר חייב לשחרר הזיכרון חזר.

636
00:50:41,720 --> 00:50:45,450
באופן זה, אם מישהו אי פעם הולך ומשתמש בפונקציה ש,

637
00:50:45,450 --> 00:50:48,150
הם יודעים שכל מה שהם מקבלים בחזרה מהפונקציה

638
00:50:48,150 --> 00:50:50,870
בשלב מסוים יצטרך להיות משוחרר.

639
00:50:50,870 --> 00:50:53,940
>> בהנחה שכל זה טוב ויפה כאן,

640
00:50:53,940 --> 00:51:02,300
אנחנו יכולים לרדת לקוד שלנו ולהחליף את כל שורות אלה ממש כאן

641
00:51:02,300 --> 00:51:05,410
עם קריאות לפונקצית הצומת לבנות שלנו.

642
00:51:05,410 --> 00:51:08,170
בואו לעשות את זה ממש מהר.

643
00:51:08,170 --> 00:51:15,840
חלק האחד שאנחנו לא הולכים להחליף את החלק הזה כאן למטה

644
00:51:15,840 --> 00:51:18,520
בתחתית שבו אנחנו למעשה נמלכד את הבלוטות להצביע לזה,

645
00:51:18,520 --> 00:51:21,030
בגלל שאנחנו לא יכולים לעשות בתפקוד שלנו.

646
00:51:21,030 --> 00:51:37,400
אבל, בואו נעשה שורש = build_node (7); צומת * 3 = build_node (3);

647
00:51:37,400 --> 00:51:47,980
צומת * 6 = build_node (6); צומת * 9 = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
ועכשיו, אנחנו גם רוצים להוסיף לצומת -

649
00:51:52,590 --> 00:52:03,530
צומת * 5 = 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
צומת * 2 = 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
אנו יודעים שזכותה של ילדת 3 היא 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 = 5;

660
00:52:58,650 --> 00:53:10,790
ולאחר מכן 8 שייכים כילד השמאלי של 9, אז 9 -> left_child = 8;

661
00:53:10,790 --> 00:53:22,190
ואז 2 הם הילד השמאלי של 3, כך שאנו יכולים לעשות את זה כאן - -> left_child = 2;.

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
הוא מבקש מאתנו לכתוב פונקציה שנקראת להוסיף - שוב, וחזר bool

677
00:55:00,540 --> 00:55:04,400
לשאלה אם אנחנו באמת יכולים להכניס את הצומת לעץ -

678
00:55:04,400 --> 00:55:07,710
ולאחר מכן הערך להכניס לתוך העץ מוגדר כ

679
00:55:07,710 --> 00:55:11,060
הוויכוח רק להוספת הפונקציה שלנו.

680
00:55:11,060 --> 00:55:18,180
אנחנו נחזור אמיתיים אם אנחנו אכן יכולים להכניס את הערך המכיל צומת לעץ,

681
00:55:18,180 --> 00:55:20,930
מה שאומר שאנחנו, אחד, היו מספיק זיכרון,

682
00:55:20,930 --> 00:55:24,840
ואז שתיים, וצומת שלא קיימת כבר בעץ מאז -

683
00:55:24,840 --> 00:55:32,170
נזכור, אנחנו לא הולכים ליש ערכים כפולים בעץ, רק כדי לעשות את הדברים פשוטים.

684
00:55:32,170 --> 00:55:35,590
אוקיי. בחזרה לקוד.

685
00:55:35,590 --> 00:55:44,240
לפתוח אותו. קרב קצת, ואז גלול למטה.

686
00:55:44,240 --> 00:55:47,220
בואו נשים את פונקציית ההוספה ימנית מעל למכיל.

687
00:55:47,220 --> 00:55:56,360
שוב, זה הולך להיקרא להכניס bool (int ערך).

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
אלא שאנחנו הולכים להיפטר מהקווים האלה - אנחנו נטפל הערה את השורות אלה -

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
מצביע נוכ הולך להיות הצבעה על null

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
אנחנו הולכים להגדיר אותו שווים ל null בתחילה,

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
>> אני חושב שהדבר אחד שאנחנו רוצים לשנות את זה הוא לבנות null צומת חוזרת.

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 = NULL!), אז -

774
01:03:53,390 --> 01:03:55,250
אם malloc חזר מצביע תקף, ואז תוכל לאתחל אותו;

775
01:03:55,250 --> 01:04:02,540
אחרת, אנחנו פשוט נחזור ושיהיו בסופו חוזר ריק עבורנו.

776
01:04:02,540 --> 01:04:13,050
עכשיו כל מה שנראה די טוב. בואו נוודא שזה באמת הידור.

777
01:04:13,050 --> 01:04:22,240
הפכו עץ בינארי, ואוה, יש לנו כמה דברים שקורים כאן.

778
01:04:22,240 --> 01:04:29,230
>> יש לנו הצהרה המרומזת של פונקציה לבנות צומת.

779
01:04:29,230 --> 01:04:31,950
שוב, עם המהדרים האלה, אנחנו הולכים להתחיל בחלק העליון.

780
01:04:31,950 --> 01:04:36,380
מה משמעות של זה הוא שאני מתקשר לבנות צומת לפני שהכרזתי עליו בפועל.

781
01:04:36,380 --> 01:04:37,730
בואו נחזור לקוד ממש מהר.

782
01:04:37,730 --> 01:04:43,510
לגלול למטה, ואכן, הוספת הפונקציה שלי הכריזה

783
01:04:43,510 --> 01:04:47,400
מעל פונקצית הצומת לבנות,

784
01:04:47,400 --> 01:04:50,070
אבל אני מנסה להשתמש לבנות צומת הפנימית של תותב.

785
01:04:50,070 --> 01:05:06,610
אני מתכוון ללכת ובהעתק - ומדביק את דרך תפקוד הצומת לבנות כאן בחלק העליון.

786
01:05:06,610 --> 01:05:11,750
בדרך זו, אני מקווה שזה יעבוד. בואו לתת את זה עוד ללכת.

787
01:05:11,750 --> 01:05:18,920
עכשיו כל זה הידור. כל טוב.

788
01:05:18,920 --> 01:05:21,640
>> אבל בנקודה זו, יש לנו לא ממש קרא הוספת הפונקציה שלנו.

789
01:05:21,640 --> 01:05:26,510
אנחנו רק יודעים שזה הידור, אז בואו נלך ובלשים כמה שיחות פנימה

790
01:05:26,510 --> 01:05:28,240
בואו לעשות את זה בפונקציה העיקרית שלנו.

791
01:05:28,240 --> 01:05:32,390
כאן, הערנו את 5, 8, ו 2,

792
01:05:32,390 --> 01:05:36,680
ואז אנחנו לא נמלכד אותם כאן למטה.

793
01:05:36,680 --> 01:05:41,640
בואו לעשות כמה שיחות כדי להוסיף,

794
01:05:41,640 --> 01:05:46,440
ובואו גם להשתמש באותו סוג של חומר שבו השתמש

795
01:05:46,440 --> 01:05:52,810
כאשר בצענו שיחות printf אלה כדי לוודא שהכל לא מקבל הוכנס כראוי.

796
01:05:52,810 --> 01:06:00,550
אני מתכוון להעתיק ולהדביק,

797
01:06:00,550 --> 01:06:12,450
ובמקום מכיל אנחנו הולכים לעשות להוסיף.

798
01:06:12,450 --> 01:06:30,140
ובמקום 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
Compile. כל טוב. עכשיו אנחנו באמת נרוץ התכנית שלנו.

801
01:06:44,050 --> 01:06:47,330
>> הכל חזר שווא.

802
01:06:47,330 --> 01:06:53,830
אז, 5, ​​8, ו 2 לא הלך, וזה נראה כאילו, מכיל לא מצא אותם.

803
01:06:53,830 --> 01:06:58,890
מה קורה? בואו להקטין את התצוגה.

804
01:06:58,890 --> 01:07:02,160
הבעיה הראשונה הייתה שהוספה נראה לחזור שקר,

805
01:07:02,160 --> 01:07:08,750
וזה נראה כאילו זה בגלל שיצאנו בקריאת שווא חזרתנו,

806
01:07:08,750 --> 01:07:14,590
ואנחנו אף פעם לא ממש חזרנו נכונים.

807
01:07:14,590 --> 01:07:17,880
אנחנו יכולים להגדיר זאת.

808
01:07:17,880 --> 01:07:25,290
הבעיה השנייה היא שעכשיו, גם אם אנחנו עושים - לשמור את זה, תפסיק עם זה,

809
01:07:25,290 --> 01:07:34,530
לרוץ לעשות שוב, יש לו לאסוף, ואז להפעיל אותו -

810
01:07:34,530 --> 01:07:37,670
אנו רואים שמשהו אחר קרה כאן.

811
01:07:37,670 --> 01:07:42,980
5, 8, ו 2 עדיין לא נמצאו בעץ.

812
01:07:42,980 --> 01:07:44,350
אז, מה קורה?

813
01:07:44,350 --> 01:07:45,700
>> בואו נסתכל על זה בקוד.

814
01:07:45,700 --> 01:07:49,790
בואו נראה אם ​​אנחנו יכולים להבין את זה.

815
01:07:49,790 --> 01:07:57,940
אנחנו מתחילים עם ההורה שאינו ריק.

816
01:07:57,940 --> 01:07:59,510
אנו קובעים את המצביע למצביע השווה השורש הנוכחי,

817
01:07:59,510 --> 01:08:04,280
ואנחנו הולכים לעבוד דרכנו במורד העץ.

818
01:08:04,280 --> 01:08:08,650
אם הצומת הנוכחית היא לא ריקה, אז אנחנו יודעים שאנחנו יכולים לעבור אותו קצת.

819
01:08:08,650 --> 01:08:12,330
אנו קובעים המצביע האם שלנו להיות שווה למצביע הנוכחי,

820
01:08:12,330 --> 01:08:15,420
בדקתי את הערך - אם הערכים הזהים חזרנו שווא.

821
01:08:15,420 --> 01:08:17,540
אם הערכים הם פחות עברנו לימין;

822
01:08:17,540 --> 01:08:20,399
אחרת, עברו לצד השמאל.

823
01:08:20,399 --> 01:08:24,220
ואז אנחנו בונים צומת. אני להתקרב קצת.

824
01:08:24,220 --> 01:08:31,410
והנה, אנחנו הולכים לנסות לחווט את הערכים להיות אותו הדבר.

825
01:08:31,410 --> 01:08:37,250
מה קורה? בואו לראות אם אולי Valgrind יכול לתת לנו רמז.

826
01:08:37,250 --> 01:08:43,910
>> אני אוהב להשתמש Valgrind רק בגלל Valgrind ממש מהר ריצות

827
01:08:43,910 --> 01:08:46,729
ואומר לך אם יש שגיאות זיכרון.

828
01:08:46,729 --> 01:08:48,300
כאשר אנו מפעילים Valgrind בקוד,

829
01:08:48,300 --> 01:08:55,859
כפי שאתה יכול לראות את להיט here--Valgrind./binary_tree--and זכות להיכנס.

830
01:08:55,859 --> 01:09:03,640
אתה רואה שלא היה לנו כל שגיאת זיכרון, כך זה נראה כאילו הכול בסדר עד כה.

831
01:09:03,640 --> 01:09:07,529
יש לנו כמה דליפות זיכרון, שאנחנו יודעים, כי אנחנו לא

832
01:09:07,529 --> 01:09:08,910
קורה לשחרור כל צומת שלנו.

833
01:09:08,910 --> 01:09:13,050
בואו ננסה לרוץ GDB כדי לראות מה באמת קורה.

834
01:09:13,050 --> 01:09:20,010
אנחנו נעשה את gdb. / Binary_tree. זה הדליק את בסדר גמור.

835
01:09:20,010 --> 01:09:23,670
בואו נקבענו נקודת הפסקה על הוספה.

836
01:09:23,670 --> 01:09:28,600
בואו לרוץ.

837
01:09:28,600 --> 01:09:31,200
זה נראה כאילו אנחנו מעולם לא קראנו להוסיף בפועל.

838
01:09:31,200 --> 01:09:39,410
זה נראה כמו הבעיה הייתה רק שכשאני השתניתי למטה בעיקרי -

839
01:09:39,410 --> 01:09:44,279
כל השיחות הללו מprintf מכיל -

840
01:09:44,279 --> 01:09:56,430
למעשה, לא השתנה אלה להתקשר להוסיף.

841
01:09:56,430 --> 01:10:01,660
עכשיו בואו לנסות את זה. בואו לקמפל.

842
01:10:01,660 --> 01:10:09,130
הכל נראה טוב שם. עכשיו בואו ננסה להפעיל אותו, לראות מה קורה.

843
01:10:09,130 --> 01:10:13,320
בסדר! הכל נראה די טוב שם.

844
01:10:13,320 --> 01:10:18,130
>> הדבר האחרון שחושבים עליו הוא, האם יש מקרי קצה כדי להכניס את זה?

845
01:10:18,130 --> 01:10:23,170
ומתברר כי, ובכן, מקרה קצה אחד שתמיד מעניין לחשוב על

846
01:10:23,170 --> 01:10:26,250
הוא, מה קורה אם העץ שלך הוא ריק ואתה קורא להוספת פונקציה זו?

847
01:10:26,250 --> 01:10:30,330
האם זה יצליח? ובכן, בואו ננסה את זה.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree ג. -

849
01:10:32,110 --> 01:10:35,810
הדרך שאנחנו הולכים לבדוק את זה, אנחנו הולכים לרדת לפונקציה העיקרית שלנו,

850
01:10:35,810 --> 01:10:41,690
במקום חיווט צומת האלה כמו זה ו,

851
01:10:41,690 --> 01:10:56,730
אנחנו פשוט הולכים להעיר את כל הדבר הזה,

852
01:10:56,730 --> 01:11:02,620
במקום חיווט את עצם וצומת,

853
01:11:02,620 --> 01:11:09,400
אנחנו באמת יכולים פשוט ללכת קדימה ולמחוק את כל זה.

854
01:11:09,400 --> 01:11:17,560
אנחנו הולכים לעשות כל מה ששיחה להוסיף.

855
01:11:17,560 --> 01:11:49,020
אז, בואו נעשה - במקום 5, 8, ו 2, אנחנו הולכים להכניס 7, 3, ו 9.

856
01:11:49,020 --> 01:11:58,440
ואז אנחנו גם רוצים להכניס 6 גם כן.

857
01:11:58,440 --> 01:12:05,190
שמור. צא. הפוך עץ בינארי.

858
01:12:05,190 --> 01:12:08,540
את כל זה הידור.

859
01:12:08,540 --> 01:12:10,320
אנחנו רק יכולים להפעיל אותו כפי שהיא ולראות מה קורים,

860
01:12:10,320 --> 01:12:12,770
אבל זה גם הולך להיות באמת חשוב לוודא כי

861
01:12:12,770 --> 01:12:14,740
אין לנו את כל שגיאות זיכרון,

862
01:12:14,740 --> 01:12:16,840
מאז זה אחד ממקרי הקצה שלנו, כי אנחנו יודעים עליו.

863
01:12:16,840 --> 01:12:20,150
>> בואו נוודא שזה עובד גם תחת Valgrind,

864
01:12:20,150 --> 01:12:28,310
שאנחנו עושים רק על ידי הפעלת Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
זה נראה כאילו אנחנו אכן יש שגיאה אחת מהקשר אחד -

866
01:12:31,110 --> 01:12:33,790
יש לנו אשמת פילוח זה.

867
01:12:33,790 --> 01:12:36,690
מה קרה?

868
01:12:36,690 --> 01:12:41,650
Valgrind בעצם אומר לנו איפה זה.

869
01:12:41,650 --> 01:12:43,050
זום החוצה קצת.

870
01:12:43,050 --> 01:12:46,040
זה נראה כמו שזה קורה בהוספת הפונקציה שלנו,

871
01:12:46,040 --> 01:12:53,420
שם יש לנו קריאה לא חוקית בגודל 4 בכנס, קו 60.

872
01:12:53,420 --> 01:13:03,590
בואו נלך אחורה ולראות מה קורה כאן.

873
01:13:03,590 --> 01:13:05,350
זום החוצה ממש מהר.

874
01:13:05,350 --> 01:13:14,230
אני רוצה לוודא שזה לא הולך לקצה של המסך כדי שנוכל לראות את הכל.

875
01:13:14,230 --> 01:13:18,760
משוך כי בקצת. אוקיי.

876
01:13:18,760 --> 01:13:35,030
לגלול למטה, והבעיה היא ממש כאן.

877
01:13:35,030 --> 01:13:40,120
מה קורה אם אנחנו יורדים והצומת הנוכחית שלנו היא כבר ריקה,

878
01:13:40,120 --> 01:13:44,010
צומת אבינו היא ריקה, כך שאם אנחנו מסתכלים על חלקו עליון, ממש כאן -

879
01:13:44,010 --> 01:13:47,340
אם לולאה בזמן זה לא באמת מבצעת

880
01:13:47,340 --> 01:13:52,330
משום שהערך הנוכחי שלנו הוא ריק - השורש שלנו הוא ריק כל כך נוכ הוא ריק -

881
01:13:52,330 --> 01:13:57,810
אז האם שלנו אף פעם לא מקבל מוגדר נוכ או לערך חוקי,

882
01:13:57,810 --> 01:14:00,580
כך, ההורה גם יכול להיות ריק.

883
01:14:00,580 --> 01:14:03,700
אנו צריכים לזכור שכדי לבדוק

884
01:14:03,700 --> 01:14:08,750
עד שהגענו לכאן, ואנחנו מתחילים גישת ערכו של ההורה.

885
01:14:08,750 --> 01:14:13,190
אז, מה קורה? ובכן, אם ההורה הוא ריק -

886
01:14:13,190 --> 01:14:17,990
אם (הורה == NULL) - אז אנחנו יודעים ש

887
01:14:17,990 --> 01:14:19,530
אסור שיהיה שום דבר בעץ.

888
01:14:19,530 --> 01:14:22,030
אנחנו חייבים להיות מנסים להכניס אותו בשורש.

889
01:14:22,030 --> 01:14:32,570
אנחנו יכולים לעשות את זה רק על ידי הגדרת השורש השווה לצומת החדשה.

890
01:14:32,570 --> 01:14:40,010
ואז, בשלב זה, אנחנו לא ממש רוצים לעבור את הדברים אחרים.

891
01:14:40,010 --> 01:14:44,780
במקום זאת, ממש כאן, אנחנו יכולים לעשות גם אחרים, אם-אחרים,

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]