[Powered by Google Translate] [Sezione 7: più confortevole]
[Rob Bowden] [Harvard University]
[Questo è CS50] [CS50.TV]
Bene. Così come ho detto nella mia e-mail,
questo sta andando essere un albero binario ad alta intensità di sezione.
Ma non ci sono che molte domande.
Quindi stiamo andando a cercare di tirar fuori ogni domanda
ed entrare nei dettagli dolorosa di tutti i modi migliori di fare le cose.
Quindi, fin dall'inizio, si va attraverso il disegno di campionamento di alberi binari e roba del genere.
Quindi, ecco, "Ricordati che un albero binario con nodi simili a quelle di una lista concatenata,
tranne che invece di un puntatore ce ne sono due: uno per 'bambino' a sinistra
e uno per il diritto di 'bambino' ".
Quindi, un albero binario è come una lista concatenata,
tranne la struttura sta per avere due puntatori.
Ci sono alberi ternario, che stanno per avere tre puntatori,
ci sono N-arie alberi, che appena hanno un puntatore generico
che è quindi necessario malloc essere grande abbastanza per avere
puntatori sufficiente a tutti i bambini possibili.
Così albero binario succede solo per avere un numero costante di due.
Se si vuole, si può dare una lista concatenata come un albero unario,
ma io non credo che nessuno lo chiama così.
"Disegna un box-e-frecce diagramma di un nodo dell'albero binario
contenente il numero preferito di Nate, 7, dove ogni puntatore bambino è nulla. "
Modalità Così iPad.
>> E 'intenzione di essere abbastanza semplice.
Stiamo solo andando ad avere un nodo, io lo disegnare come un quadrato.
E io disegnare i valori qui dentro.
Quindi, il valore andrà in qui,
e poi qui avremo il puntatore sinistra sulla sinistra e destra il puntatore sulla destra.
Ed è molto tanto convenzione di chiamare verso sinistra e destra, il nome del puntatore.
Entrambi stanno per essere nullo.
Questo sarà solo nullo, e che sarà solo essere nullo.
Va bene. Ma torniamo al qui.
"Con una lista concatenata, abbiamo solo dovuto memorizzare un puntatore
al primo nodo della lista, al fine di ricordare l'intera lista collegata, oppure l'intero elenco.
Allo stesso modo, con gli alberi, non ci resta che memorizzare un puntatore
ad un singolo nodo per ricordare tutto l'albero.
Questo nodo è la calle 'radice' dell'albero.
Sviluppare il vostro diagramma da prima o disegnare una nuova
in modo tale che si dispone di un box-e-frecce raffigurazione di un albero binario
con il valore 7, poi 3 a sinistra,
9 poi a destra, e poi 6 sulla destra del 3. "
Vediamo se riesco a ricordare tutto questo nella mia testa.
Quindi questo sarà il nostro principale qui.
Avremo un po 'di puntatore da qualche parte, qualcosa che chiameremo radice,
ed è rivolta a questo ragazzo.
Ora fare un nuovo nodo,
che cosa abbiamo, 3 a sinistra?
Così un nuovo nodo con 3, che punta inizialmente nullo.
Metto N.
Ora vogliamo fare che andare a sinistra di 7.
Quindi cambiamo questo puntatore per puntare ora a questo ragazzo.
E noi facciamo lo stesso. Vogliamo un 9 qui
che inizialmente solo dice nulla.
Stiamo andando a cambiare questo, punto puntatore a 9,
e ora vogliamo mettere 6 a destra di 3.
Così sta andando a - fare un 6.
E quel ragazzo punterà lì.
Va bene. Ecco, questo è tutto quello che ci chiede di fare.
>> Ora andiamo su alcuni termini.
Abbiamo già parlato di come la radice dell'albero è il più in alto nodo nell'albero.
Quella contenente 7. I nodi nella parte inferiore dell'albero sono chiamati le foglie.
Ogni nodo che ha appena null come suoi figli è una foglia.
Così è possibile, se il nostro albero binario è solo un singolo nodo,
che un albero è una foglia, e questo è tutto.
"Il 'height' dell'albero è il numero di salti si deve fare
per ottenere, da cima a una foglia. "
Andremo in, in un secondo, la differenza
tra gli alberi binari bilanciati e sbilanciati,
ma per ora, l'altezza di questo albero
Direi che è 3, anche se si conta il numero di hop
si deve fare per arrivare a 9, allora è davvero solo una altezza di 2.
In questo momento si tratta di un albero binario bilanciato,
ma ci parlato equilibrata quando si arriva a essere rilevante.
Così ora possiamo parlare di nodi in un albero, in termini
rispetto agli altri nodi dell'albero.
Così ora abbiamo genitori, figli, fratelli e sorelle, antenati e discendenti.
Si tratta di senso piuttosto comune, che cosa significano.
Se ci chiediamo - è genitori.
Allora, qual è il genitore di 3?
[Gli studenti] 7. Sì >>. Il genitore è solo andare a essere ciò che fa per voi.
Allora che cosa sono i figli di 7?
[Gli studenti] 3 e 9. Sì >>.
Si noti che "bambini" significa letteralmente figli,
quindi 6 non si applica, perché è come un nipote.
Ma poi se andiamo discendenti, quindi quali sono i discendenti di 7?
[Gli studenti] 3, 6 e 9. Sì >>.
I discendenti del nodo principale sta per essere tutto ciò che nella struttura,
tranne forse il nodo radice in sé, se non si vuole considerare che un discendente.
E, infine, antenati, quindi è la direzione opposta.
Ma quali sono gli antenati di 6?
[Gli studenti] 3 e 7. Sì >>. 9 non è incluso.
E 'solo la parte posteriore discendenza diretta alla radice
sta per essere i vostri antenati.
>> "Noi diciamo che un albero binario è 'ordinato' se per ogni nodo dell'albero,
tutti i suoi discendenti sulla sinistra hanno valori minori
e tutti quelli di destra hanno maggiori valori.
Ad esempio, l'albero sopra è ordinato ma non è possibile solo la disposizione ordinata. "
Prima di arrivare a questo,
un albero binario ordinato è anche conosciuto come un albero di ricerca binaria.
Qui ci capita di essere la chiamata di un albero binario ordinato,
ma non ho mai sentito chiamato un albero binario ordinato prima,
e su un quiz siamo molto più propensi a mettere albero binario di ricerca.
Sono la stessa cosa,
ed è importante riconoscere che la distinzione tra albero binario e ricerca su alberi binari.
Un albero binario è solo un albero che fa riferimento a due cose.
Ogni nodo indica due cose.
Non vi è alcuna motivazione circa i valori a cui punta.
Così come qui, dal momento che si tratta di un albero binario di ricerca,
sappiamo che se andiamo a sinistra di 7,
allora tutti i valori che si può eventualmente raggiungere
andando a sinistra del 7 deve essere inferiore a 7.
Si noti che tutti i valori inferiori a 7 sono 3 e 6.
Queste sono tutte a sinistra del 7.
Se andiamo a destra di 7, tutto deve essere superiore a 7,
9 è così a destra di 7, quindi siamo a posto.
Questo non è il caso di un albero binario,
per un albero binario regolare possiamo solo 3 nella parte superiore, a sinistra 7,
9 a sinistra 7; c'è nessun ordinamento dei valori di sorta.
Ora, noi non effettivamente fare questo perché è noioso e inutile,
ma "cercare di disegnare alberi ordinati in molti come si può pensare di
utilizzando i numeri 7, 3, 9, e 6.
Quanti accordi distinti ci sono? Qual è l'altezza di ciascuno? "
>> Faremo una coppia, ma l'idea principale è,
questo è in alcun modo una rappresentazione unica di un albero binario contenente questi valori.
Tutto quello che serve è un albero binario che contiene il 7, 3, 6, e 9.
Un altro possibile valida sarebbe la radice è 3,
andare a sinistra ed è 6, andare a sinistra ed è 7,
andare a sinistra ed è 9.
Questo è perfettamente valido albero binario di ricerca.
Non è molto utile, perché è proprio come una lista concatenata
e tutti questi puntatori sono solo nullo.
Ma è un albero valido. Si '?
[Studente] Non i valori devono essere maggiori a destra?
O si tratta di -? Questi >> volevo andare nella direzione opposta.
C'è anche - sì, facciamo passare questo.
9, 7, 6, 3. Bella presa.
Ha ancora obbedire a ciò che un albero binario di ricerca si dovrebbe fare.
Quindi tutto a sinistra deve essere minore rispetto a qualsiasi dato nodo.
Potremmo andare, per esempio, questo 6 e metterlo qui.
No, non possiamo. Perché continuo a farlo?
Facciamo - è qui 6, è qui 7, 6 punti a 3.
Questo è ancora un valido albero binario di ricerca.
Cosa c'è di sbagliato se io - vediamo se riesco a trovare una sistemazione.
Si ', va bene. Allora, cosa c'è di sbagliato in questo albero?
Credo di aver già dato un suggerimento che ci sia qualcosa che non va.
Perché continuo a farlo?
Va bene. Questo sembra ragionevole.
Se guardiamo ad ogni nodo, come il 7, poi a sinistra di 7 è una 3.
Così abbiamo 3, la cosa a destra di 3 è un 6.
E se si guarda alle 6, la cosa a destra di 6 è un 9.
Allora, perché non è questo un valido albero binario di ricerca?
[Studenti] 9 è ancora a sinistra 7. Sì >>.
Deve essere vero che tutti i valori si può eventualmente raggiungere andando a sinistra di 7 sono meno di 7.
Se andiamo a sinistra di 7, si arriva a 3 e si può ancora arrivare a 6,
possiamo ancora arrivare a 9, ma essendo andato inferiore a 7,
non dovremmo essere in grado di arrivare a un numero che è maggiore di 7.
Quindi questo non è un valido albero binario di ricerca.
>> Mio fratello in realtà ha avuto un colloquio di domanda
che era fondamentalmente questo, basta codice qualcosa per convalidare
se un albero è un albero binario di ricerca,
e così la prima cosa che fece fu solo verificare
se la sinistra e la destra sono corretti, quindi scorrere verso il basso lì.
Ma non si può semplicemente fare questo, devi tenere traccia
del fatto che, ora che sono andato a sinistra di 7,
tutto in questa sottostruttura deve essere inferiore a 7.
L'algoritmo corretto deve tenere traccia
dei limiti che i valori possono eventualmente cadranno dentro
Noi non passerà attraverso tutti loro.
C'è una relazione di ricorrenza piacevole,
anche se non siamo ancora arrivati ​​a quelli, altrimenti non si arriva a quelli,
la definizione di quanti ce ne sono in realtà.
Quindi ci sono 14 di loro.
L'idea di come si dovrebbe fare è matematicamente come,
si può scegliere uno solo di essere il nodo radice,
e poi se prendo 7 per essere il nodo radice,
poi ci sono, ad esempio, alcuni numeri che possono andare il mio nodo di sinistra,
e ci sono alcuni numeri che possono essere il mio nodo a destra,
ma se ho n il numero totale, quindi l'importo che può andare a sinistra
più l'importo che può andare a destra è n - 1.
Quindi i numeri rimanenti, devono essere in grado di andare sia a sinistra oa destra.
Sembra difficile che, se ho messo 3, primo poi tutto deve andare a sinistra,
ma se ho messo 7, quindi alcune cose possono andare a sinistra e alcune cose possono andare a destra.
E da '3 'prima volevo dire tutto può andare a destra.
E 'davvero, basta pensare a come,
quante cose possono andare al livello successivo della struttura.
E risulta essere 14; oppure è possibile disegnare tutti,
e poi avrai 14.
>> Tornando qui,
"Alberi ordinati binari sono fresche, perché si può cercare attraverso di loro
in un modo molto simile alla ricerca in un array ordinato.
Per fare ciò, si inizia dalla radice e lavorare il nostro modo l'albero
verso le foglie, il controllo dei valori di ogni nodo con i valori che stiamo cercando.
Se il valore del nodo corrente è inferiore al valore che stiamo cercando,
si va vicino al figlio destro del nodo.
In caso contrario, si va al figlio sinistro del nodo.
Ad un certo punto, potrete sia trovare il valore che stai cercando, o si incorrerà in un null,
indicante il valore non è nella struttura. "
Devo ridisegnare l'albero che avevamo prima, che prendo un secondo.
Ma noi vogliamo cercare se 6, 10, e 1 sono nella struttura.
Così che cosa è stato, 7, 9, 3, 6. Va bene.
I numeri che si desidera cercare, vogliamo guardare in alto 6.
Come funziona questo algoritmo?
Beh, abbiamo anche un po 'di puntatore root per il nostro albero.
E saremmo andati alla radice e dire, è questo valore uguale al valore che stiamo cercando?
Quindi stiamo cercando di 6, quindi non è uguale.
Quindi andare avanti, e ora diciamo, va bene, quindi 6 è inferiore a 7.
Vuol dire che vogliamo andare a sinistra, o vogliamo andare a destra?
[Studente] Sinistra. Sì >>.
E 'molto più semplice, tutto ciò che dovete fare è disegnare un nodo possibile della struttura
e poi Non. - invece di cercare di pensare nella tua testa,
Va bene, se è di meno, devo andare a sinistra o andare diritto,
solo guardando questa foto, è molto chiaro che devo andare a sinistra
se questo nodo è maggiore del valore che sto cercando.
Quindi si va a sinistra, ora sono a 3.
Voglio - 3 è inferiore al valore che sto cercando, che è 6.
Così si va a destra, e ora finisco alle 6,
che è il valore che sto cercando, così mi restituisce true.
Il valore successivo vado a cercare è 10.
Va bene. Quindi 10, ora, sta per - tagliare che - andando a seguire la radice.
Ora, 10 sta per essere superiore a 7, quindi voglio guardare a destra.
Ho intenzione di venire qui, 10 sta per essere superiore a 9,
così ho intenzione di voler guardare a destra.
Io vengo qui, ma qui ora sono a null.
Che cosa devo fare se ho colpito nulla?
[Studente] Ritorna falso? Sì >>. Non ho trovato 10.
1 sta per essere un caso quasi identico,
tranne che sta solo andando a essere capovolte, invece di guardare
lungo il lato destro, ho intenzione di guardare in basso sul lato sinistro.
>> Ora penso che effettivamente arrivare a codice.
Ecco dove - aprire l'apparecchio CS50 e navigare il vostro senso lì,
ma si può farlo anche nello spazio.
E 'probabilmente l'ideale per farlo nello spazio,
perché possiamo lavorare nello spazio.
"In primo luogo abbiamo bisogno di una nuova definizione di tipo per un nodo di albero binario che contiene valori int.
Utilizzando il boilerplate typedef di seguito,
creare una nuova definizione di tipo di un nodo in un albero binario.
Se ti trovi in ​​difficoltà. . . "Bla, bla, bla. Okay.
Quindi cerchiamo di mettere il boilerplate qui,
struct nodo typedef, e il nodo. Si ', va bene.
Ma quali sono i campi che stiamo andando a voler nel nostro nodo?
[Studente] Int e poi due puntatori?
Int >> valore, due puntatori? Come faccio a scrivere i puntatori?
[Studente] Struct. >> Dovrei Immagine Sì, così struct nodo * a sinistra,
e struct nodo * a destra.
E ricordate la discussione dell'ultima volta,
che questo non ha senso, questo non ha senso,
questo non ha senso.
Hai bisogno di tutto quello che c'è per definire questa struttura ricorsiva.
Ok, allora questo è ciò che il nostro albero è andare a guardare come.
Se abbiamo fatto un albero ternario, poi un nodo potrebbe essere simile b1, b2, b3 struct nodo *,
dove b è un ramo - in realtà, l'ho più sentito a sinistra, al centro, a destra, ma qualunque.
Ci interessa solo binario, per cui a destra, a sinistra.
"Ora dichiarare una variabile globale * nodo per la radice dell'albero."
Quindi non abbiamo intenzione di farlo.
Per rendere le cose leggermente più difficile e più generalizzata,
non avremo una variabile globale nodo.
Invece, in main dichiareremo tutte le nostre cose nodi,
e questo significa che al di sotto, quando iniziare a correre
Contiene la nostra funzione e la nostra funzione di inserimento,
al posto dei nostri contiene una funzione semplicemente utilizzando questa variabile globale nodo,
stiamo andando ad avere la prenda come argomento l'albero che vogliamo elaborare.
Avere la variabile globale avrebbe dovuto rendere le cose più facili.
Stiamo andando a fare le cose più difficili.
Ora prendete un minuto o giù di lì di fare proprio questo genere di cose,
dove all'interno del principale che si desidera creare questo albero, e questo è tutto quello che vuoi fare.
Prova a costruire questo albero nella funzione principale.
>> Va bene. Quindi non hanno nemmeno bisogno di aver costruito l'albero per tutta la strada ancora.
Ma qualcuno ha qualcosa che avrei potuto tirare su
per mostrare come si può iniziare a costruire un albero?
[Studente] Qualcuno di colpi, cercando di uscire.
[Bowden] Chiunque agio con la loro costruzione albero?
[Studente] Certo. Non è fatto. Va bene >>. Possiamo solo concludere -
oh, si può salvare? Evviva.
Quindi qui abbiamo - oh, sono leggermente tagliate.
Sto ingrandita?
Per ingrandire, scorrere fuori. >> Ho una domanda. Sì >>?
[Studente] Quando si definisce una struttura, sono cose come inizializzato a qualcosa?
[Bowden] No. >> Ok. Quindi si dovrebbe inizializzare -
[Bowden] No. Quando si definisce, o quando si dichiara una struttura,
non è inizializzato per impostazione predefinita, ma è proprio come se si dichiara un int.
E 'esattamente la stessa cosa. E 'come se ciascuno dei suoi singoli campi
possono avere un valore spazzatura in esso. >> Ed è possibile definire - o di dichiarare una struttura
in un modo che fa inizializzarli?
[Bowden] Sì. Quindi, collegamento sintassi di inizializzazione
è andare a guardare come -
Ci sono due modi in cui possiamo farlo. Penso che dovremmo compilarlo
fare Clang che fa anche questo.
L'ordine degli argomenti che viene nella struttura,
si mette come l'ordine degli argomenti all'interno di queste parentesi graffe.
Quindi, se si desidera inizializzare a 9 e ha lasciato nulla e poi a destra essere nullo,
sarebbe 9, null, null.
L'alternativa è, e l'editor non piace questa sintassi,
e pensa che io voglio un nuovo blocco,
ma l'alternativa è qualcosa di simile -
qui, la metto su una nuova riga.
Si può dire in modo esplicito, non ricordo la sintassi esatta.
Così si può esplicitamente indirizzare il messaggio per nome, e dire:
. C o. Valore = 9. NULL = sinistra.
Sto indovinando questi devono essere virgole.
. Destra = NULL, così in questo modo non si
effettivamente bisogno di conoscere l'ordine della struttura,
e quando stai leggendo questo, è molto più esplicito
su ciò che il valore è in fase di inizializzazione di.
>> Questa sembra essere una delle cose che -
così, per la maggior parte, C + + è un superset di C.
Si può prendere il codice C, spostarlo sulla C + +, e dovrebbe compilare.
Questa è una delle cose che il C + + non supporta, per cui le persone tendono a non farlo.
Non so se questo è l'unico motivo per le persone tendono a non farlo,
ma il caso in cui avevo bisogno di usare di cui aveva bisogno per lavorare con C + + e così non ho potuto usare questo.
Un altro esempio di qualcosa che non funziona con C + + è
come malloc restituisce un "void *," tecnicamente,
ma si può solo dire char * x = qualsiasi malloc,
e che verrà automaticamente il cast a un char *.
Tale fusione automatica non avviene in C + +.
Non sarebbe la compilazione, e si avrebbe bisogno di dire in modo esplicito
char *, malloc, qualsiasi cosa, per il cast di un char *.
Non ci sono molte cose che C e C + + non sono d'accordo su,
ma questi sono due.
Quindi dovremo andare con questa sintassi.
Ma anche se non siamo andati con quella sintassi,
ciò che è - potrebbe essere di sbagliato in questo?
[Studente] Non ho bisogno di dereferenziarlo? Sì >>.
Ricordate che la freccia ha un dereference implicito,
e così quando siamo solo di fronte ad un struct,
vogliamo usare. per arrivare a un campo all'interno della struttura.
E l'unica volta che usiamo freccia è quando vogliamo fare -
bene, freccia è equivalente a -
questo è quello che avrebbe voluto dire se ho usato freccia.
Tutti i mezzi freccia, dereferenziare questo, ora sono in una struttura, e posso ottenere il campo.
O ottenere il campo direttamente o dereference e ottenere il campo -
Credo che questo dovrebbe essere il valore.
Ma qui ho a che fare solo con una struttura, non un puntatore ad una struct,
e quindi non posso utilizzare la freccia.
Ma questo genere di cose che possiamo fare per tutti i nodi.
Oh mio Dio.
Questo è 6, 7, e 3.
Quindi siamo in grado di impostare i rami del nostro albero, possiamo avere 7 -
si può avere, la sua sinistra deve puntare a 3.
Quindi, come possiamo fare?
[Gli studenti, incomprensibile] >> Si '. L'indirizzo di node3,
e se non ha avuto l'indirizzo, allora semplicemente non sarebbe la compilazione.
Ma ricordate che questi sono i puntatori ai nodi successivi.
Il diritto deve puntare a 9,
e 3 deve puntare sul diritto 6.
Credo che questo sia tutto pronto. Eventuali commenti o domande?
[Studente, incomprensibile] La radice sta per essere 7.
Possiamo solo dire nodo * ptr =
o radice, = & node7.
>> Per i nostri scopi, stiamo andando a che fare con inserto,
quindi stiamo andando a voler scrivere una funzione per inserire in questo albero binario
e inserto è inevitabile che chiama malloc per creare un nuovo nodo di questo albero.
Quindi, le cose stanno andando per ottenere disordinato con il fatto che alcuni nodi
sono attualmente in pila
e altri nodi stanno andando a finire nel mucchio quando li inserisce.
Ciò è perfettamente valido, ma l'unica ragione
siamo in grado di fare questo in pila
è perché è un esempio forzato che sappiamo
l'albero dovrebbe essere costruito come 7, 3, 6, 9.
Se non avessimo questo, allora non avrebbe dovuto malloc in primo luogo.
Come vedremo un po 'più tardi, dovremmo essere malloc'ing.
In questo momento è perfettamente ragionevole per mettere in pila,
ma cambiamo ad un implementazione malloc.
Quindi, ciascuna di esse è ora di andare a essere qualcosa di simile
nodo * node9 = malloc (sizeof (nodo)).
E ora andiamo a fare il nostro check.
if (node9 == NULL) - Non volevo che -
ritorno 1, quindi possiamo fare node9-> perché ora è un puntatore,
valore = 6, node9-> sinistra = NULL,
node9-> destra = NULL,
e stiamo andando a fare che per ciascuno di questi nodi.
Così, invece, cerchiamo di metterlo all'interno di una funzione separata.
Chiamiamolo nodo * build_node,
e questo è in qualche modo simile alle API che prevede la codifica di Huffman.
Noi vi diamo le funzioni di inizializzazione per un albero
e decostruttore "funzioni" per quegli alberi e lo stesso per le foreste.
>> Quindi qui si sta andando ad avere una funzione di inizializzazione
di costruire solo un nodo per noi.
E sta andando a guardare più o meno esattamente come questo.
E sto andando anche a essere pigri e non cambiare il nome della variabile,
anche se non ha senso node9 più.
Oh, credo che il valore node9 dovrebbe non sono stati 6.
Ora possiamo ritornare node9.
E qui si deve restituire null.
Tutti d'accordo su questo build-a-nodo della funzione?
Così ora possiamo chiamare che per costruire qualsiasi nodo con un determinato valore e puntatori nulli.
Ora possiamo chiamare, si può fare il nodo * node9 = build_node (9).
E facciamolo. . .
6, 3, 7, 6, 3, 7.
E ora vogliamo impostare i puntatori stessi,
solo che adesso tutto è già in termini di puntatori
quindi non è più necessario l'indirizzo di.
Va bene. Allora, qual è l'ultima cosa che voglio fare?
C'è un controllo degli errori che non sto facendo.
Che cosa significa costruire ritorno nodo?
[Studente, incomprensibile] >> Si '. Se non malloc, che restituisca null.
Quindi ho intenzione di pigramente messo giù qui, invece di fare una condizione per ogni.
Se (node9 == NULL, o - ancora più semplice,
questo è pari a poco se non node9.
Quindi, se non node9, o non Node6, o non node3, o non node7, ritorno 1.
Forse dovremmo stampare malloc non riuscito, o qualcosa del genere.
[Studente] E 'falso uguale a null, come bene?
[Bowden] Qualsiasi valore zero è falso.
Quindi nulla è un valore zero.
Zero è un valore zero. Falso è un valore zero.
Qualsiasi - praticamente gli unici due valori zero sono nulli e zero,
falso è solo hash definito come zero.
Ciò vale anche se si dichiara variabile globale.
Se abbiamo avuto * nodo principale qui,
poi - la cosa bella di variabili globali è che hanno sempre un valore iniziale.
Non è vero di funzioni, come all'interno di qui,
se abbiamo, come, * nodo o nodo x.
Non abbiamo idea di cosa x.Value, x.whatever,
o potremmo stampare e potrebbero essere arbitraria.
Non è vero di variabili globali.
Così radice nodo o nodo x.
Per impostazione predefinita, tutto ciò che è globale, se non esplicitamente inizializzato a un valore,
ha un valore zero come valore.
Così qui, radice * nodo, non esplicitamente inizializzato a nulla,
quindi il suo valore di default è null, che è il valore zero di puntatori.
Il valore predefinito di x sta a significare che x.Value è pari a zero,
x.left è nullo, e x.right è null.
Quindi, poiché è una struttura, tutti i campi della struttura saranno i valori zero.
Non abbiamo bisogno di usare che qui, però.
[Studente] Le strutture sono diverse da quelle di altre variabili, e le altre variabili sono
valori di spazzatura, che sono zero?
[Bowden] Altri valori troppo. Quindi, in x, x sarà pari a zero.
Se è in ambito globale, ha un valore iniziale. Va bene >>.
[Bowden] In entrambi i casi il valore iniziale che ha dato o zero.
Penso che si prende cura di tutto questo.
>> Va bene. Così la parte successiva della questione si chiede,
"Ora vogliamo scrivere una funzione chiamata contiene
con un prototipo di bool valore int. "
Non abbiamo intenzione di fare bool valore int.
Il nostro prototipo è andare a guardare come
bool (valore int.
E poi stiamo anche andando a passare l'albero
che dovrebbe essere il controllo per vedere se ha quel valore.
Così nodo * albero). Va bene.
E poi si può chiamare con qualcosa di simile,
forse ci vuole printf o qualcosa del genere.
Contiene 6, la nostra radice.
Questo dovrebbe restituire uno, o vero,
che contiene 5 radice deve restituire false.
Quindi prendere un secondo per implementare questo.
Puoi farlo sia iterativo o ricorsivo.
La cosa bella del modo in cui abbiamo impostato le cose è che
si presta alla nostra soluzione ricorsiva molto più facile
rispetto alla variabile globale così ha fatto.
Perché se non ci resta che contiene un valore int, allora non abbiamo modo di recursing giù sottoalberi.
Dovremmo avere una funzione distinta di supporto che ricorsivamente le sottostrutture per noi.
Ma dal momento che abbiamo cambiato a prendere l'albero come argomento,
che deve essere sempre in primo luogo,
ora si può recurse più facilmente.
Così iterativa o ricorsiva, andremo su entrambi,
ma staremo a vedere che finisce con l'essere ricorsive abbastanza facile.
Va bene. Qualcuno ha qualcosa che possiamo lavorare?
>> [Studente] Ho una soluzione iterativa. Va bene >>, iterativo.
Ok, questo sembra buono.
Quindi, vuole camminare con noi attraverso di essa?
[Studente] Certo. Così mi sono messo una variabile temporanea per ottenere il primo nodo della struttura ad albero.
E poi ho collegato in cascata, mentre temperatura non nulla uguale,
così, mentre era ancora nella struttura, credo.
E se il valore è uguale al valore di temperatura che sta puntando,
poi restituisce tale valore.
Altrimenti, si controlla se è sul lato destro o sul lato sinistro.
Se mai una situazione in cui non c'è albero più,
poi lo restituisce - esce il ciclo e restituisce false.
[Bowden] Ok. In modo che sembra buono.
Qualcuno ha qualche commento su qualcosa?
Non ho commenti correttezza a tutti.
L'unica cosa che possiamo fare è questo ragazzo.
Oh, sta per andare un po 'lunghetta.
Io che fino sistemare. Va bene.
>> Tutti dovrebbero ricordare come ternario funziona.
Ci sono sicuramente stati quiz in passato
che ti danno una funzione con un operatore ternario,
e dire, tradurre questo, fare qualcosa che non fa uso di ternario.
Quindi questo è un caso molto comune di quando avrei pensato di usare ternario,
dove se una certa condizione impostare una variabile a qualcosa,
altro set che stessa variabile a qualcosa d'altro.
Questo è qualcosa che molto spesso può essere trasformato in questo genere di cose
dove impostare questa variabile a questo - o, beh, è ​​vero? Allora questo, altrimenti questo.
[Studente] La prima è se è vero, giusto?
[Bowden] Si '. Il modo in cui ho sempre letto è, temperatura è uguale al valore maggiore del valore temp,
allora questo, altrimenti questo. E 'una domanda.
E 'più grande? Poi fare la prima cosa. Altrimenti fare la seconda cosa.
Ho quasi sempre - i due punti, ho solo - nella mia testa, ho letto come gli altri.
>> Qualcuno ha una soluzione ricorsiva?
Va bene. Questo che andremo a - potrebbe già essere grande,
ma stiamo andando a fare ancora meglio.
Questo è più o meno la stessa idea esatta.
E 'solo che, beh, vuoi spiegare?
[Studente] Certo. Quindi stiamo facendo in modo che l'albero non è null in primo luogo,
perché se l'albero è null allora sta andando a restituire false, perché non lo abbiamo trovato.
E se c'è ancora un albero, andiamo in - per prima cosa verificare se il valore è il nodo corrente.
Restituisce vero se lo è, e se non ci ricorsione a sinistra oa destra.
Ti sembra appropriato? >> Mm-hmm. (Accordo)
Così notare che questo è quasi - strutturalmente molto simile alla soluzione iterativa.
E 'solo che invece di recursing, abbiamo avuto un ciclo while.
E il caso di base qui, dove albero non nullo pari
era la condizione in cui ci siamo lasciati fuori dal ciclo while.
Sono molto simili. Ma stiamo andando a prendere un passo avanti.
Ora, facciamo la stessa cosa qui.
Si noti che stiamo tornando la stessa cosa in entrambe le linee,
tranne che per un argomento è diverso.
Quindi stiamo andando a fare che in un ternario.
Mi ha colpito qualcosa di opzione, e ha fatto un simbolo. Va bene.
Quindi stiamo andando a tornare che contiene.
Sta per essere più righe, beh, è ​​ingrandita.
Di solito, come una cosa stilistica, non credo che molte persone
inserire uno spazio dopo la freccia, ma credo che se sei coerente, va bene.
Se il valore è inferiore al valore albero, vogliamo ricorsione a sinistra albero,
altro vogliamo ricorsione a destra albero.
Così che era passo quello di rendere questo look più piccoli.
Fase due di rendere questo look più piccoli -
siamo in grado di separare il più righe.
Va bene. Fase due di far sembrare più piccolo è qui,
modo che il valore di ritorno è uguale al valore albero, o contiene altro.
>> Questa è una cosa importante.
Non so se ha detto esplicitamente in classe,
ma si chiama corto circuito di valutazione.
L'idea qui è un valore == valore albero.
Se questo è vero, allora questo è vero, e noi vogliamo 'o' che con tutto ciò che è qui.
Così, senza nemmeno pensare a tutto ciò che è qui,
qual è l'intera espressione intenzione di tornare?
[Studente] Vero? >> Già, perché vero di qualsiasi cosa,
in OR - in OR o vero con qualcosa è necessariamente vero.
Così, non appena si vede il valore di ritorno = valore di albero,
stiamo solo andando a restituire true.
Neanche andando a recurse contiene più in basso la linea.
Siamo in grado di fare un passo ulteriore.
Albero di ritorno non nullo uguale e tutto questo.
Esso ha una funzione inline.
Questo è un esempio di valutazione di corto circuito.
Ma ora è la stessa idea -
invece di - quindi se albero non è uguale a null - o, anche,
se albero fa nulla uguale, che è il caso di cattivo,
se albero è uguale a null, quindi la prima condizione sarà falsa.
Così falsa AND con qualcosa sta per essere ciò?
[Studente] False. Sì >>. Questa è l'altra metà della valutazione di corto circuito,
dove se non nullo albero non è uguale, allora non si ha intenzione di andare anche -
o se albero fa nulla uguale, quindi non abbiamo intenzione di fare un valore == valore albero.
Stiamo solo andando a restituire immediatamente false.
Il che è importante, in quanto se così non fosse corto circuito evaluate,
poi se albero fa nulla uguale, questa seconda condizione sta andando per colpa segmento,
perché tree-> valore dereferenziazione nullo.
Quindi, questo è tutto. Può fare questo - spostare una volta sopra.
Questa è una cosa molto comune anche, non fare questa linea con questo,
ma è una cosa comune in condizioni, forse non proprio qui,
ma se (albero! = NULL, e l'albero-> Valore ==), fare qualsiasi cosa.
Questa è una condizione molto comune, in cui invece di avere
per rompere questo in due se e dove vuoi, è il nulla albero?
Ok, non è nulla, così ora è il valore dell'albero pari al valore? Fate questo.
Invece, questa condizione, questo non potrà mai errore di segmentazione
perché si romperà se questo succede a essere null.
Beh, credo che se il tuo albero è un puntatore completamente invalido, può ancora errore di segmentazione,
ma non può errore di segmentazione se albero è nullo.
Se fosse nullo, sarebbe scoppiata la prima mai dereferenziati il ​​puntatore del mouse, in primo luogo.
[Studente] E `la valutazione chiamato pigro?
>> [Bowden] valutazione pigra è una cosa a parte.
Valutazione pigra è più simile a chiedere di un valore,
Vi chiedo di calcolare un valore, un po ', ma tu non ne hai bisogno subito.
Quindi, fino a che realmente ne hanno bisogno, non viene valutato.
Questa non è esattamente la stessa cosa, ma nel pset Huffman,
si dice che noi "pigramente" scrivere.
La ragione per cui lo facciamo è perché ci sta effettivamente buffer di scrittura -
non vogliamo scrivere singoli bit alla volta,
o singoli byte alla volta, noi invece vogliamo ottenere un pezzo di byte.
Poi, una volta che abbiamo un pezzo di byte, quindi noi lo scrivere.
Anche se gli chiedi di scrivere - e fwrite e fread fare la stessa cosa.
Essi tamponare la tua legge e scrive.
Anche se si chiede di scrivere subito, probabilmente non lo farà.
E non si può essere certi che le cose stanno per essere scritto
finché non viene chiamato hfclose o qualunque cosa sia,
che poi dice, va bene, sto chiudendo il mio file,
questo significa che è meglio scrivere tutto quello che non ho scritto ancora.
Non ha bisogno di scrivere tutto fuori
fino a quando si sta chiudendo il file, e quindi ha bisogno di.
Ecco, questo è proprio quello pigro - aspetta fino a quando non deve accadere.
Questo - prendere 51 e andrai in esso in modo più dettagliato,
perché OCaml e tutto in 51, tutto è ricorsione.
Non ci sono soluzioni iterative, in fondo.
Tutto è ricorsione, e la valutazione pigra
sarà importante per molte circostanze
dove, se non si è pigramente valutare, ciò significherebbe -
L'esempio è in streaming, che sono infinitamente lungo.
In teoria, si può pensare dei numeri naturali come un flusso di 1-2-3-4-5-6-7,
Così le cose vanno bene pigramente valutati.
Se dico che voglio il decimo numero, allora posso valutare fino al decimo numero.
Se voglio il numero centesimo, allora posso valutare fino al numero centesimo.
Senza valutazione pigra, quindi sta andando a cercare di valutare tutti i numeri immediatamente.
Stai valutando i numeri infiniti, e che non è solo possibile.
Quindi ci sono un sacco di casi in cui la valutazione pigra
è solo essenziale per ottenere le cose al lavoro.
>> Ora vogliamo scrivere inserto inserto dove sta per essere
allo stesso modo cambiando nella sua definizione.
Quindi, in questo momento è inserto bool (int valore).
Stiamo andando a cambiare la situazione a inserto bool (valore int, nodo * albero).
Stiamo in realtà sta per cambiare di nuovo in un po ', vedremo il perché.
E cerchiamo di spostare build_node, solo per il gusto di farlo,
sopra inserire in modo da non dover scrivere un prototipo di funzione.
Il che è un suggerimento che si sta andando ad utilizzare build_node in inserimento.
Va bene. Prendi un minuto per questo.
Penso che ho salvato la revisione se si vuole tirare da quella,
o, almeno, l'ho fatto ora.
Volevo un momento di pausa per pensare alla logica di inserimento,
se non si può pensare di esso.
In sostanza, si sarà sempre solo l'inserimento di foglie.
Come, se inserisco 1, poi ho inevitabilmente per essere l'inserimento di 1 -
Mi cambio in nero - I'Ll essere inserendo 1 qui.
Oppure, se inserisco 4, voglio essere l'inserimento di 4 oltre qui.
Quindi, non importa quello che fai, si sta andando ad essere l'inserimento di una foglia.
Tutto quello che dovete fare è scorrere lungo l'albero fino ad arrivare al nodo
che dovrebbe essere padre del nodo, padre del nuovo nodo,
e quindi modificare il suo puntatore a sinistra oa destra, a seconda che
è maggiore o minore del nodo corrente.
Modificare tale puntatore per puntare al nuovo nodo.
Quindi scorrere verso il basso l'albero, fare il punto foglia al nuovo nodo.
Anche riflettere sul perché che vieta il tipo di situazione prima,
dove ho costruito l'albero binario in cui è stato corretto
se solo guardato un singolo nodo,
ma 9 era a sinistra del 7 se iterato giù tutto il senso.
Ecco, questo è impossibile, in questo scenario, in quanto -
pensare di inserire 9 o qualcosa, in corrispondenza del nodo prima,
Io vado a vedere 7 e sto solo intenzione di andare a destra.
Quindi, non importa quello che faccio, se sto andando a inserire una foglia,
e ad una foglia utilizzando l'algoritmo appropriato,
che sarà impossibile per me per inserire 9 a sinistra di 7
perché non appena mi ha colpito sette ho intenzione di andare a destra.
Qualcuno ha qualcosa per iniziare?
[Studente] che faccio. Certo >>.
[Studente, incomprensibile]
[Altro studente, incomprensibile]
[Bowden] E 'apprezzato. Va bene. Vuoi spiegare?
>> [Studente] Poiché sappiamo che siamo stati l'inserimento
nuovi nodi alla fine della struttura,
Ho fatto passare attraverso l'albero iterativamente
fino a quando ho avuto modo di un nodo che puntava a null.
E poi ho deciso di metterlo sia sul lato destro o sul lato sinistro
utilizzando questa variabile diritto, ma mi ha detto dove metterlo.
E poi, in sostanza, ho appena fatto che durano -
che il nodo punto di temperatura per il nuovo nodo che si stava creando,
sia sul lato sinistro o sul lato destro, a seconda che il valore di destra era.
Infine, a impostare il nuovo valore del nodo al valore del suo test.
[Bowden] Va bene, quindi non vedo un problema qui.
Questo è come il 95% del tragitto.
L'unico problema che vedo, beh, fa vedere a nessuno un problema?
Qual è la circostanza in cui si rompono fuori dal giro?
[Studente] Se temp è nullo? Sì >>. Allora, come uscire dal ciclo è se temp è nullo.
Ma cosa faccio qui?
Io temperatura dereference, che è inevitabilmente nullo.
Così l'altra cosa che devi fare non è solo tenere traccia fino a quando temperatura è nullo,
si desidera tenere traccia del genitore in ogni momento.
Vogliamo anche * nodo padre, credo che possiamo continuare che a nulla in un primo momento.
Questo sta per avere un comportamento strano per la radice dell'albero,
ma ci arriveremo.
Se il valore è maggiore di qualsiasi altra cosa, quindi temp = temperatura giusta.
Ma prima di farlo, temp = genitore.
Oppure i genitori sempre andando a temperatura uguale? E 'questo il caso?
Se temp non è nullo, quindi ho intenzione di spostare verso il basso, non importa quale,
ad un nodo per il quale temp è il genitore.
Così genitore sarà temp, e poi mi sposto temperatura verso il basso.
Ora temperatura è nullo, ma i punti padre al padre della cosa che è nullo.
Così qui, non voglio impostare uguale a destra 1.
Così ho spostato a destra, quindi se a destra = 1,
e credo che anche voi volete fare -
se si sposta a sinistra, si desidera impostare diritto uguale a 0.
Oppure se mai sposta a destra.
Quindi a destra = 0. Se il diritto = 1,
ora vogliamo rendere effettivo il diritto newnode puntatore genitore,
altra cosa vuole fare la sinistra newnode puntatore genitore.
Domande su questo?
Va bene. Quindi questo è il nostro modo - beh, in realtà, invece di fare questo,
ci aspettava quasi di utilizzare build_node.
E poi se newnode uguale a null, return false.
Questo è quello. Ora, questo è quello che ci aspettavamo di fare.
>> Questo è ciò che le soluzioni del personale fanno.
Non sono d'accordo con questo come il modo "giusto" di andare su di esso
ma questo è perfettamente bene e funzionerà.
Una cosa che è un po 'strano proprio ora è
se l'albero inizia come nullo, si passa in un albero nullo.
Credo che dipende da come si definisce il comportamento di passare in un albero nullo.
Mi sembra che se si passa in un albero nullo,
quindi inserendo il valore in un albero nullo
deve solo restituire un albero in cui l'unico valore è quello singolo nodo.
Sei persone sono d'accordo con questo? Si potrebbe, se si vuole,
se si passa in un albero nullo
e si desidera inserire un valore in esso, restituire false.
E 'a voi definire tale.
Per fare la prima cosa che ho detto e poi -
bene, si sta andando ad avere problemi di farlo, perché
sarebbe più facile se avessimo un puntatore globale alla cosa,
ma non, quindi se albero è nulla, non c'è niente che possiamo fare al riguardo.
Possiamo solo restituire false.
Quindi ho intenzione di cambiare inserto.
Siamo tecnicamente potrebbe semplicemente cambiare questo qui,
come è l'iterazione di cose,
ma ho intenzione di cambiare inserto di fare un nodo della struttura **.
Puntatori doppi.
Che cosa significa?
Invece di trattare con puntatori a nodi,
la cosa che mi vado a manipolare questo puntatore.
Io vado a manipolare questo puntatore.
Ho intenzione di essere manipolare puntatori direttamente.
Questo ha senso dal momento che, pensate in basso -
bene, in questo momento questo punti a null.
Quello che voglio fare è manipolare questo puntatore per puntare a null non.
Voglio che per puntare al mio nuovo nodo.
Se ho appena tenere traccia dei puntatori ai miei puntatori,
allora non c'è bisogno di tenere traccia di un puntatore genitore.
Posso solo tenere traccia per vedere se il puntatore punta a null,
e se il puntatore punta a null,
cambiare per puntare al nodo che voglio.
E posso cambiarlo perchè ho un puntatore al puntatore.
Vediamo un po 'adesso.
Si può effettivamente fare in modo ricorsivo abbastanza facilmente.
Vogliamo farlo?
Sì, lo facciamo.
>> Vediamolo in modo ricorsivo.
In primo luogo, ciò che è il nostro scenario di base sarà?
Quasi sempre il nostro scenario di base, ma in realtà, questo è una specie di complicato.
Per prima cosa, se (albero == NULL)
Credo che stiamo solo andando a restituire false.
Questo è diverso dal vostro albero di essere nullo.
Questo è il puntatore al puntatore nullo privilegi di root
il che significa che il puntatore radice non esiste.
Così qui, se faccio
* nodo - facciamo solo riutilizzare questo.
Nodo * root = NULL,
e poi ho intenzione di chiamare inserto facendo qualcosa di simile,
inserire 4 in & root.
Quindi & root, se root è un nodo *
allora e radice sta per essere un nodo **.
Questo è valido. In questo caso, albero, qui,
albero non è nulla - o inserto.
Qui. Albero non è null; albero * è nulla, che va bene
perché se albero * è nullo, allora posso manipolare
per puntare ora a quello che voglio puntare a.
Ma se albero è nullo, significa che ho appena venuto qui e ha detto nulla.
Questo non ha senso. Io non posso fare niente con questo.
Se albero è null, return false.
Così ho già detto in pratica ciò che il nostro scenario di base reale.
E che cosa è che sta per essere?
[Studente, incomprensibile]
[Bowden] Sì. Quindi, se (* albero == NULL).
Questo si riferisce al caso qui
dove se il mio puntatore è il puntatore sono concentrato su,
così come mi sono concentrato su questo puntatore, ora mi sono concentrato su questo puntatore.
Ora sono concentrato su questo puntatore.
Quindi, se il mio puntatore rosso, che è il mio ** nodo,
è sempre - se *, il mio puntatore rosso, è sempre nullo,
ciò significa che io sono al caso in cui mi sto concentrando su un puntatore che punti -
questo è un puntatore che appartiene ad una foglia.
Voglio cambiare questo puntatore per puntare al mio nuovo nodo.
Torna qui.
Il mio newnode sarà solo nodo * n = build_node (valore)
allora n, se n = NULL, restituisce false.
Altrimenti vogliamo cambiare ciò che il puntatore sta puntando attualmente
per puntare ora al nostro nodo di recente costruzione.
Siamo in grado di darsi da fare qui.
Invece di dire n, diciamo * albero = se albero *.
Capire a tutti che? Che da trattare con puntatori a puntatori,
siamo in grado di cambiare i puntatori nulli per puntare a cose che vogliamo loro di puntare.
Questo è il nostro scenario di base.
>> Ora la nostra ricorrenza, o il nostro ricorsione,
sta per essere molto simile a tutte le altre ricorsioni che abbiamo fatto.
Stiamo andando a voler inserire il valore,
e ora ho intenzione di usare di nuovo ternario, ma ciò che è la nostra condizione sarà?
Che cosa si prova che stiamo cercando di decidere se vogliamo andare a destra oa sinistra?
Facciamolo in fasi separate.
Se (valore <) cosa?
[Studente] Il valore dell'albero?
[Bowden] Quindi ricorda che sono attualmente -
[Gli studenti, incomprensibili]
[Bowden] Si ', quindi proprio qui, diciamo che la freccia verde
è un esempio di quale albero è attualmente, è un puntatore a questo puntatore.
Questo significa che io sono un puntatore a un puntatore a 3.
Il dereference due volte suonava bene.
Cosa devo - come faccio a farlo?
[Studente] risoluzione del riferimento di una volta, e poi fare freccia in quel modo?
[Bowden] Così (albero *) è il dereference una volta, -> valore
sta per darmi il valore del nodo che sto indicando indirettamente.
Quindi posso anche scriverlo ** tree.value se preferite.
In entrambi i casi funziona.
Se questo è il caso, allora voglio chiamare inserire con valore.
E che cosa è il mio nodo aggiornato ** sarà?
Voglio andare a sinistra, in modo da tree.left ** sarà mia sinistra.
E voglio che il puntatore a quella cosa
in modo che se la sinistra finisce per essere il puntatore nullo,
Posso modificare per puntare al mio nuovo nodo.
>> E l'altro caso può essere molto simile.
Facciamo effettivamente fare che il mio ternario in questo momento.
Inserire il valore se il valore <(albero **). Valore.
Poi vogliamo aggiornare i nostri ** a sinistra,
altra cosa desidera aggiornare i nostri ** a destra.
[Studente] Ritiene che ottenere il puntatore al puntatore?
[Bowden] Si ricorda che - ** tree.right è una stella nodo.
[Studente, incomprensibile] >> Si '.
** Tree.right è così puntatore o qualcosa del genere.
Quindi prendendo un puntatore a tale, che mi dà quello che voglio
del puntatore a quel ragazzo.
[Studente] Possiamo andare più volte perché stiamo usando i due puntatori?
[Bowden] Si '. So - no, è possibile, e che la soluzione prima di
era un modo di farlo senza fare due puntatori.
È necessario essere in grado di comprendere con due puntatori,
e questa è una soluzione detergente.
Si noti inoltre che, cosa succede se il mio albero -
cosa succede se la mia radice era nullo? Cosa succede se faccio questo caso proprio qui?
Quindi il nodo * root = NULL, inserire 4 in & root.
Ciò che è radice sarà dopo questo?
[Studente, incomprensibile] >> Si '.
Valore di riferimento sarà 4.
Root sinistra sta per essere nullo, giusto radice sta per essere nullo.
Nel caso in cui non abbiamo passato radice per indirizzo,
non siamo riusciti a modificare la root.
Nel caso in cui l'albero - dove root è stato nullo,
abbiamo dovuto restituire false. Non c'è niente che potessimo fare.
Non si può inserire un nodo in un albero vuoto.
Ma ora possiamo, dobbiamo solo fare un albero vuoto in un unico nodo della struttura.
Qual è di solito il modo atteso che si suppone di lavorare.
>> Inoltre, questo è notevolmente più corta
anche tenere traccia del genitore, e così non si scorre verso il basso tutto il senso.
Ora ho dei miei genitori, e io ho il mio puntatore del diritto dei genitori a qualsiasi altra cosa.
Invece, se abbiamo fatto questo modo iterativo, sarebbe la stessa idea con un ciclo while.
Ma invece di avere a che fare con il mio puntatore del genitore,
invece il mio puntatore attuale sarebbe la cosa
che sto modificando direttamente per puntare al mio nuovo nodo.
Non avere a che fare con il fatto che è rivolta a sinistra.
Non avere a che fare con il fatto che è rivolta verso destra.
E 'solo ciò che questo puntatore è, ho intenzione di impostare in modo che punti al mio nuovo nodo.
Tutti capire come funziona?
Se no, perché vogliamo fare in questo modo,
ma almeno che questo funziona come soluzione?
[Studente] Dove ci restituisce true?
[Bowden] Questo è probabilmente proprio qui.
Se correttamente inserito, restituisce true.
Altrimenti, qui stiamo andando a voler restituire qualunque Insert Returns.
>> E cosa c'è di speciale in questa funzione ricorsiva?
E 'la coda ricorsiva, così fino a quando si compila con qualche ottimizzazione,
si riconoscerà questo e non troverete mai un overflow dello stack da questo,
anche se il nostro albero ha un'altezza di 10.000 o 10 milioni.
[Studente, incomprensibile]
[Bowden] penso che lo fa a Dash - o quale livello di ottimizzazione
è richiesto per una ricorsione tail essere riconosciuto.
Penso che riconosce - GCC e Clang
inoltre hanno significati diversi per i loro livelli di ottimizzazione.
Voglio dire che è Dasho 2, con certezza che riconoscerà ricorsione in coda.
Ma noi - si potrebbe costruire come un esempio Fibonocci o qualcosa del genere.
Non è facile per testare con questo, perché è difficile costruire
un albero binario che è così grande.
Ma sì, penso che sia Dasho 2, che
se si compila con Dasho 2, cercherà ricorsione in coda
e ottimizzare che fuori.
Torniamo a - inserire è letteralmente l'ultima cosa di cui ha bisogno.
Torniamo all'inserto qui
dove stiamo andando a fare la stessa idea.
Sarà ancora il difetto di non essere in grado di gestire tutto
quando la radice stessa è nullo, o la voce passato è null,
ma invece di trattare con un puntatore genitore,
cerchiamo di applicare la stessa logica di puntatori mantenere ai puntatori.
Se qui mantenere il nostro nodo ** corr,
e non abbiamo bisogno di tenere traccia di destra più,
ma il nodo ** corr = & albero.
E ora il nostro ciclo while sarà mentre cur * non nullo uguale.
Non hanno bisogno di tenere traccia dei genitori più.
Non hanno bisogno di tenere traccia di destra e sinistra.
E io lo chiamo temperatura, perché stiamo già utilizzando temp.
Va bene. Quindi, se (valore> * temp),
allora e (* temp) -> a destra
else temp = & (* temp) -> a sinistra.
E ora, a questo punto, dopo questo ciclo while,
Lo faccio solo perché forse è più facile pensare che iterativamente in modo ricorsivo,
ma dopo questo ciclo while,
* Temp è il puntatore che vogliamo cambiare.
>> Prima abbiamo avuto genitori, e abbiamo deciso di cambiare o sinistra genitore o genitore a destra,
ma se vogliamo cambiare proprio genitore,
allora è giusto temperatura * genitore, e possiamo cambiare direttamente.
Così qui, si può fare * temp = newnode, e questo è tutto.
Quindi avviso, tutto quello che è stato fatto in questo estrarre righe di codice.
Al fine di tenere traccia del genitore in tutto ciò che è sforzo supplementare.
Qui, se solo tenere traccia del puntatore al puntatore,
e anche se abbiamo deciso di sbarazzarsi di tutte queste parentesi graffe ora,
farlo sembrare più breve.
Questa è oggi la soluzione esattamente lo stesso,
ma meno righe di codice.
Una volta che si avvia il riconoscimento di questa come una soluzione valida,
è anche più facile ragionare su che come, va bene,
perché ho questa bandiera a destra int?
Che cosa vuol dire? Oh, sta a significare che
ogni volta che vado a destra, ho bisogno di impostare,
altrimenti se vado a sinistra ho bisogno di impostare a zero.
Qui, non c'è bisogno di ragionare su quello, è solo più facile da pensare.
Domande?
[Studente, incomprensibile] >> Si '.
Ok, quindi in ultimo bit -
Credo che una funzione semplice e veloce che possiamo fare è,
let's - insieme, credo, cercare di scrivere una funzione contiene
che non importa se si tratta di un albero binario di ricerca.
Questo contiene la funzione deve restituire true
se da qualche parte in questo albero binario generale è il valore che stiamo cercando.
Quindi, si deve prima fare in modo ricorsivo e poi lo faremo iterativamente.
Possiamo in realtà solo farlo insieme, perché questo sarà davvero breve.
>> Qual è il mio scenario di base sarà?
[Studente, incomprensibile]
[Bowden] Quindi, se (albero == NULL), e poi?
[Studente] Return false.
[Bowden] Else, beh, non ho bisogno del resto.
Se era il mio caso altra base.
Valore [studente] Tree? Sì >>.
Quindi, se (albero-> Valore ==.
Si noti che siamo tornati a * nodo non, nodo ** s?
Contiene non avrà mai bisogno di utilizzare un nodo **,
dal momento che non sta modificando i puntatori.
Stiamo solo loro movimento.
Se ciò accade, allora vogliamo restituire true.
Altrimenti vogliamo attraversare i bambini.
Quindi non possiamo ragionare sul fatto che tutto ciò che a sinistra è meno
e tutto a destra è maggiore.
Così che cosa è la nostra condizione sta per essere qui - o, cosa dobbiamo fare?
[Studente, incomprensibile] >> Si '.
Di ritorno contiene (valore, albero-> sinistra)
o contiene (valore, albero-> destra). E questo è tutto.
E notate c'è qualche corto circuito di valutazione,
dove se capita di trovare il valore nella struttura a sinistra,
non abbiamo mai bisogno di guardare l'albero giusto.
Questa è l'intera funzione.
Ora facciamolo in modo iterativo,
che sta per essere meno bello.
Prendiamo l'inizio abituale di nodo * cur = albero.
Mentre (corr! = NULL).
Rapidamente andare a vedere un problema.
Se cur - qui, se mai uscire da questo,
allora abbiamo a corto di cose da guardare, in modo da tornare false.
Se (corr-> Valore ==), restituisce true.
Così ora, siamo in un luogo -
non sappiamo se si vuole andare a sinistra oa destra.
Così arbitrariamente, facciamo solo andare a sinistra.
Ovviamente ho incontrato un problema in cui ho completamente abbandonato tutto -
Io sempre e solo controllare il lato sinistro di un albero.
Non potrò mai controllare tutto ciò che è un figlio destro di nulla.
Come posso risolvere questo problema?
[Studente] È necessario tenere traccia di sinistra e di destra in una pila.
[Bowden] Si '. Quindi cerchiamo di rendere più
struct lista, nodo * n, e quindi il nodo ** prossimo?
Penso che funziona bene.
Vogliamo andare oltre la sinistra, o let's - qui.
Struct = lista lista, si inizierà
presso questa lista struct.
* List = NULL. In modo che sarà la nostra lista concatenata
di sottostrutture che abbiamo saltato.
Stiamo per attraversare a sinistra ora,
ma dal momento che abbiamo inevitabilmente bisogno di tornare a destra,
Abbiamo intenzione di mantenere il diritto all'interno della nostra lista struct.
Poi avremo new_list o di una struttura,
struct lista *, new_list = malloc (sizeof (lista)).
Ho intenzione di ignorare il controllo degli errori, ma si dovrebbe controllare per vedere se è null.
New_list il nodo che sta per puntare a -
oh, è per questo che ho voluto qui. E 'intenzione di puntare a una lista di struct secondo.
Questo è solo il modo collegato lavoro liste.
Questa è la stessa di una lista collegata int
tranne stiamo solo sostituendo int con * nodo.
E 'esattamente lo stesso.
Così new_list, il valore della nostra nodo new_list,
sta per essere cur-> destra.
Il valore della nostra new_list-> prossimo sarà la nostra lista originale,
e poi abbiamo intenzione di aggiornare la nostra lista per puntare a new_list.
>> Ora abbiamo bisogno di una sorta di modo di tirare le cose,
come abbiamo attraversato l'intero sotto-albero di sinistra.
Ora abbiamo bisogno di tirare roba fuori di esso,
come la corrente è nulla, noi non vogliamo tornare semplicemente false.
Vogliamo tirare fuori adesso il nostro nuovo elenco.
Un modo conveniente di fare questo - beh, in realtà, ci sono diversi modi per farlo.
Qualcuno ha un suggerimento?
Dove devo fare questo o come dovrei fare?
Abbiamo solo un paio di minuti, ma qualche suggerimento?
Invece di - un modo, invece di essere durante la nostra condizione,
quello che stiamo attualmente esaminando non è null,
invece abbiamo intenzione di continuare ad andare fino a quando la nostra lista stessa è nullo.
Quindi, se la nostra lista finisce per essere nullo,
allora abbiamo a corto di cose da cercare, per cercare oltre.
Ma questo significa che la prima cosa nella nostra lista è solo andare a essere il primo nodo.
La prima cosa sarà - non abbiamo più bisogno di vedere che.
Così list-> n sarà il nostro albero.
lista-> next sta per essere nullo.
E ora, mentre lista non fa nulla uguale.
Cur sta per tirare qualcosa dalla nostra lista.
Così cur sta per pari list-> n.
E poi lista sta per pari list-> n, o una lista-> next.
Quindi, se il valore corrente è uguale al valore.
Ora possiamo aggiungere sia il nostro puntatore a destra e la nostra sinistra puntatore
fino a quando non sono nulla.
Quaggiù, credo che avrei dovuto farlo, in primo luogo.
Se (corr-> destra! = NULL)
poi abbiamo intenzione di inserire tale nodo al nostro elenco.
Se (corr-> sinistra), questo è un po 'di lavoro in più, ma va bene.
Se (corr-> sinistra! = NULL),
e abbiamo intenzione di inserire la sinistra nella nostra lista concatenata,
e che dovrebbe essere.
Noi iterare - fintanto che qualcosa nella nostra lista,
abbiamo un altro nodo da guardare.
Quindi guardiamo a quel nodo,
avanziamo la nostra lista a quello successivo.
Se questo nodo è il valore che stiamo cercando, siamo in grado di restituire true.
Altrimenti inserire entrambi i nostri sottoalberi sinistro e destro,
fino a quando non sono nulla, nella nostra lista
in modo che inevitabilmente andare su di loro.
Quindi, se non erano nulla,
se il nostro puntatore radice ha evidenziato due cose,
poi in un primo momento abbiamo tirato fuori qualcosa così la nostra lista finisce per essere null.
E poi abbiamo messo due le cose, in modo ora la nostra lista è di dimensione 2.
Poi andremo a filo dietro e stiamo solo andando a tirare,
diciamo, il puntatore del mouse a sinistra del nostro nodo principale.
E che ti basta tenere accadendo; finiremo loop su tutto.
>> Si noti che questo era significativamente più complicato
nella soluzione ricorsiva.
E ho detto più volte
che la soluzione ricorsiva di solito ha molto in comune con la soluzione iterativa.
Ecco questo è esattamente ciò che la soluzione ricorsiva sta facendo.
L'unica modifica è che invece di implicitamente utilizzando lo stack, stack di programma,
come il tuo modo di tenere traccia di quello che i nodi che ancora bisogno di visitare,
ora è necessario utilizzare in modo esplicito una lista concatenata.
In entrambi i casi si sta tenendo traccia di quale nodo ha ancora bisogno di essere visitato.
Nel caso ricorsivo è solo più facile perché una pila
viene implementato per voi come lo stack del programma.
Si noti che questo elenco collegato, è uno stack.
Qualunque cosa abbiamo appena messo in pila
è immediatamente quello che stiamo andando a tirare fuori la pila per visitare successivo.
Siamo fuori tempo, ma tutte le domande?
[Studente, incomprensibile]
[Bowden] Si '. Quindi, se abbiamo la nostra lista concatenata,
corrente sta per puntare a questo ragazzo,
e ora stiamo solo l'approfondimento delle lista collegata a concentrarsi su questo ragazzo.
Stiamo attraversando sulla lista concatenata in quella linea.
E poi credo che dovremmo liberare la nostra lista concatenata e roba
una volta prima di ritornare vero o falso, abbiamo bisogno di
scorrere la nostra lista collegata e sempre qui, credo,
se corr diritto non è uguale a, aggiungere, quindi ora vogliamo liberare
corr perché, beh, abbiamo fatto completamente dimenticare la lista? Gia '.
Ecco, questo è quello che vogliamo fare qui.
Dov'e 'il puntatore?
Cur era allora - vogliamo una lista struct * 10 pari elenco successivo.
Elenco gratuito, elenco = temp.
E nel caso in cui si ritorna vero, abbiamo bisogno di iterare
per il resto della nostra lista concatenata liberando le cose.
La cosa bella la soluzione ricorsiva è liberare le cose
significa solo factorings popping dalla pila che avverrà per voi.
Così siamo passati da qualcosa che è come 3 linee di hard-to-think-sul codice
a qualcosa che è molto più difficile da molti-pensare-di righe di codice.
Altre domande?
Bene. Siamo a posto. Bye!
[CS50.TV]