[Powered by Google Translate] [Secció 7: més còmode]
[Rob Bowden] [Harvard University]
[Aquesta és CS50] [CS50.TV]
Està bé. Així que, com vaig dir en el meu correu electrònic,
això serà una secció de l'arbre binari d'obra.
Però no cal moltes preguntes.
Així que anem a tractar de treure cada pregunta
i entrar en detalls dolorosos de les millors maneres de fer les coses.
Així que des del principi, anem a través dels dibuixos de la mostra d'arbres binaris i aquestes coses.
Així que aquí, "Recorda que un arbre binari té nodes similars als d'una llista enllaçada,
però en lloc d'un punter hi ha dos: un per "nen" a l'esquerra
i un altre per la dreta "nen". "
Així que un arbre binari és igual que una llista enllaçada,
excepte l'estructura tindrà dos punters.
Hi ha arbres trinaris, que van a tenir tres punters,
hi ha N-àries arbres, que només tenen un punter genèric
que vostè llavors ha de malloc ser prou gran per tenir
indicadors suficients per a tots els nens possibles.
Així arbre binari només passa a tenir un nombre constant de dues.
Si ho desitja, pot donar una llista enllaçada com un arbre unari,
però jo no crec que ningú ho crida això.
"Dibuixar un diagrama de caixes i fletxes d'un node de l'arbre binari
que conté el nombre preferit de Nate, 7, on cada punter nen és nul. "
Així que la manera d'iPad.
>> Serà bastant senzill.
Només tindrem un node, ho vaig a dibuixar un quadrat.
I vaig a treure els valors d'aquí.
Així, el valor passarà d'aquí,
i llavors aquí tindrem el punter a l'esquerra de l'esquerra i el punter a la dreta a la dreta.
I és molt el que la convenció de cridar a l'esquerra i la dreta, els noms de punter.
Tots dos seran nul.
Això només serà nul, i que només serà nul.
Bé. Així que de tornada a aquí.
"Amb una llista enllaçada, només havíem de emmagatzemar un punter
al primer node de la llista per recordar tota la llista vinculada, o tota la llista.
De la mateixa manera, amb els arbres, només ha d'emmagatzemar un punter
a un únic node amb la finalitat de recordar a tot l'arbre.
Aquest node és el carrer "arrel" de l'arbre.
Basar-se en el diagrama d'abans o dibuixar un de nou
de manera que té una representació caixes i fletxes d'un arbre binari
amb el valor de 7, a continuació, 3 a l'esquerra,
a continuació, 9 a la dreta, i després 6 a la dreta de la 3. "
A veure si puc recordar tot això en el meu cap.
Així que això serà la nostra arrel fins aquí.
Tindrem una mica de punter en algun lloc, alguna cosa que anomenarem arrel,
i que apunta a aquest tipus.
Ara per fer un nou node,
¿Què és el que tenim, 3 a l'esquerra?
Així que un nou node amb 3, i que assenyala inicialment nul.
Posaré N.
Ara volem fer que anar a l'esquerra 7.
Així que canviem aquest punter per apuntar ara a aquest tipus.
I fem el mateix. Volem un 9 per aquí
que al principi només diu nul.
Anem a canviar aquest punter, assenyali a 9,
i ara volem posar 6 a la dreta de 3.
Així que va a - fer un 6.
I aquest noi va a apuntar allà.
Bé. Així que això és tot el que se'ns demana que fem.
>> Ara anem a repassar alguns termes.
Ja hem parlat de com l'arrel de l'arbre és el node de més amunt en l'arbre.
L'un que conté 7. Els nodes en la part inferior de l'arbre es diuen les fulles.
Qualsevol node que només té nul com els seus fills és un full.
Així és possible, si el nostre arbre binari és només un únic node,
que un arbre és un full, i això és tot.
"El 'height' l'arbre és el nombre de salts que ha de fer
per arribar des de la part superior a un full. "
Entrarem, en un segon, la diferència
entre els arbres binaris balancejats i no balancejats,
però per ara, l'altura total d'aquest arbre
Jo diria que és 3, encara que si es compta el nombre de salts
el que has de fer per arribar a 9, llavors és realment només una alçada de 2.
En aquest moment es tracta d'un arbre binari desequilibrat,
però anem a parlar sobre equilibrat quan arriba negatiu.
Així que ara podem parlar dels nodes d'un arbre en termes
pel que fa als altres nodes en l'arbre.
Així que ara tenim pares, fills, germans, ascendents i descendents.
Són bastant sentit comú, el que signifiquen.
Si ens preguntem - són els pares.
Llavors, què és el pare de 3?
[Els estudiants] 7. Sí >>. El pare és només serà el assenyala a vostè.
Llavors, què són els nens de 7?
[Els estudiants] 3 i 9. Sí >>.
Tingueu en compte que els "nens" significa literalment fills,
així que 6 no s'aplicaria, perquè és com un nét.
Però si anem descendents, així que el que són els descendents de 7?
[Els estudiants] 3, 6 i 9. Sí >>.
Els descendents del node arrel serà tot en l'arbre,
excepte potser el node arrel en si, si no vols tenir en compte que un descendent.
I finalment, els ancestres, pel que és la direcció oposada.
Quins són els avantpassats de 6?
[Els estudiants] 3 i 7. Sí >>. 9 no està inclòs.
És només la part de darrere llinatge directe a l'arrel
Serà seus avantpassats.
>> "Diem que un arbre binari és" ordenat "si per a cada node a l'arbre,
tots els seus descendents de l'esquerra tenen valors menors
i tots els de la dreta tenen valors majors.
Per exemple, l'arbre de dalt està ordenat, però no és l'única possible ordenat ".
Abans d'arribar a això,
un arbre binari ordenat també es coneix com un arbre binari de cerca.
Aquí succeeix que se'n diu un arbre binari ordenat,
però mai he sentit anomenar un arbre binari ordenat abans,
i en una prova que són molt més propensos a posar arbre de cerca binària.
Són un i el mateix,
i és important que vostè reconegui la distinció entre arbre i arbre binari de cerca binària.
Un arbre binari és un arbre que apunta a dues coses.
Cada node apunta dues coses.
No hi ha raonament sobre els valors que s'apunta.
Així com aquí, ja que és un arbre de cerca binària,
sabem que si anem a l'esquerra de 7,
llavors tots els valors que ens sigui possible assolir
anant a l'esquerra de 7 ha de ser menor que 7.
Tingueu en compte que tots els valors menys que 7 són 3 i 6.
Aquests són tots a l'esquerra de 7.
Si ens anem a la dreta de 7, tot ha de ser superior a 7,
9 és tan a la dreta de 7, així que estem bé.
Aquest no és el cas d'un arbre binari,
per a un arbre binari regular que es pot tenir en la part superior 3, 7 a l'esquerra,
9 a l'esquerra de 7, no hi ha ordre de valors qualssevol.
Ara, no farem això perquè és tediós i innecessari,
sinó "intentar extreure arbres ordenats com molts com vostè pot pensar en
usant els números 7, 3, 9, i 6.
Quants arranjaments diferents hi ha? Quina és l'altura de cada un? "
>> Farem una parella, però és la idea principal,
això no és de cap manera una representació única d'un arbre binari que conté aquests valors.
Tot el que necessitem és un arbre binari que conté 7, 3, 6 i 9.
Una altra possibilitat seria vàlida l'arrel és 3,
anar a l'esquerra i és 6, aneu a l'esquerra i és 7,
anar a l'esquerra i és 9.
Que és un arbre binari de recerca perfectament vàlid.
No és molt útil, ja que és com una llista enllaçada
i tots aquests punters són null.
Però és un arbre vàlida. Sí?
[Estudiant] És que els valors han de ser majors de la dreta?
O és això -? Aquests >> vaig voler anar a un altre costat.
Hi ha també - si, canviarem això.
9, 7, 6, 3. Bona captura.
Encara ha d'obeir el que és un arbre de cerca binària se suposa que ha de fer.
Així tot a l'esquerra ha de ser menor que qualsevol node donat.
Només podia moure, per exemple, el 6 i el va posar aquí.
No, no podem. Per què segueixo fent això?
Anem a fer-ho - aquí és 6, aquí és 7, 6 punts a 3.
Això segueix sent un arbre binari de recerca vàlida.
Què passa si jo - anem a veure si puc arribar a un acord.
Sí, està bé. Llavors, què està malament amb aquest arbre?
Suposo que ja t'he donat un indici que hi ha una cosa dolenta en això.
Per què segueixo fent això?
Bé. Això sembla raonable.
Si ens fixem en cada node, com 7, després a l'esquerra de 7 és un 3.
Així que tenim 3, la cosa a la dreta de 3 és un 6.
I si mires als 6, la cosa a la dreta de 6 és un 9.
Per què no és aquest un arbre binari de cerca vàlid?
[Els estudiants] 9 és encara a l'esquerra de 7. Sí >>.
Ha de ser cert que tots els valors que possiblement pot arribar per anar a l'esquerra de 7 són menys de 7.
Si es va a l'esquerra, de 7, s'arriba a 3 i encara podem arribar a 6,
encara podem arribar a 9, però per haver passat menys de 7,
no cal ser capaç d'arribar a un nombre que és més gran que 7.
Així que això no és un arbre binari de recerca vàlida.
>> El meu germà tenia realment una pregunta de l'entrevista
que era bàsicament això, només una mica de codi per validar
si un arbre és un arbre de cerca binària,
i així que el primer que va fer va ser simplement comprovi
si l'esquerra i la dreta són correctes, i després iterar per allà.
Però no es pot fer això, cal seguir la pista
el fet que ara que m'he anat a l'esquerra de 7,
tot en aquest subarbre ha de ser menor que 7.
L'algorisme correcte necessita seguir la pista
dels límits dels valors que possiblement poden caure polz
No anirem a través de tots ells.
Hi ha una relació de recurrència agradable,
encara que no hem arribat a ells, o no arribarem a ells,
definir quants són en realitat.
Així que hi ha 14 d'ells.
La idea de la manera com ho faria matemàticament és com,
vostè pot escollir un de sol per ser el node arrel,
i llavors si prenc 7 a ser el node arrel,
després hi, per exemple, alguns números que poden anar a ser el meu node esquerre,
i hi ha alguns números que poden ser el meu node de la dreta,
però si té n xifres totals, la quantitat que pot anar a l'esquerra
més la quantitat que pot anar a la dreta és n - 1.
Així dels nombres restants, han de ser capaços d'anar cap a l'esquerra o la dreta.
Sembla difícil que, si poso 3 primer i després tot el que ha d'anar a l'esquerra,
però si poso 7, a continuació, algunes coses poden anar a l'esquerra i algunes coses poden anar a la dreta.
I per '3 'primer que vaig voler dir tot pot anar a la dreta.
En realitat, només cal pensar-hi com,
quantes coses poden passar al següent nivell de l'arbre.
I ve a ser 14, o pot dibuixar tots ells,
i llavors vostè aconseguirà 14.
>> Tornant aquí,
"Va ordenar arbres binaris són frescos ja que podem buscar a través d'ells
d'una manera molt similar a la recerca a través d'una matriu ordenada.
Per això, partim de l'arrel i anem per l'arbre
cap a les fulles, comprovant els valors de cada node amb els valors que estem buscant.
Si el valor del node actual és menor que el valor que busquem,
acostar-te a fill dret del node.
En cas contrari, aneu al fill esquerre del node.
En algun moment, trobareu el valor que vostè està buscant, o et trobaràs amb un valor nul,
el que indica que el valor no està en l'arbre. "
He de tornar a dibuixar l'arbre que teníem abans, que prendrà un segon.
Però volem mirar cap amunt si 6, 10 i 1 estan en l'arbre.
Així que el que era, 7, 9, 3, 6. Bé.
Els números que voleu cercar, volem mirar cap amunt 6.
Com funciona aquest algorisme?
Bé, també tenim alguns punter arrel del nostre arbre.
I ens tornaríem a anar a l'arrel i dir, aquest valor és igual al valor que estem buscant?
Així que estem buscant per a 6, així que no és igual.
Per tant, seguir endavant, i ara es diu, està bé, així que 6 és menor que 7.
Significa això que volem anar cap a l'esquerra, o volem anar a la dreta?
[Estudiant] Esquerra. Sí >>.
És molt més fàcil, l'únic que has de fer és treure un node de l'arbre és possible
i llavors no - en lloc de tractar de pensar en el teu cap,
bé, si és menys, he d'anar a l'esquerra o anar a la dreta,
només mirar aquesta imatge, és molt clar que he d'anar a l'esquerra
si aquest node és major que el valor que jo estic buscant.
Així que anar a l'esquerra, ara estic en 3.
Vull - 3 és menor que el valor que estic buscant, que és de 6.
Així que ens anem a la dreta, i ara acabo a les 6,
que és el valor que estic buscant, així que em torni true.
El següent valor que vaig a buscar és 10.
Bé. Així que 10, ara, va a - tallar això - seguirà l'arrel.
Ara, el 10 serà superior a 7, així que vull mirar a la dreta.
Vaig a venir per aquí, 10 serà més gran que 9,
així que vaig a voler mirar a la dreta.
Jo vinc per aquí, però aquí ara estic a null.
Què faig si em va colpejar nul?
[Estudiant] Tornar fals? Sí >>. No vaig trobar 10.
1 va a ser un cas gairebé idèntic,
excepte que només donarà la volta, en lloc de buscar
pel costat dret, vaig a mirar cap avall al 'esquerra.
>> Ara crec que en realitat obtenir el codi.
Aquí és on - obrir l'aparell CS50 i navegar pel seu camí,
però vostè pot també fer-ho en l'espai.
És probable que sigui ideal per fer-ho en l'espai,
perquè podem treballar en l'espai.
"Primer anem a necessitar una definició de tipus nou per a un node de l'arbre binari que conté valors int.
Usant la repetitiva typedef continuació,
crear una definició de nou tipus per a un node en un arbre binari.
Si et quedes encallat. . . "Blah, blah, blah. Okay.
Així que anem a posar aquí el text model,
typedef struct node i node. Sí, està bé.
Llavors, què són els camps que anem a voler al nostre node?
[Estudiant] Int i després dos punters?
Int >> valor, dos punters? Com puc escriure els punters?
[Estudiant] struct. >> Em zoom in Sí, així struct node * a l'esquerra,
i struct node * dreta.
I recorda que el debat de l'última vegada,
que això no té sentit, això no té sentit,
això no té sentit.
Necessites tot el que hi ha per definir aquesta estructura recursiva.
Molt bé, així que això és el que el nostre arbre semblarà.
Si féssim un arbre ternari, a continuació, un node pot ser com b1, b2, b3 struct node *,
on b és una branca - en realitat, he sentit més a l'esquerra, centre, dreta, però el que sigui.
Només ens importa binari, per dreta, esquerra.
"Ara declarem una variable global per al node * l'arrel de l'arbre."
Així que no farem això.
Per fer les coses una mica més difícil i més generalitzada,
no tindrem una variable de node global.
En canvi, en principal per la qual ens declararà totes les nostres coses de nodes,
i això vol dir que més endavant, quan vam començar a córrer
nostra funció contains i la nostra funció d'inserció,
en lloc de les nostres conté la funció de només utilitzar aquesta variable node global,
haurem de prendre com a argument l'arbre que volem que siguin processats.
Tenir la variable global es suposa que fa les coses més fàcils.
Farem les coses més difícils.
Ara prengui un minut per només fer aquest tipus de coses,
on dins de la principal que voleu crear aquest arbre, i això és tot el que vull fer.
Intenta construir aquest arbre en la seva funció principal.
>> Bé. Així que no tenen ni tan sols haver construït l'arbre durant tot el camí encara.
Però algú té alguna cosa que pogués aixecar
per mostrar com es pot començar a construir un arbre?
[Estudiant] Algú està colpejant, tractant de sortir.
[Bowden] Qualsevol persona còmodes amb la seva construcció de l'arbre?
[Estudiant] Clar. No es fa. >> Està bé. Només podem acabar -
oh, podeu estalviar? Visca.
Així que aquí tenim - oh, estic una mica tallat.
Estic zoom?
Zoom cap a dins, desplaceu-vos cap a fora. >> Tinc una pregunta. >> Sí?
[Estudiant] Quan es defineix una estructura, són coses com inicialitzat a alguna cosa?
[Bowden] >> No Està bé. Així que hauria de inicialitzar -
[Bowden] No Quan es defineix, o quan es declara una struct,
no s'inicialitza per defecte, és com si es declara un int.
És exactament el mateix. És com si cada un dels seus camps individuals
pot tenir un valor escombraries-hi. >> I és possible definir - o declarar una estructura
d'una manera que ho fa inicialitzar ells?
[Bowden] Sí Per tant, l'accés directe sintaxi d'inicialització
es veurà com -
Hi ha dues formes en que podem fer això. Crec que hem de compilar
per fer Clang segur també ho fa.
L'ordre dels arguments que ve en l'estructura,
vostè posa l'ordre dels arguments dins d'aquestes claus.
Així que si vol inicialitzar a 9 i es queda nul i després a la dreta ser nul,
seria 9, null, null.
L'alternativa és, i l'editor no li agrada aquesta sintaxi,
i es creu que vull un nou bloc,
però l'alternativa és com -
aquí, ho vaig a posar en una nova línia.
Vostè pot explícitament dir, no recordo la sintaxi exacta.
Així que vostè pot abordar explícitament pel seu nom, i dir:
. C o. = Valor 9,. Esquerra = NULL.
Suposo que aquests han de ser comes.
. Dreta = NULL, de manera que aquest camí no ho fa
realment necessita saber l'ordre de l'estructura,
i quan vostè està llegint això, és molt més explícita
sobre quin és el valor que s'està inicialitzat a.
>> Això passa a ser una de les coses que -
així, en la seva major part, C + + és un superconjunt de C.
Vostè pot obtenir les C, moure a C + +, i s'ha de compilar.
Aquesta és una de les coses que C + + no admet, de manera que la gent tendeix a no fer-ho.
No sé si aquesta és l'única raó per la gent tendeix a no fer-ho,
però el cas on havia de fer-lo servir necessari per treballar amb C + + i el que no podia usar.
Un altre exemple d'alguna cosa que no funciona en C + + és
com malloc retorna un "void *," tècnicament,
però podeu dir char * x = qualsevol malloc,
i automàticament es converteix en un char *.
Aquest repartiment automàtic no passa en C + +.
Això no va a construir i de manera explícita hauria de dir
char *, malloc, el que sigui, per llançar-lo a un char *.
No hi ha moltes coses que C i C + + no estan d'acord en,
però aquests són dos.
Així que anirem amb aquesta sintaxi.
Però encara que no va ser amb aquesta sintaxi,
el que és - podria ser dolent en això?
[Estudiant] No cal eliminar la referència veritat? Sí >>.
Recordeu que la fletxa té un dereference implícita,
i així, quan només estem tractant amb una estructura,
que voleu utilitzar. per arribar a un camp a l'interior de l'estructura.
I l'única vegada que utilitzi la fletxa és quan volem fer -
així, la fletxa és equivalent a -
això és el que hauria significat si he fet servir fletxa.
Tots els mitjans fletxa és a dir, eliminar la referència això, ara estic en una estructura, i puc aconseguir el terreny.
Qualsevol d'obtenir el camp o directament eliminar la referència i obtenir el camp -
Suposo que això ha de ser el valor.
Però aquí estic tractant amb només una estructura, no és un punter a una estructura,
i per tant no puc utilitzar la fletxa.
Però aquest tipus de coses que podem fer per a tots els nodes.
Oh meu Déu.
Això és 6, 7, i 3.
Llavors podem establir les sucursals al nostre arbre, podem tenir 7 -
Podem tenir, a la seva esquerra ha d'apuntar a 3.
Llavors, com fer això?
[Els estudiants, inintel · ligible] >> Yeah. La direcció de node3,
i si no tenia la direcció, llavors simplement no es compilarà.
Però recordeu que aquests són punters als nodes propers.
El dret ha d'apuntar a 9,
i 3 han d'emprendre la dreta a 6.
Crec que això és tot a punt. Qualsevol comentari o pregunta?
[Estudiant, inintel · ligible] L'arrel serà 7.
Només podem dir node * ptr =
o arrel, = & node7.
>> Per als nostres propòsits, estarem tractant amb insert,
així que anem a voler escriure una funció per inserir en aquest arbre binari
i l'insert està inevitablement va a trucar a malloc per crear un nou node d'aquest arbre.
Així que les coses van a causar problemes amb el fet que alguns nodes
són actualment a la pila
i altres nodes acabaran a la pila quan les inseriu.
Això és perfectament vàlid, però l'única raó
som capaços de fer això a la pila
és pel fet que és un exemple artificial que sabem
l'arbre se suposa que es construeix com 7, 3, 6, 9.
Si no té això, llavors no hauria de malloc en el primer lloc.
Com veurem una mica més endavant, hem d'estar malloc'ing.
Ara mateix és perfectament raonable per posar a la pila,
però anem a canviar això a una implementació de malloc.
Així que cada un d'ells ara serà una cosa així com
node * node9 = malloc (sizeof (node)).
I ara haurem de fer el procés de registre.
if (node9 == NULL) - No volia que -
retorna 1, i després podem fer node9-> perquè ara és un punter,
valor = 6, node9-> left = NULL,
node9-> dreta = NULL,
i haurem de fer això per a cada un dels nodes.
Així que en comptes, posarem dins d'una funció separada.
Diguem que és el node * build_node,
i això és una cosa semblant a l'API de proporcionar per a la codificació de Huffman.
Li donem les funcions inicializador per un arbre
i deconstructor "funcions" dels arbres i el mateix per als boscos.
>> Així que aquí tindrem una funció d'inicialització
a només construir un node per a nosaltres.
I veurà gairebé exactament així.
I estic encara serà mandrós i no canviar el nom de la variable,
encara node9 no té sentit ja.
Oh, suposo valor node9 no hauria d'haver estat 6.
Ara podem tornar node9.
I aquí hem de tornar nul.
Tothom està d'acord que la funció build-a-node?
Així que ara només podem dir així a construir un node amb un valor determinat i punters nuls.
Ara podem dir així, que podem fer node * node9 = build_node (9).
I farem. . .
6, 3, 7, 6, 3, 7.
I ara volem establir els punters mateixos,
excepte que ara tot està ja en termes d'indicadors
així que ja no necessita la direcció d'.
Bé. Llavors, què és l'últim que vull fer?
Hi ha un error de comprovació de que no estic fent.
Què significa construir retorn node?
[Estudiant, inintel · ligible] >> Si. Si malloc no, tornarà null.
Així que vaig a mandrosament deixar de llegir-lo aquí en comptes de fer una condició per a cada un.
Si (node9 == NULL, - o encara més simple,
això és equivalent a poc si no node9.
Així que si no node9, o no node6, o no node3, o no node7, tornarà 1.
Potser hauríem imprimir malloc fracassat, o alguna cosa així.
[Estudiant] És fals igual a null també?
[Bowden] Qualsevol valor zero és fals.
Així nul és un valor zero.
Zero és un valor de zero. False és un valor de zero.
Qualsevol - pràcticament els únics 2 valors zero són nuls i zero,
fals és només haixix definit com zero.
Això també s'aplica si es declaren variable global.
Si tinguéssim node arrel * fins aquí,
llavors - el bo de variables globals és que sempre tenen un valor inicial.
Això no és cert de funcions, com l'interior d'aquí,
si tenim, com *, node o node x.
No tenim idea del que x.value, x.whatever,
o podríem imprimir-los i que podria resultar arbitrari.
Això no és cert de les variables globals.
Així node arrel o un node x.
Per defecte, tot el que és global, sinó explícitament inicialitzada a un valor,
té un valor de zero com el seu valor.
Així que aquí, l'arrel node *, no explícitament inicialitzar a qualsevol cosa,
pel que el seu valor per defecte serà nul, que és el valor zero de punters.
El valor per omissió de x voldrà dir que x.value és zero,
x.left és nul, i x.right és nul.
Per tant, ja que és una estructura, tots els camps de l'estructura serà el valor zero.
No cal utilitzar que aquí, però.
[Estudiant] Les estructures són diferents de les altres variables, i són les altres variables
valors d'escombraries, que són zeros?
Bowden [] Altres valors també. Així, en x, x serà zero.
Si és en l'àmbit global, té un valor inicial. >> Okay.
[Bowden] O el valor inicial que va donar o zero.
Crec que s'encarrega de tot això.
>> Bé. Així que la següent part de la pregunta es refereix,
"Ara volem escriure una funció anomenada conté
amb un prototip d'bool conté un valor int. "
No farem bool conté un valor int.
El nostre prototip s'assemblarà
bool conté (valor int.
I també passarem l'arbre
que s'ha de comprovar per veure si té aquest valor.
Així node * arbre). Bé.
I llavors podem anomenar amb alguna cosa així com:
potser voldrà printf o alguna cosa així.
Conté 6, la nostra arrel.
Això hauria de tornar un o veritable,
mentre que l'arrel conté 5 ha de tornar false.
Així que pren un segon per implementar això.
Pot fer-ho ja sigui iterativament o recursivament.
El millor de la manera com hem establert és que les coses
es presta a la nostra solució recursiva molt més fàcil
de manera global la variable fet.
Perquè si només tenim conté un valor int, llavors no tenim forma de manera recursiva per subarbres.
Hauríem de tenir una funció auxiliar independent que recursivament pels subarbres per a nosaltres.
Però ja que hem canviat a prendre l'arbre com un argument,
que hauria d'haver estat sempre, en primer lloc,
ara podem recurse amb més facilitat.
Així iteratiu o recursiu, anem a repassar tots dos,
però veurem que els extrems recursives sent bastant fàcil.
Bé. Algú té alguna cosa que puguem treballar?
>> [Estudiant] Tinc una solució iterativa. >> Molt bé, iteratiu.
Bé, això es veu bé.
Per tant, ens volen caminar a través d'ell?
[Estudiant] Clar. Així que em vaig posar una variable temporal per obtenir el primer node de l'arbre.
I llavors només en bucle mentre que la temperatura no nul · la de igualtat,
així que mentre es trobava encara a l'arbre, suposo.
I si el valor és igual al valor que està apuntant a temp,
a continuació, es torna aquest valor.
En cas contrari, es comprova si és al costat dret o el costat esquerre.
Si mai tens una situació en què no hi ha més arbres,
després torna - surt del bucle i torna false.
[Bowden] Bé. Així que sembla bo.
Qualsevol persona té algun comentari sobre qualsevol cosa?
No tinc comentaris correcció en absolut.
L'únic que podem fer és aquest tipus.
Oh, anirà una mica allargada.
Vaig a arreglar això. Bé.
>> Tothom hauria de recordar com funciona ternari.
No ha estat, sens dubte proves en el passat
que li donen una funció amb un operador ternari,
i dir, traduir això, fer una cosa que no utilitza ternari.
Així que aquest és un cas molt comú de quan se li ocorreria utilitzar ternari,
on si alguna condició establir una variable a alguna cosa,
altra indicació que la mateixa variable a una altra cosa.
Això és una cosa que molt sovint es pot transformar en aquest tipus de coses
on assignar a aquesta variable aquesta - o, bé, ¿és això cert? Després d'això, més això.
[Estudiant] La primera és si és cert, oi?
[Bowden] Yeah. La manera com sempre ho llegit és, la temperatura és igual al valor més gran que el valor temporal,
llavors això, més d'això. Està fent una pregunta.
És gran? Després fer el primer. Altres fer el segon.
Jo gairebé sempre - els dos punts, jo només - en el meu cap, he llegit com una altra cosa.
>> Algú té una solució recursiva?
Bé. Aquest anem a - que ja podia ser gran,
però ho farem encara millor.
Això és més o menys la idea exactament el mateix.
És només que, bé, és el que vols explicar?
[Estudiant] Clar. Així ens assegurem que l'arbre no és nul en primer lloc,
perquè si l'arbre és nul llavors tornarà fals, perquè no l'hem trobat.
I si encara hi ha un arbre, entrem en - en primer lloc comprovar si el valor és el node actual.
Retorna vertader si ho és, i si no recurse a l'esquerra oa la dreta.
Li sembla adequat? >> Mm-hmm. (Acord)
Així adonar que això és gairebé - estructuralment molt semblant a la solució iterativa.
És només que en lloc de recursivitat, vam tenir un bucle while.
I el cas base aquí on arbre no fa nul igual
era la condició sota la qual va trencar el bucle while.
Són molt similars. Però anem a fer un pas més enllà.
Ara, fem el mateix aquí.
Tingueu en compte que estem tornant el mateix en ambdues línies,
a excepció d'un argument és diferent.
Així que farem això en un ternari.
Vaig picar alguna cosa opció, i va fer un símbol. Bé.
Així que anem a tornar que conté.
Això s'està convertint en diverses línies, bé, el zoom és.
En general, com una cosa d'estil, no crec que molta gent
posar un espai després de la fletxa, però suposo que si ets consistent, està bé.
Si el valor és inferior al valor de l'arbre, volem recurse a l'esquerra de l'arbre,
més volem recurse a la dreta de l'arbre.
Així que aquest va ser el primer pas de fer aquesta mirada més petit.
Segon pas de fer aquesta mirada més petit -
podem separar aquesta a diverses línies.
Bé. El segon pas de fer que es vegi més petita és aquí,
així valor de retorn és igual al valor de l'arbre, o conté el que sigui.
>> Això és una cosa important.
No estic segur de si ho va dir explícitament en la classe,
però es diu l'avaluació de curtcircuit.
La idea és value == valor arbre.
Si això és veritat, llavors això és cert, i volem »o« això amb el que estigui per aquí.
Així, sense ni tan sols pensar en el que està per aquí,
Quina és l'expressió sencera va a tornar?
[Estudiant] Cert? >> Sí, perquè cert de res,
operació lògica OR - operació lògica OR o veritable amb tot és necessàriament cert.
Així que tan aviat com veiem valor de retorn = valor d'arbre,
només tornarem realitat.
Ni tan sols va a recurse conté més de la línia.
Podem fer un pas més enllà.
Arbre retorn no nul igual i tot això.
Ho va fer en funció d'una línia.
Aquest és també un exemple de l'avaluació de curtcircuit.
Però ara és la mateixa idea -
en lloc de - pel que si l'arbre no nul igual - o, bé,
si arbre fa nul · la d'igualtat, que és el cas dolent,
si l'arbre és igual a NULL, la primera condició és falsa.
Així fals AND amb qualsevol cosa serà què?
[Estudiant] Fals. Sí >>. Aquesta és l'altra meitat de l'avaluació de curtcircuit,
on si l'arbre és nul no és igual, llavors no aniran encara més -
o si ho fa nul arbre igual, llavors no farem value == valor arbre.
Només anem a tornar immediatament falsa.
La qual cosa és important, ja que si no ho fa curtcircuit evaluate,
llavors si l'arbre fa nul igual, aquesta segona condició es va a culpa seg,
perquè arbre-> valor desreferencia nul · la.
Així que això és tot. Pot fer això - canviar un cop més.
Això és una cosa molt comuna també, no fer aquesta línia amb això,
però és una cosa comuna en condicions, potser no aquí,
però si (árbol! = NULL, i l'arbre-> valor value ==), fer el que sigui.
Aquesta és una condició molt comú, on en lloc de tenir
a trencar això en dues IFS, on vulgui, és la nul · arbre?
Bé, no és nul, de manera que ara és el valor equivalent al valor de l'arbre? Feu això.
En el seu lloc, aquesta condició, això mai falla seg
perquè sortirà si això passa a ser nul.
Bé, suposo que si l'arbre és un punter nul completament, encara pot seg culpa,
però no pot seg error si l'arbre és nul.
Si fos nul, anava a esclatar abans que desreferencia el punter al primer lloc.
[Estudiant] Aquest avaluació mandrosa anomenada?
>> [Bowden] L'avaluació diferida és una cosa a part.
L'avaluació diferida és més com vostè demana un valor,
demanar-li que calculi un valor, tipus d', però vostè no ho necessita immediatament.
Així que fins que realment ho necessiten, no s'avalua.
Això no és exactament el mateix, però, en el conjunt de processadors Huffman
que diu que "mandrosa", escriuen.
La raó per la qual fem això és perquè en realitat estem amortiment de l'escriptura -
no vull escriure bits individuals alhora,
o bytes individuals alhora, en lloc vol aconseguir un tros de bytes.
Després, una vegada que tenim un fragment de bytes, llavors anem a escriure.
Tot i que es demani a escriure - i fwrite i fread fer el mateix tipus de coses.
Ells esmorteir la seva lectura i escriptura.
Tot i que es demani a escriure immediatament, probablement no ho farà.
I no es pot estar segur que les coses seran escrits
fins que es diu hfclose o el que sigui,
que després es diu, està bé, vaig a tancar el meu arxiu,
això vol dir que serà millor que escriure tot el que no he escrit encara.
No ha d'escriure tot el que fos
fins que es tanqui l'arxiu i faci el necessari.
Així que això és just el vague - que espera fins que ha de succeir.
Això - prendre 51 i podràs entrar-hi amb més detall,
perquè Ocaml i tot el que en el 51, tot és repetició.
No hi ha solucions iteratives, bàsicament.
Tot és repetició, i l'avaluació mandrosa
serà important per a un munt de circumstàncies
on, si no mandrosament avaluar, això significaria -
L'exemple és corrents, que són infinitament llarg.
En teoria, es pot pensar en els nombres naturals com un corrent de 1-2-3-4-5-6-7,
Així que les coses estan ben avaluats mandrosament.
Si dic que vull que el desè número, llavors puc avaluar fins al número deu.
Si voleu que el número cent, llavors puc avaluar fins al número cent.
Sense l'avaluació mandrosa, llavors intentarà avaluar tots els números immediatament.
S'està avaluant un nombre infinit de nombres, i això no és possible.
Així que hi ha un munt de circumstàncies en les que l'avaluació mandrosa
és essencial per aconseguir que les coses funcionin.
>> Ara volem escriure inserció insert on serà
de manera similar canviant en la seva definició.
Així que ara mateix està inserit bool (int value).
Canviarem això per inserir bool (int value, node d'arbre *).
Estem realment canviarà de nou una mica, ja veurem per què.
I passarem build_node, només pel gust de fer-ho,
per sobre d'inserir de manera que no ha d'escriure un prototip de funció.
La qual cosa és un indici que s'utilitzarà en build_node inserció.
Bé. Tome un minut per això.
Crec que em va salvar la revisió si vols tirar d'això,
o, si més no, ho vaig fer ara.
Jo volia un lleuger a pensar en la lògica de la inserció,
si vostè no pot pensar-hi.
Bàsicament, només alguna vegada s'insereix en les fulles.
Igual que, si inserit 1, llavors estic inevitablement va a inserir 1 -
Vaig a canviar a negre - Estaré inserir una per aquí.
O si puc inserir 4, vull ser la inserció de 4 per aquí.
Així que no importa el que facis, vas a inserir en un full.
Tot el que has de fer és recórrer l'arbre fins arribar al node
que ha de ser el pare del node, el pare del nou node,
i després canviar el punter d'esquerra o dreta, depenent de si
és major o menor que el node actual.
Canviar aquest punter per apuntar al seu nou node.
Així iterar cap avall de l'arbre, fan que el punt del full al nou node.
També pensi per què prohibeix el tipus de situació abans,
on va construir l'arbre binari on estava correcta
si només mirar a un sol node,
però el 9 estava a l'esquerra de 7 si reiterat per tot el camí.
Així que és impossible en aquesta situació, ja que -
pensar en la inserció de 9 o alguna cosa, en el primer node,
Vaig a veure 7 i em vaig a anar a la dreta.
Així que no importa el que faci, si estic anant a la inserció d'un full,
i a un full utilitzant l'algorisme apropiat,
que serà impossible per a mi per inserir 9 a l'esquerra, de 7 de
perquè així que em va colpejar 7 Jo vaig a anar a la dreta.
Algú té alguna cosa per començar?
[Estudiant] que faig. >> Clar.
[Estudiant, inintel · ligible]
[Un altre estudiant, inintel · ligible]
[Bowden] S'aprecia. Bé. Vols explicar?
>> [Estudiant] Ja que sabem que estàvem inserint
nous nodes a l'extrem de l'arbre,
M'envien a través de l'arbre de manera iterativa
fins que vaig arribar a un node que apuntava a null.
I llavors em vaig decidir a posar ja sigui en el costat dret o el costat esquerre
utilitzant aquesta variable correcte, sinó que em va dir on posar.
I llavors, en essència, que acabo de fer que el passat -
aquest punt temp node al nou node que s'estava creant,
ja sigui en el costat esquerre o al costat dret, depenent del que el valor de la dreta era.
Finalment, estableix el valor nou node amb el valor de la seva prova.
[Bowden] Està bé, així que no veig un problema aquí.
Això és com el 95% del camí.
L'únic problema que veig, bé, algú més veu un problema?
Quina és la circumstància en què trencar el llaç?
[Estudiant] Si la temperatura és nul? Sí >>. Llavors, com sortir del bucle és si la temperatura és nul.
Però, què faig aquí?
Jo dereference temperatura, que és inevitablement nul.
Així que el que vostè ha de fer no és només un seguiment fins que la temperatura és nul,
vostè vol estar al dia dels pares en tot moment.
També volem que els pares node *, crec que podem mantenir en nul al principi.
Això tindrà un comportament estrany en l'arrel de l'arbre,
però ja arribarem a això.
Si el valor és més gran del que sigui, llavors temp = temp dreta.
Però abans de fer això, pare temp =.
O els pares sempre van a temp iguals? És aquest el cas?
Si la temperatura no és nul, llavors jo vaig a baixar, tant i fa,
a un node per al qual la temperatura és el pare.
Així que els pares serà temporal, i després em moc per temp.
Ara la temperatura és nul, però assenyala als pares dels pares del que és nul.
Així que aquí, no vull establir dreta és igual a 1.
Així que em vaig mudar a la dreta, de manera que si la dreta = 1,
i suposo que també volen fer -
si es mou cap a l'esquerra, que vol establir el dret igual a 0.
O bé, si mai es mouen cap a la dreta.
Així dreta = 0. Si la dreta = 1,
ara volem que el pare nodo_nuevo punter dret,
altra cosa que vol fer el pare nodo_nuevo punter esquerre.
Les preguntes sobre això?
Bé. Així que aquesta és la forma en què - bé, en realitat, en lloc de fer això,
Gairebé esperava que utilitzeu build_node.
I després, si és igual nodo_nuevo nul, retorna fals.
Això és tot. Ara bé, això és el que esperàvem que fes.
>> Això és el que les solucions de personal fer.
No estic d'acord amb això com la manera "correcta" de fer les coses
però això està perfectament bé i va a funcionar.
Una cosa que és un dret mica estrany ara és
si l'arbre comença com nul, es passa a un arbre nul.
Suposo que depèn de com es defineixi el comportament del passatger en un arbre nul.
M'agradaria pensar que si es passa un arbre nul,
a continuació, inserir el valor NULL en un arbre
només ha de retornar un arbre en el qual l'únic valor és que només node.
Les persones estan d'acord amb això? Vostè pot, si vol,
si es passa un arbre nul
i desitja inserir un valor en ell, retorna fals.
Depèn de vostè per definir això.
Per això el primer que em va dir i després -
així, tindràs problemes per fer això, perquè
seria més fàcil si tinguéssim un punter global a la cosa,
però no, de manera que si l'arbre és nul, no hi ha res que puguem fer al respecte.
Només pot tornar false.
Així que em canviaré d'inserció.
Ens tècnicament podria canviar això d'aquí,
com es itera sobre les coses,
però jo canviaré d'inserció per prendre un node d'arbre. **
Punters dobles.
Què vol dir això?
En lloc de tractar amb punters a nodes,
el que vaig a estar manipulant és aquest punter.
Vaig a estar manipulant aquest punter.
Vaig a estar manipulant directament els punters.
Això té sentit ja que, pensar cap avall -
Bé, ara això apunta null.
El que vull fer és manipular aquest punter per apuntar a no nul.
Vull que apunti al meu nou node.
Si tan sols fer un seguiment dels punters als meus consells,
llavors no és necessari fer un seguiment d'un punter pares.
Acabo de fer un seguiment per veure si el punter apunta a null,
i si el punter apunta a null,
canviar perquè apunti al node que vull.
I puc canviar ja que tinc un punter al punter.
Anem a veure això ara mateix.
En realitat es pot fer de forma recursiva amb força facilitat.
Volem fer-ho?
Sí, ho fem.
>> Anem a veure de forma recursiva.
En primer lloc, quin és el nostre cas base serà?
Gairebé sempre el nostre cas base, però en realitat, això és una mica complicat.
El primer és el primer, si (arbre == NULL)
Suposo que només tornarà false.
Això és diferent de la seva nul · arbre benestar.
Aquest és el punter al punter arrel sent nul
el que significa que el punter de la seva arrel no existeix.
Així que aquí, si ho faig
* Node - tornarem a fer servir això.
Node * root = NULL,
i després em vaig a trucar a inserir fent alguna cosa com:
inserir i 4 a l'arrel.
Així i arrel, si l'arrel és un node *
i llavors l'arrel serà un ** node.
Això és vàlid. En aquest cas, l'arbre, fins aquí,
arbre no és nul - o inserció.
Aquí. Tree no és nul; arbre * és nul, la qual cosa està bé
perquè si l'arbre * és nul, llavors puc manipular
apuntar ara al que jo vull apuntar.
Però si l'arbre és nul, això vol dir que només vaig venir aquí i em va dir nul.
Això no té sentit. No puc fer res amb això.
Si l'arbre és nul, retorna fals.
Així que, bàsicament, el que ja ha dit el nostre cas base real.
I el que és que serà?
[Estudiant, inintel · ligible]
[Bowden] Sí Així que si (* arbre == NULL).
Això es relaciona amb el cas aquí
on si el meu punter vermell és el punter que estic enfocat,
així que estic centrat en aquest indicador, ara estic centrat en aquest indicador.
Ara estic centrat en aquest indicador.
Així que si el meu punter vermell, que és el meu ** nodes,
és cada vegada - si *, la meva punter vermell, és sempre nul,
això vol dir que estic en el cas que em centraré en un punter que apunta -
aquest és un punter que pertany a un full.
Vull canviar aquest punter per apuntar al meu nou node.
Torna per aquí.
La meva nodo_nuevo només serà node * n = build_node (valor)
llavors n, si n = NULL, retorna fals.
Altres vendes que volem canviar el que el punter apunta actualment
apuntar ara al nostre node de nova construcció.
De fet, podem fer això aquí.
En lloc de dir n, diem arbre * = si l'arbre *.
Tothom entén això? Això negociant amb punters a punters,
podem canviar punters nuls per apuntar a les coses que volem apuntar.
Aquest és el nostre cas base.
>> Ara el nostre recurrència, o la nostra recursivitat,
serà molt similar a tots els altres recurrències que hem estat fent.
Anem a voler inserir un valor,
i ara jo vaig a usar de nou ternari, però el que és la nostra condició serà?
Què és el que estem buscant per decidir si volem anar a l'esquerra oa la dreta?
Anem a fer-ho en passos separats.
Si (valor <) què?
[Estudiant] El valor de l'arbre?
[Bowden] Així que recordi que sóc en l'actualitat -
[Els estudiants], inintel · ligibles
[Bowden] Sí, tan bé aquí, direm que aquesta fletxa verda
és un exemple del que actualment és arbre, és un punter al punter.
Així que això significa que sóc un punter a un punter a 3.
El dereference dues vegades sonava bé.
Què - com puc fer això?
[Estudiant] eliminar la referència una vegada, i després fer fletxa d'aquesta manera?
[Bowden] Llavors (arbre *) és l'eliminació de referències una vegada, -> valor
em donarà el valor del node que estic assenyalant indirectament.
Així que també es pot escriure ** tree.value si ho prefereix això.
Qualsevol de les obres.
Si aquest és el cas, llavors vull trucar a inserir amb valor.
I el que és meu node actualitzat ** serà?
Jo vull anar a l'esquerra, de manera que arbol.izquierdo ** serà la meva esquerra.
I vull que el punter a aquesta cosa
de manera que si l'esquerra acaba sent el punter nul,
Puc modificar per apuntar al meu nou node.
>> I l'altre cas pot ser molt similar.
Farem que la meva realitat ternari en aquests moments.
Inseriu valor si el valor <(arbre **). Valor.
Llavors volem actualitzar els nostres ** a l'esquerra,
més volem actualitzar els nostres ** a la dreta.
[Estudiant] Això obtenir el punter al punter?
[Bowden] Recordeu que - ** arbol.derecho és un estel node.
[Estudiant, inintel · ligible] >> Si.
** Arbol.derecho és com aquest punter o alguna cosa així.
Així, prenent un punter a això, que em dóna el que vull
del punter a aquest tipus.
[Estudiant] Podríem anar una altra vegada per què estem utilitzant els dos punters?
[Bowden] Yeah. Per tant - no, vostè pot, i la solució que abans
Era una manera de fer-ho sense haver de fer dos punters.
Ha de ser capaç d'entendre l'ús de dos punters,
i aquesta és una solució més neta.
A més, observi que, què passa si el meu arbre -
Què passa si el meu arrel era nul? Què passa si no faig aquest cas aquí?
Així node * root = NULL, inserir i 4 a l'arrel.
Què és l'arrel serà després d'això?
[Estudiant, inintel · ligible] >> Si.
Valor de l'arrel serà 4.
Arrel esquerra serà nul, dret fonamental serà nul.
En el cas en què no va passar arran de direcció,
no podíem modificar arrel.
En el cas que l'arbre - on l'arrel era nul,
ens vam haver tornar false. No hi ha res que poguéssim fer.
No es pot inserir un node en un arbre buit.
Però ara sí, acabem de fer un arbre buit en un arbre d'un node.
La qual cosa és generalment la manera esperada que se suposa que ha de funcionar.
>> A més, aquest és significativament més curt que
també fer el seguiment dels pares, i pel que iterar cap avall tot el camí.
Ara tinc al meu pare, i jo només tinc la meva punter dret del pare al que sigui.
En canvi, si fem això iterativa, que seria la mateixa idea amb un bucle while.
Però en lloc d'haver de bregar amb el meu pare punter,
meu lloc actual del punter seria el
que estic modificant directament per apuntar al meu nou node.
Jo no he de bregar amb el fet que apunta cap a l'esquerra.
Jo no he de bregar amb el fet que apunta cap a la dreta.
És només el que aquest indicador és que em vaig a fixar perquè apunti al meu nou node.
Tothom entén com funciona?
Si no és així, per què volem fer-ho d'aquesta manera,
però almenys que això funciona com una solució?
[Estudiant] On return true?
[Bowden] Això és probablement just aquí.
Si s'insereix correctament, retorna true.
Si no, aquí anem a voler tornar al que sigui retorns d'inserció.
>> I què té d'especial aquesta funció recursiva?
És la cua recursiva, de manera que mentre es compila amb una mica d'optimització,
reconeixerà i que mai es té un desbordament de pila d'això,
fins i tot si el nostre arbre té una alçada de 10.000 milions o 10.
[Estudiant, inintel · ligible]
[Bowden] Crec que ho fa a Dash - o quin nivell d'optimització
es requereix per a una recursió de cua per ser reconegut.
Crec que el reconeix - GCC i Clang
També tenen diferents significats per als seus nivells d'optimització.
Vull dir que és DashO 2, per assegurar-se que es reconegui la recursió de cua.
Però - es pot construir com un exemple Fibonocci o alguna cosa així.
No és fàcil de provar amb això, perquè és difícil construir
un arbre binari que és tan gran.
Però sí, crec que és DashO 2, que
si es compila amb DashO 2, es buscarà la recursió de cua
i optimitzar això.
Tornem a - inserir, literalment, l'última cosa que necessita.
Tornem a la inserció d'aquí
on farem la mateixa idea.
Encara tindrem el defecte de no ser capaç de manejar tot
quan la mateixa arrel és nul, o el passat entrada és nul,
però en lloc de tractar amb un punter pare,
anem a aplicar la mateixa lògica dels punters a punters de manteniment.
Si aquí seguim el nostre node ** cursos,
i no és necessari fer un seguiment de la dreta més,
però node ** act = & arbre.
I ara el nostre bucle while serà mentre act * no nul · la de igualtat.
No cal fer un seguiment dels pares més.
No cal fer un seguiment d'esquerra i dreta.
I ho vaig a trucar a la temperatura, perquè ja estem fent servir temp.
Bé. Així que si (valor> * temp),
i llavors (* temp) -> dreta
més temp = & (* temp) -> a l'esquerra.
I ara, en aquest punt, després d'aquest bucle while,
Jo només faig això perquè potser és més fàcil pensar en forma iterativa de forma recursiva,
però després d'aquest bucle while,
* Temp és el punter que desitja canviar.
>> Abans de tenir pares, i volíem canviar cap a l'esquerra pare o pares dreta,
però si volem canviar drets dels pares,
llavors és correcte * temp pare, i podem canviar directament.
Així que aquí, podem fer * temp = nodo_nuevo, i això és tot.
Així que avís, tot el que vam fer en aquesta era treure línies de codi.
Per tal de seguir la pista de la matriu en tot el que és esforç addicional.
En aquest cas, si tan sols no perdre de vista el punter al punter,
i fins i tot si volia desfer-se de totes aquestes claus ara,
fer que es vegi més curt.
Aquesta és la mateixa solució exacta,
però menys línies de codi.
Un cop de començar a reconèixer això com una solució vàlida,
també és més fàcil de raonar sobre que com, bé,
Per què tinc aquesta bandera a la dreta int?
Què significa això? Oh, està significant que
cada vegada que vagi a la dreta, he de posar,
else if I a l'esquerra he de posar-lo a zero.
En aquest cas, no tinc la raó en això, és més fàcil que pensar.
Preguntes?
[Estudiant, inintel · ligible] >> Si.
Està bé, així que en l'últim -
Suposo que una funció ràpida i fàcil que podem fer és,
let 's - junt, crec, tractar d'escriure una funció contains
que no li importa si es tracta d'un arbre de cerca binària.
Conté funció ha de retornar true
si qualsevol part d'aquest arbre binari general és el valor que està buscant.
Així que primer anem a fer-ho de forma recursiva i després ho farem iterativa.
De fet, podem simplement fer-ho junts, perquè això serà molt curta.
>> Quina és la meva hipòtesi de base serà?
[Estudiant, inintel · ligible]
[Bowden] Així que si (arbre == NULL), llavors què?
[Estudiant] Tornar fals.
[Bowden] Si no, bé, jo no necessito l'altre.
Si va ser el meu cas una altra base.
Valor [Estudiant] Tree? Sí >>.
Així que si (arbre-> value value ==.
Tingueu en compte que estem de tornada a * node no, node ** s?
Conté no haurà de fer servir un ** nodes,
ja que no estem modificant punters.
Estem travessant ells.
Si això succeeix, llavors volem tornar realitat.
Altres vendes que volem recórrer els nens.
Així que no podem raonar sobre si tot a l'esquerra és menor
i tot a la dreta és major.
Llavors, quin és el nostre estat estarà aquí - o, què farem?
[Estudiant, inintel · ligible] >> Si.
Tornar conté (valor, arbre-> esquerre)
o conté (valor, arbre-> dreta). I això és tot.
I compte que hi ha algun tipus d'avaluació de curt circuit,
on si ens toca trobar el valor en l'arbre de l'esquerra,
que mai necessitem mirar l'arbre de la dreta.
Aquesta és la funció sencera.
Ara farem iterativament,
que serà menys agradable.
Anem a prendre la sortida habitual de node * act = arbre.
Mentre (act! = NULL).
Ràpidament veurem un problema.
Si act - aquí, si mai sortir d'això,
llavors ens hem quedat sense coses a veure, pel que retorna fals.
Si (act-> valor value ==), retorna true.
Així que ara, estem en un lloc -
no sabem si volem anar a l'esquerra oa la dreta.
Per tant arbitràriament, anirem a l'esquerra.
Òbviament he topat amb un problema en el qual m'he abandonat del tot tot -
Només vaig a comprovar sempre el costat esquerre d'un arbre.
Mai es comprovi tot el que és un fill dret a res.
Com puc solucionar aquest problema?
[Estudiant] Cal seguir la pista de l'esquerra i la dreta en una pila.
[Bowden] Yeah. Així que anem a fer-ho
struct llista node * n, i després node ** següent?
Jo crec que funciona bé.
Volem anar per l'esquerra o let 's - fins aquí.
Struct = llista de la llista, que començarà
a terme en aquesta llista struct.
* Llista = NULL. Així que serà la nostra llista enllaçada
de subarbres que hem saltat.
Anem a travessar l'esquerra ara,
però és inevitable que hagi de tornar a la dreta,
Anem a mantenir el costat dret dins la nostra llista d'estructura.
Llavors tindrem new_list o estructura,
struct llista *, new_list = malloc (sizeof (llista)).
Vaig a passar per alt la comprovació d'errors, però vostè ha de comprovar per veure si és nul.
New_list el node que va a apuntar a -
oh, és per això que ho volia aquí. Es va a apuntar a una llista struct segon.
Així és com el treball vinculat llistes.
Aquest és el mateix com una llista vinculada int
excepte només estem reemplaçant amb int * node.
És exactament el mateix.
Així new_list, el valor del nostre node new_list,
serà actualment> dreta.
El valor de la nostra new_list-> següent serà la nostra llista original,
i després anem a actualitzar la nostra llista per apuntar a new_list.
>> Ara necessitem algun tipus de forma de les coses que tiren,
com hem travessat el subarbre esquerre sencer.
Ara hem de tirar coses fora,
com act és nul, no volem tornar simplement fals.
Volem tirar ara fora de la nostra nova llista.
Una manera convenient de fer això - bé, en realitat, hi ha diverses maneres de fer això.
Algú té algun suggeriment?
On he de fer això o com ho he de fer?
Només tenim un parell de minuts, però qualsevol suggeriment?
En lloc de - d'una manera, en comptes de la nostra condició de ser temps,
el que estem mirant no és nul,
en lloc d'això continuarem per anar fins a la nostra llista en si és nul.
Així que si la nostra llista acaba sent nul,
llavors ens hem quedat sense coses que ha de buscar, a buscar un altre.
Però això vol dir que el primer a la nostra llista és només serà el primer node.
El primer serà - ja no hem de veure això.
Així llista-> n serà el nostre arbre.
llista-> següent serà nul.
I ara, mentre que la llista no nul · la de igualtat.
Cur traurà alguna cosa de la nostra llista.
Així act serà igual list-> núm.
I llavors llista serà igual list-> n, o llista-> següent.
Així que si el valor és igual al valor actual.
Ara podem afegir tant els nostres com punter dret i el nostre punter esquerre
sempre que no és nul.
Aquí baix, suposo que hauríem d'haver fet això en primer lloc.
Si (act-> bé! = NULL)
llavors anem a inserir el node a la llista.
Si (act-> esquerra), es tracta d'una mica de treball extra, però està bé.
Si (act-> esquerra! = NULL),
i anem a inserir a l'esquerra a la nostra llista enllaçada,
i que hauria de ser.
Ens iterar - sempre que tenim alguna cosa a la nostra llista,
tenim un altre node a la vista.
Així que ens fixem en aquest node,
avancem la nostra llista per a la següent.
Si el node és el valor que busquem, podem tornar realitat.
Altres vendes inserir dos subarbres nostra esquerra i la dreta,
sempre que no siguin nuls, a la llista
de manera que és inevitable anar-hi.
Així que si no eren nul · les,
si el nostre punter arrel assenyalar dues coses,
a continuació, al principi ens va treure alguna cosa de manera que la nostra llista acaba sent nul.
I després posem dues coses de nou, de manera que ara la nostra llista és de mida 2.
A continuació, anem a teixir per enrere i només tirarem,
diguem, el punter esquerre del nostre node arrel.
I això seguirà passant, anem a acabar recórrer tot.
>> Observi que això era significativament més complicat
en la solució recursiva.
I ja he dit diverses vegades
que la solució recursiva en general té molt en comú amb la solució iterativa.
Aquí és exactament el que la solució recursiva està fent.
L'únic canvi és que en lloc d'utilitzar implícitament la pila, la pila del programa,
com la seva forma de fer el seguiment de què nodes vostè encara ha de visitar,
Ara vostè ha d'utilitzar explícitament una llista enllaçada.
En ambdós casos, vostè està guardant un registre del node encara ha de ser visitat.
En el cas recursiu és més fàcil perquè una pila
que s'apliqui a vostè com la pila del programa.
Observi que aquesta llista enllaçada, és una pila.
Independentment del que acaba de posar a la pila
és immediatament el que anem a treure la pila per la propera visita.
Estem fora de temps, però alguna pregunta?
[Estudiant, inintel · ligible]
[Bowden] Yeah. Així que si tenim la nostra llista enllaçada,
actual es va a apuntar a aquest noi,
i ara estem avançant al llistat enllaçada per centrar-se en aquest tipus.
Estem travessant per la llista enllaçada en aquesta línia.
I llavors crec que hem de alliberar la nostra llista enllaçada i aquestes coses
una vegada abans de tornar veritable o falsa, hem de
iterar a través de la nostra llista enllaçada i sempre aquí baix, suposo,
si act dret no és igual que afegir, de manera que ara volem alliberar
act perquè, bé, què ens oblidem per complet de la llista? Si.
Així que això és el que volem fer aquí.
On és el punter?
Cur era llavors - volem una llista struct * 10 és igual a la llista següent.
Llista lliure, list = temp.
I en el cas que ens retorni true, necessitem iterar
durant la resta de la nostra llista enllaçada alliberar coses.
El millor de la solució recursiva és alliberar les coses
Només significa factorings apareixent de la pila que passarà per vostè.
Així que hem passat d'una cosa que és com 3 línies de dur-a-pensar-sobre el codi
a alguna cosa que és significativament molts més difícils de pensament sobre les línies de codi.
Una mica més preguntes?
Està bé. Estem bé. Bye!
[CS50.TV]