1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [제 7 조 : 더 편안한]

2
00:00:02,770 --> 00:00:05,090
[롭 보덴] [하버드 대학]

3
00:00:05,090 --> 00:00:07,930
[이 CS50입니다] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
괜찮아요. 그래서 내 이메일에서 밝혔다 같은

5
00:00:10,110 --> 00:00:14,060
이 바이너리 - 트리 위주의 섹션 될 것입니다.

6
00:00:14,060 --> 00:00:16,820
그러나 많은 질문이 없습니다.

7
00:00:16,820 --> 00:00:18,920
그래서 우리는 시도하고 각 질문을 뽑아 낼 것

8
00:00:18,920 --> 00:00:25,430
그리고 일을하는 모든 가장 좋은 방법은 고통을 구체적으로 이동합니다.

9
00:00:25,430 --> 00:00:31,200
그래서 지금 초에, 우리는 이진 나무와 물건 샘플 도면을 통해 이동합니다.

10
00:00:31,200 --> 00:00:35,970
그래서 여기, "이진 나무가 연결리스트의 비슷한 노드를 가지고 기억

11
00:00:35,970 --> 00:00:38,150
왼쪽의 '아이'의 하나 하나가 아닌 포인터의 경우를 제외하고 두 사람은 있습니다

12
00:00:38,150 --> 00:00:41,950
그리고 오른쪽 '아이'한. "

13
00:00:41,950 --> 00:00:45,630
그냥 링크 목록 같습니다 이진 트리 자

14
00:00:45,630 --> 00:00:47,910
구조체를 제외하고이 포인터를하지 않을 수 있습니다.

15
00:00:47,910 --> 00:00:51,390
세 포인터를해야합니다 trinary 나무가있어

16
00:00:51,390 --> 00:00:56,540
단지 일반 포인터를 가지고 N-워 나무가있어,

17
00:00:56,540 --> 00:01:00,320
그때 당신은 가질 정도로 크게 malloc해야한다는

18
00:01:00,320 --> 00:01:04,840
가능한 모든 어린이들에게 충분한 포인터.

19
00:01:04,840 --> 00:01:08,200
따라서 이진 트리가 두 상수가 발생합니다.

20
00:01:08,200 --> 00:01:11,260
원하는 경우, 당신은 단항 트리 연결된 목록을 제공 할 수 있습니다

21
00:01:11,260 --> 00:01:15,360
하지만 누군가가 그런 전화를 생각하지 않아요.

22
00:01:15,360 --> 00:01:18,060
"이진 트리 노드의 상자 - 및 - 화살표 다이어그램을 그립니다

23
00:01:18,060 --> 00:01:24,110
각 하위 포인터가 null입니다 네이트 좋아하는 숫자, 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
이 모두 null이 될 것이다.

32
00:01:52,460 --> 00:01:57,870
그건 그냥 null이됩니다, 그는 null이됩니다.

33
00:01:57,870 --> 00:02:03,630
좋아요. 그래서 여기에 백업합니다.

34
00:02:03,630 --> 00:02:05,700
"연결리스트로 우리는 포인터를 저장했다

35
00:02:05,700 --> 00:02:09,639
전체 연결 목록이나 전체 목록을 기억하기 위해 목록의 첫 번째 노드 있습니다.

36
00:02:09,639 --> 00:02:11,650
마찬가지로, 나무, 우리는 포인터를 저장해야

37
00:02:11,650 --> 00:02:13,420
전체 트리를 기억하기 위해 단일 ​​노드 있습니다.

38
00:02:13,420 --> 00:02:15,980
이 노드는 트리의 '루트'칼레 수 있습니다.

39
00:02:15,980 --> 00:02:18,320
이전에서 다이어그램에 구축하거나 새를 그릴

40
00:02:18,320 --> 00:02:21,690
당신은 바이너리 트리의 상자 - 및 - 화살표의 묘사되어 있는지 등

41
00:02:21,690 --> 00:02:25,730
로 왼쪽 3 다음 값을 7,,

42
00:02:25,730 --> 00:02:32,760
3의 오른쪽에있는 다음 오른쪽에 9, 다음 6. "

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
난 그냥 N. 놓을 게요

51
00:02:59,190 --> 00:03:02,250
이제 7의 왼쪽로 이동하고 싶은데요.

52
00:03:02,250 --> 00:03:06,840
그래서 우리는 지금이 남자를 가리 키도록이 포인터를 변경합니다.

53
00:03:06,840 --> 00:03:12,420
그리고 우리는 동일한 기능을 수행. 우리는 여기에 9 원

54
00:03:12,420 --> 00:03:14,620
이는 처음에 그냥 null을 말합니다.

55
00:03:14,620 --> 00:03:19,600
우리는 9이 포인터 지점을 변경 할거야

56
00:03:19,600 --> 00:03:23,310
지금 우리는 3 오른쪽에 6 놓고 싶어.

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
단지의 자녀로 NULL이있는 노드는 잎입니다.

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
따라서 세의 부모는 무엇인가?

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
가 손자 같은 거죠 여섯 있도록이 적용되지 않을 것입니다.

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
그냥 루트에 직접 계보 (Lineage) 돌아

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
일반 이진 트리에 우리가, 왼쪽 상단, 7시 3 수 있습니다

119
00:07:40,020 --> 00:07:47,630
7 왼쪽에 9; 더 어떠한 값의 순서가 없습니다.

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
이러한 포인터의 모든은 null이됩니다.

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, 3-6 점입니다.

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
하지만 나는 그 총 숫자, 왼쪽으로 이동 할 수있는 금액을 습니 경우

180
00:12:15,090 --> 00:12:18,820
플러스 오른쪽으로 이동 할 수있는 금액은 습니입니다 - 1.

181
00:12:18,820 --> 00:12:26,130
그럼 나머지 숫자들은 왼쪽 또는 오른쪽으로가는 것도 할 수 있습니다.

182
00:12:26,130 --> 00:12:31,580
그것은 내가 처음에 3 넣어 경우 모든 왼쪽으로 이동하는, 그런 어려운 것 같습니다

183
00:12:31,580 --> 00:12:35,080
하지만 7을 돌리기 만한다면 다음 몇 가지의 왼쪽을 할 수 있으며 몇 가지 오른쪽으로 이동할 수 있습니다.

184
00:12:35,080 --> 00:12:39,570
그리고 '3 첫 번째 '으로 나는 모든 오른쪽으로 갈 수 의미.

