[Powered by Google Translate] [Section 7: Plus confortable]
[Rob Bowden] [Université de Harvard]
[C'est CS50] [CS50.TV]
Très bien. Donc, comme je l'ai dit dans mon email,
cela va être une section binary-tree-d'œuvre.
Mais il n'ya pas que de nombreuses questions.
Donc, nous allons essayer de tirer chaque question
et entrer dans le détail douloureuse de toutes les meilleures façons de faire les choses.
Ainsi, dès le début, nous passons par des exemples de dessins d'arbres binaires et d'autres choses.
Donc, ici, «Se rappeler qu'un arbre binaire possède des nœuds semblables à ceux d'une liste chaînée,
sauf qu'au lieu d'un pointeur, il ya deux: un pour «enfant» de la gauche
et l'autre pour le droit "enfant". "
Ainsi, un arbre binaire, c'est comme une liste chaînée,
l'exception de la structure va avoir deux pointeurs.
Il ya des arbres ternaires, qui vont avoir trois pointeurs,
il ya des arbres n-aires, qui ont seulement un pointeur générique
que vous aurez ensuite à malloc être assez grande pour avoir
pointeurs suffisamment à tous les enfants possibles.
Donc arbre binaire arrive juste pour avoir un nombre constant de deux.
Si vous voulez, vous pouvez donner une liste chaînée comme un arbre unaire,
mais je ne pense pas que quiconque appelle ça.
«Dessinez un diagramme des boîtes-et-flèches d'un nœud de l'arbre binaire
contenant le numéro préféré de Nate, 7, où chaque enfant pointeur est nul. "
Ainsi, le mode iPad.
>> Ça va être assez simple.
Nous allons juste faire un nœud, je vais la dessiner comme un carré.
Et je vais tirer les valeurs ici.
Ainsi, la valeur sera déposée à cet endroit,
et puis ici-bas, nous aurons le pointeur de la gauche sur la gauche et la droite pointeur sur la droite.
Et il est très bien si la convention d'appeler la gauche et la droite, les noms pointeur.
Ces deux vont être nulle.
Cela va juste être nulle, et qui va juste être nulle.
D'accord. Donc, retour à ici.
«Avec une liste chaînée, nous n'avons eu à stocker un pointeur
le premier nœud de la liste dans l'ordre de se rappeler toute la liste liée, ou toute la liste.
De même, avec des arbres, il suffit de stocker un pointeur
à un seul nœud dans le but de mémoriser l'arbre tout entier.
Ce nœud est calle la «racine» de l'arbre.
S'appuyer sur le diagramme d'avant ou de dessiner un nouveau
de telle sorte que vous avez une représentation boîtes-et-flèches d'un arbre binaire
avec la valeur 7, puis 3 dans la gauche,
puis 9 à droite, puis 6 sur le droit de la 3 ".
Voyons voir si je peux me rappeler tout cela dans ma tête.
Donc cela va être notre racine ici.
Nous aurons quelques pointeur quelque part, quelque chose que nous appellerons racine,
et il pointe vers ce type.
Maintenant, pour faire un nouveau noeud,
qu'est-ce que nous avons, 3 à gauche?
Ainsi, un nouveau noeud avec 3, et il souligne initialement nulle.
Je vais mettre N.
Maintenant, nous voulons faire cela, allez à gauche de 7.
Donc, nous changeons ce pointeur pour pointer désormais à ce type.
Et nous faisons de même. Nous voulons un 9 par ici
qui, au départ juste dit nulle.
Nous allons changer ce pointeur, pointez sur 9,
et maintenant nous voulons mettre 6 à la droite de 3.
Donc, ça va - faire un 6.
Et ce gars il remarquer.
D'accord. Donc, c'est tout ce qu'il nous demande de faire.
>> Maintenant, nous allons passer en revue certains termes.
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.
Le contenant 7. Les noeuds dans la partie inférieure de l'arbre sont appelés les feuilles.
Tout nœud qui vient de nulle comme ses enfants est une feuille.
Il est donc possible, si notre arbre binaire est juste un noeud unique,
qu'un arbre est une feuille, et c'est tout.
"La 'hauteur' de l'arbre est le nombre de sauts que vous avez à faire
à obtenir à partir du haut de la feuille. "
Nous allons entrer, en une seconde, la différence
entre les arbres binaires symétriques et asymétriques,
mais pour l'instant, la hauteur totale de cet arbre
Je dirais 3, mais si vous comptez le nombre de sauts
vous avez à faire pour arriver à 9, alors c'est vraiment seulement une hauteur de 2.
À l'heure actuelle il s'agit d'un arbre binaire asymétrique,
mais nous allons parlé équilibré quand il arrive à être pertinent.
Alors maintenant, nous pouvons parler de nœuds dans une arborescence en termes
par rapport aux autres noeuds dans l'arbre.
Alors maintenant, nous avons des parents, des enfants, des frères et sœurs, ascendants et descendants.
Ils sont de bon sens assez commun, ce qu'ils veulent dire.
Si nous demandons - ses parents.
Alors, quelle est la société mère de 3?
[Etudiants] 7. Ouais >>. Le parent va juste être ce que fait pour vous.
Puis ce sont les enfants de 7?
[Etudiants] 3 et 9. Ouais >>.
Notez que les «enfants» signifie littéralement les enfants,
donc 6 ne s'applique pas, parce que c'est comme un petit enfant.
Mais alors, si nous allons descendants, alors quelles sont les descendants des 7?
[Etudiants] 3, 6 et 9. Ouais >>.
Les descendants du nœud racine va être tout dans l'arbre,
sauf peut-être le nœud racine elle-même, si vous ne voulez pas de considérer que le descendant.
Et enfin, les ancêtres, c'est donc la direction opposée.
Alors, quelles sont les ancêtres de 6?
[Etudiants] 3 et 7. Ouais >>. 9 n'est pas inclus.
C'est simplement le dos lignée directe à la racine
va être vos ancêtres.
>> "On dit qu'un arbre binaire est« ordonné »si pour chaque nœud de l'arbre,
tous ses descendants à gauche ont des valeurs moindres
et tous ceux de droite ont des valeurs supérieures.
Par exemple, l'arbre ci-dessus est commandé mais il n'est pas le seul arrangement possible ordonné. "
Avant d'en arriver là,
un arbre binaire ordonné est également connu comme un arbre binaire de recherche.
Ici, il nous arrive d'être l'appeler un arbre binaire ordonné,
mais je n'ai jamais entendu dire qu'il a appelé un arbre binaire ordonné avant,
et sur un questionnaire que nous sommes beaucoup plus susceptibles de mettre arbre binaire de recherche.
Ils sont l'un et le même,
et il est important que vous la distinction entre arbre binaire et arbre binaire de recherche.
Un arbre binaire est juste un arbre qui pointe vers deux choses.
Chaque nœud fait à deux choses.
Il n'ya pas de raisonner sur les valeurs qui elle pointe.
Donc, comme ici, car c'est un arbre binaire de recherche,
nous savons que si nous allons à gauche de 7,
alors toutes les valeurs que l'on peut éventuellement atteindre
en allant de gauche 7 à être inférieur à 7.
Notez que toutes les valeurs inférieures à 7 sont 3 et 6.
Ce sont tous sur la gauche de 7.
Si nous allons à droite de 7, tout doit être supérieur à 7,
si 9 est à la droite de 7, de sorte que nous sommes bons.
Ce n'est pas le cas pour un arbre binaire,
pour un arbre binaire ordinaire, nous pouvons juste 3 en haut, 7 à gauche,
9 vers la gauche de 7, il n'y a pas de commande de valeurs quelconques.
Maintenant, nous ne réalisons pas cela parce que c'est fastidieux et inutile,
mais «essayer d'en tirer le plus d'arbres ordonnés comme vous pouvez le penser
en utilisant les numéros 7, 9, 3, et 6.
Combien d'arrangements distincts sont-ils? Quelle est la hauteur de chacun d'eux? "
>> Nous ferons un couple, mais l'idée principale est,
ce n'est en aucun cas une représentation unique d'un arbre binaire contenant ces valeurs.
Tous nous avons besoin est un arbre binaire qui contient 7, 3, 6 et 9.
Une autre possible valable serait la racine est 3,
allez vers la gauche et il est 6, allez à gauche et il a 7 ans,
allez vers la gauche et il est 9.
C'est un arbre binaire de recherche tout à fait valable.
Ce n'est pas très utile, parce que c'est comme une liste chaînée
et tous ces pointeurs sont juste nul.
Mais c'est un arbre valide. Ouais?
[Étudiants] Ne pas les valeurs doivent être plus à droite?
Ou est-ce -? Ceux-ci >> je voulais aller dans l'autre sens.
Il ya aussi - oui, nous allons passer cela.
9, 7, 6, 3. Bonne prise.
Il reste encore à obéir à ce que un arbre de recherche binaire est censé faire.
Donc tout ce qui précède doit être inférieur à un nœud donné.
Nous pourrions tout simplement déplacer, disons, le 6 et le mettre ici.
Non, nous ne pouvons pas. Pourquoi dois-je continuer à le faire?
Faisons - est ici 6, voici 7, 6 points à 3.
Ceci est encore un arbre binaire valide recherche.
Quel est le problème si je - nous allons voir si je peux arriver à un arrangement.
Ouais, d'accord. Alors quel est le problème avec cet arbre?
Je crois que je vous ai déjà donné une indication qu'il ya quelque chose de mal à cela.
Pourquoi dois-je continuer à le faire?
D'accord. Cela semble raisonnable.
Si nous regardons chaque nœud, comme 7, puis vers la gauche de la figure 7 est un 3.
Nous avons donc 3, la chose à la droite de la figure 3 est un 6.
Et si vous regardez à 6, la seule chose à la droite de la figure 6 est un 9.
Alors, pourquoi n'est-ce pas un arbre binaire valide la recherche?
[Etudiants] 9 est toujours à la gauche de 7. Ouais >>.
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.
Si nous allons à gauche de 7, nous arrivons à 3 et nous pouvons encore obtenir à 6,
nous pouvons encore obtenir à 9, mais en ayant passé moins de 7,
nous ne devrions pas être en mesure d'arriver à un chiffre qui est supérieur à 7.
Donc, ce n'est pas un arbre binaire valide recherche.
>> Mon frère avait fait une question d'entrevue
qui était essentiellement cela, il suffit de code quelque chose pour valider
si un arbre est un arbre binaire de recherche,
et la première chose qu'il a fait était juste vérifier
si la gauche et la droite sont corrects, puis itérer là-bas.
Mais vous ne pouvez pas faire cela, vous devez garder une trace
du fait que, maintenant que je suis allé à gauche de 7,
tout dans ce sous-arbre doit être inférieur à 7.
L'algorithme correct a besoin de garder une trace
des limites à ce que les valeurs peuvent éventuellement tomber po
Nous n'allons pas passer par chacun d'eux.
Il ya une relation de récurrence agréable,
même si nous n'avons pas obtenu de ceux-ci, ou nous n'arriverons pas à ceux qui,
définir combien il ya effectivement.
Donc, il ya 14 d'entre eux.
L'idée de la façon dont vous le feriez est mathématiquement comme,
vous pouvez choisir n'importe quel seul à être le nœud racine,
et puis si je prends 7 pour être le nœud racine,
puis il ya, disons, quelques chiffres qui peuvent aller être mon nœud de gauche,
et il ya des chiffres qui peuvent être mon nœud de droit,
mais si je l'ai n le nombre total, le montant qui peut aller vers la gauche
plus le montant qui peut aller vers la droite est n - 1.
Ainsi, des nombres restants, ils doivent être en mesure d'aller soit vers la gauche ou la droite.
Il semble difficile que, si je mets 3 premiers alors tout doit aller vers la gauche,
mais si je mets 7 puis certaines choses ne peuvent aller à gauche la et certaines choses peuvent aller vers la droite.
Et par '3 'abord, je vise tout peut aller vers la droite.
C'est vraiment, vous avez juste à penser que,
combien de choses peuvent aller au niveau suivant de l'arbre.
Et il sort à 14; ou vous pouvez dessiner chacun d'entre eux,
et alors vous aurez 14.
>> Pour en revenir ici,
«Ordonné arbres binaires sont cool parce qu'on peut chercher dans les
d'une manière très semblable à la recherche sur un tableau trié.
Pour ce faire, nous partons à la racine et de travailler notre chemin vers le bas de l'arbre
vers les feuilles, vérifier les valeurs de chaque nœud à l'encontre des valeurs que nous sommes à la recherche d'.
Si la valeur du nœud actuel est inférieur à la valeur que nous recherchons,
vous aller ensuite à l'enfant le droit du nœud.
Sinon, vous allez au fils gauche du nœud.
À un certain point, vous aurez soit trouver la valeur que vous cherchez, ou vous tomberez sur un nul,
indiquant la valeur n'est pas dans l'arbre. "
Je dois redessiner l'arbre que nous avions avant, qui va prendre une seconde.
Mais nous voulons rechercher si 6, 10 et 1 sont dans l'arbre.
Alors qu'est-ce que c'était, 7, 9, 3, 6. D'accord.
Les chiffres que vous souhaitez rechercher, nous voulons examiner en hausse de 6.
Comment cela fonctionne-t algorithme?
Eh bien, nous avons aussi des pointeur de racine de notre arbre.
Et nous irions à la racine et de dire, est-ce une valeur égale à la valeur que nous cherchons?
Nous sommes donc à la recherche de 6, donc ce n'est pas égale.
Nous avons donc continuer, et maintenant nous dire, d'accord, si 6 est inférieur à 7.
Est-ce que cela veut dire que nous voulons aller vers la gauche, ou voulons-nous aller à droite?
[Étudiants] Gauche. Ouais >>.
Il est beaucoup plus facile, tout ce que vous avez à faire est de dessiner un nœud possible de l'arbre
et puis vous ne - au lieu d'essayer de penser dans votre tête,
ok, si c'est moins, puis-je aller à gauche ou aller à droite,
simplement en regardant cette image, il est très clair que je dois aller vers la gauche
si le noeud est supérieure à la valeur que je suis à la recherche.
Alors vous allez vers la gauche, maintenant je suis à 3.
Je tiens à - 3 est inférieure à la valeur que je cherche, qui est de 6.
Alors on va vers la droite, et maintenant je me retrouve à 6,
qui est la valeur que je cherche, donc je retourne vrai.
La valeur suivante, je vais chercher, c'est 10.
D'accord. Donc, 10, désormais, va - couper que - va suivre la racine.
Maintenant, 10 va être supérieur à 7, donc je veux regarder à droite.
Je vais venir ici, 10 va être supérieur à 9,
donc je vais avoir à regarder vers la droite.
Je viens par ici, mais ici je suis maintenant à zéro.
Que dois-je faire si j'ai touché nulle?
[Étudiants] Retour faux? Ouais >>. Je n'ai pas trouvé 10.
1 va être un cas presque identique,
sauf qu'il va juste être retourné, au lieu de regarder
sur le côté droit, je vais regarder vers le bas sur le côté gauche.
>> Maintenant, je pense que nous obtenons réellement le code.
Voici où - ouvrir l'appareil CS50 et naviguer dans votre chemin,
mais vous pouvez aussi le faire dans l'espace.
C'est probablement idéal pour le faire dans l'espace,
car nous pouvons travailler dans l'espace.
"Nous allons d'abord besoin d'une définition de type nouveau pour un nœud de l'arbre binaire contenant les valeurs int.
Utilisation du passe-partout typedef ci-dessous,
créer une définition de type nouveau pour un noeud dans un arbre binaire.
Si vous êtes coincé. . . "Blah, blah, blah. D'accord.
Donc, il faut mettre le passe-partout ici,
typedef struct noeud, et un noeud. Ouais, d'accord.
Alors, quels sont les domaines que nous allons voulons dans notre noeud?
[Étudiants] Int puis deux pointeurs?
>> Int valeur, deux pointeurs? Comment puis-je écrire les pointeurs?
[Étudiants] Struct. >> Je devrais effectuer un zoom avant Ouais, donc noeud struct * à gauche,
struct noeud * et droite.
Et souvenez-vous de la discussion de la dernière fois,
que cela n'a aucun sens, cela n'a aucun sens,
cela n'a aucun sens.
Vous devez tout ce qu'il ya dans le but de définir cette structure récursive.
Bon, alors c'est ce que notre arbre va ressembler.
Si nous faisions un arbre ternaire, puis un nœud pourrait ressembler b1, b2, b3 struct noeud *,
où b est une branche - en fait, j'ai plus entendu gauche, milieu, droite, mais peu importe.
Nous ne se soucient binaire, droite, gauche.
«Maintenant déclarer une variable de nœud mondial * de la racine de l'arbre."
Donc, nous n'allons pas le faire.
Afin de rendre les choses un peu plus difficile et plus généralisée,
nous n'aurons pas une variable de nœud mondial.
Au lieu de cela, en principal, nous déclarons toutes nos affaires nœud,
et cela signifie que ci-dessous, lorsque nous avons commencer à courir
notre fonction contains et notre fonction d'insertion,
au lieu de nos contient une fonction simplement en utilisant cette variable de nœud mondial,
nous allons devoir le prendre comme argument l'arbre que nous voulons c'est de traiter.
Avoir la variable globale était censé rendre les choses plus faciles.
Nous allons faire les choses plus difficiles.
Maintenant, prenez une minute pour simplement faire ce genre de chose,
où à l'intérieur du principal que vous souhaitez créer cet arbre, et c'est tout ce que vous voulez faire.
Essayez de construire cet arbre dans votre fonction principale.
>> D'accord. Donc, vous n'avez même pas besoin d'avoir construit l'arbre tout le chemin encore.
Mais ce que quelqu'un a quelque chose que je pouvais tirer vers le haut
pour montrer comment on peut commencer à construire un tel arbre?
[Étudiants] de quelqu'un frapper, en essayant de sortir.
[Bowden] Toute l'aise avec leur construction de l'arbre?
[Étudiants] Bien sûr. Ce n'est pas fait. >> C'est bien. Nous pouvons simplement terminer -
oh, pouvez-vous l'enregistrer? Hourra.
Nous avons donc ici - oh, je suis un peu coupé.
Suis-je un zoom avant?
Zoomer, faire défiler sur. >> J'ai une question. Ouais >>?
[Étudiants] Lorsque vous définissez une structure, sont des choses comme initialisé à quelque chose?
[Bowden] No. >> Okay. Donc, vous devez initialiser -
[Bowden] No. Lorsque vous définissez ou lorsque vous déclarez une structure,
il n'est pas initialisé par défaut; c'est comme si vous déclarez un int.
C'est exactement la même chose. C'est comme si chacun de ses domaines individuels
peut avoir une valeur ordures dans celui-ci. >> Et est-il possible de définir - ou de déclarer une structure
de façon que le fait de les initialiser?
[Bowden] Oui. Ainsi, la syntaxe d'initialisation de raccourci
va ressembler -
Il ya deux façons de le faire. Je pense que nous devrions le compiler
pour faire Clang-vous le fait aussi.
L'ordre des arguments qui vient dans la structure,
vous mettez que l'ordre des arguments à l'intérieur de ces accolades.
Donc, si vous voulez l'initialiser à 9 et à gauche sont nuls et puis à droite est nulle,
il serait 9, null, null.
L'alternative est, et l'éditeur n'aime pas cette syntaxe,
et il pense que je veux un nouveau bloc,
mais l'alternative est quelque chose comme -
ici, je vais le mettre sur une nouvelle ligne.
Vous pouvez explicitement dire, j'ai oublié la syntaxe exacte.
Ainsi, vous pouvez explicitement appeler par leur nom, et dire:
. Valeur c, ou. = 9,. NULL = gauche.
Je suppose que ceux-ci doivent être des virgules.
. Droite = NULL, alors cette façon, vous ne
réellement besoin de connaître l'ordre de la structure,
et quand vous lisez ceci, c'est beaucoup plus explicite
sur ce que la valeur est en cours d'initialisation d'.
>> Cela arrive à être l'une des choses que -
oui, pour la plupart, C + + est un sur-ensemble de C.
Vous pouvez prendre le code C, le déplacer vers C + +, et il devrait compiler.
C'est l'une des choses que C + + ne prend pas en charge, afin que les gens ont tendance à ne pas le faire.
Je ne sais pas si c'est la seule raison pour laquelle les gens ont tendance à ne pas le faire,
mais au cas où j'avais besoin de l'utiliser nécessaires pour travailler avec C + + et je ne pouvais pas l'utiliser.
Un autre exemple de quelque chose qui ne fonctionne pas avec C + + est
comment malloc retourne un «void *», techniquement,
mais vous pourriez simplement dire tout ce char * x = malloc,
et il sera automatiquement converti en un char *.
C'est fonte automatique ne se fait pas en C + +.
Ce ne serait pas compiler, et vous auriez besoin de le dire explicitement
char *, malloc, que ce soit, de le jeter à un char *.
Il n'y a pas beaucoup de choses que C et C + + sont en désaccord sur,
mais ce sont deux.
Nous allons donc avec cette syntaxe.
Mais même si nous n'avons pas aller avec cette syntaxe,
ce qui est - peut-être le problème?
[Étudiants] Je n'ai pas besoin de le déréférencer? Ouais >>.
Rappelez-vous que la flèche a un déréférencement implicite,
et donc quand nous sommes juste face à une struct,
nous voulons utiliser. pour obtenir à l'intérieur du champ de la structure.
Et la seule fois où nous utilisons flèche, c'est quand nous voulons faire -
ainsi, la flèche est équivalent à -
c'est ce qu'il aurait voulu dire si j'ai utilisé flèche.
Tous les moyens flèche, ce déréférencement, maintenant je suis à un struct, et je peux obtenir sur le terrain.
Soit obtenir le champ directement ou déréférencer et obtenir sur le terrain -
Je suppose que ce doit être la valeur.
Mais ici, je fais face à tout un struct, pas un pointeur vers une struct,
et je ne peux donc pas utiliser la flèche.
Mais ce genre de chose que nous pouvons faire pour tous les nœuds.
Oh mon Dieu.
C'est 6, 7, et 3.
Ensuite, nous pouvons mettre en place les branches de notre arbre, nous pouvons avoir 7 -
nous pouvons avoir, à sa gauche doit pointer vers 3.
Alors, comment faisons-nous cela?
[Etudiants, inintelligible] >> Oui. L'adresse de node3,
et si vous n'avez pas d'adresse, il ne serait pas juste de compiler.
Mais n'oubliez pas que ce sont des pointeurs vers les noeuds suivants.
Le droit doit pointer à 9,
et 3 doit pointer sur le droit à 6.
Je pense que c'est tous ensemble. Des commentaires ou des questions?
[Étudiant, inintelligible] La racine va être 7.
Nous pouvons simplement dire nœud * ptr =
ou de la racine, = & node7.
>> Pour nos besoins, nous allons avoir affaire avec insert,
alors nous allons vouloir écrire une fonction pour insérer dans cet arbre binaire
et l'insert va inévitablement appeler malloc pour créer un nouveau nœud de cet arbre.
Donc, les choses vont déraper avec le fait que certains nœuds
sont actuellement dans la pile
et les autres nœuds vont se retrouver sur le tas quand on les insérer.
Ceci est tout à fait valable, mais la seule raison
nous sommes en mesure de le faire sur la pile
C'est parce que c'est un exemple artificiel que nous savons
l'arbre est supposé être réalisé sous la forme 7, 3, 6, 9.
Si nous n'avions pas cela, alors nous n'aurions pas à malloc en premier lieu.
Comme nous le verrons un peu plus tard, nous devrions être malloc'ing.
En ce moment il est parfaitement raisonnable de mettre sur la pile,
mais nous allons changer cela en une implémentation de malloc.
Ainsi, chacun de ceux-ci va maintenant être quelque chose comme
* node9 noeud = malloc (sizeof (noeud)).
Et maintenant, nous allons faire notre chèque.
if (node9 == NULL) - Je ne voulais pas que -
retourner 1, puis que nous pouvons faire node9-> parce que maintenant c'est un pointeur,
valeur = 6, node9-> gauche = NULL,
node9-> droite = NULL,
et nous allons devoir le faire pour chacun de ces nœuds.
Ainsi, au lieu, nous allons mettre à l'intérieur d'une fonction distincte.
Appelons-le noeud * build_node,
et cela est quelque peu similaire à l'API que nous offrons à codage de Huffman.
Nous vous donnons fonctions initialiseur pour un arbre
et deconstructor «fonctions» de ces arbres et les mêmes pour les forêts.
>> Donc, ici, nous allons avoir une fonction d'initialisation
pour compiler un nœud pour nous.
Et il va chercher à peu près exactement comme ça.
Et je vais même être paresseux et de ne pas changer le nom de la variable,
même si node9 ne fait pas plus de sens.
Oh, je suppose que la valeur node9 ne doit pas avoir été 6.
Maintenant nous pouvons revenir node9.
Et là, on doit retourner null.
Tout le monde d'accord sur cette fonction build-a-noeud?
Alors maintenant, nous pouvons simplement appeler cela de construire un nœud avec une valeur donnée et des pointeurs nuls.
Maintenant, nous pouvons l'appeler ainsi, nous pouvons faire noeud * node9 = build_node (9).
Et nous allons le faire. . .
6, 3, 7, 6, 3, 7.
Et maintenant, nous voulons mettre en place les pointeurs mêmes,
sauf que maintenant tout est déjà en termes de pointeurs
donc plus besoin de l'adresse d'.
D'accord. Alors, quelle est la dernière chose que je veux faire?
Il s'agit d'une vérification des erreurs que je ne fais pas.
Qu'est-ce que la construction noeud retour?
[Étudiant, inintelligible] >> Oui. Si malloc échoué, il va retourner null.
Donc, je vais le mettre lazily ici au lieu de faire un état pour chacun.
Si (node9 == NULL, ou - encore plus simple,
ce qui équivaut à un peu si ce n'est pas node9.
Donc, si pas node9, ou non Node6, ou non node3, ou non node7, retourner 1.
Peut-être que nous devrions imprimer malloc échoué, ou quelque chose.
[Étudiants] est fausse égale à null ainsi?
[Bowden] Toute valeur nulle est fausse.
Donc nulle est une valeur nulle.
Zéro est une valeur nulle. Faux est une valeur nulle.
Tout - à peu près les 2 seules valeurs nulles sont nuls et zéro,
faux est juste de hachage définie comme égale à zéro.
Cela s'applique également si nous déclarons une variable globale.
Si nous avions racine * noeud ici,
puis - la bonne chose à propos des variables globales, c'est qu'ils ont toujours une valeur initiale.
Ce n'est pas vrai des fonctions, faire à l'intérieur d'ici,
si nous avons, comme, * nœud ou le nœud x.
Nous n'avons aucune idée ce que x.value, x.whatever,
ou nous pourrions les imprimer et ils pourraient être arbitraire.
Ce n'est pas vrai de variables globales.
Racine, afin nœud ou le nœud x.
Par défaut, tout ce qui est global, si elle n'est pas explicitement initialisé à une certaine valeur,
a une valeur nulle comme valeur.
Donc ici, la racine * noeud, nous n'avons pas explicitement l'initialiser à rien,
si la valeur par défaut sera nulle, ce qui correspond à la valeur zéro des pointeurs.
La valeur par défaut de x va dire que x.value est égal à zéro,
x.left est nulle, et x.right est nulle.
Donc, puisqu'il s'agit d'une structure, tous les champs de la structure seront nulles.
Nous n'avons pas besoin de l'utiliser ici, cependant.
[Étudiants] Les structs sont différentes de celles d'autres variables, et les autres variables sont
des valeurs parasites, ce sont des zéros?
[Bowden] D'autres valeurs aussi. Donc, en x, x sera égal à zéro.
Si c'est avec une portée globale, il a une valeur initiale. Ok >>.
[Bowden] Soit la valeur initiale vous lui avez donné ou nul.
Je pense qui prend soin de tout cela.
>> D'accord. Ainsi, la partie suivante de la question demande,
"Maintenant, nous voulons écrire une fonction appelée contient
avec un prototype de bool contient une valeur int. "
Nous n'allons pas faire bool contient une valeur int.
Notre prototype va ressembler
bool contient (int value.
Et puis nous allons aussi lui passer l'arbre
qu'il convient de vérifier pour voir si elle a cette valeur.
Donc noeud * arbre). D'accord.
Et puis on peut l'appeler avec quelque chose comme:
peut-être que nous voudrons printf ou quelque chose.
Contient 6, notre racine.
Qui devrait renvoyer un ou vrai,
tandis que la racine contient 5 devrait retourner false.
Alors, prenez une seconde pour mettre en œuvre.
Vous pouvez le faire soit de manière itérative ou récursive.
La bonne chose au sujet de la façon dont nous avons mis les choses, c'est que
il se prête à notre solution récursive beaucoup plus facile
que la variable de façon globale fait.
Parce que si nous avons juste valeur contient int, alors nous n'avons aucun moyen de récursion vers le bas sous-arbres.
Nous aimerions avoir une fonction d'assistance distinct récursivement les sous-arbres vers le bas pour nous.
Mais depuis que nous avons changé pour prendre l'arbre comme un argument,
lequel il aurait toujours été en premier lieu,
maintenant nous pouvons recurse plus facilement.
Donc, itératif ou récursif, nous allons passer en revue tous les deux,
mais nous allons voir ce que les extrémités recursive par être assez facile.
D'accord. Quelqu'un at-il quelque chose que nous pouvons travailler avec?
>> [Étudiants] J'ai une solution itérative. >> Très bien, itératif.
Bon, ça a l'air bon.
Donc, nous voulons marcher à travers elle?
[Étudiants] Bien sûr. J'ai donc mis une variable temp pour obtenir le premier nœud de l'arbre.
Et puis je viens de boucle à travers tout température n'est pas nulle égale,
si tout était toujours dans l'arbre, je suppose.
Et si la valeur est égale à la valeur que temp est pointant vers,
puis il retourne cette valeur.
Dans le cas contraire, il vérifie si elle est sur le côté droit ou le côté gauche.
Si jamais vous avez une situation où il n'y a plus d'arbres,
puis il revient - il sort de la boucle et retourne false.
[Bowden] D'accord. Donc, cela semble bon.
Quelqu'un at-il des commentaires sur quelque chose?
Je n'ai pas de commentaires exactitude du tout.
La seule chose que nous pouvons faire est de ce type.
Oh, ça va aller un peu allongée.
Je vais arranger ça. D'accord.
>> Tout le monde devrait se rappeler comment fonctionne ternaire.
Il a certainement été quiz dans le passé
qui vous donnent une fonction avec un opérateur ternaire,
et de dire, de traduire cela, faire quelque chose qui n'utilise pas ternaire.
Donc, c'est un cas très fréquent quand je pense à utiliser ternaire,
où si une condition de définir une variable à quelque chose,
autre indication que même variable à autre chose.
C'est quelque chose que très souvent, peut être transformé en ce genre de chose
où mettre cette variable à cela - ou bien, est-ce vrai? Ensuite cela, sinon cela.
[Étudiants] Le premier est si vrai, non?
[Bowden] Ouais. La façon dont je lis toujours est égale à la valeur de température supérieure à la valeur de température,
puis cela, sinon cela. Il a posé une question.
Est-il plus? Ensuite, faites la première chose. D'autre faire la deuxième chose.
J'ai presque toujours - du côlon, je viens - dans ma tête, j'ai lu que d'autre.
>> Quelqu'un at-il une solution récursive?
D'accord. Celui-ci nous allons - il pourrait déjà être grande,
mais nous allons faire encore mieux.
C'est à peu près la même idée exacte.
C'est juste que, eh bien, voulez-vous expliquer?
[Étudiants] Bien sûr. Donc, nous faisons en sorte que l'arbre n'est pas null abord,
parce que si l'arbre est NULL, alors il va retourner faux parce que nous ne l'avons pas trouvé.
Et si il ya encore un arbre, nous entrons dans - nous vérifions d'abord si la valeur est le noeud courant.
Retourne vrai si c'est le cas, et si nous ne recurse sur la gauche ou la droite.
Est-ce que le son approprié? >> Mm-hmm. (Accord)
Donc remarquerez que ce n'est presque - structurellement très similaire à la solution itérative.
C'est juste qu'au lieu de récursion, nous avons eu une boucle while.
Et le scénario de base là où l'arbre n'est pas nulle égale
était la condition sous laquelle nous avons cassé hors de la boucle while.
Ils sont très similaires. Mais nous allons prendre un peu plus loin.
Maintenant, nous faisons la même chose ici.
Notez que nous retournant la même chose dans l'autre de ces lignes,
sauf pour un seul argument est différent.
Donc, nous allons faire cela dans un ternaire.
J'ai touché quelque chose option, et il a fait un symbole. D'accord.
Donc, nous allons revenir contient que.
Ceci est en train de devenir plusieurs lignes, eh bien, c'est un zoom avant.
Habituellement, comme une chose stylistique, je ne pense pas que beaucoup de gens
mettre un espace après la flèche, mais je suppose que si vous êtes cohérent, c'est bien.
Si la valeur est inférieure à la valeur des arbres, nous voulons recurse sur la gauche arbre,
d'autre nous voulons recurse à droite arbre.
C'était donc la première étape de faire ce regard plus petit.
L'étape deux de faire ce regard plus petit -
nous pouvons séparer plusieurs lignes.
D'accord. La deuxième étape de la faire paraître plus petit est ici,
si la valeur de retour est égal à la valeur des arbres, ou contient autre chose.
>> C'est une chose importante.
Je ne sais pas si il a dit explicitement dans la classe,
mais il est appelé court-circuit d'évaluation.
L'idée ici est la valeur == valeur des arbres.
Si cela est vrai, alors cela est vrai, et nous voulons »ou« avec tout ce qui est ici.
Ainsi, sans même y penser tout ce qui est ici,
ce qui est l'expression entière va revenir?
[Étudiants] True? >> Ouais, parce que vrai de rien,
or'd - or'd ou quoi que ce soit vrai est nécessairement vrai.
Donc dès que nous voyons valeur de retour = valeur des arbres,
nous allons juste pour retourner true.
Ne vais même pas recurse contient en outre sur toute la ligne.
Nous pouvons prendre un peu plus loin.
Arbre de retour n'est pas nulle d'égalité et tout cela.
Il a une fonction d'une seule ligne.
C'est aussi un exemple de court-circuit d'évaluation.
Mais maintenant, c'est la même idée -
au lieu de - si l'arbre n'est pas nulle d'égalité - ou bien,
si l'arbre fait nulle égale, ce qui est le cas mauvais,
si l'arbre est égal à NULL, alors la première condition va être faux.
Donc fausse AND avec quoi que ce soit va être quoi?
[Étudiants] Faux. Ouais >>. C'est l'autre moitié de court-circuit d'évaluation,
où si nul arbre ne pas égaux, alors nous n'allons pas même aller -
ou si l'arbre fait nulle égaux, alors nous n'allons pas faire value == valeur des arbres.
Nous allons juste revenir immédiatement faux.
Ce qui est important, car si elle n'a pas de court-circuit evaluate,
alors si nul arbre ne égales par ailleurs, cette deuxième condition va à la faute seg,
parce arbre-> valeur est nulle déréférencement.
Donc, c'est tout. Peut faire cela - se déplacer une fois terminé.
C'est une chose très commune aussi, ne pas faire cette simple ligne avec cela,
mais c'est une chose commune dans des conditions, peut-être pas ici,
mais si (arbre! = NULL, et l'arbre-> valeur == valeur), faire n'importe quoi.
Il s'agit d'une affection très fréquente, où, au lieu d'avoir
de briser ce en deux ifs, où voulez, c'est l'hypothèse nulle arbre?
Bon, ce n'est pas nul, alors maintenant est la valeur d'arbre égale à la valeur? Pour ce faire.
Au lieu de cela, cette condition, ce ne sera jamais seg faute
car il va éclater si cela arrive à être nulle.
Eh bien, je suppose que si votre arbre est un pointeur invalide complètement, il peut encore seg faute,
mais il ne peut pas seg faute si l'arbre est nulle.
Si elle était nulle, elle allait éclater avant que vous ne le pointeur déréférencé en premier lieu.
[Étudiants] Est-ce qu'on appelle l'évaluation paresseuse?
>> [Bowden] l'évaluation paresseuse est une chose distincte.
L'évaluation paresseuse ressemble plus à vous demander pour une valeur,
vous demander de calculer une valeur, en quelque sorte, mais vous n'en avez pas besoin immédiatement.
Donc, tant que vous en avez besoin, il n'est pas évaluée.
Ce n'est pas exactement la même chose, mais dans le pset Huffman,
il dit que nous "lazily" écrire.
La raison pour laquelle nous faisons cela parce que nous sommes en train de tampon d'écriture -
nous ne voulons pas d'écrire des bits individuels à la fois,
ou différents octets à la fois, au lieu que nous voulons obtenir un morceau d'octets.
Puis, une fois que nous avons un gros morceau d'octets, puis nous allons l'écrire.
Même si vous lui demandez d'écrire - et fwrite et fread faire le même genre de chose.
Ils tampon de votre lit et écrit.
Même si vous lui demandez d'écrire tout de suite, il ne sera probablement pas le cas.
Et vous ne pouvez pas être sûr que les choses vont être écrites
jusqu'à ce que vous appelez hfclose ou quoi que ce soit,
qui dit alors, d'accord, je ferme mon dossier,
cela signifie que je ferais mieux d'écrire tout ce que je n'ai pas encore écrite.
Il n'a pas besoin de tout écrire sur
jusqu'à ce que vous fermez le fichier, puis il a besoin.
Donc, c'est exactement ce que paresseux - il attend que cela doit arriver.
Ce - prendre 51 et vous y entrer plus en détail,
parce OCaml et tout en 51, tout est récursivité.
Il n'existe pas de solutions itératives, essentiellement.
Tout est récurrence et l'évaluation paresseuse
va être important pour un grand nombre de circonstances
où, si vous n'avez pas lazily évaluer, cela signifierait -
L'exemple est ruisseaux, qui sont infiniment long.
En théorie, vous pouvez penser à des nombres naturels en tant que flux de 1-2-3-4-5-6-7,
Tant de choses paresseusement évalués sont très bien.
Si je dis que je veux le dixième nombre, alors je peux évaluer jusqu'à la dixième nombre.
Si je veux le numéro centième, alors je peux évaluer jusqu'à concurrence du nombre centième.
Sans évaluation paresseuse, alors il va essayer d'évaluer tous les numéros immédiatement.
Vous évaluez une infinité de nombres, et c'est juste pas possible.
Donc, il ya beaucoup de cas où l'évaluation paresseuse
est tout simplement indispensable pour obtenir des choses à travailler.
>> Maintenant, nous voulons écrire insert insert où va être
même évolution dans sa définition.
Donc maintenant c'est insert bool (int value).
Nous allons changer cela à insert bool (int valeur, noeud * arbre).
Nous allons en fait pour changer cette fois un peu, nous allons voir pourquoi.
Et passons build_node, juste pour le plaisir de le faire,
ci-dessus insérez donc nous n'avons pas besoin d'écrire un prototype de fonction.
Ce qui est une indication que vous allez utiliser build_node dans l'insert.
D'accord. Prenez une minute pour cela.
Je pense que j'ai sauvé la révision, si vous voulez tirer de cela,
ou, du moins, je l'ai fait aujourd'hui.
Je voulais une légère cassure à réfléchir à la logique de l'insertion,
si vous ne pouvez pas y penser.
Fondamentalement, vous ne jamais être à l'insertion des feuilles.
Comme, si j'insère 1, alors je suis inévitablement à insérer 1 -
Je vais changer au noir - je vais être insérant 1 sur ici.
Ou si j'insère 4, je veux être insérant 4 sur ici.
Donc, peu importe ce que vous faites, vous allez être à l'insertion d'une feuille.
Tout ce que vous avez à faire est itérer descendre dans l'arborescence jusqu'à ce que vous arrivez à le nœud
qui devrait être parent du nœud, parent du nouveau nœud,
puis changer son pointeur vers la gauche ou la droite, selon que
il est supérieur ou inférieur au noeud courant.
Changer ce pointeur pour pointer vers votre nouveau nœud.
Donc itérer l'arbre, faire le point de feuille vers le nouveau nœud.
Également réfléchir à la raison qui interdit ce genre de situation auparavant,
où j'ai construit l'arbre binaire où elle était correcte
si vous seulement regardé un seul nœud,
mais 9 était à la gauche de 7 si vous itéré fond vers le bas.
Donc, c'est impossible dans ce scénario, car -
pensez à insérer 9 ou quelque chose, au tout premier nœud,
Je vais voir 7 et je vais juste aller à droite.
Donc, peu importe ce que je fais, si je suis en allant à l'insertion d'une feuille,
et une feuille à l'aide de l'algorithme approprié,
il va être impossible pour moi d'insérer 9 à la gauche de 7
parce que dès que j'ai touché 7 Je vais aller vers la droite.
Quelqu'un at-il quelque chose pour commencer?
[Étudiants] je fais. >> Bien sûr.
[Étudiant, inintelligible]
[Étudiant Autre, inintelligible]
[Bowden] Il est apprécié. D'accord. Voulez-vous expliquer?
>> [Étudiants] Puisque nous savons que nous avons été insertion
de nouveaux noeuds à l'extrémité de l'arbre,
J'ai bouclé à travers l'arbre de manière itérative
jusqu'à ce que j'arrive à un nœud qui fait la valeur null.
Et puis j'ai décidé de le mettre soit sur le côté droit ou le côté gauche
en utilisant cette variable raison, il m'a dit où le mettre.
Et puis, pour l'essentiel, je viens de faire qui durent -
ce point nœud temporaire pour le nouveau nœud qu'il créait,
soit sur le côté gauche ou sur le côté droit, en fonction de ce que la valeur de droite était.
Enfin, j'ai mis la valeur nouveau nœud à la valeur de ses essais.
[Bowden] Bon, je vois un problème ici.
C'est comme 95% du chemin.
Le seul problème que je vois, eh bien, personne d'autre ne voyez un problème?
Qu'est-ce que les circonstances dans lesquelles ils sortir de la boucle?
[Étudiants] Si la température est nulle? Ouais >>. Alors, comment vous sortir de la boucle est si la température est nulle.
Mais qu'est-ce que je fais ici?
Température de déréférencer I, qui est forcément nul.
Donc, la chose que vous devez faire est de ne pas garder trace jusqu'à température est nulle,
vous voulez garder une trace de la mère à tout moment.
Nous voulons aussi que parent node *, je pense que nous pouvons tenir qu'à nulle au premier abord.
Cela va avoir un comportement bizarre de la racine de l'arbre,
mais nous y reviendrons.
Si la valeur est supérieure à ce que, alors bonne température temp =.
Mais avant de faire cela, parent temp =.
Ou sont les parents va toujours à température égale? Est-ce le cas?
Si la température n'est pas nulle, alors je vais descendre, peu importe quoi,
à un poste pour lequel temp est le parent.
Donc parent va être temp, puis-je déplacer température vers le bas.
Maintenant température est nulle, mais les points mères à la mère de la chose qui est nulle.
Donc ici, je ne veux pas mettre équivaut à droite 1.
Alors je me suis déplacé vers la droite, si droite = 1,
et je suppose que vous aussi vous voulez faire -
si vous vous déplacez vers la gauche, vous voulez définir un droit égal à 0.
Ou bien si jamais vous déplacer vers la droite.
Donc, droite = 0. Si la droite = 1,
maintenant, nous voulons faire la newnode pointeur parent droite,
autre que nous voulons faire le newnode pointeur parent.
Questions à ce sujet?
D'accord. Donc, c'est la façon dont nous - et, en fait, au lieu de faire cela,
nous vous m'attendais à utiliser build_node.
Et puis, si newnode est égal à NULL, retourne false.
C'est tout. Maintenant, c'est ce que nous nous attendions à vous de le faire.
>> C'est ce que les solutions du personnel faire.
Je suis en désaccord avec ce que la «bonne» façon de s'y prendre
mais cela est parfaitement bien et il va fonctionner.
Une chose qui est un peu bizarre à droite est maintenant
si l'arbre commence comme nulle, nous passons dans un arbre nul.
Je suppose que cela dépend de comment vous définissez le comportement de passer dans un arbre nul.
Je pense que si vous passez dans un arbre nul,
puis en insérant la valeur nulle dans un arbre
doit simplement retourner un arbre où la seule valeur est ce nœud unique.
Les gens d'accord avec cela? Vous pouvez, si vous le souhaitez,
si vous passez dans un arbre nulle
et que vous voulez insérer une valeur en elle, retourne false.
C'est à vous de définir cela.
Pour ce faire, la première chose que j'ai dit et puis -
bien, vous allez avoir du mal à le faire, car
il serait plus facile si nous avions un pointeur global à la chose,
mais nous n'avons pas, donc si l'arbre est nulle, il n'y a rien que nous puissions faire à ce sujet.
On peut juste retourner false.
Donc, je vais changer d'insertion.
Nous technique pourrait tout changer ici,
comment il est itérer sur les choses,
mais je vais changer l'insertion de prendre un nœud de l'arbre. **
Pointeurs doubles.
Qu'est-ce que cela signifie?
Au lieu de traiter avec des pointeurs vers les nœuds,
la chose que je vais être la manipulation de ce pointeur.
Je vais être la manipulation de ce pointeur.
Je vais être la manipulation de pointeurs directement.
Cela est logique puisque, pensez à bas -
bien, maintenant ce point à null.
Ce que je veux faire, c'est de manipuler ce pointeur pour pointer vers NOT NULL.
Je veux faire remarquer à mon nouveau nœud.
Si je viens de garder une trace des pointeurs à mes pointeurs,
alors je n'ai pas besoin de garder une trace d'un pointeur parent.
Je peux juste garder la trace pour voir si le pointeur pointe sur null,
et si le pointeur pointe sur null,
le modifier pour pointer vers le nœud que je veux.
Et je peux le changer puisque j'ai un pointeur sur le pointeur.
Voyons ça tout de suite.
Vous pouvez effectivement le faire récursivement assez facilement.
Voulons-nous faire cela?
Oui, nous le faisons.
>> Voyons cela de manière récursive.
Tout d'abord, ce qui est notre cas de base va être?
Presque toujours notre scénario de base, mais en réalité, c'est un peu délicat.
Tout d'abord, si (arbre == NULL)
Je suppose que nous allons juste return false.
Ceci est différent de votre arbre étant nulle.
C'est le pointeur sur le pointeur de la racine étant nulle
ce qui signifie que le pointeur de la racine n'existe pas.
Donc, ici-bas, si je le fais
* noeud - disons simplement réutiliser ce.
Node * root = NULL,
et puis je vais appeler insert en faisant quelque chose comme:
insérer 4 dans et racine.
So & racine, si la racine est un nœud *
alors racine et va être un nœud **.
Ceci est valable. Dans ce cas, l'arbre, là-haut,
arbre n'est pas nulle - ou d'insertion.
Ici. Arbre n'est pas null; arbre * est nul, ce qui est bien
car si l'arbre * est nul, alors je peux le manipuler
maintenant pointer vers ce que je veux pointer.
Mais si l'arbre est nulle, cela signifie que je viens ici et a déclaré nulle.
Cela n'a pas de sens. Je ne peux pas faire n'importe quoi avec ça.
Si l'arbre est nul, retourne false.
J'ai donc essentiellement déjà dit ce que notre scénario de base réelle.
Et qu'est-ce que cela va être?
[Étudiant, inintelligible]
[Bowden] Oui. Donc, si (* arbre == NULL).
Cela concerne le cas ici
où si mon pointeur rouge est le pointeur je suis concentré sur,
de sorte que je me concentre sur ce pointeur, maintenant je me concentre sur ce pointeur.
Maintenant, je me concentre sur ce pointeur.
Donc, si mon pointeur rouge, ce qui est mon nœud **,
est toujours - si *, mon pointeur rouge, n'est jamais nulle,
cela signifie que je suis au cas où je me concentre sur un pointeur qui pointe -
il s'agit d'un pointeur qui fait partie d'une feuille.
Je veux changer ce pointeur pour pointer vers mon nouveau nœud.
Revenez ici.
Mon newnode sera juste noeud * n = build_node (valeur)
alors n, si n = NULL, retourne false.
Sinon, nous voulons changer ce que le pointeur pointe actuellement
maintenant pointer vers notre nœud nouvellement construit.
Nous pouvons en fait faire ici.
Au lieu de dire n, on dit arbre * = * si l'arbre.
Tout le monde comprend cela? C'est en traitant avec des pointeurs sur des pointeurs,
nous pouvons changer pointeurs nuls pour pointer vers ce que nous voulons les faire pointer vers.
C'est notre scénario de base.
>> Maintenant, notre récurrence, ou notre récursion,
va être très semblable à tous les autres récurrences que nous avons faites.
Nous allons à insérer la valeur,
et maintenant je vais utiliser à nouveau ternaire, mais ce qui est notre condition va être?
Qu'est-ce qu'il nous recherchons pour décider si nous voulons aller à gauche ou à droite?
Faisons-le en étapes distinctes.
If (valeur <) quoi?
[Étudiants] Valeur de l'arbre?
[Bowden] Alors, n'oubliez pas que je suis actuellement -
[Etudiants, inintelligibles]
[Bowden] Ouais, donc ici, disons que cette flèche verte
est un exemple de ce que l'arbre est actuellement, est un pointeur sur ce pointeur.
Cela signifie donc que je suis un pointeur vers un pointeur à 3.
Le déréférencement deux fois sonnait bien.
Que dois-je - comment puis-je faire cela?
[Étudiants] déréférencement une fois, puis faire flèche de cette façon?
[Bowden] Donc (* arbre) est le déréférencement fois, -> la valeur
va me donner la valeur du nœud que je suis indirectement pointe.
Donc, je peux aussi écrire ** tree.value si vous préférez.
Soit fonctionne.
Si tel est le cas, alors je veux appeler insérer une valeur.
Et ce qui est mon nœud mis à jour ** va être?
Je veux aller à gauche, de sorte tree.left ** va être ma gauche.
Et je veux le pointeur sur cette chose
de sorte que si la gauche finit par être le pointeur nul,
Je peux le modifier pour pointer vers mon nouveau nœud.
>> Et l'autre cas peuvent être très similaires.
Nous allons effectivement faire que mon ternaire en ce moment.
Insérer la valeur si la valeur de <(arbre **). Valeur.
Ensuite, nous voulons mettre à jour nos ** vers la gauche,
autre que nous voulons mettre à jour nos ** vers la droite.
[Étudiants] Est-ce que placer le pointeur sur le pointeur?
[Bowden] Rappelez-vous que - ** tree.right est une étoile nœud.
[Étudiant, inintelligible] >> Oui.
** Tree.right est comme ce pointeur ou quelque chose.
Donc, en prenant un pointeur vers ça, ça me donne ce que je veux
du pointeur de ce type.
[Étudiants] Peut-on aller encore pourquoi nous utilisons les deux pointeurs?
[Bowden] Ouais. Ainsi - non, vous le pouvez, et que la solution avant
C'était une façon de le faire sans faire deux pointeurs.
Vous devez être capable de comprendre l'aide de deux pointeurs,
et c'est une solution plus propre.
Aussi, notez que, qu'advient-il si mon arbre -
qu'advient-il si ma racine était nulle? Qu'advient-il si je fais ce cas ici?
Alors nœud racine * = NULL, insérez 4 dans et racine.
Quelle est la racine va être après cela?
[Étudiant, inintelligible] >> Oui.
Valeur de la racine va être 4.
Gauche racine sera nulle, non racine va être nulle.
Dans le cas où nous n'avons pas adopté la racine par adresse,
nous ne pouvions pas modifier racine.
Dans le cas où l'arbre - où la racine est nulle,
nous avons juste eu à renvoyer false. Il n'y a rien que nous pouvions faire.
Nous ne pouvons pas insérer un nœud dans un arbre vide.
Mais maintenant, nous pouvons, que nous venons de faire un arbre vide dans un arbre à un nœud.
Qui est généralement de la manière attendue qu'il est censé fonctionner.
>> En outre, ce qui est nettement plus courte que
également garder la trace de la mère, et ainsi de vous réitérer tout le chemin vers le bas.
Maintenant, j'ai ma mère, et je dois mon pointeur droit du parent à l'autre chose.
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.
Mais au lieu d'avoir à traiter avec mon pointeur parent,
au lieu mon pointeur courant serait la chose
que je suis directement modifier pour pointer vers mon nouveau nœud.
Je n'ai pas à traiter si elle est orientée vers la gauche.
Je n'ai pas à traiter si elle est orientée vers la droite.
C'est juste ce que ce pointeur est, je vais le mettre pour pointer vers mon nouveau nœud.
Tout le monde à comprendre comment cela fonctionne?
Si non, pourquoi voulons-nous faire de cette façon,
mais au moins que cela fonctionne comme une solution?
[Étudiants] Où allons-nous retourner vrai?
[Bowden] C'est probablement ici.
Si nous avons bien l'insérer, retournez true.
Sinon, ici-bas, nous allons vouloir revenir retours d'insertion que ce soit.
>> Et ce qui est spécial à propos de cette fonction récursive?
Il est récursive, tant et aussi longtemps que nous compilons avec une certaine optimisation,
il le reconnaître et vous n'obtiendrez jamais un débordement de pile de cela,
même si notre arbre a une hauteur de 10.000 ou 10 millions.
[Étudiant, inintelligible]
[Bowden] Je pense que c'est le cas au Dash - ou ce niveau d'optimisation
est requis pour une récursivité terminale à reconnaître.
Je pense qu'il reconnaît - GCC et Clang
également avoir des significations différentes pour leurs niveaux d'optimisation.
Je veux dire que c'est DashO 2, c'est sûr qu'il va reconnaître la récursivité terminale.
Mais nous - vous pourriez construire comme un exemple Fibonocci ou quelque chose.
Il n'est pas facile de tester avec cela, parce qu'il est difficile de construire
un arbre binaire qui est si grande.
Mais oui, je pense que c'est DashO 2, qui
si vous compilez avec DashO 2, il va chercher la récursivité terminale
et d'optimiser cela.
Revenons à - insérer est littéralement la dernière chose dont il a besoin.
Revenons à l'insert par ici
où nous allons faire la même idée.
Il vous reste encore le défaut de ne pas être en mesure de gérer entièrement
lorsque la racine elle-même est nulle, ou l'entrée passée est null,
mais au lieu de traiter avec un pointeur parent,
nous allons appliquer la même logique de maintien pointeurs sur des pointeurs.
Si ici nous gardons notre noeud ** actu,
et nous n'avons pas besoin de garder une trace de droite plus,
mais noeud ** = & actu arbre.
Et maintenant, notre boucle while va être tout * actu n'est pas nulle d'égalité.
Vous n'avez pas besoin de garder une trace des parents plus.
Vous n'avez pas besoin de garder une trace de gauche et de droite.
Et je vais l'appeler intérim, parce que nous sommes déjà en utilisant temp.
D'accord. Donc, si (valeur> * temp),
alors & (* temp) -> droit
d'autre temp = & (* temp) -> gauche.
Et maintenant, en ce moment, après cette boucle while,
Je ne fais cela parce que c'est peut-être plus facile de penser que itérative de façon récursive,
mais après cette boucle while,
* Temp est le pointeur que nous voulons changer.
>> Avant, nous avions des parents, et nous voulions changer gauche parent ou le parent soit à droite,
mais si nous voulons changer le droit des parents,
puis temp * est bon parent, et nous pouvons le modifier directement.
Donc, ici, nous pouvons faire * temp = newnode, et c'est tout.
Alors préavis, tout nous avons fait dans ce n'était sortir des lignes de code.
Afin de garder une trace de la mère dans tout ce qui est effort supplémentaire.
Ici, si nous venons de suivre le pointeur sur le pointeur,
et même si l'on voulait se débarrasser de toutes ces accolades maintenant,
lui donner l'air plus courte.
C'est maintenant exactement la même solution,
mais moins de lignes de code.
Une fois que vous commencer à reconnaître cela comme une solution valable,
il est aussi plus facile de raisonner sur que comme, d'accord,
pourquoi dois-je ce drapeau à droite int?
Qu'est-ce que ça veut dire? Oh, ça signifie que
chaque fois que je vais à droite, j'ai besoin de le configurer,
d'autre si je vais à gauche je dois le remettre à zéro.
Ici, je n'ai pas de raison à ce sujet, c'est juste plus facile de penser.
Des questions?
[Étudiant, inintelligible] >> Oui.
Ok, donc dans le dernier bit -
Je suppose une fonction rapide et facile que nous pouvons faire est,
let's - ainsi, je pense, essayer d'écrire une fonction contains
qui ne se soucie pas de savoir si c'est un arbre binaire de recherche.
Celui-ci contient la fonction doit renvoyer true
plus que partout ailleurs dans cet arbre binaire générale est la valeur que nous recherchons.
Donc, nous allons d'abord le faire de manière récursive, puis nous le ferons de façon itérative.
Nous pouvons en fait il suffit de faire ensemble, parce que cela va être très court.
>> Ce qui est mon cas, la base va être?
[Étudiant, inintelligible]
[Bowden] Donc, si (arbre == NULL), alors quoi?
[Étudiants] Retour faux.
[Bowden] Sinon, eh bien, je n'ai pas besoin de l'autre.
Si c'était mon cas une autre base.
[Étudiants] Arbre de la valeur? Ouais >>.
Donc, si (arbre-> valeur == valeur.
Remarquez que nous sommes de retour à noeud *, ** noeud ne s?
Contient n'aurez jamais besoin d'utiliser un nœud **,
puisque nous ne modifient pas les pointeurs.
Nous sommes en train de les traverser.
Si cela se produit, nous voulons retourner vrai.
Sinon nous voulons traverser les enfants.
Donc, nous ne pouvons pas raisonner pour savoir si tout ce qui précède est moins
et tout ce qui suit est plus grande.
Alors, quelle est notre situation va être ici - ou, qu'allons-nous faire?
[Étudiant, inintelligible] >> Oui.
Retour contient (valeur, arbre-> gauche)
ou contient (valeur, arbre-> droite). Et c'est tout.
Et remarquez qu'il ya une certaine évaluation de court-circuit,
où si l'on arrive à trouver la valeur dans l'arborescence de gauche,
nous n'avons jamais besoin de regarder le bon arbre.
C'est la fonction entière.
Maintenant, nous allons le faire de manière itérative,
qui va être moins agréable.
Nous allons prendre le départ habituel de noeud * actu arbre =.
While (actu! = NULL).
Rapidement aller voir un problème.
Si actu - ici, si jamais nous sortir de cela,
alors nous sommes à court de choses à regarder, alors retourner faux.
Si (actu-> valeur == valeur), retournez true.
Alors maintenant, nous sommes dans un lieu -
nous ne savons pas si nous voulons aller à gauche ou à droite.
Ainsi arbitraire, nous allons simplement aller à gauche.
J'ai évidemment fonctionner dans une question où j'ai complètement abandonné tout -
Je ne jamais vérifier le côté gauche d'un arbre.
Je ne pourrai jamais vérifier quoi que ce soit qui est un enfant droite de quoi que ce soit.
Comment puis-je résoudre ce problème?
[Étudiants] Vous devez garder une trace de la gauche et la droite dans une pile.
[Bowden] Ouais. Donc, nous allons faire
struct liste, noeud * n, puis noeud ** prochaine?
Je pense que ce qui fonctionne parfaitement.
Nous voulons aller sur la gauche, ou let's - ici.
= Struct liste de la liste, il va commencer
sur cette liste struct.
* Liste = NULL. Alors que va être notre liste chaînée
de sous-arbres que nous avons sautés.
Nous allons maintenant traverser à gauche,
mais depuis que nous avons inévitablement besoin de revenir vers la droite,
Nous allons garder le côté droit à l'intérieur de notre liste struct.
Ensuite, nous aurons new_list ou d'une structure,
struct liste *, new_list = malloc (sizeof (liste)).
Je vais ignorer le contrôle des erreurs, mais vous devriez vérifier pour voir si elle est null.
New_list le nœud auquel il va pointer vers -
oh, c'est pour ça que je le voulais ici. Il va pointer vers une liste struct seconde.
C'est juste la façon dont le travail lié listes.
C'est la même chose comme une liste liée int
sauf que nous ne faisons que remplacer int * avec noeud.
C'est exactement la même chose.
Donc new_list, la valeur de notre noeud new_list,
va être actu-> droite.
La valeur de notre new_list-> suivant va être notre liste originale,
et ensuite nous allons mettre à jour notre liste pour pointer vers new_list.
>> Maintenant, nous devons une sorte de mode de choses de traction,
comme nous l'avons traversé le sous-arbre gauche entier.
Maintenant, nous devons tirer des choses hors de lui,
comme cur est nulle, nous ne voulons pas simplement renvoyer false.
Nous voulons maintenant tirer en dehors de notre nouvelle liste.
Une façon pratique de le faire - bien, en fait, il ya plusieurs façons de le faire.
Quelqu'un at-il une suggestion?
Où je devrais faire ceci ou comment je dois faire?
Nous n'avons que quelques minutes, mais des suggestions?
Au lieu de - dans un sens, au lieu de notre condition étant alors que,
ce que nous sommes en train de regarder n'est pas nulle,
au contraire, nous allons continuer d'aller jusqu'à notre liste elle-même est nulle.
Donc, si notre liste finit par être nulle,
puis nous avons plus de choses à chercher, à chercher plus.
Mais cela veut dire que la première chose dans notre liste va juste être le premier nœud.
La première chose sera - nous n'avons plus besoin de voir ça.
Donc liste-> n sera notre arbre.
liste-> suivant va être nulle.
Et maintenant, alors que la liste n'est pas nulle d'égalité.
Actu est en train de tirer quelque chose de notre liste.
Donc actu va égale liste-> n.
Et puis, la liste va égale liste-> n, ou une liste-> suivant.
Donc, si la valeur est égale à la valeur actu.
Maintenant, nous pouvons ajouter à la fois notre droit et notre pointeur pointeur vers la gauche
tant qu'ils ne sont pas nuls.
Ici, je pense que nous aurions dû le faire en premier lieu.
Si (actu-> droite! = NULL)
alors nous allons insérer ce noeud à notre liste.
Si (actu-> gauche), c'est un peu de travail supplémentaire, mais c'est très bien.
Si (actu-> gauche! = NULL),
et nous allons insérer la gauche dans notre liste chaînée,
et qui doit être elle.
Nous itérer - aussi longtemps que nous avons quelque chose dans notre liste,
nous avons un autre noeud à regarder.
Nous cherchons donc à ce noeud,
nous avançons notre liste à la suivante.
Si ce nœud est la valeur que nous recherchons, nous pouvons retourner la valeur true.
Sinon insérer les deux sous-arbres gauche et droit de notre,
tant qu'ils ne sont pas nuls, dans notre liste
de sorte que nous inévitablement sur eux.
Donc, si elles ne sont pas nulles,
si notre pointeur de racine souligné deux choses,
puis dans un premier temps nous avons tiré quelque chose pour que notre liste finit par être nulle.
Et puis nous avons mis deux choses en, maintenant, notre liste est de taille 2.
Ensuite, nous allons faire une boucle de retour et nous sommes juste en train de tirer,
disons, le pointeur de la gauche de notre nœud racine.
Et que vais continuer d'avancer, nous allons finir par une boucle sur tout.
>> Notez que ce fut beaucoup plus compliqué
dans la solution récursive.
Et je l'ai dit à plusieurs reprises
que la solution récursive est généralement beaucoup plus en commun avec la solution itérative.
Ici, c'est exactement ce que la solution récursive fait.
Le seul changement est que, plutôt que de manière implicite à l'aide de la pile, la pile du programme,
que votre façon de garder une trace de ce que vous avez toujours besoin nœuds à visiter,
Maintenant, vous devez utiliser explicitement une liste chaînée.
Dans les deux cas, vous gardez une trace de ce noeud doit encore être visités.
Dans le cas récursif c'est juste plus facile, car une pile
est mis en œuvre pour vous que la pile du programme.
Notez que cette liste chaînée, il s'agit d'une pile.
Quel que soit nous venons de mettre sur la pile
est immédiatement ce que nous allons retirer la pile pour la prochaine visite.
Nous n'avons plus de temps, mais des questions?
[Étudiant, inintelligible]
[Bowden] Ouais. Donc, si nous avons notre liste chaînée,
actuelle va pointer vers ce type,
et maintenant nous ne faisons que progresser notre liste chaînée de se concentrer sur ce gars.
Nous traversant sur la liste chaînée dans cette ligne.
Et puis je suppose que nous devrions libérer notre liste chaînée et des trucs
une fois avant de retourner vrai ou faux, nous devons
itérer sur notre liste, et toujours ici-bas, je suppose,
si nous actu droit n'est pas égal à, l'ajouter, alors maintenant nous voulons libérer
actu parce que, bon, ne nous oubliez complètement sur la liste? Ouais.
C'est donc ce que nous voulons faire ici.
Où est le pointeur?
Actu était alors - nous voulons une liste struct * 10 équivaut à la liste suivante.
Liste libre, liste = temp.
Et dans le cas où l'on retourne vrai, nous n'avons pas besoin d'itérer
sur le reste de notre liste chaînée libérant les choses.
La bonne chose à propos de la solution récursive est de libérer les choses
signifie simplement factorings popping de la pile qui va se passer pour vous.
Donc, nous sommes passés de quelque chose qui est comme 3 lignes de dur-à-penser-à propos du code
à quelque chose qui est beaucoup beaucoup plus dur-à-penser-sur lignes de code.
D'autres questions?
Très bien. Nous sommes bons. Bye!
[CS50.TV]