1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Section 7: Plus confortable]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Université de Harvard]

3
00:00:05,090 --> 00:00:07,930
[C'est CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Très bien. Donc, comme je l'ai dit dans mon email,

5
00:00:10,110 --> 00:00:14,060
cela va être une section binary-tree-d'œuvre.

6
00:00:14,060 --> 00:00:16,820
Mais il n'ya pas que de nombreuses questions.

7
00:00:16,820 --> 00:00:18,920
Donc, nous allons essayer de tirer chaque question

8
00:00:18,920 --> 00:00:25,430
et entrer dans le détail douloureuse de toutes les meilleures façons de faire les choses.

9
00:00:25,430 --> 00:00:31,200
Ainsi, dès le début, nous passons par des exemples de dessins d'arbres binaires et d'autres choses.

10
00:00:31,200 --> 00:00:35,970
Donc, ici, «Se rappeler qu'un arbre binaire possède des nœuds semblables à ceux d'une liste chaînée,

11
00:00:35,970 --> 00:00:38,150
sauf qu'au lieu d'un pointeur, il ya deux: un pour «enfant» de la gauche

12
00:00:38,150 --> 00:00:41,950
et l'autre pour le droit "enfant". "

13
00:00:41,950 --> 00:00:45,630
Ainsi, un arbre binaire, c'est comme une liste chaînée,

14
00:00:45,630 --> 00:00:47,910
l'exception de la structure va avoir deux pointeurs.

15
00:00:47,910 --> 00:00:51,390
Il ya des arbres ternaires, qui vont avoir trois pointeurs,

16
00:00:51,390 --> 00:00:56,540
il ya des arbres n-aires, qui ont seulement un pointeur générique

17
00:00:56,540 --> 00:01:00,320
que vous aurez ensuite à malloc être assez grande pour avoir

18
00:01:00,320 --> 00:01:04,840
pointeurs suffisamment à tous les enfants possibles.

19
00:01:04,840 --> 00:01:08,200
Donc arbre binaire arrive juste pour avoir un nombre constant de deux.

20
00:01:08,200 --> 00:01:11,260
Si vous voulez, vous pouvez donner une liste chaînée comme un arbre unaire,

21
00:01:11,260 --> 00:01:15,360
mais je ne pense pas que quiconque appelle ça.

22
00:01:15,360 --> 00:01:18,060
«Dessinez un diagramme des boîtes-et-flèches d'un nœud de l'arbre binaire

23
00:01:18,060 --> 00:01:24,110
contenant le numéro préféré de Nate, 7, où chaque enfant pointeur est nul. "

24
00:01:24,110 --> 00:01:27,780
Ainsi, le mode iPad.

25
00:01:27,780 --> 00:01:30,280
>> Ça va être assez simple.

26
00:01:30,280 --> 00:01:36,150
Nous allons juste faire un nœud, je vais la dessiner comme un carré.

27
00:01:36,150 --> 00:01:38,730
Et je vais tirer les valeurs ici.

28
00:01:38,730 --> 00:01:41,090
Ainsi, la valeur sera déposée à cet endroit,

29
00:01:41,090 --> 00:01:44,770
et puis ici-bas, nous aurons le pointeur de la gauche sur la gauche et la droite pointeur sur la droite.

30
00:01:44,770 --> 00:01:50,430
Et il est très bien si la convention d'appeler la gauche et la droite, les noms pointeur.

31
00:01:50,430 --> 00:01:52,460
Ces deux vont être nulle.

32
00:01:52,460 --> 00:01:57,870
Cela va juste être nulle, et qui va juste être nulle.

33
00:01:57,870 --> 00:02:03,630
D'accord. Donc, retour à ici.

34
00:02:03,630 --> 00:02:05,700
«Avec une liste chaînée, nous n'avons eu à stocker un pointeur

35
00:02:05,700 --> 00:02:09,639
le premier nœud de la liste dans l'ordre de se rappeler toute la liste liée, ou toute la liste.

36
00:02:09,639 --> 00:02:11,650
De même, avec des arbres, il suffit de stocker un pointeur

37
00:02:11,650 --> 00:02:13,420
à un seul nœud dans le but de mémoriser l'arbre tout entier.

38
00:02:13,420 --> 00:02:15,980
Ce nœud est calle la «racine» de l'arbre.

39
00:02:15,980 --> 00:02:18,320
S'appuyer sur le diagramme d'avant ou de dessiner un nouveau

40
00:02:18,320 --> 00:02:21,690
de telle sorte que vous avez une représentation boîtes-et-flèches d'un arbre binaire

41
00:02:21,690 --> 00:02:25,730
avec la valeur 7, puis 3 dans la gauche,

42
00:02:25,730 --> 00:02:32,760
puis 9 à droite, puis 6 sur le droit de la 3 ".

43
00:02:32,760 --> 00:02:34,810
Voyons voir si je peux me rappeler tout cela dans ma tête.

44
00:02:34,810 --> 00:02:37,670
Donc cela va être notre racine ici.

45
00:02:37,670 --> 00:02:41,600
Nous aurons quelques pointeur quelque part, quelque chose que nous appellerons racine,

46
00:02:41,600 --> 00:02:45,140
et il pointe vers ce type.

47
00:02:45,140 --> 00:02:48,490
Maintenant, pour faire un nouveau noeud,

48
00:02:48,490 --> 00:02:52,870
qu'est-ce que nous avons, 3 à gauche?

49
00:02:52,870 --> 00:02:57,140
Ainsi, un nouveau noeud avec 3, et il souligne initialement nulle.

50
00:02:57,140 --> 00:02:59,190
Je vais mettre N.

51
00:02:59,190 --> 00:03:02,250
Maintenant, nous voulons faire cela, allez à gauche de 7.

52
00:03:02,250 --> 00:03:06,840
Donc, nous changeons ce pointeur pour pointer désormais à ce type.

53
00:03:06,840 --> 00:03:12,420
Et nous faisons de même. Nous voulons un 9 par ici

54
00:03:12,420 --> 00:03:14,620
qui, au départ juste dit nulle.

55
00:03:14,620 --> 00:03:19,600
Nous allons changer ce pointeur, pointez sur 9,

56
00:03:19,600 --> 00:03:23,310
et maintenant nous voulons mettre 6 à la droite de 3.

57
00:03:23,310 --> 00:03:32,170
Donc, ça va - faire un 6.

58
00:03:32,170 --> 00:03:34,310
Et ce gars il remarquer.

59
00:03:34,310 --> 00:03:38,320
D'accord. Donc, c'est tout ce qu'il nous demande de faire.

60
00:03:38,320 --> 00:03:42,770
>> Maintenant, nous allons passer en revue certains termes.

61
00:03:42,770 --> 00:03:46,690
Nous avons déjà parlé de la façon la racine de l'arbre est le nœud de plus haut niveau dans l'arborescence.

62
00:03:46,690 --> 00:03:54,720
Le contenant 7. Les noeuds dans la partie inférieure de l'arbre sont appelés les feuilles.

63
00:03:54,720 --> 00:04:01,240
Tout nœud qui vient de nulle comme ses enfants est une feuille.

64
00:04:01,240 --> 00:04:03,680
Il est donc possible, si notre arbre binaire est juste un noeud unique,

65
00:04:03,680 --> 00:04:10,130
qu'un arbre est une feuille, et c'est tout.

66
00:04:10,130 --> 00:04:12,060
"La 'hauteur' de l'arbre est le nombre de sauts que vous avez à faire

67
00:04:12,060 --> 00:04:16,620
à obtenir à partir du haut de la feuille. "

68
00:04:16,620 --> 00:04:18,640
Nous allons entrer, en une seconde, la différence

69
00:04:18,640 --> 00:04:21,940
entre les arbres binaires symétriques et asymétriques,

70
00:04:21,940 --> 00:04:29,470
mais pour l'instant, la hauteur totale de cet arbre

71
00:04:29,470 --> 00:04:34,520
Je dirais 3, mais si vous comptez le nombre de sauts

72
00:04:34,520 --> 00:04:39,710
vous avez à faire pour arriver à 9, alors c'est vraiment seulement une hauteur de 2.

73
00:04:39,710 --> 00:04:43,340
À l'heure actuelle il s'agit d'un arbre binaire asymétrique,

74
00:04:43,340 --> 00:04:49,840
mais nous allons parlé équilibré quand il arrive à être pertinent.

75
00:04:49,840 --> 00:04:52,040
Alors maintenant, nous pouvons parler de nœuds dans une arborescence en termes

76
00:04:52,040 --> 00:04:54,700
par rapport aux autres noeuds dans l'arbre.

77
00:04:54,700 --> 00:04:59,730
Alors maintenant, nous avons des parents, des enfants, des frères et sœurs, ascendants et descendants.

78
00:04:59,730 --> 00:05:05,650
Ils sont de bon sens assez commun, ce qu'ils veulent dire.

79
00:05:05,650 --> 00:05:09,610
Si nous demandons - ses parents.

80
00:05:09,610 --> 00:05:12,830
Alors, quelle est la société mère de 3?

81
00:05:12,830 --> 00:05:16,090
[Etudiants] 7. Ouais >>. Le parent va juste être ce que fait pour vous.

82
00:05:16,090 --> 00:05:20,510
Puis ce sont les enfants de 7?

83
00:05:20,510 --> 00:05:23,860
[Etudiants] 3 et 9. Ouais >>.

84
00:05:23,860 --> 00:05:26,460
Notez que les «enfants» signifie littéralement les enfants,

85
00:05:26,460 --> 00:05:31,010
donc 6 ne s'applique pas, parce que c'est comme un petit enfant.

86
00:05:31,010 --> 00:05:35,540
Mais alors, si nous allons descendants, alors quelles sont les descendants des 7?

87
00:05:35,540 --> 00:05:37,500
[Etudiants] 3, 6 et 9. Ouais >>.

88
00:05:37,500 --> 00:05:42,330
Les descendants du nœud racine va être tout dans l'arbre,

89
00:05:42,330 --> 00:05:47,950
sauf peut-être le nœud racine elle-même, si vous ne voulez pas de considérer que le descendant.

90
00:05:47,950 --> 00:05:50,750
Et enfin, les ancêtres, c'est donc la direction opposée.

91
00:05:50,750 --> 00:05:55,740
Alors, quelles sont les ancêtres de 6?

92
00:05:55,740 --> 00:05:58,920
[Etudiants] 3 et 7. Ouais >>. 9 n'est pas inclus.

93
00:05:58,920 --> 00:06:02,520
C'est simplement le dos lignée directe à la racine

94
00:06:02,520 --> 00:06:13,230
va être vos ancêtres.

95
00:06:13,230 --> 00:06:16,300
>> "On dit qu'un arbre binaire est« ordonné »si pour chaque nœud de l'arbre,

96
00:06:16,300 --> 00:06:19,530
tous ses descendants à gauche ont des valeurs moindres

97
00:06:19,530 --> 00:06:22,890
et tous ceux de droite ont des valeurs supérieures.

98
00:06:22,890 --> 00:06:27,060
Par exemple, l'arbre ci-dessus est commandé mais il n'est pas le seul arrangement possible ordonné. "

99
00:06:27,060 --> 00:06:30,180
Avant d'en arriver là,

100
00:06:30,180 --> 00:06:36,420
un arbre binaire ordonné est également connu comme un arbre binaire de recherche.

101
00:06:36,420 --> 00:06:38,660
Ici, il nous arrive d'être l'appeler un arbre binaire ordonné,

102
00:06:38,660 --> 00:06:41,850
mais je n'ai jamais entendu dire qu'il a appelé un arbre binaire ordonné avant,

103
00:06:41,850 --> 00:06:46,650
et sur un questionnaire que nous sommes beaucoup plus susceptibles de mettre arbre binaire de recherche.

104
00:06:46,650 --> 00:06:49,250
Ils sont l'un et le même,

105
00:06:49,250 --> 00:06:54,580
et il est important que vous la distinction entre arbre binaire et arbre binaire de recherche.

106
00:06:54,580 --> 00:06:58,830
Un arbre binaire est juste un arbre qui pointe vers deux choses.

107
00:06:58,830 --> 00:07:02,120
Chaque nœud fait à deux choses.

108
00:07:02,120 --> 00:07:06,310
Il n'ya pas de raisonner sur les valeurs qui elle pointe.

109
00:07:06,310 --> 00:07:11,370
Donc, comme ici, car c'est un arbre binaire de recherche,

110
00:07:11,370 --> 00:07:14,030
nous savons que si nous allons à gauche de 7,

111
00:07:14,030 --> 00:07:16,670
alors toutes les valeurs que l'on peut éventuellement atteindre

112
00:07:16,670 --> 00:07:19,310
en allant de gauche 7 à être inférieur à 7.

113
00:07:19,310 --> 00:07:24,070
Notez que toutes les valeurs inférieures à 7 sont 3 et 6.

114
00:07:24,070 --> 00:07:26,040
Ce sont tous sur la gauche de 7.

115
00:07:26,040 --> 00:07:29,020
Si nous allons à droite de 7, tout doit être supérieur à 7,

116
00:07:29,020 --> 00:07:33,220
si 9 est à la droite de 7, de sorte que nous sommes bons.

117
00:07:33,220 --> 00:07:36,150
Ce n'est pas le cas pour un arbre binaire,

118
00:07:36,150 --> 00:07:40,020
pour un arbre binaire ordinaire, nous pouvons juste 3 en haut, 7 à gauche,

119
00:07:40,020 --> 00:07:47,630
9 vers la gauche de 7, il n'y a pas de commande de valeurs quelconques.

120
00:07:47,630 --> 00:07:56,140
Maintenant, nous ne réalisons pas cela parce que c'est fastidieux et inutile,

121
00:07:56,140 --> 00:07:59,400
mais «essayer d'en tirer le plus d'arbres ordonnés comme vous pouvez le penser

122
00:07:59,400 --> 00:08:01,900
en utilisant les numéros 7, 9, 3, et 6.

123
00:08:01,900 --> 00:08:06,800
Combien d'arrangements distincts sont-ils? Quelle est la hauteur de chacun d'eux? "

124
00:08:06,800 --> 00:08:10,480
>> Nous ferons un couple, mais l'idée principale est,

125
00:08:10,480 --> 00:08:16,530
ce n'est en aucun cas une représentation unique d'un arbre binaire contenant ces valeurs.

126
00:08:16,530 --> 00:08:22,760
Tous nous avons besoin est un arbre binaire qui contient 7, 3, 6 et 9.

127
00:08:22,760 --> 00:08:25,960
Une autre possible valable serait la racine est 3,

128
00:08:25,960 --> 00:08:30,260
allez vers la gauche et il est 6, allez à gauche et il a 7 ans,

129
00:08:30,260 --> 00:08:32,730
allez vers la gauche et il est 9.

130
00:08:32,730 --> 00:08:36,169
C'est un arbre binaire de recherche tout à fait valable.

131
00:08:36,169 --> 00:08:39,570
Ce n'est pas très utile, parce que c'est comme une liste chaînée

132
00:08:39,570 --> 00:08:43,750
et tous ces pointeurs sont juste nul.

133
00:08:43,750 --> 00:08:48,900
Mais c'est un arbre valide. Ouais?

134
00:08:48,900 --> 00:08:51,310
[Étudiants] Ne pas les valeurs doivent être plus à droite?

135
00:08:51,310 --> 00:08:56,700
Ou est-ce -? Ceux-ci >> je voulais aller dans l'autre sens.

136
00:08:56,700 --> 00:09:00,960
Il ya aussi - oui, nous allons passer cela.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Bonne prise.

138
00:09:07,770 --> 00:09:11,730
Il reste encore à obéir à ce que un arbre de recherche binaire est censé faire.

139
00:09:11,730 --> 00:09:15,650
Donc tout ce qui précède doit être inférieur à un nœud donné.

140
00:09:15,650 --> 00:09:23,180
Nous pourrions tout simplement déplacer, disons, le 6 et le mettre ici.

141
00:09:23,180 --> 00:09:26,880
Non, nous ne pouvons pas. Pourquoi dois-je continuer à le faire?

142
00:09:26,880 --> 00:09:35,350
Faisons - est ici 6, voici 7, 6 points à 3.

143
00:09:35,350 --> 00:09:39,290
Ceci est encore un arbre binaire valide recherche.

144
00:09:39,290 --> 00:09:49,260
Quel est le problème si je - nous allons voir si je peux arriver à un arrangement.

145
00:09:49,260 --> 00:09:52,280
Ouais, d'accord. Alors quel est le problème avec cet arbre?

146
00:09:52,280 --> 00:10:08,920
Je crois que je vous ai déjà donné une indication qu'il ya quelque chose de mal à cela.

147
00:10:08,920 --> 00:10:14,430
Pourquoi dois-je continuer à le faire?

148
00:10:14,430 --> 00:10:18,510
D'accord. Cela semble raisonnable.

149
00:10:18,510 --> 00:10:22,590
Si nous regardons chaque nœud, comme 7, puis vers la gauche de la figure 7 est un 3.

150
00:10:22,590 --> 00:10:24,960
Nous avons donc 3, la chose à la droite de la figure 3 est un 6.

151
00:10:24,960 --> 00:10:27,750
Et si vous regardez à 6, la seule chose à la droite de la figure 6 est un 9.

152
00:10:27,750 --> 00:10:30,910
Alors, pourquoi n'est-ce pas un arbre binaire valide la recherche?

153
00:10:30,910 --> 00:10:36,330
[Etudiants] 9 est toujours à la gauche de 7. Ouais >>.

154
00:10:36,330 --> 00:10:43,710
Cela doit être vrai que toutes les valeurs que vous pouvez éventuellement atteindre en allant vers la gauche de 7 représentent moins de 7.

155
00:10:43,710 --> 00:10:49,120
Si nous allons à gauche de 7, nous arrivons à 3 et nous pouvons encore obtenir à 6,

156
00:10:49,120 --> 00:10:52,520
nous pouvons encore obtenir à 9, mais en ayant passé moins de 7,

157
00:10:52,520 --> 00:10:55,070
nous ne devrions pas être en mesure d'arriver à un chiffre qui est supérieur à 7.

158
00:10:55,070 --> 00:10:59,830
Donc, ce n'est pas un arbre binaire valide recherche.

159
00:10:59,830 --> 00:11:02,330
>> Mon frère avait fait une question d'entrevue

160
00:11:02,330 --> 00:11:07,760
qui était essentiellement cela, il suffit de code quelque chose pour valider

161
00:11:07,760 --> 00:11:10,500
si un arbre est un arbre binaire de recherche,

162
00:11:10,500 --> 00:11:13,580
et la première chose qu'il a fait était juste vérifier

163
00:11:13,580 --> 00:11:17,020
si la gauche et la droite sont corrects, puis itérer là-bas.

164
00:11:17,020 --> 00:11:19,700
Mais vous ne pouvez pas faire cela, vous devez garder une trace

165
00:11:19,700 --> 00:11:22,550
du fait que, maintenant que je suis allé à gauche de 7,

166
00:11:22,550 --> 00:11:26,340
tout dans ce sous-arbre doit être inférieur à 7.

167
00:11:26,340 --> 00:11:28,430
L'algorithme correct a besoin de garder une trace

168
00:11:28,430 --> 00:11:35,970
des limites à ce que les valeurs peuvent éventuellement tomber po

169
00:11:35,970 --> 00:11:38,360
Nous n'allons pas passer par chacun d'eux.

170
00:11:38,360 --> 00:11:41,630
Il ya une relation de récurrence agréable,

171
00:11:41,630 --> 00:11:44,810
même si nous n'avons pas obtenu de ceux-ci, ou nous n'arriverons pas à ceux qui,

172
00:11:44,810 --> 00:11:47,030
définir combien il ya effectivement.

173
00:11:47,030 --> 00:11:53,180
Donc, il ya 14 d'entre eux.

174
00:11:53,180 --> 00:11:56,020
L'idée de la façon dont vous le feriez est mathématiquement comme,

175
00:11:56,020 --> 00:11:59,770
vous pouvez choisir n'importe quel seul à être le nœud racine,

176
00:11:59,770 --> 00:12:03,160
et puis si je prends 7 pour être le nœud racine,

177
00:12:03,160 --> 00:12:08,150
puis il ya, disons, quelques chiffres qui peuvent aller être mon nœud de gauche,

178
00:12:08,150 --> 00:12:10,440
et il ya des chiffres qui peuvent être mon nœud de droit,

179
00:12:10,440 --> 00:12:15,090
mais si je l'ai n le nombre total, le montant qui peut aller vers la gauche

180
00:12:15,090 --> 00:12:18,820
plus le montant qui peut aller vers la droite est n - 1.

181
00:12:18,820 --> 00:12:26,130
Ainsi, des nombres restants, ils doivent être en mesure d'aller soit vers la gauche ou la droite.

182
00:12:26,130 --> 00:12:31,580
Il semble difficile que, si je mets 3 premiers alors tout doit aller vers la gauche,

183
00:12:31,580 --> 00:12:35,080
mais si je mets 7 puis certaines choses ne peuvent aller à gauche la et certaines choses peuvent aller vers la droite.

184
00:12:35,080 --> 00:12:39,570
Et par '3 'abord, je vise tout peut aller vers la droite.

185
00:12:39,570 --> 00:12:42,350
C'est vraiment, vous avez juste à penser que,

186
00:12:42,350 --> 00:12:47,980
combien de choses peuvent aller au niveau suivant de l'arbre.

187
00:12:47,980 --> 00:12:50,420
Et il sort à 14; ou vous pouvez dessiner chacun d'entre eux,

188
00:12:50,420 --> 00:12:54,650
et alors vous aurez 14.

189
00:12:54,650 --> 00:13:01,120
>> Pour en revenir ici,

190
00:13:01,120 --> 00:13:03,510
«Ordonné arbres binaires sont cool parce qu'on peut chercher dans les

191
00:13:03,510 --> 00:13:06,910
d'une manière très semblable à la recherche sur un tableau trié.

192
00:13:06,910 --> 00:13:10,120
Pour ce faire, nous partons à la racine et de travailler notre chemin vers le bas de l'arbre

193
00:13:10,120 --> 00:13:13,440
vers les feuilles, vérifier les valeurs de chaque nœud à l'encontre des valeurs que nous sommes à la recherche d'.

194
00:13:13,440 --> 00:13:15,810
Si la valeur du nœud actuel est inférieur à la valeur que nous recherchons,

195
00:13:15,810 --> 00:13:18,050
vous aller ensuite à l'enfant le droit du nœud.

196
00:13:18,050 --> 00:13:20,030
Sinon, vous allez au fils gauche du nœud.

197
00:13:20,030 --> 00:13:22,800
À un certain point, vous aurez soit trouver la valeur que vous cherchez, ou vous tomberez sur un nul,

198
00:13:22,800 --> 00:13:28,520
indiquant la valeur n'est pas dans l'arbre. "

199
00:13:28,520 --> 00:13:32,450
Je dois redessiner l'arbre que nous avions avant, qui va prendre une seconde.

200
00:13:32,450 --> 00:13:38,280
Mais nous voulons rechercher si 6, 10 et 1 sont dans l'arbre.

201
00:13:38,280 --> 00:13:49,180
Alors qu'est-ce que c'était, 7, 9, 3, 6. D'accord.

202
00:13:49,180 --> 00:13:52,730
Les chiffres que vous souhaitez rechercher, nous voulons examiner en hausse de 6.

203
00:13:52,730 --> 00:13:55,440
Comment cela fonctionne-t algorithme?

204
00:13:55,440 --> 00:14:03,040
Eh bien, nous avons aussi des pointeur de racine de notre arbre.

205
00:14:03,040 --> 00:14:12,460
Et nous irions à la racine et de dire, est-ce une valeur égale à la valeur que nous cherchons?

206
00:14:12,460 --> 00:14:15,000
Nous sommes donc à la recherche de 6, donc ce n'est pas égale.

207
00:14:15,000 --> 00:14:20,140
Nous avons donc continuer, et maintenant nous dire, d'accord, si 6 est inférieur à 7.

208
00:14:20,140 --> 00:14:23,940
Est-ce que cela veut dire que nous voulons aller vers la gauche, ou voulons-nous aller à droite?

209
00:14:23,940 --> 00:14:27,340
[Étudiants] Gauche. Ouais >>.

210
00:14:27,340 --> 00:14:33,340
Il est beaucoup plus facile, tout ce que vous avez à faire est de dessiner un nœud possible de l'arbre

211
00:14:33,340 --> 00:14:37,760
et puis vous ne - au lieu d'essayer de penser dans votre tête,

212
00:14:37,760 --> 00:14:40,020
ok, si c'est moins, puis-je aller à gauche ou aller à droite,

213
00:14:40,020 --> 00:14:43,030
simplement en regardant cette image, il est très clair que je dois aller vers la gauche

214
00:14:43,030 --> 00:14:47,700
si le noeud est supérieure à la valeur que je suis à la recherche.

215
00:14:47,700 --> 00:14:52,600
Alors vous allez vers la gauche, maintenant je suis à 3.

216
00:14:52,600 --> 00:14:57,770
Je tiens à - 3 est inférieure à la valeur que je cherche, qui est de 6.

217
00:14:57,770 --> 00:15:03,420
Alors on va vers la droite, et maintenant je me retrouve à 6,

218
00:15:03,420 --> 00:15:07,380
qui est la valeur que je cherche, donc je retourne vrai.

219
00:15:07,380 --> 00:15:15,760
La valeur suivante, je vais chercher, c'est 10.

220
00:15:15,760 --> 00:15:23,230
D'accord. Donc, 10, désormais, va - couper que - va suivre la racine.

221
00:15:23,230 --> 00:15:27,670
Maintenant, 10 va être supérieur à 7, donc je veux regarder à droite.

222
00:15:27,670 --> 00:15:31,660
Je vais venir ici, 10 va être supérieur à 9,

223
00:15:31,660 --> 00:15:34,520
donc je vais avoir à regarder vers la droite.

224
00:15:34,520 --> 00:15:42,100
Je viens par ici, mais ici je suis maintenant à zéro.

225
00:15:42,100 --> 00:15:44,170
Que dois-je faire si j'ai touché nulle?

226
00:15:44,170 --> 00:15:47,440
[Étudiants] Retour faux? Ouais >>. Je n'ai pas trouvé 10.

227
00:15:47,440 --> 00:15:49,800
1 va être un cas presque identique,

228
00:15:49,800 --> 00:15:51,950
sauf qu'il va juste être retourné, au lieu de regarder

229
00:15:51,950 --> 00:15:56,540
sur le côté droit, je vais regarder vers le bas sur le côté gauche.

230
00:15:56,540 --> 00:16:00,430
>> Maintenant, je pense que nous obtenons réellement le code.

231
00:16:00,430 --> 00:16:04,070
Voici où - ouvrir l'appareil CS50 et naviguer dans votre chemin,

232
00:16:04,070 --> 00:16:07,010
mais vous pouvez aussi le faire dans l'espace.

233
00:16:07,010 --> 00:16:09,170
C'est probablement idéal pour le faire dans l'espace,

234
00:16:09,170 --> 00:16:13,760
car nous pouvons travailler dans l'espace.

235
00:16:13,760 --> 00:16:19,170
"Nous allons d'abord besoin d'une définition de type nouveau pour un nœud de l'arbre binaire contenant les valeurs int.

236
00:16:19,170 --> 00:16:21,400
Utilisation du passe-partout typedef ci-dessous,

237
00:16:21,400 --> 00:16:24,510
créer une définition de type nouveau pour un noeud dans un arbre binaire.

238
00:16:24,510 --> 00:16:27,930
Si vous êtes coincé. . . "Blah, blah, blah. D'accord.

239
00:16:27,930 --> 00:16:30,380
Donc, il faut mettre le passe-partout ici,

240
00:16:30,380 --> 00:16:41,630
typedef struct noeud, et un noeud. Ouais, d'accord.

241
00:16:41,630 --> 00:16:44,270
Alors, quels sont les domaines que nous allons voulons dans notre noeud?

242
00:16:44,270 --> 00:16:46,520
[Étudiants] Int puis deux pointeurs?

243
00:16:46,520 --> 00:16:49,700
>> Int valeur, deux pointeurs? Comment puis-je écrire les pointeurs?

244
00:16:49,700 --> 00:16:58,440
[Étudiants] Struct. >> Je devrais effectuer un zoom avant Ouais, donc noeud struct * à gauche,

245
00:16:58,440 --> 00:17:01,320
struct noeud * et droite.

246
00:17:01,320 --> 00:17:03,460
Et souvenez-vous de la discussion de la dernière fois,

247
00:17:03,460 --> 00:17:15,290
que cela n'a aucun sens, cela n'a aucun sens,

248
00:17:15,290 --> 00:17:18,270
cela n'a aucun sens.

249
00:17:18,270 --> 00:17:25,000
Vous devez tout ce qu'il ya dans le but de définir cette structure récursive.

250
00:17:25,000 --> 00:17:27,970
Bon, alors c'est ce que notre arbre va ressembler.

251
00:17:27,970 --> 00:17:37,670
Si nous faisions un arbre ternaire, puis un nœud pourrait ressembler b1, b2, b3 struct noeud *,

252
00:17:37,670 --> 00:17:43,470
où b est une branche - en fait, j'ai plus entendu gauche, milieu, droite, mais peu importe.

253
00:17:43,470 --> 00:17:55,610
Nous ne se soucient binaire, droite, gauche.

254
00:17:55,610 --> 00:17:59,110
«Maintenant déclarer une variable de nœud mondial * de la racine de l'arbre."

255
00:17:59,110 --> 00:18:01,510
Donc, nous n'allons pas le faire.

256
00:18:01,510 --> 00:18:08,950
Afin de rendre les choses un peu plus difficile et plus généralisée,

257
00:18:08,950 --> 00:18:11,570
nous n'aurons pas une variable de nœud mondial.

258
00:18:11,570 --> 00:18:16,710
Au lieu de cela, en principal, nous déclarons toutes nos affaires nœud,

259
00:18:16,710 --> 00:18:20,500
et cela signifie que ci-dessous, lorsque nous avons commencer à courir

260
00:18:20,500 --> 00:18:23,130
notre fonction contains et notre fonction d'insertion,

261
00:18:23,130 --> 00:18:27,410
au lieu de nos contient une fonction simplement en utilisant cette variable de nœud mondial,

262
00:18:27,410 --> 00:18:34,280
nous allons devoir le prendre comme argument l'arbre que nous voulons c'est de traiter.

263
00:18:34,280 --> 00:18:36,650
Avoir la variable globale était censé rendre les choses plus faciles.

264
00:18:36,650 --> 00:18:42,310
Nous allons faire les choses plus difficiles.

265
00:18:42,310 --> 00:18:51,210
Maintenant, prenez une minute pour simplement faire ce genre de chose,

266
00:18:51,210 --> 00:18:57,690
où à l'intérieur du principal que vous souhaitez créer cet arbre, et c'est tout ce que vous voulez faire.

267
00:18:57,690 --> 00:19:04,530
Essayez de construire cet arbre dans votre fonction principale.

268
00:19:42,760 --> 00:19:47,610
>> D'accord. Donc, vous n'avez même pas besoin d'avoir construit l'arbre tout le chemin encore.

269
00:19:47,610 --> 00:19:49,840
Mais ce que quelqu'un a quelque chose que je pouvais tirer vers le haut

270
00:19:49,840 --> 00:20:03,130
pour montrer comment on peut commencer à construire un tel arbre?

271
00:20:03,130 --> 00:20:08,080
[Étudiants] de quelqu'un frapper, en essayant de sortir.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Toute l'aise avec leur construction de l'arbre?

273
00:20:13,100 --> 00:20:15,520
[Étudiants] Bien sûr. Ce n'est pas fait. >> C'est bien. Nous pouvons simplement terminer -

274
00:20:15,520 --> 00:20:26,860
oh, pouvez-vous l'enregistrer? Hourra.

275
00:20:26,860 --> 00:20:32,020
Nous avons donc ici - oh, je suis un peu coupé.

276
00:20:32,020 --> 00:20:34,770
Suis-je un zoom avant?

277
00:20:34,770 --> 00:20:37,730
Zoomer, faire défiler sur. >> J'ai une question. Ouais >>?

278
00:20:37,730 --> 00:20:44,410
[Étudiants] Lorsque vous définissez une structure, sont des choses comme initialisé à quelque chose?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No. >> Okay. Donc, vous devez initialiser -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No. Lorsque vous définissez ou lorsque vous déclarez une structure,

281
00:20:50,450 --> 00:20:55,600
il n'est pas initialisé par défaut; c'est comme si vous déclarez un int.

282
00:20:55,600 --> 00:20:59,020
C'est exactement la même chose. C'est comme si chacun de ses domaines individuels

283
00:20:59,020 --> 00:21:04,460
peut avoir une valeur ordures dans celui-ci. >> Et est-il possible de définir - ou de déclarer une structure

284
00:21:04,460 --> 00:21:07,740
de façon que le fait de les initialiser?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Oui. Ainsi, la syntaxe d'initialisation de raccourci

286
00:21:13,200 --> 00:21:18,660
va ressembler -

287
00:21:18,660 --> 00:21:22,200
Il ya deux façons de le faire. Je pense que nous devrions le compiler

288
00:21:22,200 --> 00:21:25,840
pour faire Clang-vous le fait aussi.

289
00:21:25,840 --> 00:21:28,510
L'ordre des arguments qui vient dans la structure,

290
00:21:28,510 --> 00:21:32,170
vous mettez que l'ordre des arguments à l'intérieur de ces accolades.

291
00:21:32,170 --> 00:21:35,690
Donc, si vous voulez l'initialiser à 9 et à gauche sont nuls et puis à droite est nulle,

292
00:21:35,690 --> 00:21:41,570
il serait 9, null, null.

293
00:21:41,570 --> 00:21:47,890
L'alternative est, et l'éditeur n'aime pas cette syntaxe,

294
00:21:47,890 --> 00:21:50,300
et il pense que je veux un nouveau bloc,

295
00:21:50,300 --> 00:22:01,800
mais l'alternative est quelque chose comme -

296
00:22:01,800 --> 00:22:04,190
ici, je vais le mettre sur une nouvelle ligne.

297
00:22:04,190 --> 00:22:09,140
Vous pouvez explicitement dire, j'ai oublié la syntaxe exacte.

298
00:22:09,140 --> 00:22:13,110
Ainsi, vous pouvez explicitement appeler par leur nom, et dire:

299
00:22:13,110 --> 00:22:21,570
. Valeur c, ou. = 9,. NULL = gauche.

300
00:22:21,570 --> 00:22:24,540
Je suppose que ceux-ci doivent être des virgules.

301
00:22:24,540 --> 00:22:29,110
. Droite = NULL, alors cette façon, vous ne

302
00:22:29,110 --> 00:22:33,780
réellement besoin de connaître l'ordre de la structure,

303
00:22:33,780 --> 00:22:36,650
et quand vous lisez ceci, c'est beaucoup plus explicite

304
00:22:36,650 --> 00:22:41,920
sur ce que la valeur est en cours d'initialisation d'.

305
00:22:41,920 --> 00:22:44,080
>> Cela arrive à être l'une des choses que -

306
00:22:44,080 --> 00:22:49,100
oui, pour la plupart, C + + est un sur-ensemble de C.

307
00:22:49,100 --> 00:22:54,160
Vous pouvez prendre le code C, le déplacer vers C + +, et il devrait compiler.

308
00:22:54,160 --> 00:22:59,570
C'est l'une des choses que C + + ne prend pas en charge, afin que les gens ont tendance à ne pas le faire.

309
00:22:59,570 --> 00:23:01,850
Je ne sais pas si c'est la seule raison pour laquelle les gens ont tendance à ne pas le faire,

310
00:23:01,850 --> 00:23:10,540
mais au cas où j'avais besoin de l'utiliser nécessaires pour travailler avec C + + et je ne pouvais pas l'utiliser.

311
00:23:10,540 --> 00:23:14,000
Un autre exemple de quelque chose qui ne fonctionne pas avec C + + est

312
00:23:14,000 --> 00:23:16,940
comment malloc retourne un «void *», techniquement,

313
00:23:16,940 --> 00:23:20,200
mais vous pourriez simplement dire tout ce char * x = malloc,

314
00:23:20,200 --> 00:23:22,840
et il sera automatiquement converti en un char *.

315
00:23:22,840 --> 00:23:25,450
C'est fonte automatique ne se fait pas en C + +.

316
00:23:25,450 --> 00:23:28,150
Ce ne serait pas compiler, et vous auriez besoin de le dire explicitement

317
00:23:28,150 --> 00:23:34,510
char *, malloc, que ce soit, de le jeter à un char *.

318
00:23:34,510 --> 00:23:37,270
Il n'y a pas beaucoup de choses que C et C + + sont en désaccord sur,

319
00:23:37,270 --> 00:23:40,620
mais ce sont deux.

320
00:23:40,620 --> 00:23:43,120
Nous allons donc avec cette syntaxe.

321
00:23:43,120 --> 00:23:46,150
Mais même si nous n'avons pas aller avec cette syntaxe,

322
00:23:46,150 --> 00:23:49,470
ce qui est - peut-être le problème?

323
00:23:49,470 --> 00:23:52,170
[Étudiants] Je n'ai pas besoin de le déréférencer? Ouais >>.

324
00:23:52,170 --> 00:23:55,110
Rappelez-vous que la flèche a un déréférencement implicite,

325
00:23:55,110 --> 00:23:58,230
et donc quand nous sommes juste face à une struct,

326
00:23:58,230 --> 00:24:04,300
nous voulons utiliser. pour obtenir à l'intérieur du champ de la structure.

327
00:24:04,300 --> 00:24:07,200
Et la seule fois où nous utilisons flèche, c'est quand nous voulons faire -

328
00:24:07,200 --> 00:24:13,450
ainsi, la flèche est équivalent à -

329
00:24:13,450 --> 00:24:17,020
c'est ce qu'il aurait voulu dire si j'ai utilisé flèche.

330
00:24:17,020 --> 00:24:24,600
Tous les moyens flèche, ce déréférencement, maintenant je suis à un struct, et je peux obtenir sur le terrain.

331
00:24:24,600 --> 00:24:28,040
Soit obtenir le champ directement ou déréférencer et obtenir sur le terrain -

332
00:24:28,040 --> 00:24:30,380
Je suppose que ce doit être la valeur.

333
00:24:30,380 --> 00:24:33,910
Mais ici, je fais face à tout un struct, pas un pointeur vers une struct,

334
00:24:33,910 --> 00:24:38,780
et je ne peux donc pas utiliser la flèche.

335
00:24:38,780 --> 00:24:47,510
Mais ce genre de chose que nous pouvons faire pour tous les nœuds.

336
00:24:47,510 --> 00:24:55,790
Oh mon Dieu.

337
00:24:55,790 --> 00:25:09,540
C'est 6, 7, et 3.

338
00:25:09,540 --> 00:25:16,470
Ensuite, nous pouvons mettre en place les branches de notre arbre, nous pouvons avoir 7 -

339
00:25:16,470 --> 00:25:21,650
nous pouvons avoir, à sa gauche doit pointer vers 3.

340
00:25:21,650 --> 00:25:25,130
Alors, comment faisons-nous cela?

341
00:25:25,130 --> 00:25:29,320
[Etudiants, inintelligible] >> Oui. L'adresse de node3,

342
00:25:29,320 --> 00:25:34,170
et si vous n'avez pas d'adresse, il ne serait pas juste de compiler.

343
00:25:34,170 --> 00:25:38,190
Mais n'oubliez pas que ce sont des pointeurs vers les noeuds suivants.

344
00:25:38,190 --> 00:25:44,930
Le droit doit pointer à 9,

345
00:25:44,930 --> 00:25:53,330
et 3 doit pointer sur le droit à 6.

346
00:25:53,330 --> 00:25:58,480
Je pense que c'est tous ensemble. Des commentaires ou des questions?

347
00:25:58,480 --> 00:26:02,060
[Étudiant, inintelligible] La racine va être 7.

348
00:26:02,060 --> 00:26:08,210
Nous pouvons simplement dire nœud * ptr =

349
00:26:08,210 --> 00:26:14,160
ou de la racine, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Pour nos besoins, nous allons avoir affaire avec insert,

351
00:26:20,730 --> 00:26:25,490
alors nous allons vouloir écrire une fonction pour insérer dans cet arbre binaire

352
00:26:25,490 --> 00:26:34,230
et l'insert va inévitablement appeler malloc pour créer un nouveau nœud de cet arbre.

353
00:26:34,230 --> 00:26:36,590
Donc, les choses vont déraper avec le fait que certains nœuds

354
00:26:36,590 --> 00:26:38,590
sont actuellement dans la pile

355
00:26:38,590 --> 00:26:43,680
et les autres nœuds vont se retrouver sur le tas quand on les insérer.

356
00:26:43,680 --> 00:26:47,640
Ceci est tout à fait valable, mais la seule raison

357
00:26:47,640 --> 00:26:49,600
nous sommes en mesure de le faire sur la pile

358
00:26:49,600 --> 00:26:51,840
C'est parce que c'est un exemple artificiel que nous savons

359
00:26:51,840 --> 00:26:56,360
l'arbre est supposé être réalisé sous la forme 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Si nous n'avions pas cela, alors nous n'aurions pas à malloc en premier lieu.

361
00:27:02,970 --> 00:27:06,160
Comme nous le verrons un peu plus tard, nous devrions être malloc'ing.

362
00:27:06,160 --> 00:27:08,570
En ce moment il est parfaitement raisonnable de mettre sur la pile,

363
00:27:08,570 --> 00:27:14,750
mais nous allons changer cela en une implémentation de malloc.

364
00:27:14,750 --> 00:27:17,160
Ainsi, chacun de ceux-ci va maintenant être quelque chose comme

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

366
00:27:24,240 --> 00:27:28,040
Et maintenant, nous allons faire notre chèque.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Je ne voulais pas que -

368
00:27:34,010 --> 00:27:40,950
retourner 1, puis que nous pouvons faire node9-> parce que maintenant c'est un pointeur,

369
00:27:40,950 --> 00:27:45,300
valeur = 6, node9-> gauche = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> droite = NULL,

371
00:27:48,930 --> 00:27:51,410
et nous allons devoir le faire pour chacun de ces nœuds.

372
00:27:51,410 --> 00:27:57,490
Ainsi, au lieu, nous allons mettre à l'intérieur d'une fonction distincte.

373
00:27:57,490 --> 00:28:00,620
Appelons-le noeud * build_node,

374
00:28:00,620 --> 00:28:09,050
et cela est quelque peu similaire à l'API que nous offrons à codage de Huffman.

375
00:28:09,050 --> 00:28:12,730
Nous vous donnons fonctions initialiseur pour un arbre

376
00:28:12,730 --> 00:28:20,520
et deconstructor «fonctions» de ces arbres et les mêmes pour les forêts.

377
00:28:20,520 --> 00:28:22,570
>> Donc, ici, nous allons avoir une fonction d'initialisation

378
00:28:22,570 --> 00:28:25,170
pour compiler un nœud pour nous.

379
00:28:25,170 --> 00:28:29,320
Et il va chercher à peu près exactement comme ça.

380
00:28:29,320 --> 00:28:32,230
Et je vais même être paresseux et de ne pas changer le nom de la variable,

381
00:28:32,230 --> 00:28:34,380
même si node9 ne fait pas plus de sens.

382
00:28:34,380 --> 00:28:38,610
Oh, je suppose que la valeur node9 ne doit pas avoir été 6.

383
00:28:38,610 --> 00:28:42,800
Maintenant nous pouvons revenir node9.

384
00:28:42,800 --> 00:28:49,550
Et là, on doit retourner null.

385
00:28:49,550 --> 00:28:52,690
Tout le monde d'accord sur cette fonction build-a-noeud?

386
00:28:52,690 --> 00:28:59,780
Alors maintenant, nous pouvons simplement appeler cela de construire un nœud avec une valeur donnée et des pointeurs nuls.

387
00:28:59,780 --> 00:29:09,750
Maintenant, nous pouvons l'appeler ainsi, nous pouvons faire noeud * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Et nous allons le faire. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Et maintenant, nous voulons mettre en place les pointeurs mêmes,

391
00:29:39,330 --> 00:29:42,470
sauf que maintenant tout est déjà en termes de pointeurs

392
00:29:42,470 --> 00:29:48,480
donc plus besoin de l'adresse d'.

393
00:29:48,480 --> 00:29:56,300
D'accord. Alors, quelle est la dernière chose que je veux faire?

394
00:29:56,300 --> 00:30:03,850
Il s'agit d'une vérification des erreurs que je ne fais pas.

395
00:30:03,850 --> 00:30:06,800
Qu'est-ce que la construction noeud retour?

396
00:30:06,800 --> 00:30:11,660
[Étudiant, inintelligible] >> Oui. Si malloc échoué, il va retourner null.

397
00:30:11,660 --> 00:30:16,460
Donc, je vais le mettre lazily ici au lieu de faire un état pour chacun.

398
00:30:16,460 --> 00:30:22,320
Si (node9 == NULL, ou - encore plus simple,

399
00:30:22,320 --> 00:30:28,020
ce qui équivaut à un peu si ce n'est pas node9.

400
00:30:28,020 --> 00:30:38,310
Donc, si pas node9, ou non Node6, ou non node3, ou non node7, retourner 1.

401
00:30:38,310 --> 00:30:42,850
Peut-être que nous devrions imprimer malloc échoué, ou quelque chose.

402
00:30:42,850 --> 00:30:46,680
[Étudiants] est fausse égale à null ainsi?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Toute valeur nulle est fausse.

404
00:30:51,290 --> 00:30:53,920
Donc nulle est une valeur nulle.

405
00:30:53,920 --> 00:30:56,780
Zéro est une valeur nulle. Faux est une valeur nulle.

406
00:30:56,780 --> 00:31:02,130
Tout - à peu près les 2 seules valeurs nulles sont nuls et zéro,

407
00:31:02,130 --> 00:31:07,900
faux est juste de hachage définie comme égale à zéro.

408
00:31:07,900 --> 00:31:13,030
Cela s'applique également si nous déclarons une variable globale.

409
00:31:13,030 --> 00:31:17,890
Si nous avions racine * noeud ici,

410
00:31:17,890 --> 00:31:24,150
puis - la bonne chose à propos des variables globales, c'est qu'ils ont toujours une valeur initiale.

411
00:31:24,150 --> 00:31:27,500
Ce n'est pas vrai des fonctions, faire à l'intérieur d'ici,

412
00:31:27,500 --> 00:31:34,870
si nous avons, comme, * nœud ou le nœud x.

413
00:31:34,870 --> 00:31:37,380
Nous n'avons aucune idée ce que x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
ou nous pourrions les imprimer et ils pourraient être arbitraire.

415
00:31:40,700 --> 00:31:44,980
Ce n'est pas vrai de variables globales.

416
00:31:44,980 --> 00:31:47,450
Racine, afin nœud ou le nœud x.

417
00:31:47,450 --> 00:31:53,410
Par défaut, tout ce qui est global, si elle n'est pas explicitement initialisé à une certaine valeur,

418
00:31:53,410 --> 00:31:57,390
a une valeur nulle comme valeur.

419
00:31:57,390 --> 00:32:01,150
Donc ici, la racine * noeud, nous n'avons pas explicitement l'initialiser à rien,

420
00:32:01,150 --> 00:32:06,350
si la valeur par défaut sera nulle, ce qui correspond à la valeur zéro des pointeurs.

421
00:32:06,350 --> 00:32:11,870
La valeur par défaut de x va dire que x.value est égal à zéro,

422
00:32:11,870 --> 00:32:14,260
x.left est nulle, et x.right est nulle.

423
00:32:14,260 --> 00:32:21,070
Donc, puisqu'il s'agit d'une structure, tous les champs de la structure seront nulles.

424
00:32:21,070 --> 00:32:24,410
Nous n'avons pas besoin de l'utiliser ici, cependant.

425
00:32:24,410 --> 00:32:27,320
[Étudiants] Les structs sont différentes de celles d'autres variables, et les autres variables sont

426
00:32:27,320 --> 00:32:31,400
des valeurs parasites, ce sont des zéros?

427
00:32:31,400 --> 00:32:36,220
[Bowden] D'autres valeurs aussi. Donc, en x, x sera égal à zéro.

428
00:32:36,220 --> 00:32:40,070
Si c'est avec une portée globale, il a une valeur initiale. Ok >>.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Soit la valeur initiale vous lui avez donné ou nul.

430
00:32:48,950 --> 00:32:53,260
Je pense qui prend soin de tout cela.

431
00:32:53,260 --> 00:32:58,390
>> D'accord. Ainsi, la partie suivante de la question demande,

432
00:32:58,390 --> 00:33:01,260
"Maintenant, nous voulons écrire une fonction appelée contient

433
00:33:01,260 --> 00:33:04,930
avec un prototype de bool contient une valeur int. "

434
00:33:04,930 --> 00:33:08,340
Nous n'allons pas faire bool contient une valeur int.

435
00:33:08,340 --> 00:33:15,110
Notre prototype va ressembler

436
00:33:15,110 --> 00:33:22,380
bool contient (int value.

437
00:33:22,380 --> 00:33:24,490
Et puis nous allons aussi lui passer l'arbre

438
00:33:24,490 --> 00:33:28,870
qu'il convient de vérifier pour voir si elle a cette valeur.

439
00:33:28,870 --> 00:33:38,290
Donc noeud * arbre). D'accord.

440
00:33:38,290 --> 00:33:44,440
Et puis on peut l'appeler avec quelque chose comme:

441
00:33:44,440 --> 00:33:46,090
peut-être que nous voudrons printf ou quelque chose.

442
00:33:46,090 --> 00:33:51,040
Contient 6, notre racine.

443
00:33:51,040 --> 00:33:54,300
Qui devrait renvoyer un ou vrai,

444
00:33:54,300 --> 00:33:59,390
tandis que la racine contient 5 devrait retourner false.

445
00:33:59,390 --> 00:34:02,690
Alors, prenez une seconde pour mettre en œuvre.

446
00:34:02,690 --> 00:34:06,780
Vous pouvez le faire soit de manière itérative ou récursive.

447
00:34:06,780 --> 00:34:09,739
La bonne chose au sujet de la façon dont nous avons mis les choses, c'est que

448
00:34:09,739 --> 00:34:12,300
il se prête à notre solution récursive beaucoup plus facile

449
00:34:12,300 --> 00:34:14,719
que la variable de façon globale fait.

450
00:34:14,719 --> 00:34:19,750
Parce que si nous avons juste valeur contient int, alors nous n'avons aucun moyen de récursion vers le bas sous-arbres.

451
00:34:19,750 --> 00:34:24,130
Nous aimerions avoir une fonction d'assistance distinct récursivement les sous-arbres vers le bas pour nous.

452
00:34:24,130 --> 00:34:29,610
Mais depuis que nous avons changé pour prendre l'arbre comme un argument,

453
00:34:29,610 --> 00:34:32,760
lequel il aurait toujours été en premier lieu,

454
00:34:32,760 --> 00:34:35,710
maintenant nous pouvons recurse plus facilement.

455
00:34:35,710 --> 00:34:38,960
Donc, itératif ou récursif, nous allons passer en revue tous les deux,

456
00:34:38,960 --> 00:34:46,139
mais nous allons voir ce que les extrémités recursive par être assez facile.

457
00:34:59,140 --> 00:35:02,480
D'accord. Quelqu'un at-il quelque chose que nous pouvons travailler avec?

458
00:35:02,480 --> 00:35:12,000
>> [Étudiants] J'ai une solution itérative. >> Très bien, itératif.

459
00:35:12,000 --> 00:35:16,030
Bon, ça a l'air bon.

460
00:35:16,030 --> 00:35:18,920
Donc, nous voulons marcher à travers elle?

461
00:35:18,920 --> 00:35:25,780
[Étudiants] Bien sûr. J'ai donc mis une variable temp pour obtenir le premier nœud de l'arbre.

462
00:35:25,780 --> 00:35:28,330
Et puis je viens de boucle à travers tout température n'est pas nulle égale,

463
00:35:28,330 --> 00:35:31,700
si tout était toujours dans l'arbre, je suppose.

464
00:35:31,700 --> 00:35:35,710
Et si la valeur est égale à la valeur que temp est pointant vers,

465
00:35:35,710 --> 00:35:37,640
puis il retourne cette valeur.

466
00:35:37,640 --> 00:35:40,210
Dans le cas contraire, il vérifie si elle est sur le côté droit ou le côté gauche.

467
00:35:40,210 --> 00:35:43,400
Si jamais vous avez une situation où il n'y a plus d'arbres,

468
00:35:43,400 --> 00:35:47,330
puis il revient - il sort de la boucle et retourne false.

469
00:35:47,330 --> 00:35:52,190
[Bowden] D'accord. Donc, cela semble bon.

470
00:35:52,190 --> 00:35:58,470
Quelqu'un at-il des commentaires sur quelque chose?

471
00:35:58,470 --> 00:36:02,400
Je n'ai pas de commentaires exactitude du tout.

472
00:36:02,400 --> 00:36:11,020
La seule chose que nous pouvons faire est de ce type.

473
00:36:11,020 --> 00:36:21,660
Oh, ça va aller un peu allongée.

474
00:36:21,660 --> 00:36:33,460
Je vais arranger ça. D'accord.

475
00:36:33,460 --> 00:36:37,150
>> Tout le monde devrait se rappeler comment fonctionne ternaire.

476
00:36:37,150 --> 00:36:38,610
Il a certainement été quiz dans le passé

477
00:36:38,610 --> 00:36:41,170
qui vous donnent une fonction avec un opérateur ternaire,

478
00:36:41,170 --> 00:36:45,750
et de dire, de traduire cela, faire quelque chose qui n'utilise pas ternaire.

479
00:36:45,750 --> 00:36:49,140
Donc, c'est un cas très fréquent quand je pense à utiliser ternaire,

480
00:36:49,140 --> 00:36:54,610
où si une condition de définir une variable à quelque chose,

481
00:36:54,610 --> 00:36:58,580
autre indication que même variable à autre chose.

482
00:36:58,580 --> 00:37:03,390
C'est quelque chose que très souvent, peut être transformé en ce genre de chose

483
00:37:03,390 --> 00:37:14,420
où mettre cette variable à cela - ou bien, est-ce vrai? Ensuite cela, sinon cela.

484
00:37:14,420 --> 00:37:18,550
[Étudiants] Le premier est si vrai, non?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Ouais. La façon dont je lis toujours est égale à la valeur de température supérieure à la valeur de température,

486
00:37:25,570 --> 00:37:30,680
puis cela, sinon cela. Il a posé une question.

487
00:37:30,680 --> 00:37:35,200
Est-il plus? Ensuite, faites la première chose. D'autre faire la deuxième chose.

488
00:37:35,200 --> 00:37:41,670
J'ai presque toujours - du côlon, je viens - dans ma tête, j'ai lu que d'autre.

489
00:37:41,670 --> 00:37:47,180
>> Quelqu'un at-il une solution récursive?

490
00:37:47,180 --> 00:37:49,670
D'accord. Celui-ci nous allons - il pourrait déjà être grande,

491
00:37:49,670 --> 00:37:53,990
mais nous allons faire encore mieux.

492
00:37:53,990 --> 00:37:58,720
C'est à peu près la même idée exacte.

493
00:37:58,720 --> 00:38:03,060
C'est juste que, eh bien, voulez-vous expliquer?

494
00:38:03,060 --> 00:38:08,340
[Étudiants] Bien sûr. Donc, nous faisons en sorte que l'arbre n'est pas null abord,

495
00:38:08,340 --> 00:38:13,380
parce que si l'arbre est NULL, alors il va retourner faux parce que nous ne l'avons pas trouvé.

496
00:38:13,380 --> 00:38:19,200
Et si il ya encore un arbre, nous entrons dans - nous vérifions d'abord si la valeur est le noeud courant.

497
00:38:19,200 --> 00:38:23,740
Retourne vrai si c'est le cas, et si nous ne recurse sur la gauche ou la droite.

498
00:38:23,740 --> 00:38:25,970
Est-ce que le son approprié? >> Mm-hmm. (Accord)

499
00:38:25,970 --> 00:38:33,880
Donc remarquerez que ce n'est presque - structurellement très similaire à la solution itérative.

500
00:38:33,880 --> 00:38:38,200
C'est juste qu'au lieu de récursion, nous avons eu une boucle while.

501
00:38:38,200 --> 00:38:40,840
Et le scénario de base là où l'arbre n'est pas nulle égale

502
00:38:40,840 --> 00:38:44,850
était la condition sous laquelle nous avons cassé hors de la boucle while.

503
00:38:44,850 --> 00:38:50,200
Ils sont très similaires. Mais nous allons prendre un peu plus loin.

504
00:38:50,200 --> 00:38:54,190
Maintenant, nous faisons la même chose ici.

505
00:38:54,190 --> 00:38:57,680
Notez que nous retournant la même chose dans l'autre de ces lignes,

506
00:38:57,680 --> 00:39:00,220
sauf pour un seul argument est différent.

507
00:39:00,220 --> 00:39:07,950
Donc, nous allons faire cela dans un ternaire.

508
00:39:07,950 --> 00:39:13,790
J'ai touché quelque chose option, et il a fait un symbole. D'accord.

509
00:39:13,790 --> 00:39:21,720
Donc, nous allons revenir contient que.

510
00:39:21,720 --> 00:39:28,030
Ceci est en train de devenir plusieurs lignes, eh bien, c'est un zoom avant.

511
00:39:28,030 --> 00:39:31,060
Habituellement, comme une chose stylistique, je ne pense pas que beaucoup de gens

512
00:39:31,060 --> 00:39:38,640
mettre un espace après la flèche, mais je suppose que si vous êtes cohérent, c'est bien.

513
00:39:38,640 --> 00:39:44,320
Si la valeur est inférieure à la valeur des arbres, nous voulons recurse sur la gauche arbre,

514
00:39:44,320 --> 00:39:53,890
d'autre nous voulons recurse à droite arbre.

515
00:39:53,890 --> 00:39:58,610
C'était donc la première étape de faire ce regard plus petit.

516
00:39:58,610 --> 00:40:02,660
L'étape deux de faire ce regard plus petit -

517
00:40:02,660 --> 00:40:09,150
nous pouvons séparer plusieurs lignes.

518
00:40:09,150 --> 00:40:16,500
D'accord. La deuxième étape de la faire paraître plus petit est ici,

519
00:40:16,500 --> 00:40:25,860
si la valeur de retour est égal à la valeur des arbres, ou contient autre chose.

520
00:40:25,860 --> 00:40:28,340
>> C'est une chose importante.

521
00:40:28,340 --> 00:40:30,860
Je ne sais pas si il a dit explicitement dans la classe,

522
00:40:30,860 --> 00:40:34,740
mais il est appelé court-circuit d'évaluation.

523
00:40:34,740 --> 00:40:41,060
L'idée ici est la valeur == valeur des arbres.

524
00:40:41,060 --> 00:40:49,960
Si cela est vrai, alors cela est vrai, et nous voulons »ou« avec tout ce qui est ici.

525
00:40:49,960 --> 00:40:52,520
Ainsi, sans même y penser tout ce qui est ici,

526
00:40:52,520 --> 00:40:55,070
ce qui est l'expression entière va revenir?

527
00:40:55,070 --> 00:40:59,430
[Étudiants] True? >> Ouais, parce que vrai de rien,

528
00:40:59,430 --> 00:41:04,990
or'd - or'd ou quoi que ce soit vrai est nécessairement vrai.

529
00:41:04,990 --> 00:41:08,150
Donc dès que nous voyons valeur de retour = valeur des arbres,

530
00:41:08,150 --> 00:41:10,140
nous allons juste pour retourner true.

531
00:41:10,140 --> 00:41:15,710
Ne vais même pas recurse contient en outre sur toute la ligne.

532
00:41:15,710 --> 00:41:20,980
Nous pouvons prendre un peu plus loin.

533
00:41:20,980 --> 00:41:29,490
Arbre de retour n'est pas nulle d'égalité et tout cela.

534
00:41:29,490 --> 00:41:32,650
Il a une fonction d'une seule ligne.

535
00:41:32,650 --> 00:41:36,790
C'est aussi un exemple de court-circuit d'évaluation.

536
00:41:36,790 --> 00:41:40,680
Mais maintenant, c'est la même idée -

537
00:41:40,680 --> 00:41:47,320
au lieu de - si l'arbre n'est pas nulle d'égalité - ou bien,

538
00:41:47,320 --> 00:41:49,580
si l'arbre fait nulle égale, ce qui est le cas mauvais,

539
00:41:49,580 --> 00:41:54,790
si l'arbre est égal à NULL, alors la première condition va être faux.

540
00:41:54,790 --> 00:42:00,550
Donc fausse AND avec quoi que ce soit va être quoi?

541
00:42:00,550 --> 00:42:04,640
[Étudiants] Faux. Ouais >>. C'est l'autre moitié de court-circuit d'évaluation,

542
00:42:04,640 --> 00:42:10,710
où si nul arbre ne pas égaux, alors nous n'allons pas même aller -

543
00:42:10,710 --> 00:42:14,930
ou si l'arbre fait nulle égaux, alors nous n'allons pas faire value == valeur des arbres.

544
00:42:14,930 --> 00:42:17,010
Nous allons juste revenir immédiatement faux.

545
00:42:17,010 --> 00:42:20,970
Ce qui est important, car si elle n'a pas de court-circuit evaluate,

546
00:42:20,970 --> 00:42:25,860
alors si nul arbre ne égales par ailleurs, cette deuxième condition va à la faute seg,

547
00:42:25,860 --> 00:42:32,510
parce arbre-> valeur est nulle déréférencement.

548
00:42:32,510 --> 00:42:40,490
Donc, c'est tout. Peut faire cela - se déplacer une fois terminé.

549
00:42:40,490 --> 00:42:44,840
C'est une chose très commune aussi, ne pas faire cette simple ligne avec cela,

550
00:42:44,840 --> 00:42:49,000
mais c'est une chose commune dans des conditions, peut-être pas ici,

551
00:42:49,000 --> 00:42:59,380
mais si (arbre! = NULL, et l'arbre-> valeur == valeur), faire n'importe quoi.

552
00:42:59,380 --> 00:43:01,560
Il s'agit d'une affection très fréquente, où, au lieu d'avoir

553
00:43:01,560 --> 00:43:06,770
de briser ce en deux ifs, où voulez, c'est l'hypothèse nulle arbre?

554
00:43:06,770 --> 00:43:11,780
Bon, ce n'est pas nul, alors maintenant est la valeur d'arbre égale à la valeur? Pour ce faire.

555
00:43:11,780 --> 00:43:17,300
Au lieu de cela, cette condition, ce ne sera jamais seg faute

556
00:43:17,300 --> 00:43:21,220
car il va éclater si cela arrive à être nulle.

557
00:43:21,220 --> 00:43:24,000
Eh bien, je suppose que si votre arbre est un pointeur invalide complètement, il peut encore seg faute,

558
00:43:24,000 --> 00:43:26,620
mais il ne peut pas seg faute si l'arbre est nulle.

559
00:43:26,620 --> 00:43:32,900
Si elle était nulle, elle allait éclater avant que vous ne le pointeur déréférencé en premier lieu.

560
00:43:32,900 --> 00:43:35,000
[Étudiants] Est-ce qu'on appelle l'évaluation paresseuse?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] l'évaluation paresseuse est une chose distincte.

562
00:43:40,770 --> 00:43:49,880
L'évaluation paresseuse ressemble plus à vous demander pour une valeur,

563
00:43:49,880 --> 00:43:54,270
vous demander de calculer une valeur, en quelque sorte, mais vous n'en avez pas besoin immédiatement.

564
00:43:54,270 --> 00:43:59,040
Donc, tant que vous en avez besoin, il n'est pas évaluée.

565
00:43:59,040 --> 00:44:03,920
Ce n'est pas exactement la même chose, mais dans le pset Huffman,

566
00:44:03,920 --> 00:44:06,520
il dit que nous "lazily" écrire.

567
00:44:06,520 --> 00:44:08,670
La raison pour laquelle nous faisons cela parce que nous sommes en train de tampon d'écriture -

568
00:44:08,670 --> 00:44:11,820
nous ne voulons pas d'écrire des bits individuels à la fois,

569
00:44:11,820 --> 00:44:15,450
ou différents octets à la fois, au lieu que nous voulons obtenir un morceau d'octets.

570
00:44:15,450 --> 00:44:19,270
Puis, une fois que nous avons un gros morceau d'octets, puis nous allons l'écrire.

571
00:44:19,270 --> 00:44:22,640
Même si vous lui demandez d'écrire - et fwrite et fread faire le même genre de chose.

572
00:44:22,640 --> 00:44:26,260
Ils tampon de votre lit et écrit.

573
00:44:26,260 --> 00:44:31,610
Même si vous lui demandez d'écrire tout de suite, il ne sera probablement pas le cas.

574
00:44:31,610 --> 00:44:34,540
Et vous ne pouvez pas être sûr que les choses vont être écrites

575
00:44:34,540 --> 00:44:37,540
jusqu'à ce que vous appelez hfclose ou quoi que ce soit,

576
00:44:37,540 --> 00:44:39,620
qui dit alors, d'accord, je ferme mon dossier,

577
00:44:39,620 --> 00:44:43,450
cela signifie que je ferais mieux d'écrire tout ce que je n'ai pas encore écrite.

578
00:44:43,450 --> 00:44:45,770
Il n'a pas besoin de tout écrire sur

579
00:44:45,770 --> 00:44:49,010
jusqu'à ce que vous fermez le fichier, puis il a besoin.

580
00:44:49,010 --> 00:44:56,220
Donc, c'est exactement ce que paresseux - il attend que cela doit arriver.

581
00:44:56,220 --> 00:44:59,990
Ce - prendre 51 et vous y entrer plus en détail,

582
00:44:59,990 --> 00:45:05,470
parce OCaml et tout en 51, tout est récursivité.

583
00:45:05,470 --> 00:45:08,890
Il n'existe pas de solutions itératives, essentiellement.

584
00:45:08,890 --> 00:45:11,550
Tout est récurrence et l'évaluation paresseuse

585
00:45:11,550 --> 00:45:14,790
va être important pour un grand nombre de circonstances

586
00:45:14,790 --> 00:45:19,920
où, si vous n'avez pas lazily évaluer, cela signifierait -

587
00:45:19,920 --> 00:45:24,760
L'exemple est ruisseaux, qui sont infiniment long.

588
00:45:24,760 --> 00:45:30,990
En théorie, vous pouvez penser à des nombres naturels en tant que flux de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Tant de choses paresseusement évalués sont très bien.

590
00:45:33,090 --> 00:45:37,210
Si je dis que je veux le dixième nombre, alors je peux évaluer jusqu'à la dixième nombre.

591
00:45:37,210 --> 00:45:40,300
Si je veux le numéro centième, alors je peux évaluer jusqu'à concurrence du nombre centième.

592
00:45:40,300 --> 00:45:46,290
Sans évaluation paresseuse, alors il va essayer d'évaluer tous les numéros immédiatement.

593
00:45:46,290 --> 00:45:50,000
Vous évaluez une infinité de nombres, et c'est juste pas possible.

594
00:45:50,000 --> 00:45:52,080
Donc, il ya beaucoup de cas où l'évaluation paresseuse

595
00:45:52,080 --> 00:45:57,840
est tout simplement indispensable pour obtenir des choses à travailler.

596
00:45:57,840 --> 00:46:05,260
>> Maintenant, nous voulons écrire insert insert où va être

597
00:46:05,260 --> 00:46:08,430
même évolution dans sa définition.

598
00:46:08,430 --> 00:46:10,470
Donc maintenant c'est insert bool (int value).

599
00:46:10,470 --> 00:46:23,850
Nous allons changer cela à insert bool (int valeur, noeud * arbre).

600
00:46:23,850 --> 00:46:29,120
Nous allons en fait pour changer cette fois un peu, nous allons voir pourquoi.

601
00:46:29,120 --> 00:46:32,210
Et passons build_node, juste pour le plaisir de le faire,

602
00:46:32,210 --> 00:46:36,730
ci-dessus insérez donc nous n'avons pas besoin d'écrire un prototype de fonction.

603
00:46:36,730 --> 00:46:42,450
Ce qui est une indication que vous allez utiliser build_node dans l'insert.

604
00:46:42,450 --> 00:46:49,590
D'accord. Prenez une minute pour cela.

605
00:46:49,590 --> 00:46:52,130
Je pense que j'ai sauvé la révision, si vous voulez tirer de cela,

606
00:46:52,130 --> 00:47:00,240
ou, du moins, je l'ai fait aujourd'hui.

607
00:47:00,240 --> 00:47:04,190
Je voulais une légère cassure à réfléchir à la logique de l'insertion,

608
00:47:04,190 --> 00:47:08,750
si vous ne pouvez pas y penser.

609
00:47:08,750 --> 00:47:12,860
Fondamentalement, vous ne jamais être à l'insertion des feuilles.

610
00:47:12,860 --> 00:47:18,640
Comme, si j'insère 1, alors je suis inévitablement à insérer 1 -

611
00:47:18,640 --> 00:47:21,820
Je vais changer au noir - je vais être insérant 1 sur ici.

612
00:47:21,820 --> 00:47:28,070
Ou si j'insère 4, je veux être insérant 4 sur ici.

613
00:47:28,070 --> 00:47:32,180
Donc, peu importe ce que vous faites, vous allez être à l'insertion d'une feuille.

614
00:47:32,180 --> 00:47:36,130
Tout ce que vous avez à faire est itérer descendre dans l'arborescence jusqu'à ce que vous arrivez à le nœud

615
00:47:36,130 --> 00:47:40,890
qui devrait être parent du nœud, parent du nouveau nœud,

616
00:47:40,890 --> 00:47:44,560
puis changer son pointeur vers la gauche ou la droite, selon que

617
00:47:44,560 --> 00:47:47,060
il est supérieur ou inférieur au noeud courant.

618
00:47:47,060 --> 00:47:51,180
Changer ce pointeur pour pointer vers votre nouveau nœud.

619
00:47:51,180 --> 00:48:05,490
Donc itérer l'arbre, faire le point de feuille vers le nouveau nœud.

620
00:48:05,490 --> 00:48:09,810
Également réfléchir à la raison qui interdit ce genre de situation auparavant,

621
00:48:09,810 --> 00:48:17,990
où j'ai construit l'arbre binaire où elle était correcte

622
00:48:17,990 --> 00:48:19,920
si vous seulement regardé un seul nœud,

623
00:48:19,920 --> 00:48:24,830
mais 9 était à la gauche de 7 si vous itéré fond vers le bas.

624
00:48:24,830 --> 00:48:29,770
Donc, c'est impossible dans ce scénario, car -

625
00:48:29,770 --> 00:48:32,530
pensez à insérer 9 ou quelque chose, au tout premier nœud,

626
00:48:32,530 --> 00:48:35,350
Je vais voir 7 et je vais juste aller à droite.

627
00:48:35,350 --> 00:48:38,490
Donc, peu importe ce que je fais, si je suis en allant à l'insertion d'une feuille,

628
00:48:38,490 --> 00:48:40,790
et une feuille à l'aide de l'algorithme approprié,

629
00:48:40,790 --> 00:48:43,130
il va être impossible pour moi d'insérer 9 à la gauche de 7

630
00:48:43,130 --> 00:48:48,250
parce que dès que j'ai touché 7 Je vais aller vers la droite.

631
00:48:59,740 --> 00:49:02,070
Quelqu'un at-il quelque chose pour commencer?

632
00:49:02,070 --> 00:49:05,480
[Étudiants] je fais. >> Bien sûr.

633
00:49:05,480 --> 00:49:09,200
[Étudiant, inintelligible]

634
00:49:09,200 --> 00:49:14,390
[Étudiant Autre, inintelligible]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Il est apprécié. D'accord. Voulez-vous expliquer?

636
00:49:18,330 --> 00:49:20,690
>> [Étudiants] Puisque nous savons que nous avons été insertion

637
00:49:20,690 --> 00:49:24,060
de nouveaux noeuds à l'extrémité de l'arbre,

638
00:49:24,060 --> 00:49:28,070
J'ai bouclé à travers l'arbre de manière itérative

639
00:49:28,070 --> 00:49:31,360
jusqu'à ce que j'arrive à un nœud qui fait la valeur null.

640
00:49:31,360 --> 00:49:34,220
Et puis j'ai décidé de le mettre soit sur le côté droit ou le côté gauche

641
00:49:34,220 --> 00:49:37,420
en utilisant cette variable raison, il m'a dit où le mettre.

642
00:49:37,420 --> 00:49:41,850
Et puis, pour l'essentiel, je viens de faire qui durent -

643
00:49:41,850 --> 00:49:47,520
ce point nœud temporaire pour le nouveau nœud qu'il créait,

644
00:49:47,520 --> 00:49:50,770
soit sur le côté gauche ou sur le côté droit, en fonction de ce que la valeur de droite était.

645
00:49:50,770 --> 00:49:56,530
Enfin, j'ai mis la valeur nouveau nœud à la valeur de ses essais.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Bon, je vois un problème ici.

647
00:49:59,550 --> 00:50:02,050
C'est comme 95% du chemin.

648
00:50:02,050 --> 00:50:07,550
Le seul problème que je vois, eh bien, personne d'autre ne voyez un problème?

649
00:50:07,550 --> 00:50:18,400
Qu'est-ce que les circonstances dans lesquelles ils sortir de la boucle?

650
00:50:18,400 --> 00:50:22,100
[Étudiants] Si la température est nulle? Ouais >>. Alors, comment vous sortir de la boucle est si la température est nulle.

651
00:50:22,100 --> 00:50:30,220
Mais qu'est-ce que je fais ici?

652
00:50:30,220 --> 00:50:35,410
Température de déréférencer I, qui est forcément nul.

653
00:50:35,410 --> 00:50:39,840
Donc, la chose que vous devez faire est de ne pas garder trace jusqu'à température est nulle,

654
00:50:39,840 --> 00:50:45,590
vous voulez garder une trace de la mère à tout moment.

655
00:50:45,590 --> 00:50:52,190
Nous voulons aussi que parent node *, je pense que nous pouvons tenir qu'à nulle au premier abord.

656
00:50:52,190 --> 00:50:55,480
Cela va avoir un comportement bizarre de la racine de l'arbre,

657
00:50:55,480 --> 00:50:59,210
mais nous y reviendrons.

658
00:50:59,210 --> 00:51:03,950
Si la valeur est supérieure à ce que, alors bonne température temp =.

659
00:51:03,950 --> 00:51:07,910
Mais avant de faire cela, parent temp =.

660
00:51:07,910 --> 00:51:14,500
Ou sont les parents va toujours à température égale? Est-ce le cas?

661
00:51:14,500 --> 00:51:19,560
Si la température n'est pas nulle, alors je vais descendre, peu importe quoi,

662
00:51:19,560 --> 00:51:24,030
à un poste pour lequel temp est le parent.

663
00:51:24,030 --> 00:51:27,500
Donc parent va être temp, puis-je déplacer température vers le bas.

664
00:51:27,500 --> 00:51:32,410
Maintenant température est nulle, mais les points mères à la mère de la chose qui est nulle.

665
00:51:32,410 --> 00:51:39,110
Donc ici, je ne veux pas mettre équivaut à droite 1.

666
00:51:39,110 --> 00:51:41,300
Alors je me suis déplacé vers la droite, si droite = 1,

667
00:51:41,300 --> 00:51:45,130
et je suppose que vous aussi vous voulez faire -

668
00:51:45,130 --> 00:51:48,530
si vous vous déplacez vers la gauche, vous voulez définir un droit égal à 0.

669
00:51:48,530 --> 00:51:55,950
Ou bien si jamais vous déplacer vers la droite.

670
00:51:55,950 --> 00:51:58,590
Donc, droite = 0. Si la droite = 1,

671
00:51:58,590 --> 00:52:04,260
maintenant, nous voulons faire la newnode pointeur parent droite,

672
00:52:04,260 --> 00:52:08,520
autre que nous voulons faire le newnode pointeur parent.

673
00:52:08,520 --> 00:52:16,850
Questions à ce sujet?

674
00:52:16,850 --> 00:52:24,880
D'accord. Donc, c'est la façon dont nous - et, en fait, au lieu de faire cela,

675
00:52:24,880 --> 00:52:29,630
nous vous m'attendais à utiliser build_node.

676
00:52:29,630 --> 00:52:40,450
Et puis, si newnode est égal à NULL, retourne false.

677
00:52:40,450 --> 00:52:44,170
C'est tout. Maintenant, c'est ce que nous nous attendions à vous de le faire.

678
00:52:44,170 --> 00:52:47,690
>> C'est ce que les solutions du personnel faire.

679
00:52:47,690 --> 00:52:52,360
Je suis en désaccord avec ce que la «bonne» façon de s'y prendre

680
00:52:52,360 --> 00:52:57,820
mais cela est parfaitement bien et il va fonctionner.

681
00:52:57,820 --> 00:53:02,840
Une chose qui est un peu bizarre à droite est maintenant

682
00:53:02,840 --> 00:53:08,310
si l'arbre commence comme nulle, nous passons dans un arbre nul.

683
00:53:08,310 --> 00:53:12,650
Je suppose que cela dépend de comment vous définissez le comportement de passer dans un arbre nul.

684
00:53:12,650 --> 00:53:15,490
Je pense que si vous passez dans un arbre nul,

685
00:53:15,490 --> 00:53:17,520
puis en insérant la valeur nulle dans un arbre

686
00:53:17,520 --> 00:53:23,030
doit simplement retourner un arbre où la seule valeur est ce nœud unique.

687
00:53:23,030 --> 00:53:25,830
Les gens d'accord avec cela? Vous pouvez, si vous le souhaitez,

688
00:53:25,830 --> 00:53:28,050
si vous passez dans un arbre nulle

689
00:53:28,050 --> 00:53:31,320
et que vous voulez insérer une valeur en elle, retourne false.

690
00:53:31,320 --> 00:53:33,830
C'est à vous de définir cela.

691
00:53:33,830 --> 00:53:38,320
Pour ce faire, la première chose que j'ai dit et puis -

692
00:53:38,320 --> 00:53:40,720
bien, vous allez avoir du mal à le faire, car

693
00:53:40,720 --> 00:53:44,090
il serait plus facile si nous avions un pointeur global à la chose,

694
00:53:44,090 --> 00:53:48,570
mais nous n'avons pas, donc si l'arbre est nulle, il n'y a rien que nous puissions faire à ce sujet.

695
00:53:48,570 --> 00:53:50,960
On peut juste retourner false.

696
00:53:50,960 --> 00:53:52,840
Donc, je vais changer d'insertion.

697
00:53:52,840 --> 00:53:56,540
Nous technique pourrait tout changer ici,

698
00:53:56,540 --> 00:53:58,400
comment il est itérer sur les choses,

699
00:53:58,400 --> 00:54:04,530
mais je vais changer l'insertion de prendre un nœud de l'arbre. **

700
00:54:04,530 --> 00:54:07,510
Pointeurs doubles.

701
00:54:07,510 --> 00:54:09,710
Qu'est-ce que cela signifie?

702
00:54:09,710 --> 00:54:12,330
Au lieu de traiter avec des pointeurs vers les nœuds,

703
00:54:12,330 --> 00:54:16,690
la chose que je vais être la manipulation de ce pointeur.

704
00:54:16,690 --> 00:54:18,790
Je vais être la manipulation de ce pointeur.

705
00:54:18,790 --> 00:54:21,770
Je vais être la manipulation de pointeurs directement.

706
00:54:21,770 --> 00:54:25,760
Cela est logique puisque, pensez à bas -

707
00:54:25,760 --> 00:54:33,340
bien, maintenant ce point à null.

708
00:54:33,340 --> 00:54:38,130
Ce que je veux faire, c'est de manipuler ce pointeur pour pointer vers NOT NULL.

709
00:54:38,130 --> 00:54:40,970
Je veux faire remarquer à mon nouveau nœud.

710
00:54:40,970 --> 00:54:44,870
Si je viens de garder une trace des pointeurs à mes pointeurs,

711
00:54:44,870 --> 00:54:47,840
alors je n'ai pas besoin de garder une trace d'un pointeur parent.

712
00:54:47,840 --> 00:54:52,640
Je peux juste garder la trace pour voir si le pointeur pointe sur null,

713
00:54:52,640 --> 00:54:54,580
et si le pointeur pointe sur null,

714
00:54:54,580 --> 00:54:57,370
le modifier pour pointer vers le nœud que je veux.

715
00:54:57,370 --> 00:55:00,070
Et je peux le changer puisque j'ai un pointeur sur le pointeur.

716
00:55:00,070 --> 00:55:02,040
Voyons ça tout de suite.

717
00:55:02,040 --> 00:55:05,470
Vous pouvez effectivement le faire récursivement assez facilement.

718
00:55:05,470 --> 00:55:08,080
Voulons-nous faire cela?

719
00:55:08,080 --> 00:55:10,980
Oui, nous le faisons.

720
00:55:10,980 --> 00:55:16,790
>> Voyons cela de manière récursive.

721
00:55:16,790 --> 00:55:24,070
Tout d'abord, ce qui est notre cas de base va être?

722
00:55:24,070 --> 00:55:29,140
Presque toujours notre scénario de base, mais en réalité, c'est un peu délicat.

723
00:55:29,140 --> 00:55:34,370
Tout d'abord, si (arbre == NULL)

724
00:55:34,370 --> 00:55:37,550
Je suppose que nous allons juste return false.

725
00:55:37,550 --> 00:55:40,460
Ceci est différent de votre arbre étant nulle.

726
00:55:40,460 --> 00:55:44,510
C'est le pointeur sur le pointeur de la racine étant nulle

727
00:55:44,510 --> 00:55:48,360
ce qui signifie que le pointeur de la racine n'existe pas.

728
00:55:48,360 --> 00:55:52,390
Donc, ici-bas, si je le fais

729
00:55:52,390 --> 00:55:55,760
* noeud - disons simplement réutiliser ce.

730
00:55:55,760 --> 00:55:58,960
Node * root = NULL,

731
00:55:58,960 --> 00:56:00,730
et puis je vais appeler insert en faisant quelque chose comme:

732
00:56:00,730 --> 00:56:04,540
insérer 4 dans et racine.

733
00:56:04,540 --> 00:56:06,560
So & racine, si la racine est un nœud *

734
00:56:06,560 --> 00:56:11,170
alors racine et va être un nœud **.

735
00:56:11,170 --> 00:56:15,120
Ceci est valable. Dans ce cas, l'arbre, là-haut,

736
00:56:15,120 --> 00:56:20,120
arbre n'est pas nulle - ou d'insertion.

737
00:56:20,120 --> 00:56:24,630
Ici. Arbre n'est pas null; arbre * est nul, ce qui est bien

738
00:56:24,630 --> 00:56:26,680
car si l'arbre * est nul, alors je peux le manipuler

739
00:56:26,680 --> 00:56:29,210
maintenant pointer vers ce que je veux pointer.

740
00:56:29,210 --> 00:56:34,750
Mais si l'arbre est nulle, cela signifie que je viens ici et a déclaré nulle.

741
00:56:34,750 --> 00:56:42,710
Cela n'a pas de sens. Je ne peux pas faire n'importe quoi avec ça.

742
00:56:42,710 --> 00:56:45,540
Si l'arbre est nul, retourne false.

743
00:56:45,540 --> 00:56:48,220
J'ai donc essentiellement déjà dit ce que notre scénario de base réelle.

744
00:56:48,220 --> 00:56:50,580
Et qu'est-ce que cela va être?

745
00:56:50,580 --> 00:56:55,030
[Étudiant, inintelligible]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Oui. Donc, si (* arbre == NULL).

747
00:57:00,000 --> 00:57:04,520
Cela concerne le cas ici

748
00:57:04,520 --> 00:57:09,640
où si mon pointeur rouge est le pointeur je suis concentré sur,

749
00:57:09,640 --> 00:57:12,960
de sorte que je me concentre sur ce pointeur, maintenant je me concentre sur ce pointeur.

750
00:57:12,960 --> 00:57:15,150
Maintenant, je me concentre sur ce pointeur.

751
00:57:15,150 --> 00:57:18,160
Donc, si mon pointeur rouge, ce qui est mon nœud **,

752
00:57:18,160 --> 00:57:22,880
est toujours - si *, mon pointeur rouge, n'est jamais nulle,

753
00:57:22,880 --> 00:57:28,470
cela signifie que je suis au cas où je me concentre sur un pointeur qui pointe -

754
00:57:28,470 --> 00:57:32,530
il s'agit d'un pointeur qui fait partie d'une feuille.

755
00:57:32,530 --> 00:57:41,090
Je veux changer ce pointeur pour pointer vers mon nouveau nœud.

756
00:57:41,090 --> 00:57:45,230
Revenez ici.

757
00:57:45,230 --> 00:57:56,490
Mon newnode sera juste noeud * n = build_node (valeur)

758
00:57:56,490 --> 00:58:07,300
alors n, si n = NULL, retourne false.

759
00:58:07,300 --> 00:58:12,600
Sinon, nous voulons changer ce que le pointeur pointe actuellement

760
00:58:12,600 --> 00:58:17,830
maintenant pointer vers notre nœud nouvellement construit.

761
00:58:17,830 --> 00:58:20,280
Nous pouvons en fait faire ici.

762
00:58:20,280 --> 00:58:30,660
Au lieu de dire n, on dit arbre * = * si l'arbre.

763
00:58:30,660 --> 00:58:35,450
Tout le monde comprend cela? C'est en traitant avec des pointeurs sur des pointeurs,

764
00:58:35,450 --> 00:58:40,750
nous pouvons changer pointeurs nuls pour pointer vers ce que nous voulons les faire pointer vers.

765
00:58:40,750 --> 00:58:42,820
C'est notre scénario de base.

766
00:58:42,820 --> 00:58:45,740
>> Maintenant, notre récurrence, ou notre récursion,

767
00:58:45,740 --> 00:58:51,430
va être très semblable à tous les autres récurrences que nous avons faites.

768
00:58:51,430 --> 00:58:55,830
Nous allons à insérer la valeur,

769
00:58:55,830 --> 00:58:59,040
et maintenant je vais utiliser à nouveau ternaire, mais ce qui est notre condition va être?

770
00:58:59,040 --> 00:59:05,180
Qu'est-ce qu'il nous recherchons pour décider si nous voulons aller à gauche ou à droite?

771
00:59:05,180 --> 00:59:07,760
Faisons-le en étapes distinctes.

772
00:59:07,760 --> 00:59:18,850
If (valeur <) quoi?

773
00:59:18,850 --> 00:59:23,200
[Étudiants] Valeur de l'arbre?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Alors, n'oubliez pas que je suis actuellement -

775
00:59:27,490 --> 00:59:31,260
[Etudiants, inintelligibles]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Ouais, donc ici, disons que cette flèche verte

777
00:59:34,140 --> 00:59:39,050
est un exemple de ce que l'arbre est actuellement, est un pointeur sur ce pointeur.

778
00:59:39,050 --> 00:59:46,610
Cela signifie donc que je suis un pointeur vers un pointeur à 3.

779
00:59:46,610 --> 00:59:48,800
Le déréférencement deux fois sonnait bien.

780
00:59:48,800 --> 00:59:51,010
Que dois-je - comment puis-je faire cela?

781
00:59:51,010 --> 00:59:53,210
[Étudiants] déréférencement une fois, puis faire flèche de cette façon?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Donc (* arbre) est le déréférencement fois, -> la valeur

783
00:59:58,420 --> 01:00:05,960
va me donner la valeur du nœud que je suis indirectement pointe.

784
01:00:05,960 --> 01:00:11,980
Donc, je peux aussi écrire ** tree.value si vous préférez.

785
01:00:11,980 --> 01:00:18,490
Soit fonctionne.

786
01:00:18,490 --> 01:00:26,190
Si tel est le cas, alors je veux appeler insérer une valeur.

787
01:00:26,190 --> 01:00:32,590
Et ce qui est mon nœud mis à jour ** va être?

788
01:00:32,590 --> 01:00:39,440
Je veux aller à gauche, de sorte tree.left ** va être ma gauche.

789
01:00:39,440 --> 01:00:41,900
Et je veux le pointeur sur cette chose

790
01:00:41,900 --> 01:00:44,930
de sorte que si la gauche finit par être le pointeur nul,

791
01:00:44,930 --> 01:00:48,360
Je peux le modifier pour pointer vers mon nouveau nœud.

792
01:00:48,360 --> 01:00:51,460
>> Et l'autre cas peuvent être très similaires.

793
01:00:51,460 --> 01:00:55,600
Nous allons effectivement faire que mon ternaire en ce moment.

794
01:00:55,600 --> 01:01:04,480
Insérer la valeur si la valeur de <(arbre **). Valeur.

795
01:01:04,480 --> 01:01:11,040
Ensuite, nous voulons mettre à jour nos ** vers la gauche,

796
01:01:11,040 --> 01:01:17,030
autre que nous voulons mettre à jour nos ** vers la droite.

797
01:01:17,030 --> 01:01:22,540
[Étudiants] Est-ce que placer le pointeur sur le pointeur?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Rappelez-vous que - ** tree.right est une étoile nœud.

799
01:01:30,940 --> 01:01:35,040
[Étudiant, inintelligible] >> Oui.

800
01:01:35,040 --> 01:01:41,140
** Tree.right est comme ce pointeur ou quelque chose.

801
01:01:41,140 --> 01:01:45,140
Donc, en prenant un pointeur vers ça, ça me donne ce que je veux

802
01:01:45,140 --> 01:01:50,090
du pointeur de ce type.

803
01:01:50,090 --> 01:01:54,260
[Étudiants] Peut-on aller encore pourquoi nous utilisons les deux pointeurs?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Ouais. Ainsi - non, vous le pouvez, et que la solution avant

805
01:01:58,220 --> 01:02:04,540
C'était une façon de le faire sans faire deux pointeurs.

806
01:02:04,540 --> 01:02:08,740
Vous devez être capable de comprendre l'aide de deux pointeurs,

807
01:02:08,740 --> 01:02:11,660
et c'est une solution plus propre.

808
01:02:11,660 --> 01:02:16,090
Aussi, notez que, qu'advient-il si mon arbre -

809
01:02:16,090 --> 01:02:24,480
qu'advient-il si ma racine était nulle? Qu'advient-il si je fais ce cas ici?

810
01:02:24,480 --> 01:02:30,540
Alors nœud racine * = NULL, insérez 4 dans et racine.

811
01:02:30,540 --> 01:02:35,110
Quelle est la racine va être après cela?

812
01:02:35,110 --> 01:02:37,470
[Étudiant, inintelligible] >> Oui.

813
01:02:37,470 --> 01:02:41,710
Valeur de la racine va être 4.

814
01:02:41,710 --> 01:02:45,510
Gauche racine sera nulle, non racine va être nulle.

815
01:02:45,510 --> 01:02:49,490
Dans le cas où nous n'avons pas adopté la racine par adresse,

816
01:02:49,490 --> 01:02:52,490
nous ne pouvions pas modifier racine.

817
01:02:52,490 --> 01:02:56,020
Dans le cas où l'arbre - où la racine est nulle,

818
01:02:56,020 --> 01:02:58,410
nous avons juste eu à renvoyer false. Il n'y a rien que nous pouvions faire.

819
01:02:58,410 --> 01:03:01,520
Nous ne pouvons pas insérer un nœud dans un arbre vide.

820
01:03:01,520 --> 01:03:06,810
Mais maintenant, nous pouvons, que nous venons de faire un arbre vide dans un arbre à un nœud.

821
01:03:06,810 --> 01:03:13,400
Qui est généralement de la manière attendue qu'il est censé fonctionner.

822
01:03:13,400 --> 01:03:21,610
>> En outre, ce qui est nettement plus courte que

823
01:03:21,610 --> 01:03:26,240
également garder la trace de la mère, et ainsi de vous réitérer tout le chemin vers le bas.

824
01:03:26,240 --> 01:03:30,140
Maintenant, j'ai ma mère, et je dois mon pointeur droit du parent à l'autre chose.

825
01:03:30,140 --> 01:03:35,640
Au lieu de cela, si nous l'avons fait de manière itérative, ce serait la même idée avec une boucle while.

826
01:03:35,640 --> 01:03:38,100
Mais au lieu d'avoir à traiter avec mon pointeur parent,

827
01:03:38,100 --> 01:03:40,600
au lieu mon pointeur courant serait la chose

828
01:03:40,600 --> 01:03:43,790
que je suis directement modifier pour pointer vers mon nouveau nœud.

829
01:03:43,790 --> 01:03:46,090
Je n'ai pas à traiter si elle est orientée vers la gauche.

830
01:03:46,090 --> 01:03:48,810
Je n'ai pas à traiter si elle est orientée vers la droite.

831
01:03:48,810 --> 01:04:00,860
C'est juste ce que ce pointeur est, je vais le mettre pour pointer vers mon nouveau nœud.

832
01:04:00,860 --> 01:04:05,740
Tout le monde à comprendre comment cela fonctionne?

833
01:04:05,740 --> 01:04:09,460
Si non, pourquoi voulons-nous faire de cette façon,

834
01:04:09,460 --> 01:04:14,920
mais au moins que cela fonctionne comme une solution?

835
01:04:14,920 --> 01:04:17,110
[Étudiants] Où allons-nous retourner vrai?

836
01:04:17,110 --> 01:04:21,550
[Bowden] C'est probablement ici.

837
01:04:21,550 --> 01:04:26,690
Si nous avons bien l'insérer, retournez true.

838
01:04:26,690 --> 01:04:32,010
Sinon, ici-bas, nous allons vouloir revenir retours d'insertion que ce soit.

839
01:04:32,010 --> 01:04:35,950
>> Et ce qui est spécial à propos de cette fonction récursive?

840
01:04:35,950 --> 01:04:43,010
Il est récursive, tant et aussi longtemps que nous compilons avec une certaine optimisation,

841
01:04:43,010 --> 01:04:48,060
il le reconnaître et vous n'obtiendrez jamais un débordement de pile de cela,

842
01:04:48,060 --> 01:04:53,230
même si notre arbre a une hauteur de 10.000 ou 10 millions.

843
01:04:53,230 --> 01:04:55,630
[Étudiant, inintelligible]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Je pense que c'est le cas au Dash - ou ce niveau d'optimisation

845
01:05:00,310 --> 01:05:03,820
est requis pour une récursivité terminale à reconnaître.

846
01:05:03,820 --> 01:05:09,350
Je pense qu'il reconnaît - GCC et Clang

847
01:05:09,350 --> 01:05:12,610
également avoir des significations différentes pour leurs niveaux d'optimisation.

848
01:05:12,610 --> 01:05:17,870
Je veux dire que c'est DashO 2, c'est sûr qu'il va reconnaître la récursivité terminale.

849
01:05:17,870 --> 01:05:27,880
Mais nous - vous pourriez construire comme un exemple Fibonocci ou quelque chose.

850
01:05:27,880 --> 01:05:30,030
Il n'est pas facile de tester avec cela, parce qu'il est difficile de construire

851
01:05:30,030 --> 01:05:32,600
un arbre binaire qui est si grande.

852
01:05:32,600 --> 01:05:37,140
Mais oui, je pense que c'est DashO 2, qui

853
01:05:37,140 --> 01:05:40,580
si vous compilez avec DashO 2, il va chercher la récursivité terminale

854
01:05:40,580 --> 01:05:54,030
et d'optimiser cela.

855
01:05:54,030 --> 01:05:58,190
Revenons à - insérer est littéralement la dernière chose dont il a besoin.

856
01:05:58,190 --> 01:06:04,900
Revenons à l'insert par ici

857
01:06:04,900 --> 01:06:07,840
où nous allons faire la même idée.

858
01:06:07,840 --> 01:06:14,340
Il vous reste encore le défaut de ne pas être en mesure de gérer entièrement

859
01:06:14,340 --> 01:06:17,940
lorsque la racine elle-même est nulle, ou l'entrée passée est null,

860
01:06:17,940 --> 01:06:20,060
mais au lieu de traiter avec un pointeur parent,

861
01:06:20,060 --> 01:06:27,430
nous allons appliquer la même logique de maintien pointeurs sur des pointeurs.

862
01:06:27,430 --> 01:06:35,580
Si ici nous gardons notre noeud ** actu,

863
01:06:35,580 --> 01:06:37,860
et nous n'avons pas besoin de garder une trace de droite plus,

864
01:06:37,860 --> 01:06:47,190
mais noeud ** = & actu arbre.

865
01:06:47,190 --> 01:06:54,800
Et maintenant, notre boucle while va être tout * actu n'est pas nulle d'égalité.

866
01:06:54,800 --> 01:07:00,270
Vous n'avez pas besoin de garder une trace des parents plus.

867
01:07:00,270 --> 01:07:04,180
Vous n'avez pas besoin de garder une trace de gauche et de droite.

868
01:07:04,180 --> 01:07:10,190
Et je vais l'appeler intérim, parce que nous sommes déjà en utilisant temp.

869
01:07:10,190 --> 01:07:17,200
D'accord. Donc, si (valeur> * temp),

870
01:07:17,200 --> 01:07:24,010
alors & (* temp) -> droit

871
01:07:24,010 --> 01:07:29,250
d'autre temp = & (* temp) -> gauche.

872
01:07:29,250 --> 01:07:32,730
Et maintenant, en ce moment, après cette boucle while,

873
01:07:32,730 --> 01:07:36,380
Je ne fais cela parce que c'est peut-être plus facile de penser que itérative de façon récursive,

874
01:07:36,380 --> 01:07:39,010
mais après cette boucle while,

875
01:07:39,010 --> 01:07:43,820
* Temp est le pointeur que nous voulons changer.

876
01:07:43,820 --> 01:07:48,960
>> Avant, nous avions des parents, et nous voulions changer gauche parent ou le parent soit à droite,

877
01:07:48,960 --> 01:07:51,310
mais si nous voulons changer le droit des parents,

878
01:07:51,310 --> 01:07:54,550
puis temp * est bon parent, et nous pouvons le modifier directement.

879
01:07:54,550 --> 01:08:05,860
Donc, ici, nous pouvons faire * temp = newnode, et c'est tout.

880
01:08:05,860 --> 01:08:09,540
Alors préavis, tout nous avons fait dans ce n'était sortir des lignes de code.

881
01:08:09,540 --> 01:08:14,770
Afin de garder une trace de la mère dans tout ce qui est effort supplémentaire.

882
01:08:14,770 --> 01:08:18,689
Ici, si nous venons de suivre le pointeur sur le pointeur,

883
01:08:18,689 --> 01:08:22,990
et même si l'on voulait se débarrasser de toutes ces accolades maintenant,

884
01:08:22,990 --> 01:08:27,170
lui donner l'air plus courte.

885
01:08:27,170 --> 01:08:32,529
C'est maintenant exactement la même solution,

886
01:08:32,529 --> 01:08:38,210
mais moins de lignes de code.

887
01:08:38,210 --> 01:08:41,229
Une fois que vous commencer à reconnaître cela comme une solution valable,

888
01:08:41,229 --> 01:08:43,529
il est aussi plus facile de raisonner sur que comme, d'accord,

889
01:08:43,529 --> 01:08:45,779
pourquoi dois-je ce drapeau à droite int?

890
01:08:45,779 --> 01:08:49,290
Qu'est-ce que ça veut dire? Oh, ça signifie que

891
01:08:49,290 --> 01:08:51,370
chaque fois que je vais à droite, j'ai besoin de le configurer,

892
01:08:51,370 --> 01:08:53,819
d'autre si je vais à gauche je dois le remettre à zéro.

893
01:08:53,819 --> 01:09:04,060
Ici, je n'ai pas de raison à ce sujet, c'est juste plus facile de penser.

894
01:09:04,060 --> 01:09:06,710
Des questions?

895
01:09:06,710 --> 01:09:16,290
[Étudiant, inintelligible] >> Oui.

896
01:09:16,290 --> 01:09:23,359
Ok, donc dans le dernier bit -

897
01:09:23,359 --> 01:09:28,080
Je suppose une fonction rapide et facile que nous pouvons faire est,

898
01:09:28,080 --> 01:09:34,910
let's - ainsi, je pense, essayer d'écrire une fonction contains

899
01:09:34,910 --> 01:09:38,899
qui ne se soucie pas de savoir si c'est un arbre binaire de recherche.

900
01:09:38,899 --> 01:09:43,770
Celui-ci contient la fonction doit renvoyer true

901
01:09:43,770 --> 01:09:58,330
plus que partout ailleurs dans cet arbre binaire générale est la valeur que nous recherchons.

902
01:09:58,330 --> 01:10:02,520
Donc, nous allons d'abord le faire de manière récursive, puis nous le ferons de façon itérative.

903
01:10:02,520 --> 01:10:07,300
Nous pouvons en fait il suffit de faire ensemble, parce que cela va être très court.

904
01:10:07,300 --> 01:10:11,510
>> Ce qui est mon cas, la base va être?

905
01:10:11,510 --> 01:10:13,890
[Étudiant, inintelligible]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Donc, si (arbre == NULL), alors quoi?

907
01:10:18,230 --> 01:10:22,740
[Étudiants] Retour faux.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Sinon, eh bien, je n'ai pas besoin de l'autre.

909
01:10:26,160 --> 01:10:30,250
Si c'était mon cas une autre base.

910
01:10:30,250 --> 01:10:32,450
[Étudiants] Arbre de la valeur? Ouais >>.

911
01:10:32,450 --> 01:10:36,430
Donc, si (arbre-> valeur == valeur.

912
01:10:36,430 --> 01:10:39,920
Remarquez que nous sommes de retour à noeud *, ** noeud ne s?

913
01:10:39,920 --> 01:10:42,990
Contient n'aurez jamais besoin d'utiliser un nœud **,

914
01:10:42,990 --> 01:10:45,480
puisque nous ne modifient pas les pointeurs.

915
01:10:45,480 --> 01:10:50,540
Nous sommes en train de les traverser.

916
01:10:50,540 --> 01:10:53,830
Si cela se produit, nous voulons retourner vrai.

917
01:10:53,830 --> 01:10:58,270
Sinon nous voulons traverser les enfants.

918
01:10:58,270 --> 01:11:02,620
Donc, nous ne pouvons pas raisonner pour savoir si tout ce qui précède est moins

919
01:11:02,620 --> 01:11:05,390
et tout ce qui suit est plus grande.

920
01:11:05,390 --> 01:11:09,590
Alors, quelle est notre situation va être ici - ou, qu'allons-nous faire?

921
01:11:09,590 --> 01:11:11,840
[Étudiant, inintelligible] >> Oui.

922
01:11:11,840 --> 01:11:17,400
Retour contient (valeur, arbre-> gauche)

923
01:11:17,400 --> 01:11:26,860
ou contient (valeur, arbre-> droite). Et c'est tout.

924
01:11:26,860 --> 01:11:29,080
Et remarquez qu'il ya une certaine évaluation de court-circuit,

925
01:11:29,080 --> 01:11:32,520
où si l'on arrive à trouver la valeur dans l'arborescence de gauche,

926
01:11:32,520 --> 01:11:36,820
nous n'avons jamais besoin de regarder le bon arbre.

927
01:11:36,820 --> 01:11:40,430
C'est la fonction entière.

928
01:11:40,430 --> 01:11:43,690
Maintenant, nous allons le faire de manière itérative,

929
01:11:43,690 --> 01:11:48,060
qui va être moins agréable.

930
01:11:48,060 --> 01:11:54,750
Nous allons prendre le départ habituel de noeud * actu arbre =.

931
01:11:54,750 --> 01:12:03,250
While (actu! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rapidement aller voir un problème.

933
01:12:08,600 --> 01:12:12,250
Si actu - ici, si jamais nous sortir de cela,

934
01:12:12,250 --> 01:12:16,020
alors nous sommes à court de choses à regarder, alors retourner faux.

935
01:12:16,020 --> 01:12:24,810
Si (actu-> valeur == valeur), retournez true.

936
01:12:24,810 --> 01:12:32,910
Alors maintenant, nous sommes dans un lieu -

937
01:12:32,910 --> 01:12:36,250
nous ne savons pas si nous voulons aller à gauche ou à droite.

938
01:12:36,250 --> 01:12:44,590
Ainsi arbitraire, nous allons simplement aller à gauche.

939
01:12:44,590 --> 01:12:47,910
J'ai évidemment fonctionner dans une question où j'ai complètement abandonné tout -

940
01:12:47,910 --> 01:12:50,760
Je ne jamais vérifier le côté gauche d'un arbre.

941
01:12:50,760 --> 01:12:56,050
Je ne pourrai jamais vérifier quoi que ce soit qui est un enfant droite de quoi que ce soit.

942
01:12:56,050 --> 01:13:00,910
Comment puis-je résoudre ce problème?

943
01:13:00,910 --> 01:13:05,260
[Étudiants] Vous devez garder une trace de la gauche et la droite dans une pile.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Ouais. Donc, nous allons faire

945
01:13:13,710 --> 01:13:32,360
struct liste, noeud * n, puis noeud ** prochaine?

946
01:13:32,360 --> 01:13:40,240
Je pense que ce qui fonctionne parfaitement.

947
01:13:40,240 --> 01:13:45,940
Nous voulons aller sur la gauche, ou let's - ici.

948
01:13:45,940 --> 01:13:54,350
= Struct liste de la liste, il va commencer

949
01:13:54,350 --> 01:13:58,170
sur cette liste struct.

950
01:13:58,170 --> 01:14:04,040
* Liste = NULL. Alors que va être notre liste chaînée

951
01:14:04,040 --> 01:14:08,430
de sous-arbres que nous avons sautés.

952
01:14:08,430 --> 01:14:13,800
Nous allons maintenant traverser à gauche,

953
01:14:13,800 --> 01:14:17,870
mais depuis que nous avons inévitablement besoin de revenir vers la droite,

954
01:14:17,870 --> 01:14:26,140
Nous allons garder le côté droit à l'intérieur de notre liste struct.

955
01:14:26,140 --> 01:14:32,620
Ensuite, nous aurons new_list ou d'une structure,

956
01:14:32,620 --> 01:14:41,080
struct liste *, new_list = malloc (sizeof (liste)).

957
01:14:41,080 --> 01:14:44,920
Je vais ignorer le contrôle des erreurs, mais vous devriez vérifier pour voir si elle est null.

958
01:14:44,920 --> 01:14:50,540
New_list le nœud auquel il va pointer vers -

959
01:14:50,540 --> 01:14:56,890
oh, c'est pour ça que je le voulais ici. Il va pointer vers une liste struct seconde.

960
01:14:56,890 --> 01:15:02,380
C'est juste la façon dont le travail lié listes.

961
01:15:02,380 --> 01:15:04,810
C'est la même chose comme une liste liée int

962
01:15:04,810 --> 01:15:06,960
sauf que nous ne faisons que remplacer int * avec noeud.

963
01:15:06,960 --> 01:15:11,040
C'est exactement la même chose.

964
01:15:11,040 --> 01:15:15,100
Donc new_list, la valeur de notre noeud new_list,

965
01:15:15,100 --> 01:15:19,120
va être actu-> droite.

966
01:15:19,120 --> 01:15:24,280
La valeur de notre new_list-> suivant va être notre liste originale,

967
01:15:24,280 --> 01:15:30,760
et ensuite nous allons mettre à jour notre liste pour pointer vers new_list.

968
01:15:30,760 --> 01:15:33,650
>> Maintenant, nous devons une sorte de mode de choses de traction,

969
01:15:33,650 --> 01:15:37,020
comme nous l'avons traversé le sous-arbre gauche entier.

970
01:15:37,020 --> 01:15:40,480
Maintenant, nous devons tirer des choses hors de lui,

971
01:15:40,480 --> 01:15:43,850
comme cur est nulle, nous ne voulons pas simplement renvoyer false.

972
01:15:43,850 --> 01:15:50,370
Nous voulons maintenant tirer en dehors de notre nouvelle liste.

973
01:15:50,370 --> 01:15:53,690
Une façon pratique de le faire - bien, en fait, il ya plusieurs façons de le faire.

974
01:15:53,690 --> 01:15:56,680
Quelqu'un at-il une suggestion?

975
01:15:56,680 --> 01:15:58,790
Où je devrais faire ceci ou comment je dois faire?

976
01:15:58,790 --> 01:16:08,010
Nous n'avons que quelques minutes, mais des suggestions?

977
01:16:08,010 --> 01:16:14,750
Au lieu de - dans un sens, au lieu de notre condition étant alors que,

978
01:16:14,750 --> 01:16:17,090
ce que nous sommes en train de regarder n'est pas nulle,

979
01:16:17,090 --> 01:16:22,340
au contraire, nous allons continuer d'aller jusqu'à notre liste elle-même est nulle.

980
01:16:22,340 --> 01:16:25,680
Donc, si notre liste finit par être nulle,

981
01:16:25,680 --> 01:16:30,680
puis nous avons plus de choses à chercher, à chercher plus.

982
01:16:30,680 --> 01:16:39,860
Mais cela veut dire que la première chose dans notre liste va juste être le premier nœud.

983
01:16:39,860 --> 01:16:49,730
La première chose sera - nous n'avons plus besoin de voir ça.

984
01:16:49,730 --> 01:16:58,710
Donc liste-> n sera notre arbre.

985
01:16:58,710 --> 01:17:02,860
liste-> suivant va être nulle.

986
01:17:02,860 --> 01:17:07,580
Et maintenant, alors que la liste n'est pas nulle d'égalité.

987
01:17:07,580 --> 01:17:11,610
Actu est en train de tirer quelque chose de notre liste.

988
01:17:11,610 --> 01:17:13,500
Donc actu va égale liste-> n.

989
01:17:13,500 --> 01:17:20,850
Et puis, la liste va égale liste-> n, ou une liste-> suivant.

990
01:17:20,850 --> 01:17:23,480
Donc, si la valeur est égale à la valeur actu.

991
01:17:23,480 --> 01:17:28,790
Maintenant, nous pouvons ajouter à la fois notre droit et notre pointeur pointeur vers la gauche

992
01:17:28,790 --> 01:17:32,900
tant qu'ils ne sont pas nuls.

993
01:17:32,900 --> 01:17:36,390
Ici, je pense que nous aurions dû le faire en premier lieu.

994
01:17:36,390 --> 01:17:44,080
Si (actu-> droite! = NULL)

995
01:17:44,080 --> 01:17:56,380
alors nous allons insérer ce noeud à notre liste.

996
01:17:56,380 --> 01:17:59,290
Si (actu-> gauche), c'est un peu de travail supplémentaire, mais c'est très bien.

997
01:17:59,290 --> 01:18:02,690
Si (actu-> gauche! = NULL),

998
01:18:02,690 --> 01:18:14,310
et nous allons insérer la gauche dans notre liste chaînée,

999
01:18:14,310 --> 01:18:19,700
et qui doit être elle.

1000
01:18:19,700 --> 01:18:22,670
Nous itérer - aussi longtemps que nous avons quelque chose dans notre liste,

1001
01:18:22,670 --> 01:18:26,640
nous avons un autre noeud à regarder.

1002
01:18:26,640 --> 01:18:28,920
Nous cherchons donc à ce noeud,

1003
01:18:28,920 --> 01:18:31,390
nous avançons notre liste à la suivante.

1004
01:18:31,390 --> 01:18:34,060
Si ce nœud est la valeur que nous recherchons, nous pouvons retourner la valeur true.

1005
01:18:34,060 --> 01:18:37,640
Sinon insérer les deux sous-arbres gauche et droit de notre,

1006
01:18:37,640 --> 01:18:40,510
tant qu'ils ne sont pas nuls, dans notre liste

1007
01:18:40,510 --> 01:18:43,120
de sorte que nous inévitablement sur eux.

1008
01:18:43,120 --> 01:18:45,160
Donc, si elles ne sont pas nulles,

1009
01:18:45,160 --> 01:18:47,950
si notre pointeur de racine souligné deux choses,

1010
01:18:47,950 --> 01:18:51,670
puis dans un premier temps nous avons tiré quelque chose pour que notre liste finit par être nulle.

1011
01:18:51,670 --> 01:18:56,890
Et puis nous avons mis deux choses en, maintenant, notre liste est de taille 2.

1012
01:18:56,890 --> 01:19:00,030
Ensuite, nous allons faire une boucle de retour et nous sommes juste en train de tirer,

1013
01:19:00,030 --> 01:19:04,250
disons, le pointeur de la gauche de notre nœud racine.

1014
01:19:04,250 --> 01:19:07,730
Et que vais continuer d'avancer, nous allons finir par une boucle sur tout.

1015
01:19:07,730 --> 01:19:11,280
>> Notez que ce fut beaucoup plus compliqué

1016
01:19:11,280 --> 01:19:14,160
dans la solution récursive.

1017
01:19:14,160 --> 01:19:17,260
Et je l'ai dit à plusieurs reprises

1018
01:19:17,260 --> 01:19:25,120
que la solution récursive est généralement beaucoup plus en commun avec la solution itérative.

1019
01:19:25,120 --> 01:19:30,820
Ici, c'est exactement ce que la solution récursive fait.

1020
01:19:30,820 --> 01:19:36,740
Le seul changement est que, plutôt que de manière implicite à l'aide de la pile, la pile du programme,

1021
01:19:36,740 --> 01:19:40,840
que votre façon de garder une trace de ce que vous avez toujours besoin nœuds à visiter,

1022
01:19:40,840 --> 01:19:45,430
Maintenant, vous devez utiliser explicitement une liste chaînée.

1023
01:19:45,430 --> 01:19:49,070
Dans les deux cas, vous gardez une trace de ce noeud doit encore être visités.

1024
01:19:49,070 --> 01:19:51,790
Dans le cas récursif c'est juste plus facile, car une pile

1025
01:19:51,790 --> 01:19:57,100
est mis en œuvre pour vous que la pile du programme.

1026
01:19:57,100 --> 01:19:59,550
Notez que cette liste chaînée, il s'agit d'une pile.

1027
01:19:59,550 --> 01:20:01,580
Quel que soit nous venons de mettre sur la pile

1028
01:20:01,580 --> 01:20:09,960
est immédiatement ce que nous allons retirer la pile pour la prochaine visite.

1029
01:20:09,960 --> 01:20:14,380
Nous n'avons plus de temps, mais des questions?

1030
01:20:14,380 --> 01:20:23,530
[Étudiant, inintelligible]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Ouais. Donc, si nous avons notre liste chaînée,

1032
01:20:27,790 --> 01:20:30,150
actuelle va pointer vers ce type,

1033
01:20:30,150 --> 01:20:34,690
et maintenant nous ne faisons que progresser notre liste chaînée de se concentrer sur ce gars.

1034
01:20:34,690 --> 01:20:44,200
Nous traversant sur la liste chaînée dans cette ligne.

1035
01:20:44,200 --> 01:20:51,200
Et puis je suppose que nous devrions libérer notre liste chaînée et des trucs

1036
01:20:51,200 --> 01:20:53,880
une fois avant de retourner vrai ou faux, nous devons

1037
01:20:53,880 --> 01:20:57,360
itérer sur notre liste, et toujours ici-bas, je suppose,

1038
01:20:57,360 --> 01:21:03,900
si nous actu droit n'est pas égal à, l'ajouter, alors maintenant nous voulons libérer

1039
01:21:03,900 --> 01:21:09,600
actu parce que, bon, ne nous oubliez complètement sur la liste? Ouais.

1040
01:21:09,600 --> 01:21:12,880
C'est donc ce que nous voulons faire ici.

1041
01:21:12,880 --> 01:21:16,730
Où est le pointeur?

1042
01:21:16,730 --> 01:21:23,320
Actu était alors - nous voulons une liste struct * 10 équivaut à la liste suivante.

1043
01:21:23,320 --> 01:21:29,240
Liste libre, liste = temp.

1044
01:21:29,240 --> 01:21:32,820
Et dans le cas où l'on retourne vrai, nous n'avons pas besoin d'itérer

1045
01:21:32,820 --> 01:21:37,050
sur le reste de notre liste chaînée libérant les choses.

1046
01:21:37,050 --> 01:21:39,700
La bonne chose à propos de la solution récursive est de libérer les choses

1047
01:21:39,700 --> 01:21:44,930
signifie simplement factorings popping de la pile qui va se passer pour vous.

1048
01:21:44,930 --> 01:21:50,720
Donc, nous sommes passés de quelque chose qui est comme 3 lignes de dur-à-penser-à propos du code

1049
01:21:50,720 --> 01:21:57,520
à quelque chose qui est beaucoup beaucoup plus dur-à-penser-sur lignes de code.

1050
01:21:57,520 --> 01:22:00,620
D'autres questions?

1051
01:22:00,620 --> 01:22:08,760
Très bien. Nous sommes bons. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]