185
00:12:39,570 --> 00:12:42,350
정말이야, 당신은 같은 생각해야

186
00:12:42,350 --> 00:12:47,980
얼마나 많은 일들이 나무의 다음 수준에 갈 수 있습니다.

187
00:12:47,980 --> 00:12:50,420
또는 당신은 모두를 그릴 수 있습니다 그리고 14으로 나오면

188
00:12:50,420 --> 00:12:54,650
그리고 나서 14을드립니다.

189
00:12:54,650 --> 00:13:01,120
>> 여기로 돌아갑니다,

190
00:13:01,120 --> 00:13:03,510
우리가 그들을 통해 검색 할 수 있기 때문에 "순서 이진 나무는 멋진

191
00:13:03,510 --> 00:13:06,910
정렬 배열을 통해 검색에 매우 유사한 방법 인치

192
00:13:06,910 --> 00:13:10,120
이렇게하려면 우리는 루트에서 시작하여 트리 아래의 방식으로 작동

193
00:13:10,120 --> 00:13:13,440
잎에 대한, 우리가 검색하는 값에 대해 각 노드의 값을 확인.

194
00:13:13,440 --> 00:13:15,810
현재 노드의 값이 값보다 작 으면 우리는 찾고

195
00:13:15,810 --> 00:13:18,050
당신은 노드의 오른쪽 자식 옆에 이동합니다.

196
00:13:18,050 --> 00:13:20,030
그렇지 않으면, 당신은 노드의 왼쪽 자식으로 이동합니다.

197
00:13:20,030 --> 00:13:22,800
어떤 시점에서, 여러분은 여러분이 원하는 값을 찾을 수 있습니다, 또는 당신은 널 (null)로 실행됩니다

198
00:13:22,800 --> 00:13:28,520
값을 나타내는 것은 트리에 없습니다. "

199
00:13:28,520 --> 00:13:32,450
나는 우리가 예전의 트리를 다시 그리기해야, 그 몇초 밖에 안 걸릴거야.

200
00:13:32,450 --> 00:13:38,280
하지만 우리는 6, 10, 1 트리에 있는지 찾아하고 싶습니다.

201
00:13:38,280 --> 00:13:49,180
그럼 그게 뭔지, 7, 9, 3, 6. 좋아요.

202
00:13:49,180 --> 00:13:52,730
당신이보고 싶지 번호는, 우리는 6을보고 싶어요.

203
00:13:52,730 --> 00:13:55,440
이 방법 알고리즘의 작동 원리는 무엇입니까?

204
00:13:55,440 --> 00:14:03,040
음, 우리는 또한 우리 나무에 몇 가지 루트 포인터가 있습니다.

205
00:14:03,040 --> 00:14:12,460
그리고 우리가 루트에 가서 말하면, 우리가 검색하는 값 같은이 값인가요?

206
00:14:12,460 --> 00:14:15,000
그래서 우리는 6 찾고, 그래서 평등 없습니다.

207
00:14:15,000 --> 00:14:20,140
그래서 6 7보다 적은, 좋아, 그래서 우리는 계속, 지금 우리는 말한다.

208
00:14:20,140 --> 00:14:23,940
우리가 왼쪽으로 가고 싶어 의미합니까, 아니면 오른쪽으로 가고 싶어?

209
00:14:23,940 --> 00:14:27,340
[학생] 왼쪽. >> 그래.

210
00:14:27,340 --> 00:14:33,340
그것은 상당히 쉽게, 당신이해야 할 모든 나무의 하나의 가능한 노드를 세우면

211
00:14:33,340 --> 00:14:37,760
그리고 당신은 엔 - 머리에 생각하는 대신에,

212
00:14:37,760 --> 00:14:40,020
그래, 덜 있다면, 난 왼쪽으로 이동하거나 권리를가는거야

213
00:14:40,020 --> 00:14:43,030
단지이 사진을 본, 내가 왼쪽으로 가야한다는 아주 명확한

214
00:14:43,030 --> 00:14:47,700
이 노드가 내가 찾는 그 값보다 큰 경우.

215
00:14:47,700 --> 00:14:52,600
그래서 당신은 지금 3에있어 왼쪽으로 이동합니다.

216
00:14:52,600 --> 00:14:57,770
전 가고 싶어요 - 3 6입니다 내가 찾는 값보다 작습니다.

217
00:14:57,770 --> 00:15:03,420
그래서 우리는 오른쪽으로 가고, 지금은 6시 종료

218
00:15:03,420 --> 00:15:07,380
이는 내가 진짜 돌아 있도록이 찾고있는 값입니다.

219
00:15:07,380 --> 00:15:15,760
제가 찾으러 가겠어요 다음 값은 10입니다.

220
00:15:15,760 --> 00:15:23,230
좋아요. 루트를 따라 오지 - 그 잘라 - 10 그래서, 지금, 것입니다.

221
00:15:23,230 --> 00:15:27,670
지금 10은 7보다 큰 될 것입니다, 그래서 제가 오른쪽으로보고 싶어요.

222
00:15:27,670 --> 00:15:31,660
내가 여기 올거야, 10, 9보다 더 될 것입니다

223
00:15:31,660 --> 00:15:34,520
그래서 오른쪽으로보고 싶지 겠어.

224
00:15:34,520 --> 00:15:42,100
여기 올 있지만, 여기에 지금은 널 (null)에 있어요.

225
00:15:42,100 --> 00:15:44,170
나는 null을 친다면 어떻게해야합니까?

226
00:15:44,170 --> 00:15:47,440
[학생] False를 반환? >> 그래. I 10를 찾지 못했습니다.

227
00:15:47,440 --> 00:15:49,800
1은 거의 동일 경우 될 것입니다,

228
00:15:49,800 --> 00:15:51,950
를 제외하고 그냥 이성을 상실 할거야, 보는 대신

229
00:15:51,950 --> 00:15:56,540
오른쪽 아래, 나는 왼쪽을 볼거야.

230
00:15:56,540 --> 00:16:00,430
>> 지금은 우리가 실제로 코드를 얻을 생각합니다.

231
00:16:00,430 --> 00:16:04,070
이곳이야 - CS50 어플라이언스를 열고이 길을 이동

232
00:16:04,070 --> 00:16:07,010
뿐만 아니라 공간에서 할 만 할 수 있습니다.

233
00:16:07,010 --> 00:16:09,170
그것은 아마도 공간에서 작업을 수행하는 것이 좋습니다

234
00:16:09,170 --> 00:16:13,760
우리는 공간에서 일을 할수 있기 때문이다.

235
00:16:13,760 --> 00:16:19,170
"처음에 우리는 정수 값을 포함하는 이진 트리 노드에 대한 새 유형의 정의가 필요합니다.

236
00:16:19,170 --> 00:16:21,400
아래 typedef 상용구를 사용하여

237
00:16:21,400 --> 00:16:24,510
이진 트리에서 노드에 대해 새로운 유형의 정의를 만들 수 있습니다.

238
00:16:24,510 --> 00:16:27,930
당신은 문제가 발생할 경우. . . "어쩌구 저쩌구. 좋아요.

239
00:16:27,930 --> 00:16:30,380
그럼 여기서 반복을 놓고,

240
00:16:30,380 --> 00:16:41,630
typedef 구조체 노드와 노드. 그래, 알았어.

241
00:16:41,630 --> 00:16:44,270
그래서 우리가 우리의 노드에서 원하는 거예요 필드는 무엇입니까?

242
00:16:44,270 --> 00:16:46,520
[학생] 두 포인터 후 INT와?

243
00:16:46,520 --> 00:16:49,700
>> int 값, 두 포인터? 어떻게 포인터를 작성하려면 어떻게해야합니까?

244
00:16:49,700 --> 00:16:58,440
[학생] 구조체. >> 저는 그래, 구조체 노드가 * 왼쪽 확대해야

245
00:16:58,440 --> 00:17:01,320
그리고 구조체 노드 * 좋아.

246
00:17:01,320 --> 00:17:03,460
그리고 마지막에서 논의를 기억

247
00:17:03,460 --> 00:17:15,290
이 말이 안되는,이 말이 안

248
00:17:15,290 --> 00:17:18,270
이 말도하지 않습니다.

249
00:17:18,270 --> 00:17:25,000
이 재귀 구조체를 정의하기 위해 전 거기에 모든 것을해야합니다.

250
00:17:25,000 --> 00:17:27,970
좋아, 그럼 우리 나무의 모습을 것입니다 수 있도록.

251
00:17:27,970 --> 00:17:37,670
우리가 trinary 나무를 한 경우, 노드는 B1, B2, 구조체 노드 * B3, 같이 보일 수 있습니다

252
00:17:37,670 --> 00:17:43,470
B는 지점입니다 - 사실,이, 중간, 오른쪽,하지만 무엇이든을 떠난 들었습니다.

253
00:17:43,470 --> 00:17:55,610
우리는 바이너리 관심, 그래서 오른쪽, 왼쪽.

254
00:17:55,610 --> 00:17:59,110
"이제 트리의 루트에 대한 글로벌 노드 * 변수를 선언합니다."

255
00:17:59,110 --> 00:18:01,510
그래서 우리가 그렇게 할 수 없어.

256
00:18:01,510 --> 00:18:08,950
일 약간 더 어렵고 더 일반화하기 위해서는,

257
00:18:08,950 --> 00:18:11,570
우리는 글로벌 노드 변수가 없습니다.

258
00:18:11,570 --> 00:18:16,710
대신, 주에 우리는 우리의 모든 노드 것을 선언합니다

259
00:18:16,710 --> 00:18:20,500
우리가 실행 시작할 때 그, 그 아래의 의미

260
00:18:20,500 --> 00:18:23,130
우리가 포함되어 기능 및 삽입 기능,

261
00:18:23,130 --> 00:18:27,410
대신에 우리가 포함을, 그냥이 글로벌 노드 변수를 사용하여 제대로 작동

262
00:18:27,410 --> 00:18:34,280
우리는 우리가 처리 할가 인자로 나무를 할 겁니다.

263
00:18:34,280 --> 00:18:36,650
전역 변수를 갖는다는 것은 일을 더 쉽게 만들고했는데.

264
00:18:36,650 --> 00:18:42,310
우리는 일 열심히 할거야.

265
00:18:42,310 --> 00:18:51,210
이제 이런 건 그냥하는 분 정도를

266
00:18:51,210 --> 00:18:57,690
내부의 주요의이 트리를 만들려면, 바로 당신이 원하는 모든 어디.

267
00:18:57,690 --> 00:19:04,530
시도 및 주요 기능에이 나무를 구성합니다.

268
00:19:42,760 --> 00:19:47,610
>> 좋아요. 그래서 아직 나무에게 전체 방법을지었습니다 할 필요가 없습니다.

269
00:19:47,610 --> 00:19:49,840
그러나 사람은 내가 끌어 수있는 일이

270
00:19:49,840 --> 00:20:03,130
하나는 이러한 트리를 만들어야하는 방법을 표시합니다?

271
00:20:03,130 --> 00:20:08,080
[학생] 사람의 음탕 한 짓에서 벗어나려고 노력.

272
00:20:08,080 --> 00:20:13,100
[보덴]의 트리 구조를 갖춘 편안한 사람이 있나요?

273
00:20:13,100 --> 00:20:15,520
[학생] 그래. 그런데 아직. 아니, 괜찮아 >>. 우리가 끝낼 수 -

274
00:20:15,520 --> 00:20:26,860
오, 당신을 절약 할 수 있습니다? 좋아.

275
00:20:26,860 --> 00:20:32,020
그래서 여기에 우리가해야 - 아, 약간 잘라거야.

276
00:20:32,020 --> 00:20:34,770
나는 확대 이유는 무엇입니까?

277
00:20:34,770 --> 00:20:37,730
확대, 나가 스크롤됩니다. 제가 질​​문이 >>. >> 응?

278
00:20:37,730 --> 00:20:44,410
[학생]는 당신이 구조체를 정의 할 때, 아무로 초기화 같은 일이 있습니까?

279
00:20:44,410 --> 00:20:47,160
[보덴] 번호 >> 좋아요. 그래서 초기화해야 -

280
00:20:47,160 --> 00:20:50,450
[보덴] 번호 구조체를 사용자가 정의 할 때, 또는 선언 할 때,

281
00:20:50,450 --> 00:20:55,600
그것은 기본적으로 초기화되지 않습니다, 당신은 정수를 선언하는 경우가 똑같아.

282
00:20:55,600 --> 00:20:59,020
그것은 정확히 같은 일입니다. 이은 개별 필드의 각 같아요

283
00:20:59,020 --> 00:21:04,460
거기에 쓰레기 값을 가질 수 있습니다. 구조체 또는 선언 - >> 그리고 정의 할 수 있습니다

284
00:21:04,460 --> 00:21:07,740
가 않는 방식으로 그들을 초기화?

285
00:21:07,740 --> 00:21:13,200
[보덴] 예. 자, 바로 가기 초기화 구문

286
00:21:13,200 --> 00:21:18,660
모양 것입니다 -

287
00:21:18,660 --> 00:21:22,200
우리가 이런 일을 할 수있는 두 가지 방법이 있어요. 나는 우리가 그것을 컴파일해야한다고 생각

288
00:21:22,200 --> 00:21:25,840
확실히 꽝를 만들기 위해하면이 작업을 수행합니다.

289
00:21:25,840 --> 00:21:28,510
구조체에 제공 인자의 순서

290
00:21:28,510 --> 00:21:32,170
당신은이 중괄호 내부 인자의 순서로 넣어.

291
00:21:32,170 --> 00:21:35,690
당신은 9를 초기화하려면 왼쪽면을 마우스 오른쪽, null이 null이 될 수 있으며

292
00:21:35,690 --> 00:21:41,570
그것은, 0, null이 9가 될 것입니다.

293
00:21:41,570 --> 00:21:47,890
, 대안이 있으며, 편집기는이 구문을 좋아하지 않아

294
00:21:47,890 --> 00:21:50,300
그리고 내가 새로운 블록을 원하는 생각

295
00:21:50,300 --> 00:22:01,800
하지만 대안은 무언가 같다 -

296
00:22:01,800 --> 00:22:04,190
여기, 내가 새 줄에 올려 놓을 게요.

297
00:22:04,190 --> 00:22:09,140
당신은 명시 적으로 말할 수, 나는 정확한 구문을 잊어 버려.

298
00:22:09,140 --> 00:22:13,110
그래서 당신은 명시 적으로, 이름하여 해결하고, 말을 할 수

299
00:22:13,110 --> 00:22:21,570
. c 또는. 값 = 9. 왼쪽 =의 NULL.

300
00:22:21,570 --> 00:22:24,540
나는 쉼표 될 수있는 이러한 필요성을 추측거야.

301
00:22:24,540 --> 00:22:29,110
. 오른쪽 = NULL, 그래서 당신은 몰라요 이런 식으로

302
00:22:29,110 --> 00:22:33,780
실제로 구조체의 순서를 알 필요가

303
00:22:33,780 --> 00:22:36,650
당신이 이걸 읽는 때, 훨씬 더 명시 적입니다

304
00:22:36,650 --> 00:22:41,920
일에 대해 값이로 초기화되고있어.

305
00:22:41,920 --> 00:22:44,080
>> 이는 일 중 하나 일 -

306
00:22:44,080 --> 00:22:49,100
따라서 대부분의 경우, C + + C.의 Superset 임

307
00:22:49,100 --> 00:22:54,160
당신은 C + +,하고 컴파일해야합니다 이쪽으로 이동, C 코드를 취할 수 있습니다.

308
00:22:54,160 --> 00:22:59,570
이 C + +에서 지원하지 않는 것 중 하나이기 때문에, 사람들은 그렇게하지 ​​경향이 있습니다.

309
00:22:59,570 --> 00:23:01,850
그 사람들이 그렇게하지 ​​않는 경향이 유일한 이유인지는 모르겠지만

310
00:23:01,850 --> 00:23:10,540
하지만 그것을 사용하는 데 필요한 경우는 C + +와 그래서이 장치를 사용할 수 작업이 필요합니다.

311
00:23:10,540 --> 00:23:14,000
뭔가의 또 다른 예는 C + +과 함께 작동하지 않습니다

312
00:23:14,000 --> 00:23:16,940
어떻게 malloc은 기술적으로 '공극 * "를 반환

313
00:23:16,940 --> 00:23:20,200
하지만, 그냥 숯불 * X = malloc의 무엇이든을 말할 수

314
00:23:20,200 --> 00:23:22,840
그리고 그것은 자동으로 숯불 *로 캐스트 될 것입니다.

315
00:23:22,840 --> 00:23:25,450
그 자동 캐스트에서 발생하지 않는 C + +.

316
00:23:25,450 --> 00:23:28,150
컴파일하지 않을, 당신은 명시 적으로 말을해야 그

317
00:23:28,150 --> 00:23:34,510
숯불 * malloc, 뭐든간에, 숯불 *로 캐스팅 할 수 있습니다.

318
00:23:34,510 --> 00:23:37,270
C와 C + +에 동의한다는 여러 가지가 있는데,하지 않습니다

319
00:23:37,270 --> 00:23:40,620
하지만 그건 두 가지입니다.

320
00:23:40,620 --> 00:23:43,120
그래서 우리는이 구문 갈거야.

321
00:23:43,120 --> 00:23:46,150
하지만 그 구문 가지 않았더라도하면,

322
00:23:46,150 --> 00:23:49,470
무슨 -이 문제가 될 수 있을까요?

323
00:23:49,470 --> 00:23:52,170
[학생] 내가이 역 참조를 필요하지 않습니다? >> 그래.

324
00:23:52,170 --> 00:23:55,110
, 화살표가 암시 적 역 참조를 가지고 기억

325
00:23:55,110 --> 00:23:58,230
그래서 우리는, 구조체를 처리 할 때

326
00:23:58,230 --> 00:24:04,300
우리는 사용하고 싶습니다. 구조체의 필드 내에서 얻을합니다.

327
00:24:04,300 --> 00:24:07,200
그리고 우리가 화살표를 사용하여 유일한 시간은 우리가 어떻게 할 때입니다 -

328
00:24:07,200 --> 00:24:13,450
음, 화살표와 동일합니다 -

329
00:24:13,450 --> 00:24:17,020
그건 내가 화살표를 사용한 경우가 의미했을거야.

330
00:24:17,020 --> 00:24:24,600
모든 화살표 수단은 역 참조이 지금은 구조체에있어 있으며, 그 필드를 얻을 수 있습니다.

331
00:24:24,600 --> 00:24:28,040
직접 또는 역 참조 필드를 가져 와서 현장을 -

332
00:24:28,040 --> 00:24:30,380
나는이 값이어야합니다 같아요.

333
00:24:30,380 --> 00:24:33,910
하지만 이곳은 그냥 구조체가 아닌 구조체에 대한 포인터가 좀있어서 ..

334
00:24:33,910 --> 00:24:38,780
그래서 난 화살표를 사용할 수 없습니다.

335
00:24:38,780 --> 00:24:47,510
그러나 이런 건 우리가 모든 노드에 대해 수행 할 수 있습니다.

336
00:24:47,510 --> 00:24:55,790
오, 맙소사.

337
00:24:55,790 --> 00:25:09,540
이 6, 7, 3입니다.

338
00:25:09,540 --> 00:25:16,470
그런 다음 우리는 나무의 가지를 설정할 수 있습니다, 우리는 7 할 수 있습니다 -

339
00:25:16,470 --> 00:25:21,650
우리는 그 왼쪽 3를 가리켜 수 있습니다.

340
00:25:21,650 --> 00:25:25,130
그럼 어떻게 그렇게 우리합니까?

341
00:25:25,130 --> 00:25:29,320
[학생 이해할 수없는] >> 그래. node3의 주소,

342
00:25:29,320 --> 00:25:34,170
당신이 주소를 가지고 있지 않은 경우, 그냥 컴파일되지 것입니다.

343
00:25:34,170 --> 00:25:38,190
그러나 이러한 다음 노드에 대한 포인터임을 기억나요.

344
00:25:38,190 --> 00:25:44,930
그래, 9 가리켜 야합니다

345
00:25:44,930 --> 00:25:53,330
3는 6 오른쪽에 지정해야합니다.

346
00:25:53,330 --> 00:25:58,480
이 모든 준비가 생각합니다. 의견이나 질문?

347
00:25:58,480 --> 00:26:02,060
[학생, 이해할 수없는] 루트 7가 될 것입니다.

348
00:26:02,060 --> 00:26:08,210
우리는 노드를 말할 수 * PTR =

349
00:26:08,210 --> 00:26:14,160
또는 루트 = & node7.

350
00:26:14,160 --> 00:26:20,730
>> 우리의 목적을 위해, 우리는 삽입 처리 할 것

351
00:26:20,730 --> 00:26:25,490
그래서 우리는이 이진 트리에 삽입 할 수있는 기능을 작성하려는거야

352
00:26:25,490 --> 00:26:34,230
그리고 삽입은 필연적으로이 나무에 대한 새로운 노드를 만들 malloc를 호출 할 수 있습니다.

353
00:26:34,230 --> 00:26:36,590
그래서 결국은 사실과 혼란 얻을 수있는 몇 가지 노드

354
00:26:36,590 --> 00:26:38,590
스택에 현재

355
00:26:38,590 --> 00:26:43,680
와 다른 노드 우리가 그들을 삽입 할 때 힙에 종료 할 수 있습니다.

356
00:26:43,680 --> 00:26:47,640
이 완벽하게 유효하지만 유일한 이유는

357
00:26:47,640 --> 00:26:49,600
우리는 스택에이 작업을 수행 할 수

358
00:26:49,600 --> 00:26:51,840
우리가 알고있는 이러한 인위적인 예이기 때문입니다

359
00:26:51,840 --> 00:26:56,360
나무는 7, 3, 6, 9로 건설 될 예정입니다.

360
00:26:56,360 --> 00:27:02,970
우리가이하지 않은 경우, 우리는 처음에 malloc 할 필요가 없습니다 것입니다.

361
00:27:02,970 --> 00:27:06,160
우리는 조금 나중에 보 겠지만, 우리는 malloc'ing해야합니다.

362
00:27:06,160 --> 00:27:08,570
지금은 스택에 넣어 완벽하게 합리적

363
00:27:08,570 --> 00:27:14,750
하지만 우린 malloc 구현이 변경 보자.

364
00:27:14,750 --> 00:27:17,160
따라서 이러한 각각의 지금 뭔가 같은 것입니다

365
00:27:17,160 --> 00:27:24,240
노드 * node9 = malloc (sizeof (노드)).

366
00:27:24,240 --> 00:27:28,040
그리고 지금 우리는 우리의 검사를해야 할거야.

367
00:27:28,040 --> 00:27:34,010
(== NULL node9)가있는 경우 - 제가 그렇게 싫었 어 -

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
이제 우리는 주어진 값과 널 포인터가있는 모든 노드를 만들 것을 호출 할 수 있습니다.

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
노드 수익 (ROI)을 어떻게 구축합니까?

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
경우 (node​​9 == 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
[보덴] 모든 제로 값은 false입니다.

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 제로 값은 널 (null)과 제로이며,

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
의 값으로 0 값을 수 있습니다.

419
00:31:57,390 --> 00:32:01,150
그래서 여기, 노드 * 루트, 우리는 명시 적으로 아무것도에 초기화하지 않습니다

420
00:32:01,150 --> 00:32:06,350
그래서 기본 값은 포인터의 제로 값입니다, null이됩니다.

421
00:32:06,350 --> 00:32:11,870
X의 기본 값은 x.value이 0 인 것을 의미 것입니다

422
00:32:11,870 --> 00:32:14,260
x.left가 null이며, x.right가 null입니다.

423
00:32:14,260 --> 00:32:21,070
이 구조체가되도록 있기 때문에, 구조체의 필드의 모든 제로 값이 될 것입니다.

424
00:32:21,070 --> 00:32:24,410
우리는하지만, 여기서는 그런 사용할 필요가 없습니다.

425
00:32:24,410 --> 00:32:27,320
[학생] structs는 다른 변수보다 다른, 다른 변수는

426
00:32:27,320 --> 00:32:31,400
쓰레기 값은, 이것들은 제로인가요?

427
00:32:31,400 --> 00:32:36,220
너무 [보덴] 기타 값입니다. 따라서 X에서, x는 0이 될 것입니다.

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 뿌리는 false를 반환해야합니다.

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
우리는 우리 하위 트리를 recurses 별도의 도우미 기능을 가지고 있어야합니다.

452
00:34:24,130 --> 00:34:29,610
하지만 우리가 변경 한 이후는, 인수로 나무를 사용하려면

453
00:34:29,610 --> 00:34:32,760
어떤 항상 맨 처음에 있었어야

454
00:34:32,760 --> 00:34:35,710
이제 우리는 재귀 호출을 더 쉽게 할 수 있습니다.

455
00:34:35,710 --> 00:34:38,960
따라서 반복 또는 재귀, 우리는 모두 이상 갈거야

456
00:34:38,960 --> 00:34:46,139
하지만 우리는 매우 쉽게되는 백업이 재귀 끝을 볼 수 있습니다.

457
00:34:59,140 --> 00:35:02,480
좋아요. 사람이 우리가 일을 할 수있는 일이 있습니까?

458
00:35:02,480 --> 00:35:12,000
>> [학생] 나는이 솔루션을 반복적있어. >> 좋아, 반복.

459
00:35:12,000 --> 00:35:16,030
좋아요, 좋아 보입니다.

460
00:35:16,030 --> 00:35:18,920
그래서,을 통해 문의 걸어 줄까?

461
00:35:18,920 --> 00:35:25,780
[학생] 그래. 그래서 나무의 첫 번째 노드를 가져 오기 위해 임시 변수를 설정합니다.

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
가 종료 루프를하고 false를 반환합니다 - 그럼 반환합니다.

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
아, 그건 좀 longish을 시작합니다.

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
즉, 당신에게 3 원 연산자와 함수를 제공

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
나무가 null 경우 다음 우리가 그것을 발견하지 않았기 때문에 false를 반환하는거야 때문입니다.

496
00:38:13,380 --> 00:38:19,200
그리고 나무가 아직 거기 있다면, 우리는로 이동 - 값이 현재 노드 인 경우 먼저 확인합니다.

497
00:38:19,200 --> 00:38:23,740
이 경우 TRUE를 반환하고, 왼쪽 또는 오른쪽에 있지 않은 경우 우리는 재귀 호출.

498
00:38:23,740 --> 00:38:25,970
그 소리는 적절한합니까? >> 음. (계약)

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
좋아요. 이 작은 보이게의 2 단계는 여기

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
우리는 TRUE를 반환거야.

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
나무가 같은 널을하면되는데,이, 나쁜 경우입니다

539
00:41:49,580 --> 00:41:54,790
나무가 null이 동일 경우, 첫 번째 조건은 false가 될 것입니다.

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
곳 나무, 우리는 더 갈 같지 않음 null이 안 간다 않는 경우 -

543
00:42:10,710 --> 00:42:14,930
나무가 동일한 null을 수행하는 경우 나, 우리는 가치 == 나무 값을하지 않을 수 있습니다.

544
00:42:14,930 --> 00:42:17,010
우리는 즉시 false를 반환하는거야.

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)을 dereferencing 때문입니다.

548
00:42:32,510 --> 00:42:40,490
그래서 그런 걸. 이 할 수 있습니다 - 한 번 이상 이동.

549
00:42:40,490 --> 00:42:44,840
이,이와 함께 한 줄을 벌어 또한 아주 흔한 일이

550
00:42:44,840 --> 00:42:49,000
하지만, 여기 아마 조건에서 일반적인 일이 아닙니다

551
00:42:49,000 --> 00:42:59,380
하지만 (나무! = NULL, 그리고 나무> 값 == 값), 뭐든지합니다.

552
00:42:59,380 --> 00:43:01,560
이것은 아주 일반적인 상태이며, 어디에서 대신 문제의

553
00:43:01,560 --> 00:43:06,770
이 IFS에이 침입하는 곳, 나무 널입니까?

554
00:43:06,770 --> 00:43:11,780
좋아,이 null 아니라, 그래서 지금은 값 같은 나무 값? 이 작업을 수행합니다.

555
00:43:11,780 --> 00:43:17,300
대신,이 조건이 잘못을 감금하지 않습니다

556
00:43:17,300 --> 00:43:21,220
이 널 (null) 일 경우는 탈출합니다 때문입니다.

557
00:43:21,220 --> 00:43:24,000
당신의 나무가 완전히 잘못된 포인터 인 경우 음, 내 생각, 그것은 여전히​​ 잘못을 감금 할 수 있습니다

558
00:43:24,000 --> 00:43:26,620
나무가 null 인 경우이지만 잘못을 감금 할 수 없습니다.

559
00:43:26,620 --> 00:43:32,900
가 널 (null)이라면 본 적 처음에 포인터를 역 참조하기 전에, 그것은 탈출합니다.

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
51에서 OCaml과 모든, 모든 재귀 때문입니다.

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 번까지 평가할 수 있습니다.

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 삽입하면, 그냥은 필연적으로 하나를 삽입 할거야 -

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
당신이해야 할 모든이 노드에 얻을 때까지 트리를 반복 is

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
나 7의 왼쪽에있는 9 삽입 할 불가능할 거 같아

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
[학생] 임시가 null 경우? >> 그래. 임시 널 (null) 인 경우 그래서 당신은 루프의 탈출 방법은 있습니다.

651
00:50:22,100 --> 00:50:30,220
하지만 여기에 무엇을해야합니까?

652
00:50:30,220 --> 00:50:35,410
필연적으로 null입니다 I 역 참조 온도.

653
00:50:35,410 --> 00:50:39,840
당신이해야 할 또 다른 문제는 임시 null이 될 때까지, 그냥 추적하지 않습니다

654
00:50:39,840 --> 00:50:45,590
당신은 항상 부모의 트랙을 유지하고 싶습니다.

655
00:50:45,590 --> 00:50:52,190
우리는 또한 노드 * 부모를 원해, 난 우리가 널 (null)에서 처음하는을 유지할 수 있습니다 같아요.

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
값이 무엇이든보다 큰 경우, 온도 = 임시 좋아.

659
00:51:03,950 --> 00:51:07,910
하지만 우리가 전에, 부모 = 온도.

660
00:51:07,910 --> 00:51:14,500
부모는 항상 동일한 temp에가는거야? 경우 것이 있나요?

661
00:51:14,500 --> 00:51:19,560
임시 null이 아닌 경우, 그럼, 무슨 일이 있어도 아래로 이동하지거야

662
00:51:19,560 --> 00:51:24,030
임시 부모되는 노드 있습니다.

663
00:51:24,030 --> 00:51:27,500
따라서 부모가 temp 될거야 그리고 난 아래로 온도 이동합니다.

664
00:51:27,500 --> 00:51:32,410
지금 온도 널 (null)이지만, null입니다 일을 부모 부모를 가리 킵니다.

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이 null 동일하면 다음 false를 반환합니다.

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
나무 널로에서 시작하면, 우리는 널 (null) 나무에 전달합니다.

683
00:53:08,310 --> 00:53:12,650
난 당신이 null이 나무에 전달의 동작을 정의하는 방법에 따라 달라집니다 같아요.

684
00:53:12,650 --> 00:53:15,490
당신이 null이 나무에 통과하면 그렇게 생각

685
00:53:15,490 --> 00:53:17,520
다음 null이 나무에 값을 삽입

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
당신은 null이 나무에 합격 할 경우

689
00:53:28,050 --> 00:53:31,320
그리고 당신이에 값을 삽입하려는 false를 반환합니다.

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
나무가 null 경우 우리는, 그래서 우리가 그것에 대해 할 수있는 건 아무 것도 없어요.

695
00:53:48,570 --> 00:53:50,960
우리는 false를 반환 할 수 있습니다.

696
00:53:50,960 --> 00:53:52,840
그래서 삽입을 변경거야.

697
00:53:52,840 --> 00:53:56,540
우리는 기술적으로 단지 바로 지금이 순간을 변경할 수 있습니다

698
00:53:56,540 --> 00:53:58,400
어떻게이 일을 통해 반복 있어요

699
00:53:58,400 --> 00:54:04,530
하지만 노드에게 ** 나무를 취할 삽입을 변경하는거야.

700
00:54:04,530 --> 00:54:07,510
더블 포인터.

701
00:54:07,510 --> 00:54:09,710
이것은 무엇을 의미할까요?

702
00:54:09,710 --> 00:54:12,330
대신 노드에 대한 포인터를 처리하는,

703
00:54:12,330 --> 00:54:16,690
나는 조작 할 건데 것은이 포인터입니다.

704
00:54:16,690 --> 00:54:18,790
이 포인터를 조작 할거야.

705
00:54:18,790 --> 00:54:21,770
나는 직접 포인터를 조작 할거야.

706
00:54:21,770 --> 00:54:25,760
아래로 생각 때문에이 의미가 -

707
00:54:25,760 --> 00:54:33,340
물론, 지금은이 점은 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
난 그냥 우리가 false를 반환하는 것 같아요.

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
또는 삽입 - 나무는 null이 아닙니다.

737
00:56:20,120 --> 00:56:24,630
여기. 나무가 null가 아니라 * 나무는 null입니다, 아주 좋아하는

738
00:56:24,630 --> 00:56:26,680
* 나무가 null 인 경우, 그럼 그것을 조작 할 수 있기 때문에

739
00:56:26,680 --> 00:56:29,210
지금 난 그게을 가리 키도록 원하는 것을 가리합니다.

740
00:56:29,210 --> 00:56:34,750
나무가 null이라면, 그건 내가 그냥 여기까지 와서 널 밝혔다 의미합니다.

741
00:56:34,750 --> 00:56:42,710
이해가 안되는데. 난 그걸 아무 것도 할 수 없습니다.

742
00:56:42,710 --> 00:56:45,540
나무가 null 인 경우 false를 반환합니다.

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
내 빨간색 포인터가 포인터 인 경우 I가에 초점을 맞춘 곳,

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 경우 false를 반환합니다.

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
우리는 그들에게 가리 싶은 일을 가리 키도록 널 포인터를 변경할 수 있습니다.

765
00:58:40,750 --> 00:58:42,820
그게 우리 기지 케이스입니다.

766
00:58:42,820 --> 00:58:45,740
>> 이제 재발, 또는 재귀,

767
00:58:45,740 --> 00:58:51,430
우리가하고있어 다른 모든 recursions과 매우 유사가 될 것입니다.

768
00:58:51,430 --> 00:58:55,830
우리는 가치를 삽입 할 거예요

769
00:58:55,830 --> 00:58:59,040
지금은 다시 삼원를 사용하는거야,하지만 우리의 조건은하실 건가요?

770
00:58:59,040 --> 00:59:05,180
우리는 우리가 왼쪽 또는 오른쪽으로 이동할지 여부를 결정 무엇을 찾고 무엇입니까?

771
00:59:05,180 --> 00:59:07,760
별도의 단계를 수행하자.

772
00:59:07,760 --> 00:59:18,850
경우 (값 <) 뭐?

773
00:59:18,850 --> 00:59:23,200
[학생] 나무의 가치?

774
00:59:23,200 --> 00:59:27,490
[보덴] 그래서 현재 걸 기억 -

775
00:59:27,490 --> 00:59:31,260
[학생 이해할 수없는]

776
00:59:31,260 --> 00:59:34,140
[보덴]이 (가) 그래, 바로 여기, 보자 그이 녹색 화살표

777
00:59:34,140 --> 00:59:39,050
나무가 현재의 한 예입니다,이 포인터에 대한 포인터입니다.

778
00:59:39,050 --> 00:59:46,610
그게 내가 3 포인터에 대한 포인터입니다 의미합니다.

779
00:59:46,610 --> 00:59:48,800
역 참조는 두 번 그럴싸한.

780
00:59:48,800 --> 00:59:51,010
내가 무슨 짓을 - 어떻게 그런 짓을합니까?

781
00:59:51,010 --> 00:59:53,210
[학생] 번 역 참조하고 수행 화살표를 그런 식으로?

782
00:59:53,210 --> 00:59:58,420
[보덴]이 자 (* 나무가) 번 역 참조이고, -> 값

783
00:59:58,420 --> 01:00:05,960
내게는 간접적으로 가리키는 것만 노드의 값을 제공 예정이다.

784
01:00:05,960 --> 01:00:11,980
그래서 또한 당신이 그렇게 원하는 경우가 tree.value을 ** 쓸 수 있습니다.

785
01:00:11,980 --> 01:00:18,490
작동 중.

786
01:00:18,490 --> 01:00:26,190
그런 경우라면, 나는 값이 삽입 호출하고 싶습니다.

787
01:00:26,190 --> 01:00:32,590
그럼 내 업데이트 노드는 **하실 건가요?

788
01:00:32,590 --> 01:00:39,440
나는 왼쪽으로 가고 싶어하므로 ** tree.left 내 왼쪽 될 것입니다.

789
01:00:39,440 --> 01:00:41,900
그리고 그 일에 대한 포인터를 원하는

790
01:00:41,900 --> 01:00:44,930
그래서 왼쪽은 NULL 포인터가되는 것을 포기 끝나는 경우는,

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
내 뿌리가 null이라면 어떻게됩니까? 바로 여기이 경우 작업을 수행하면 어떻게됩니까?

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
루트 왼쪽은 null 될 것입니다, 루트 권한이 null가 될 것입니다.

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
경우 트리 - 루트가 null이었고,

818
01:02:56,020 --> 01:02:58,410
우리는 False를 반환했습니다. 우리가 할 수있는 일은 아무것도 없습니다.

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
[학생] 어디 ​​TRUE를 반환합니까?

836
01:04:17,110 --> 01:04:21,550
[보덴] 바로 여기 일거야.

837
01:04:21,550 --> 01:04:26,690
우리가 올바르게 삽입하면 TRUE를 반환.

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 만 달러의 높이가 경우에도 마찬가지입니다.

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
루트 자체가 null, 또는 과거 항목은 널 (null) 인 경우

860
01:06:17,940 --> 01:06:20,060
대신 부모 포인터를 처리하는,

861
01:06:20,060 --> 01:06:27,430
가 포인터 to 유지 포인터의 동일한 논리를 적용 보자.

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
그런 다음 & (* 온도) -> 오른쪽

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
이 함수는 TRUE를 반환해야합니다 포함되어 있습니다

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
우리가 노드 ** s의 노드 *로하지 보셨습니까?

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
그렇게되면, 우리는 TRUE를 반환하고 싶습니다.

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
그리고 우리가 볼을 떨쳐 버리게 한, 그래서 false를 반환합니다.

935
01:12:16,020 --> 01:12:24,810
(현재 -> 값 == 값), TRUE를 반환합니다.

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
구조체 목록, 노드 * N, 다음 노드 ** 다음은?

946
01:13:32,360 --> 01:13:40,240
전 괜찮아요 작동 생각합니다.

947
01:13:40,240 --> 01:13:45,940
여기까지 - 우리는 왼쪽, 또는 let's 넘어 가고 싶어요.

948
01:13:45,940 --> 01:13:54,350
구조체 목록 목록 =이, 그것은 시작합니다

949
01:13:54,350 --> 01:13:58,170
이 구조체 목록에서 아웃.

950
01:13:58,170 --> 01:14:04,040
* 목록 = NULL. 그래서 우리의 연결 목록이 될거에요

951
01:14:04,040 --> 01:14:08,430
우리가 이상 생략 한 하위 트리의.

952
01:14:08,430 --> 01:14:13,800
우리는 지금 왼쪽 통과 거예요

953
01:14:13,800 --> 01:14:17,870
그러나 우리는 필연적으로 오른쪽으로 돌아와야 때문에,

954
01:14:17,870 --> 01:14:26,140
우리는 우리의 구조체 목록의 내부 오른쪽을 유지거야.

955
01:14:26,140 --> 01:14:32,620
그런 다음 우리는 new_list 또는 구조체를해야합니다

956
01:14:32,620 --> 01:14:41,080
구조체 목록 * new_list = malloc (sizeof (목록)).

957
01:14:41,080 --> 01:14:44,920
난 오류 검사 무시하는거야,하지만 당신은 경우 그건 null을 확인해야합니다.

958
01:14:44,920 --> 01:14:50,540
가 가리 키도록거야 노드를 New_list -

959
01:14:50,540 --> 01:14:56,890
난 여기를 원 왜 오, 그게. 이 두 번째 구조체 목록을 가리 키도록거야.

960
01:14:56,890 --> 01:15:02,380
그 목록 작업을 연결 단지 방법입니다.

961
01:15:02,380 --> 01:15:04,810
이 정수 연결리스트와 동일합니다

962
01:15:04,810 --> 01:15:06,960
를 제외하고 우리는 노드 *로 정수를 대체하고 있습니다.

963
01:15:06,960 --> 01:15:11,040
그것은 정확히 같은거야.

964
01:15:11,040 --> 01:15:15,100
그럼 new_list 우리 new_list 노드의 값

965
01:15:15,100 --> 01:15:19,120
현재 -> 오른쪽 될 것입니다.

966
01:15:19,120 --> 01:15:24,280
우리의 가치 new_list -> 옆에있는 우리의 원본 목록 될 것입니다,

967
01:15:24,280 --> 01:15:30,760
그리고 우리는 new_list를 가리 키도록 목록을 업데이트거야.

968
01:15:30,760 --> 01:15:33,650
>> 이제 우리는, 당기는 가지 방법의 일종이 필요합니다

969
01:15:33,650 --> 01:15:37,020
우리는 전체 왼쪽 하위 트리를 통과 한 것.

970
01:15:37,020 --> 01:15:40,480
이제 우리는, 그것을 물건을 꺼내야

971
01:15:40,480 --> 01:15:43,850
같은 현재이 Null입니다, 우리는 False를 반환하지 않습니다.

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
우리가 현재보고있는 것은 null이되지 않습니다

979
01:16:17,090 --> 01:16:22,340
대신 우리는 우리의 목록 자체가 null이 될 때까지 계속해서 이동거야.

980
01:16:22,340 --> 01:16:25,680
목록은 널 (null)가되는 것을 포기 끝나는면

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
목록 -> 다음은 null가 될 것입니다.

986
01:17:02,860 --> 01:17:07,580
이제 목록은 동일한 null을하지 않지만.

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
그 노드가 우리가 찾는 값이 있으면, 우리는 TRUE를 반환 할 수 있습니다.

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
그들은 null이 아니었다,면

1009
01:18:45,160 --> 01:18:47,950
우리의 루트 포인터가 두 가지 점을 지적, 경우

1010
01:18:47,950 --> 01:18:51,670
목록이 null가되는 것을 포기 끝나는 그래서 처음에는 우리가 뭔가를 꺼냈다.

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
한 번에 true 또는 false 반환하기 전에, 우리는 필요

1037
01:20:53,880 --> 01:20:57,360
우리 연결리스트를 통해 반복하고 항상 여기, 내가, 추측

1038
01:20:57,360 --> 01:21:03,900
우리 현재 바로 동일하지 않을 경우, 이제 우리가 확보 할을 추가

1039
01:21:03,900 --> 01:21:09,600
현재 때문에, 잘, 우리는 완전히 목록을 잊어 버렸 을까? 그래.

1040
01:21:09,600 --> 01:21:12,880
그럼 우리가 여기서하고 싶은거야.

1041
01:21:12,880 --> 01:21:16,730
포인터가 어디있어?

1042
01:21:16,730 --> 01:21:23,320
현재는 있었어요 - 우리가 구조체 목록에 * 10 다음 목록을 동일 싶습니다.

1043
01:21:23,320 --> 01:21:29,240
무료 목록, 목록 = 임시.

1044
01:21:29,240 --> 01:21:32,820
그리고 경우에 우리가 TRUE를 반환 곳, 우리는 반복을해야하나요

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]