[Powered by Google Translate] [Sezione 7] [meno confortevole] [Nate Hardison] [Harvard University] [Questo è CS50.] [CS50.TV] 

Benvenuti alla Sezione 7. Grazie a Sandy uragano, invece di avere una sezione normale di questa settimana, lo stiamo facendo walk-through, attraverso la sezione di domande. Ho intenzione di seguire in particolare il problema Set 6 Specification, e passando attraverso tutte le domande del Una sezione della sezione Domande. Se ci sono delle domande, si prega di inviare questi su CS50 discutere. 

Va bene. Cominciamo. In questo momento sto guardando la pagina 3 della Specifica Set problema. Stiamo per iniziare prima a parlare di alberi binari in quanto tali hanno un sacco di rilevanza per set problema di questa settimana - la codifica di Huffman. Una delle strutture di dati molto prima abbiamo parlato sul CS50 era la matrice. Ricordate che un array è una sequenza di elementi - tutte dello stesso tipo - memorizzato accanto all'altro in memoria. Se ho un array di interi che posso disegnare con questo scatole-numeri-interi stile - Diciamo che ho 5 nella prima casella, ho 7 nel secondo, poi ho 8, 10, e 20 nella casella finale. Ricordate le cose, le due realtà positive di questa matrice è che abbiamo questo tempo costante accesso a qualsiasi elemento particolare  nella matrice se sappiamo suo indice. Per esempio, se voglio prendere il terzo elemento della matrice - 2 dell'indice usando il nostro a base zero sistema di indicizzazione - Ho letteralmente solo fare un semplice calcolo matematico, hop a quella posizione nella matrice, estrarre la 8 che è memorizzato, e io sono a posto. 

Una delle cose brutte su questo array - di cui abbiamo parlato quando abbiamo discusso liste concatenate - è che se voglio inserire un elemento in questa matrice, Ho intenzione di fare un po 'a vacillare. Ad esempio, questa matrice qui è in modo ordinato - in ordine crescente - 5, poi 7, poi 8, poi 10, poi 20 - ma se voglio inserire il numero 9 in questa matrice, Sto andando a spostare alcuni degli elementi, al fine di fare spazio. Siamo in grado di disegnare questo qui. Sto andando a spostare il 5, il 7, e poi la 8; creare uno spazio dove posso mettere il 9, e poi il 10 e il 20 può andare alla destra del 9. Si tratta di una specie di dolore perché nel peggiore dei casi - quando siamo dover inserire o all'inizio o alla fine della matrice, a seconda di come ci stiamo spostando - potremmo finire per dover spostare tutti gli elementi che stiamo attualmente memorizzando nella matrice. 

Allora, che cosa è stato il modo per aggirare questo? Il modo per aggirare questo è stato quello di andare alla nostra lista concatenata metodo in cui - invece di memorizzare gli elementi 5, 7, 8, 10 e 20 tutti adiacenti in memoria - quello che abbiamo fatto è stato invece conservarli tipo di ovunque volessimo per memorizzarli in queste liste collegate nodi che sto disegnando qui, un po 'ad hoc. E poi li abbiamo collegati tra loro con questi puntatori successivi. Posso avere un puntatore dalla 5 alla 7, un puntatore dalla 7 alla 8, un puntatore dalla 8 alla 10, e, infine, un puntatore dalla 10 alla 20, e poi un puntatore nullo al 20 che indica che non c'è niente di sinistra. Il trade-off che abbiamo qui è che ora se vogliamo inserire il numero 9 nella nostra lista ordinata, tutto quello che dobbiamo fare è creare un nuovo nodo con 9, collegarlo fino al punto fino al luogo appropriato, e poi ri-legare l'8 a puntare verso il basso al 9. E 'abbastanza veloce, assumendo sappiamo esattamente dove si vuole inserire il 9. Ma il trade-off in cambio di questo è che ora abbiamo perso la costante tempo di accesso a qualsiasi elemento particolare nella nostra struttura dati. Per esempio, se voglio trovare il quarto elemento in questa lista collegata, Ho intenzione di ricominciare proprio all'inizio della lista e lavorare la mia strada attraverso il conteggio nodo per nodo fino a trovare il quarto. 

Al fine di ottenere prestazioni di accesso meglio di una lista concatenata - ma anche mantenere alcuni dei vantaggi che abbiamo avuto in termini di inserimento a tempo da una lista concatenata - un albero binario sta andando ad avere bisogno di utilizzare la memoria un po 'di più. In particolare, invece di avere un puntatore a un nodo di albero binario - come la lista concatenata nodo fa - abbiamo intenzione di aggiungere un secondo puntatore al nodo albero binario. Piuttosto che avere un puntatore all'elemento successivo, stiamo andando ad avere un puntatore a un figlio sinistro e figlio destro. 

Facciamo un disegno per vedere ciò che in realtà sembra. Ancora una volta, ho intenzione di utilizzare queste scatole e frecce. Un nodo di albero binario partirà con solo una semplice scatola. E 'intenzione di avere uno spazio per il valore, e poi è anche intenzione di avere uno spazio per il figlio sinistro e figlio destro. Ho intenzione di etichettarli qui. Stiamo per avere il bambino a sinistra, e poi abbiamo intenzione di avere il figlio destro. Ci sono molti modi diversi di fare questo. A volte, per lo spazio e la comodità, Io in realtà disegnare come sto facendo qui in basso dove ho intenzione di avere il valore in alto, e poi il bambino a destra in basso a destra, e il figlio sinistro in basso a sinistra. Tornando a questo diagramma in alto, abbiamo il valore in cima, poi abbiamo la sinistra-bambino puntatore e quindi abbiamo il diritto-bambino puntatore. 

Nella specifica Set problema, si parla di disegnare un nodo che ha un valore di 7, e poi a sinistra-figlio puntatore che è nullo, e un diritto-figlio puntatore che è nullo. Possiamo scrivere NULL capitale nello spazio per sia il figlio sinistro e il figlio destro, o siamo in grado di disegnare questa barra diagonale attraverso ciascuna delle caselle per indicare che è nullo. Ho intenzione di farlo solo perché è più semplice. Quello che vedete qui sono due modi di diagrammi molto semplice nodo di albero binario dove abbiamo il valore 7 e puntatori nulli bambino. 

La seconda parte delle nostre discussioni specifiche su come con le liste collegate - ricordate, abbiamo avuto solo a mantenere il primo elemento di una lista per ricordare l'intero elenco - e allo stesso modo, con un albero binario, non ci resta che aggrapparsi a un puntatore alla struttura ad albero al fine di mantenere il controllo sulla struttura dati intera. Questo elemento particolare della struttura ad albero si chiama il nodo radice dell'albero. Ad esempio, se questo nodo - il nodo contenente il valore 7 con puntatori nulli a destra ea sinistra del figlio - erano il valore solo nel nostro albero, allora questo sarebbe il nostro nodo principale. E 'proprio all'inizio del nostro albero. Possiamo vedere questo un po 'più chiaro una volta che iniziare ad aggiungere ulteriori nodi al nostro albero. Permettetemi di tirare su una nuova pagina. 

Ora stiamo andando a disegnare un albero che ha 7 alla radice, e 3 all'interno del figlio sinistro, e 9 all'interno del figlio destro. Ancora una volta, questo è abbastanza semplice. Abbiamo 7, disegnare un nodo per la 3, un nodo per 9, e ho intenzione di impostare il puntatore a sinistra bambino di 7 punti al nodo contenente 3, e il diritto-bambino puntatore del nodo contenente 7 al nodo contenente 9. Ora, dal momento che 3 e 9 non ha figli, stiamo andando a impostare tutti i loro puntatori figlio per essere nullo. Qui, la radice del nostro albero corrisponde al nodo contenente il numero 7. Si può vedere che se tutto quello che abbiamo è un puntatore a quel nodo radice, possiamo poi a piedi attraverso il nostro albero e accedere a entrambi i nodi figlio - sia 3 e 9. Non c'è bisogno di mantenere i puntatori ad ogni singolo nodo sull'albero. Va bene. Ora stiamo andando ad aggiungere un altro nodo a questo schema. Stiamo per aggiungere un nodo contenente 6, e abbiamo intenzione di aggiungere questo come il figlio destro del nodo contenente 3. Per fare questo, ho intenzione di cancellare quel puntatore nullo nel 3-nodo e cavo fino a puntare al nodo contenente 6. Va bene. 

A questo punto, andiamo su un po 'di terminologia. Per iniziare, la ragione per cui si parla di un albero binario, in particolare, è che ha due puntatori figlio. Ci sono altri tipi di alberi che hanno più puntatori bambino. In particolare, hai fatto un 'try' nel set Problema 5. Si noterà che in quella prova, voi aveva 27 diversi puntatori ai bambini diverse - uno per ciascuna delle 26 lettere dell'alfabeto inglese, e poi il 27 per l'apostrofo - così, che è simile a un tipo di albero. Ma qui, dal momento che è binaria, abbiamo solo due puntatori figlio. 

Oltre a questo nodo principale di cui abbiamo parlato, abbiamo anche buttato intorno a questo termine 'bambino.' Che cosa significa per un nodo di essere figlio di un altro nodo? Letteralmente significa che un nodo figlio è un figlio di un altro nodo se tale nodo ha uno dei suoi figli puntatori impostata per puntare a quel nodo. Per mettere questo in termini più concreti, se 3 è puntato da uno dei puntatori figlio di 7, quindi 3 è un bambino di 7. Se dovessimo capire che cosa i figli di 7 sono - bene, vediamo che 7 ha un puntatore a 3 e un puntatore a 9, così 9 e 3 sono i figli di 7. Nove non ha figli perché i suoi figli puntatori sono nulli, e 3 ha un solo figlio, 6. Sei inoltre non ha figli perché entrambi i suoi puntatori sono nulli, che tireremo in questo momento. 

Inoltre, parliamo anche i genitori di un nodo particolare, e questo è, come ci si aspetterebbe, il contrario di questa descrizione bambino. Ogni nodo ha un solo genitore - invece di due, come ci si potrebbe aspettare con gli esseri umani. Per esempio, il genitore di 3 è 7. Il padre di 9 è anche 7, e la madre di 6 è 3. Non c'è molto da esso. Abbiamo anche termini per parlare di nonni e nipoti, e più in generale si parla di antenati e discendenti di un nodo particolare. L'antenato di un nodo - o antenati, piuttosto, di un nodo - sono tutti i nodi che si trovano sul percorso dalla radice a quel nodo. Per esempio, se sto guardando il nodo 6, poi gli antenati stanno per essere sia 3 e 7. Gli antenati di 9, per esempio, sono - se sto guardando il nodo 9 - poi l'antenato del 9 è solo 7. E discendenti sono esattamente il contrario. Se voglio vedere tutti i discendenti del 7, allora devo guardare tutti i nodi sotto di esso. Così, ho 3, 9, e 6 tutti come discendenti di 7. 

Il termine finale che parleremo di questo concetto di essere un fratello. Siblings - tipo di seguito lungo in questi termini famiglie - sono nodi che sono allo stesso livello nell'albero. Quindi, 3 e 9 sono fratelli perché sono allo stesso livello nell'albero. Entrambi hanno lo stesso padre, 7. Il 6 non ha fratelli, perché 9 non ha figli. E 7 non ha fratelli o sorelle, perché è la radice del nostro albero, e c'è sempre e solo 1 root. Per 7 di avere fratelli ci dovrebbe essere un nodo superiore a 7. Ci dovrebbe essere un genitore di 7, nel qual caso 7 non sarebbe più la radice dell'albero. Poi quel nuovo genitore del 7 dovrebbe anche avere un figlio, e quel bambino sarebbe poi il fratello di 7. 

Va bene. Passando. Quando abbiamo iniziato la nostra discussione di alberi binari, abbiamo parlato di come avremmo usarli per ottenere un vantaggio su entrambi gli array e liste concatenate. E il modo in cui abbiamo intenzione di farlo è con questa proprietà di ordinazione. Diciamo che un albero binario è ordinato, secondo la specifica, se per ogni nodo nell'albero, tutti i suoi discendenti a sinistra - il figlio sinistro e tutti i discendenti del bambino di sinistra - hanno meno valori, e tutti i nodi a destra - il bambino a destra e tutti i discendenti del bambino di destra - avere nodi superiori al valore del nodo corrente che stiamo guardando. Solo per semplicità, abbiamo intenzione di assumere che non ci sono i nodi duplicati nel nostro albero. Ad esempio, in questo albero non stiamo andando a trattare il caso dove abbiamo il valore 7 alla radice  e poi abbiamo anche il valore 7 altrove nella struttura ad albero. In questo caso, si noterà che questo albero è davvero ordinata. Abbiamo il valore 7 alla radice. Tutto a sinistra di 7 - se io sciolgo tutti questi piccoli segni qui - tutto a sinistra di 7 - il 3 e il 6 - questi valori sono entrambi meno di 7, e tutto a destra - che è proprio questo 9 - è maggiore di 7. 

Questo non è l'unico albero ordinato contenente questi valori, ma cerchiamo di disegnare un paio di più di loro. Vi è in realtà un sacco di modi in cui possiamo fare questo. Ho intenzione di utilizzare una scorciatoia solo per mantenere le cose semplici in cui - anziché disegnare l'intera scatole-e-frecce - Sto solo andando a disegnare i numeri e aggiungere frecce che li collegano. Per iniziare, ci limiteremo a scrivere il nostro albero originale di nuovo dove abbiamo avuto 7, e poi un 3, e poi 3 indicò a destra per il 6, e 7 aveva un figlio destro che era 9. Va bene. Che è un altro modo in cui si potrebbe scrivere questo albero? Invece di avere 3 Sii il figlio sinistro di 7, si potrebbe anche avere il 6 essere il figlio sinistro di 7, 3 e quindi essere il figlio sinistro del 6. Questo sarebbe simile a questo albero proprio qui dove ho 7, poi 6, poi 3, e 9 sulla destra. Inoltre, non c'è bisogno di avere 7 come il nostro nodo principale. Potremmo anche avere 6 come il nostro nodo principale. Cosa che sembrano? Se abbiamo intenzione di mantenere questa struttura ordinata, tutto a sinistra del 6 deve essere inferiore a esso. C'è solo una possibilità, e questo è 3. Ma poi come il figlio destro di 6, abbiamo due possibilità. In primo luogo, si potrebbe avere il 7 e poi il 9, o potremmo trarre - come se fossi sul punto di fare qui - dove abbiamo la 9 come figlio destro del 6, e poi il 7 come figlio sinistro del 9. 

Ora, 7 e 6 non sono gli unici valori possibili per la radice. Possiamo anche avere tre essere alla radice. Cosa succede se 3 è alla radice? Qui, le cose si fanno un po 'interessante. Tre non ha valori che sono meno di esso, in modo che l'intero lato sinistro della struttura è solo andare a essere nullo. Non ci sarà nulla. A destra, potremmo elencare le cose in ordine crescente. Potremmo avere 3, poi 6, poi 7, poi 9. Oppure, potremmo fare 3, poi 6, poi 9, poi 7. Oppure, potremmo fare 3, poi 7, poi 6, poi 9. In alternativa, 3, 7 - in realtà no, non si può fare un 7 più. Questa è la nostra unica cosa lì. Possiamo fare 9 e quindi dal 9 possiamo fare 6 e poi 7. In alternativa, si può fare 3, poi 9, poi 7, e poi 6. 

Una cosa da attirare la vostra attenzione qui è che questi alberi sono un po 'strano aspetto. In particolare, se guardiamo i 4 alberi sul lato destro - Li cerchio, qui - questi alberi sembrano quasi esattamente come una lista concatenata. Ogni nodo ha un solo figlio, e quindi non abbiamo nulla di tutto questo albero come la struttura che si vede, per esempio,  in questo albero solitario uno qui in basso a sinistra. Questi alberi sono in realtà chiamati degeneri alberi binari, e parleremo di questi più in futuro - soprattutto se si va a prendere altri corsi di informatica. Questi alberi sono degeneri. Non sono molto utili perché, in effetti, questa struttura si presta  di ricercare i tempi simili a quello di una lista collegata. Noi non riusciamo a sfruttare la memoria aggiuntiva - questo puntatore extra - a causa della nostra struttura di essere male in questo modo. Piuttosto che andare avanti e tirare fuori gli alberi binari che hanno 9 alla radice, che è il caso finale che avremmo, siamo invece, a questo punto, di andare a parlare un po 'su questo altro termine che usiamo quando parliamo di alberi, che si chiama l'altezza. 

L'altezza di un albero è la distanza dalla radice al nodo più lontano, o meglio il numero di salti che si dovrebbe fare in modo da inizia dalla radice e poi finire al più lontano nodo nell'albero. Se guardiamo ad alcuni di questi alberi che abbiamo disegnato proprio qui, possiamo vedere che se prendiamo questo albero in alto a sinistra e iniziamo a 3, allora dobbiamo fare 1 salto per arrivare al 6, un secondo nodo per arrivare al 7, e un terzo hop per arrivare al 9. Quindi, l'altezza di questo albero è 3. Possiamo fare lo stesso esercizio per gli altri alberi descritti con questo verde, e vediamo che l'altezza di tutti questi alberi è effettivamente 3. Questo è parte di ciò che li rende degenere - che la loro altezza è solo uno meno del numero di nodi in tutto l'albero. Se osserviamo questo altro albero che è circondata di rosso, invece, vediamo che i più distanti nodi foglia sono il 6 e il 9 - le foglie essendo quei nodi che non hanno figli. Quindi, al fine di ottenere dal nodo radice né al 6 o al 9, dobbiamo fare un salto per arrivare al 7 e poi un secondo hop per arrivare al 9, e allo stesso modo, solo un secondo hop dal 7 per arrivare al 6. Quindi, l'altezza di questo albero qui è solo 2. Si può tornare indietro e farlo per tutti gli altri alberi che abbiamo discusso in precedenza cominciando con il 7 e il 6, e troverete che l'altezza di tutti questi alberi è anche 2. 

Il motivo per cui abbiamo parlato ordinata alberi binari e perché sono cool è perché è possibile cercare attraverso di loro in un modo molto simile alla ricerca in un array ordinato. Questo è dove si parla di ottenere che il tempo migliore ricerca il semplice elenco collegato. Con una lista concatenata - se si vuole trovare un particolare elemento - sei nella migliore delle ipotesi di andare a fare una sorta di ricerca lineare dove si inizia all'inizio di un elenco e hop one-by-one - un nodo da un nodo - attraverso l'intero elenco fino a trovare quello che stai cercando. Considerando che, se si dispone di un albero binario che è memorizzato in questo formato bello, si può effettivamente ottenere più di una ricerca binaria in corso dove si divide et impera e di ricerca attraverso la metà appropriata della struttura ad ogni passo. Vediamo come funziona. 

Se abbiamo - di nuovo, tornando al nostro albero originale - si inizia alle 7, abbiamo 3 a sinistra, a destra 9, e sotto il 3 abbiamo la 6. Se vogliamo cercare il numero 6 in questo albero, ci piacerebbe iniziare alla radice. Vorremmo confrontare il valore che stiamo cercando, per esempio 6, al valore memorizzato nel nodo che stiamo attualmente esaminando, 7, trova che 6 è effettivamente inferiore a 7, quindi ci sposta verso sinistra. Se il valore di 6 era maggiore di 7, avremmo invece spostato verso destra. Poiché sappiamo che - a causa della struttura del nostro albero binario ordinato - tutti i valori inferiori a 7 saranno immagazzinati a sinistra 7, non c'è bisogno di preoccuparsi, anche guardando attraverso il lato destro dell'albero. Una volta che ci si sposta verso sinistra e siamo ora al nodo che contiene 3, possiamo farlo di nuovo lo stesso confronto in cui si confronta il 3 e il 6. E troviamo che mentre il 6 - il valore che stiamo cercando - è maggiore di 3, possiamo andare al lato destro del nodo contenente 3. Non c'è sinistra qui, così avremmo potuto ignorare questo. Ma si sa solo che, perché stiamo guardando lo stesso albero, e possiamo vedere che l'albero non ha figli. 

E 'anche abbastanza facile da consultare 6 in questo albero, se lo stiamo facendo noi stessi come esseri umani, ma cerchiamo di seguire questo processo meccanico come un computer farebbe per capire veramente l'algoritmo. A questo punto, stiamo ora cercando un nodo che contiene 6, e stiamo cercando il valore 6, così, infatti, abbiamo trovato il nodo appropriato. Abbiamo trovato il valore 6 nel nostro albero, e siamo in grado di fermare la nostra ricerca. A questo punto, a seconda di quello che sta succedendo, si può dire, sì, abbiamo trovato il valore 6, che esiste nel nostro albero. Oppure, se stiamo pensando di inserire un nodo o fare qualcosa, possiamo farlo a questo punto. 

Facciamo un altro paio di ricerche solo per vedere come funziona. Diamo un'occhiata a cosa succede se dovessimo provare a cercare il valore 10. Se dovessimo cercare il valore 10, avremmo iniziato alla radice. Ci piacerebbe vedere che 10 è maggiore di 7, quindi ci si sposta verso destra. Ci piacerebbe arrivare al 9 e confrontare 9 al 10 e vedere che 9 è meno del 10. Quindi, di nuovo, ci piacerebbe provare a spostare a destra. Ma a questo punto, avevamo notato che siamo in un nodo nullo. Non c'e 'niente. Non c'è niente di cui il 10 dovrebbe essere. Questo è dove si segnala il fallimento - che non vi è infatti no 10 nella struttura. E, infine, andiamo attraverso il caso in cui stiamo cercando di guardare up 1 nella struttura. Questo è simile a quello che succede se guardiamo il 10, solo che invece di andare a destra, stiamo per andare a sinistra. Si comincia al 7 e vedere che 1 è inferiore a 7, in modo da spostare a sinistra. Arriviamo al 3 e vedere che 1 è inferiore a 3, quindi ancora una volta si tenta di spostare a sinistra. A questo punto abbiamo un nodo nullo, per cui ancora una volta siamo in grado di segnalare il guasto. 

Se si desidera saperne di più su alberi binari, ci sono un sacco di divertimento piccoli problemi che si possono fare con loro. Vi suggerisco di praticare il disegno di questi diagrammi one-by-one e in seguito attraverso tutte le diverse fasi, perché questo verrà in super-pratico non solo quando si sta facendo la codifica del set di Huffman problema ma anche in corsi successivi - solo imparando a tirare fuori queste strutture dati e pensare attraverso i problemi con carta e penna o, in questo caso, iPad e stilo. 

A questo punto, però, abbiamo intenzione di passare a fare un pò di pratica di codifica e proprio di giocare con questi alberi binari e vedere. Ho intenzione di tornare al mio computer. Per questa parte della sezione, invece di utilizzare Run CS50 o CS50 spazi, Ho intenzione di utilizzare l'apparecchio. 

Proseguendo lungo con la specifica Set problema, Vedo che dovrei aprire l'apparecchio, vai alla mia cartella Dropbox, creare una cartella denominata Sezione 7, e quindi creare un file chiamato binary_tree.c. Ci siamo. Ho l'apparecchio già aperto. Vado tirare su un terminale. Ho intenzione di passare alla cartella Dropbox, una directory chiamata sezione 7, e vedere che è completamente vuoto. Ora ho intenzione di aprire binary_tree.c. Va bene. Ci siamo - file vuoto. 

Torniamo alla specifica. La specifica chiede di creare una nuova definizione di tipo per un nodo di albero binario che contiene i valori int - proprio come i valori che ci ha richiamato nella nostra diagrammi prima. Stiamo andando a utilizzare questo boilerplate typedef che abbiamo fatto proprio qui che si dovrebbe riconoscere dal Set Problema 5 - se avete fatto la strada tabella hash di conquistare il programma speller. Si dovrebbe anche riconoscerlo da parte della scorsa settimana in cui abbiamo parlato di liste concatenate. Abbiamo ottenuto questo typedef di un nodo struct, e abbiamo dato questo nodo struct il nome del nodo struct in anticipo in modo da poter poi fare riferimento ad esso dal momento che vorrà avere puntatori struct nodo come parte della nostra struttura, ma abbiamo poi circondato questo - o meglio, racchiuso questo - in un typedef in modo che, più avanti nel codice, si può fare riferimento a questa struttura solo come un nodo al posto di un nodo struct. 

Questo sarà molto simile al singolarmente-linked definizione di elenco che abbiamo visto la scorsa settimana. Per fare questo, facciamo solo iniziare a scrivere il boilerplate. Sappiamo che dobbiamo avere un valore intero, quindi dovremo mettere in valore int, e quindi invece di avere solo un puntatore all'elemento successivo - come abbiamo fatto con singolarmente legati liste - stiamo andando ad avere puntatori figlio sinistro e destro. E 'abbastanza semplice, troppo - struct nodo figlio * sinistra; e struct nodo * diritto minorile;. Cool. Che sembra un buon inizio. Torniamo alla specifica. 

Ora abbiamo bisogno di dichiarare una variabile globale * nodo per la radice di un albero. Stiamo andando a fare questo mondiale, proprio come abbiamo fatto nel nostro primo puntatore lista collegata anche globale. Questo è stato in modo che le funzioni che scrivono non c'è bisogno di continuare passa intorno questa radice - anche se vedremo che se si vuole scrivere queste funzioni in modo ricorsivo, potrebbe essere meglio nemmeno passarlo in giro come un mondiale, in primo luogo e invece l'inizializzazione locale nella funzione principale. Ma, lo faremo a livello globale per iniziare. Anche in questo caso, daremo un paio di spazi, e ho intenzione di dichiarare una radice nodo *. Giusto per fare in modo che non mi lasciare questo non inizializzato, ho intenzione di impostarlo uguale a null. Ora, la funzione principale - di cui parleremo scrivere molto velocemente proprio qui - int main (int argc, char * argv []) - e ho intenzione di iniziare a dichiarare il mio array argv come const solo in modo che io so che tali argomenti sono argomenti che probabilmente non si desidera modificare. Se voglio modificarli forse dovrei essere l'esecuzione di copie di essi. Vedrete questo molto in codice. Va bene in entrambi i modi. Va bene lasciare come - omettere il const se lo desideri. Io di solito messo in proprio in modo che ricordo a me stesso  che probabilmente non si desidera modificare tali argomenti. 

Come sempre, ho intenzione di includere questo 0 tubazione di ritorno alla fine del principale. Ecco, io inizializzare il mio nodo principale. Così com'è adesso, ho un puntatore che è impostato su null, quindi è che punta a nulla. Al fine di iniziare a realizzare il nodo, Ho bisogno di allocare memoria per esso. Ho intenzione di farlo facendo memoria heap usando malloc. Ho intenzione di impostare radice uguale al risultato di malloc, e ho intenzione di usare l'operatore sizeof per calcolare la dimensione di un nodo. La ragione per cui io uso il nodo sizeof a differenza, per esempio, facendo qualcosa di simile - malloc (4 + 4 +4) o malloc 12 - è perché io voglio che il mio codice sia il più compatibile possibile. Voglio essere in grado di prendere questo file. C, compilarlo sull'apparecchio, e quindi compilarlo sul mio a 64-bit per Mac - o su un'architettura completamente diversa - e voglio che questo tutti funzionano allo stesso modo. 

Se sto facendo ipotesi circa le dimensioni di variabili - la dimensione di un int o la dimensione di un puntatore - poi mi sono anche fare ipotesi sul tipo di architetture su cui il mio codice può compilare correttamente quando viene eseguito. Usare sempre sizeof in contrasto manualmente sommando i campi struct. L'altra ragione è che ci potrebbe anche essere imbottitura che il compilatore inserisce nella struttura. Anche solo sommando i singoli campi non è una cosa che in genere si desidera fare, , cancellare quella linea. Ora, per inizializzare davvero questo nodo radice, Sto andando a inserire i valori per ciascuno dei suoi diversi settori. Ad esempio, per il valore so che voglio inizializzare a 7, e per ora ho intenzione di impostare il figlio sinistro di essere nullo e il bambino il diritto di essere anche nullo. Fantastico! Abbiamo fatto parte della specifica. 

La specifica verso il basso nella parte inferiore della pagina 3 mi chiede per creare più tre nodi - uno contenente 3, uno contenente 6, e uno con 9 - e poi cablare in modo che appaia esattamente come il nostro diagramma ad albero che parlavamo in precedenza. Facciamo che piuttosto velocemente qui. Vedrete molto in fretta che ho intenzione di iniziare a scrivere un mucchio di codice duplicato. Ho intenzione di creare un * nodo e ho intenzione di chiamare tre. Ho intenzione di impostarlo uguale a malloc (sizeof (nodo)). Ho intenzione di impostare tre-> valore = 3. Tre -> left_child = NULL; tre -> destra _child = NULL; pure. Che sembra piuttosto simile a inizializzare la radice, e questo è esattamente ciò che Ho intenzione di fare se mi metto l'inizializzazione 6 e 9 come bene. Lo farò molto velocemente qui - in realtà, ho intenzione di fare un po 'di copia e incolla, e fare in modo che io - va bene.  Ora, ho copiato e posso andare avanti e impostare questo uguale a 6. Si può vedere che questo richiede un po 'e non è super-efficiente. In appena un po ', ci scrivere una funzione che lo farà per noi. Voglio sostituire questo con un 9, sostituire che con un 6. 

Ora abbiamo tutti i nostri nodi creato e inizializzato. Abbiamo impostato la nostra radice uguale a 7, o contenenti il ​​valore 7, il nostro nodo contenente 3, il nostro nodo contenente 6, e il nostro nodo contenente 9. A questo punto, tutto quello che dobbiamo fare è tutto filo fino. Il motivo per cui ho inizializzato tutti i puntatori a null è proprio così che io faccio in modo che Non ho tutti i puntatori non inizializzati in là per caso. E anche perché, a questo punto, devo solo connettere effettivamente i nodi tra di loro - a quelli che sono in realtà collegati - che non c'è bisogno di passare attraverso e fare Assicurarsi che tutti i valori null sono lì nei luoghi appropriati. 

A partire dalla radice, so che figlio sinistro della radice è 3. So che figlio destro della radice è 9. Dopo di che, l'unico altro bambino che ho lasciato di cui preoccuparsi è il figlio destro 3, che è 6. A questo punto, tutto sembra abbastanza buono. Ci eliminare alcune di queste linee. Ora tutto sembra piuttosto buono. Torniamo alle nostre specifiche e vedere quello che dobbiamo fare. 

A questo punto, dobbiamo scrivere una funzione chiamata 'contiene' con un prototipo di 'contiene bool (int valore). E questo contiene la funzione sta per restituire true  se l'albero a cui punta la variabile root globale  contiene il valore passato alla funzione e false in caso contrario. Andiamo avanti e farlo. Questo sta per essere esattamente come la ricerca che abbiamo fatto a mano su iPad solo un po 'di tempo fa. Facciamo ingrandire di nuovo un po 'e scorrere verso l'alto. Stiamo per mettere questa funzione proprio sopra la nostra funzione principale in modo da non dover fare alcun tipo di prototipazione. Quindi, bool (int valore). Ecco fatto. C'è la nostra dichiarazione boilerplate. Giusto per fare in modo che questo compilerà, Ho intenzione di andare avanti e basta porla uguale a restituire false. Al momento questa funzione è sufficiente non fare nulla e sempre riportano che il valore che stiamo cercando non è nella struttura. 

A questo punto, è probabilmente una buona idea - da quando abbiamo scritto un sacco di codice e non abbiamo nemmeno provato provarla ancora - per assicurarsi che raccoglie tutte. Ci sono un paio di cose che dobbiamo fare per fare in modo che questo sarà effettivamente compilato. In primo luogo, verificare se abbiamo usato le funzioni in tutte le librerie che non abbiamo ancora inclusi. Le funzioni che abbiamo usato finora sono malloc, e poi abbiamo anche usato questo tipo - questo tipo non standard chiamato 'bool' - che è incluso nel file di intestazione standard bool. Abbiamo sicuramente desidera includere bool.h standard per il tipo bool, e vogliamo anche includere # lib.h standard per le librerie standard che includono malloc, e libero, e tutto il resto. Quindi, eseguire lo zoom indietro, stiamo andando a smettere. Cerchiamo di fare in modo che questa realtà ha fatto di compilazione. Si vede che lo fa, quindi siamo sulla strada giusta. 

Apriamo il binary_tree.c nuovo. Si compila. Andiamo verso il basso e fare in modo di inserire alcune chiamate alla nostra funzione contiene - solo per assicurarsi che questo è cosa buona e giusta. Per esempio, quando abbiamo fatto alcune ricerche nel nostro albero in precedenza, abbiamo provato a cercare i valori 6, 10, e 1, e sapevamo che 6 era nella struttura, 10 non era nella struttura, e 1 non era nella struttura sia. Usiamo queste chiamate di esempio come un modo per capire se la nostra funzione contiene funziona. Per fare questo, ho intenzione di utilizzare la funzione printf, e stiamo andando a stampare il risultato della chiamata a contiene. Ho intenzione di mettere in una stringa "contiene (% d) = perché  stiamo andando a inserire il valore che stiamo andando a cercare, e =% s \ n "e l'uso che la nostra stringa di formato. Stiamo solo andando a vedere - letteralmente stampare sullo schermo - quella che appare come una chiamata di funzione. Questo non è in realtà la chiamata di funzione.  Questa è solo una stringa progettato per apparire come una chiamata di funzione. 

Ora, andiamo a collegare i valori. Stiamo andando a cercare contiene il 6, e poi quello che andremo a fare è utilizzare tale operatore ternario. Vediamo un po '- contiene 6 - così, ora ho conteneva 6 e se contiene 6 è vero, la stringa che stiamo per inviare al carattere di formato% s sarà la stringa "true". Facciamo scorrere sopra un po '. In caso contrario, si desidera inviare la stringa "false" se contiene 6 restituisce false. Questo è un po 'goffo di aspetto, ma ho capito che potrebbe anche illustrare ciò che l'operatore ternario sembra che dal momento che non l'ho visto per un po '. Questo sarà un modo semplice e comodo per capire se la nostra funzione contiene funziona. Io vado a scorrere indietro verso sinistra, e ho intenzione di copiare e incollare questa linea un paio di volte. Ha cambiato alcuni di questi valori in giro, quindi questo sarà 1, e questo sta per essere 10. 

A questo punto abbiamo una funzione di Nizza contiene. Abbiamo alcuni test, e vedremo se tutto questo funziona. A questo punto abbiamo scritto il codice un po 'di più. È ora di uscire fuori e fare in modo che tutto ciò che compila ancora. Esci fuori, e ora proviamo a fare albero binario di nuovo. Beh, sembra che abbiamo un errore, e abbiamo ottenuto questo dichiarare in modo esplicito la funzione di libreria printf. Sembra che abbiamo bisogno di andare in e # include standardio.h. E con questo, tutto dovrebbe compilare. Siamo tutti buoni. Ora proviamo in esecuzione albero binario e vedere cosa succede. Eccoci qui,. / Binary_tree, e vediamo che, come ci aspettavamo - perché non abbiamo ancora implementato contiene, o meglio, abbiamo appena messo in return false - si vede che è solo restituire false per tutti loro, così che è tutto funziona per la maggior parte abbastanza bene. 

Torniamo indietro e di attuare effettivamente contiene, a questo punto. Io vado a scorrere verso il basso, lo zoom, e - ricordate, l'algoritmo che abbiamo usato è che abbiamo iniziato in corrispondenza del nodo radice e poi ad ogni nodo che incontriamo, facciamo un confronto, e sulla base di tale confronto ci sia passare al figlio sinistro o per il figlio destro. Questo sta a guardare molto simile al codice binario di ricerca che abbiamo scritto in precedenza nel periodo. Quando iniziare, sappiamo che vogliamo mantenere il nodo corrente che stiamo guardando, e il nodo corrente sta per essere inizializzato al nodo radice. E ora, andiamo ad andare avanti attraverso l'albero, e ricordare che la nostra condizione di arresto -  quando abbiamo effettivamente lavorato con l'esempio a mano - è stato quando abbiamo incontrato un nodo nullo, non quando abbiamo guardato un bambino nullo, ma quando abbiamo effettivamente trasferiti in un nodo dell'albero e ha scoperto che siamo in un nodo nullo. Stiamo andando a scorrere fino a cur non è uguale a null. E che cosa abbiamo intenzione di fare? Stiamo andando a verificare se (corr -> Valore ==), allora sappiamo che abbiamo effettivamente trovato il nodo che stiamo cercando. Così qui, siamo in grado di restituire true. Altrimenti, vogliamo vedere se il valore è inferiore al valore. Se il valore del nodo corrente è inferiore al valore che stiamo cercando, stiamo andando a spostarsi verso destra. Quindi, cur cur = -> right_child, e in caso contrario, abbiamo intenzione di spostarsi a sinistra. cur = cur -> left_child;. Abbastanza semplice. 

Probabilmente riconoscere il ciclo che sembra molto simile a questo da ricerca binaria in precedenza nel termine, salvo poi abbiamo a che fare con basse, medie e alte. Qui, non ci resta che guardare un valore corrente, quindi è bello e semplice. Facciamo in modo che questo codice funziona. Per prima cosa, assicurarsi che compila. Sembra che lo fa. Proviamo eseguirlo. E in effetti, esso stampa tutto quello che ci aspettavamo. Essa trova 6 nella struttura, non trova 10 perché 10 non è nella struttura, e non riesce a trovare uno o perché uno non è anche nella struttura. Cool stuff. 

Va bene. Torniamo alle nostre specifiche e vedere cosa c'è dopo. Ora, vuole aggiungere un po 'di nodi in più per il nostro albero. Vuole aggiungere 5, 2, e 8, e fare in modo che il nostro contiene il codice funziona ancora come previsto. Andiamo a farlo. A questo punto, piuttosto che fare quella copia fastidioso e incolla di nuovo, cerchiamo di scrivere una funzione per creare effettivamente un nodo. Se scorrere verso il basso fino alla principale, si vede che abbiamo fatto questo codice molto simile più e più volte ogni volta che vogliamo creare un nodo. 

Facciamo scrivere una funzione che effettivamente creare un nodo per noi e restituirlo. Io vado a chiamare build_node. Ho intenzione di costruire un nodo con un valore particolare. Zoom qui. La prima cosa che ho intenzione di fare è in realtà creare spazio per il nodo sul mucchio. Quindi, il nodo * n = malloc (sizeof (nodo)); n -> Valore = valore; e poi qui, sto solo andando per inizializzare tutti i campi da valori appropriati. E alla fine, torneremo il nostro nodo. Va bene. Una cosa da notare è che questa funzione proprio qui sta per tornare un puntatore alla memoria che è stato heap allocata. Il bello di questo è che ora questo nodo - dobbiamo dichiarare sul mucchio perché se ha dichiarato in pila non sarebbe in grado di farlo in questa funzione come questa. Quel ricordo usciva di portata e sarebbe valida se abbiamo tentato di accedere in seguito. Dal momento che stiamo dichiarando heap allocata la memoria, stiamo andando a prendersi cura di liberare in un secondo momento per il nostro programma di non perdere la memoria. Abbiamo andare in barca sul che per tutto il resto del codice solo per semplicità, al momento, ma se mai scrivere una funzione che assomiglia a questo dove hai - alcuni lo chiamano una malloc o realloc all'interno - si vuole fare in modo che si mette una sorta di commento qui che dice, hey, sai, restituisce un heap-allocato nodo inizializzato con il valore passato. E poi si vuole fare in modo che si inserisce in una sorta di nota che dice: il chiamante deve liberare la memoria restituita. In questo modo, se qualcuno va mai e utilizza tale funzione, sanno che tutto ciò che tornare da quella funzione ad un certo punto dovrà essere liberato. 

Partendo dal presupposto che tutto va bene e bene qui, si può scendere nel nostro codice e sostituire tutte queste linee qui alle chiamate verso la nostra funzione di nodo di compilazione. Facciamo davvero in fretta. L'unica parte che non stiamo andando a sostituire questa parte qui nella parte inferiore dove abbiamo effettivamente cablaggio degli nodi per puntare a vicenda, perché non possiamo fare nella nostra funzione. Ma, facciamo root = build_node (7); nodo * tre = build_node (3); nodo * = build_node sei (6); nodo * = build_node nove (9). E ora, abbiamo anche voluto aggiungere nodi per - nodo * = build_node cinque (5); nodo * = build_node otto (8); e quello che era l'altro nodo? Vediamo qui. Abbiamo voluto aggiungere anche un 2 - nodo * due = build_node (2),. Va bene. A questo punto, sappiamo che abbiamo il 7, il 3, il 9 e il 6 tutti collegati in modo appropriato, ma per quanto riguarda il 5, l'8 e il 2? Per tenere tutto nel corretto ordine, sappiamo che tre figlio destro è pari a 6. Quindi, se abbiamo intenzione di aggiungere il 5, il 5 appartiene anche nel lato destro dell'albero di cui 3 è la radice, quindi 5 appartiene come il figlio sinistro di 6. Possiamo farlo dicendo, sei -> left_child = cinque; e poi l'8 appartiene come il figlio sinistro di 9, in modo da nove -> left_child = otto; e poi 2 è il figlio sinistro di 3, in modo che possiamo farlo qui - te -> left_child = due;. Se non riusciva a seguire con questo, ti consiglio di disegnare voi stessi. 

Va bene. Salviamo questo. Usciamo e assicurarsi che compila, e poi possiamo aggiungere nelle nostre chiamate contiene. Sembra che tutto ciò che compila ancora. Entriamo e aggiungere in qualche contiene chiamate. Ancora una volta, ho intenzione di fare un po 'di copia e incolla. Ora la ricerca di 5, 8, e 2. Va bene. Facciamo in modo che tutto questo sembra buono ancora. Fantastico! Salvare e uscire. Ora facciamo, compilare, e ora corriamo. Dai risultati, sembra che tutto funziona solo bello e bene. Fantastico! Così ora abbiamo le nostre contiene una funzione scritta. Andiamo avanti e iniziare a lavorare su come inserire i nodi nella struttura in quanto, come lo stiamo facendo in questo momento, le cose non sono molto belle. 

Se torniamo alle specifiche, ci chiede di scrivere una funzione chiamata inserire - ancora una volta, la restituzione di un bool per se o non si potesse davvero inserire il nodo nella struttura - e quindi il valore da inserire l'albero viene specificato come l'unico argomento per la nostra funzione di inserimento. Torneremo vero se potremmo davvero inserire il valore del nodo che contiene nella struttura, il che significa che, uno, aveva memoria sufficiente, e poi due, quel nodo non è già presente nella struttura in quanto - ricordate, non stiamo andando ad avere valori duplicati nella struttura, giusto per rendere le cose semplici. Va bene. Eseguire il codice. Aprirlo. Zoom in un po ', quindi scorrere verso il basso. Mettiamo la funzione di inserimento a destra sopra le contains. Anche in questo caso, sta andando essere chiamato inserto bool (int valore). Dategli un po 'più di spazio, e poi, come impostazione predefinita, mettiamo in return false alla fine. Ora, giù in fondo, andiamo avanti e invece di costruzione manuale dei nodi in noi stessi e il cablaggio principale loro fino al punto l'un l'altro come stiamo facendo, faremo affidamento sulla nostra funzione di inserimento di farlo. Non si affidano alla nostra funzione di inserimento di costruire l'intero albero da zero appena ancora, ma ci sbarazzarsi di queste linee - we'll commentare queste righe - che costruire i nodi 5, 8, e 2. E invece, dovremo inserire le chiamate alla nostra funzione di insert fare in modo che che funziona realmente. Ci siamo. 

Ora abbiamo commentato queste righe. Abbiamo solo 7, 3, 9, e 6 nel nostro albero a questo punto. Per assicurarsi che tutto questo è lavoro, siamo in grado di eseguire lo zoom indietro, fare il nostro albero binario, eseguirlo, e possiamo vedere che contiene ora ci dice che siamo totalmente di destra - 5, 8, e 2 non sono più nella struttura. Torna nel codice, e come facciamo a inserire? Ricordate quello che abbiamo fatto quando eravamo in realtà l'inserimento di 5, 8, e 2 in precedenza. Abbiamo giocato quel gioco Plinko dove siamo partiti alla radice, è andato giù quello albero uno per uno finché non abbiamo trovato la distanza appropriata, e poi cablato nel nodo nel punto appropriato. Stiamo andando a fare la stessa cosa. Questo è fondamentalmente come scrivere il codice che abbiamo usato nella funzione contiene per trovare il punto in cui il nodo dovrebbe essere, e poi stiamo solo andando a inserire il nodo proprio lì. Cominciamo a farlo. 

Così abbiamo un nodo * cur = root, stiamo solo andando a seguire la contiene il codice fino a trovare che non va a buon fine per noi. Stiamo per passare attraverso l'albero, mentre l'elemento corrente non è null, e se troviamo valore corrente è uguale al valore che stiamo cercando di inserire - bene, questo è uno dei casi in cui non potrebbe effettivamente inserire il nodo nell'albero, perché questo significa che abbiamo un valore duplicato. Qui stiamo effettivamente andando a restituire false. Ora il resto, se il valore corrente è inferiore al valore, ora sappiamo che ci si sposta verso destra  perché il valore appartiene nella metà destra della struttura corrente. In caso contrario, andremo a spostarsi a sinistra. Questo è fondamentalmente nostri Funzione contains proprio lì. 

A questo punto, una volta che abbiamo completato questo ciclo while, il nostro puntatore corrente sta per puntare a null se la funzione non è già tornato. Stiamo quindi con corr nel punto in cui si vuole inserire il nuovo nodo. Che cosa resta da fare è quello di costruire in realtà il nuovo nodo, che si può fare abbastanza facilmente. Possiamo usare il nostro super-comoda la funzione del nodo di generazione, e qualcosa che non abbiamo fatto in precedenza - abbiamo solo tipo di dato per scontato, ma ora faremo solo per assicurarsi - ci prova per assicurarsi che il valore restituito da nuovo nodo era in realtà non nullo, perché non si vuole avviare l'accesso che la memoria se è null. Possiamo provare a fare in modo che il nuovo nodo non è uguale a null. O invece, possiamo solo vedere se è effettivamente nullo, e se è nullo, allora possiamo semplicemente restituire false presto. 

A questo punto, dobbiamo cablare nuovo nodo nella sua posizione appropriata nella struttura. Se guardiamo indietro a principale e dove eravamo in realtà cablaggio in valori prima, vediamo che il modo in cui lo stavamo facendo quando abbiamo voluto mettere 3 nella struttura ad albero è stato abbiamo accesso al figlio sinistro della radice. Quando abbiamo messo 9 nella struttura, abbiamo dovuto accedere al figlio destro della radice. Abbiamo dovuto avere un puntatore al genitore, al fine di mettere un nuovo valore nella struttura. Scorrendo il backup da inserire, che non sta andando a lavorare abbastanza qui perché non si dispone di un puntatore genitore. Quello che vogliamo essere in grado di fare è, a questo punto, controllare il valore del genitore e vedere - beh, cavolo, se il valore del genitore è inferiore al valore corrente, poi figlio destro del genitore dovrebbe essere il nuovo nodo; in caso contrario, figlio sinistro del genitore dovrebbe essere il nuovo nodo. Ma, non abbiamo questo puntatore genitore ancora abbastanza. 

Per farlo, in realtà stiamo andando ad avere per tenerne traccia come andiamo attraverso l'albero e trovare il punto appropriato nel nostro ciclo precedente. Possiamo farlo scorrendo indietro fino alla cima della nostra funzione di insert e il monitoraggio di un altro variabile puntatore chiamato il padre. Stiamo per impostarlo uguale a null inizialmente, e poi ogni volta che andiamo attraverso l'albero, stiamo andando a impostare il puntatore del genitore in base al corrente del puntatore. Imposta raccolta principale pari a cur. In questo modo, ogni volta che passare attraverso, stiamo andando a garantire che la corrente del puntatore viene incrementato il puntatore genitore segue - solo un livello superiore rispetto al puntatore corrente nella struttura. Che tutto sembra piuttosto buono. 

Penso che l'unica cosa che dobbiamo provare a modificare questa build è nullo nodo di ritorno. Al fine di ottenere costruire nodo realmente successo restituire null, dovremo modificare il codice, perché qui, non abbiamo mai provato a fare in modo che malloc ha restituito un puntatore valido. Quindi, se (n = NULL!), Poi - se malloc ha restituito un puntatore valido, poi ci inizializzarlo; in caso contrario, ci limiteremo a tornare e che finirà per tornare nulla per noi. Ora tutto sembra piuttosto buono. Facciamo in modo che questo compila in realtà. Fai albero binario, e oh, abbiamo un po 'di roba in corso qui. 

Abbiamo una dichiarazione implicita di funzione di costruzione del nodo. Anche in questo caso, con questi compilatori, stiamo per iniziare al top. Cosa che deve dire è che sto chiamando costruire nodo prima di aver effettivamente dichiarato. Torniamo al codice molto velocemente. Scorrere verso il basso, e abbastanza sicuro, la mia funzione di insert è dichiarata al di sopra della funzione del nodo di generazione, ma sto cercando di usare costruire nodo all'interno dell'inserto. Ho intenzione di andare a copia - e quindi incollare il modo in cui la funzione del nodo di generazione qui in alto. In questo modo, si spera che funzioni. Diamo questo un altro andare. Ora compila tutto. Tutto è buono. 

Ma a questo punto, non abbiamo effettivamente chiamato la nostra funzione di inserimento. Sappiamo solo che si compila, quindi cerchiamo di andare a mettere un po 'le chiamate trovi Facciamo che nella nostra funzione principale. Qui, ha commentato su 5, 8, e 2, e poi non li cablare qui. Facciamo alcune chiamate di inserire, e cerchiamo di utilizzare lo stesso tipo di cose che abbiamo usato quando abbiamo fatto queste chiamate printf per fare in modo che tutto ciò che si ha inserito correttamente. Ho intenzione di copiare e incollare, e invece di contiene andremo a fare inserire. E invece di 6, 10, e 1, che andremo a usare 5, 8, e 2. Questo dovrebbe auspicabilmente inserire 5, 8, e 2 nella struttura. Compilare. Tutto è buono. Ora ci troveremo a eseguire il nostro programma. 

Tutto ciò che ha restituito false. Quindi, 5, 8, e 2 non è andato, e sembra che contiene non li ha trovato né. Cosa sta succedendo? Andiamo diminuire. Il primo problema era che sembrava inserto per restituire false, e sembra che è perché abbiamo lasciato nella nostra chiamata return false, e non abbiamo mai restituito true. Siamo in grado di configurare il monitoraggio. Il secondo problema è, ora, anche se lo facciamo - salvare questo, uscire da questa, eseguire make, farlo compilare, quindi eseguirlo - vediamo che qualcosa è successo qui. Il 5, 8, e 2 non sono mai stati ancora trovati nella struttura. Allora, che cosa sta succedendo? 

Diamo uno sguardo a questo nel codice. Vediamo se siamo in grado di capirlo. Si comincia con il genitore non essere nulla. Abbiamo impostato il puntatore corrente pari al puntatore radice, e stiamo andando a lavorare il nostro percorso attraverso l'albero. Se il nodo corrente non è nullo, allora sappiamo che siamo in grado di spostare verso il basso un po '. Abbiamo impostato il nostro puntatore del genitore di essere uguale alla corrente del puntatore, controllato il valore - se i valori sono gli stessi che ha restituito false. Se i valori sono meno ci siamo spostati a destra; in caso contrario, ci siamo spostati a sinistra. Poi costruire un nodo. Io lo zoom un po '. E qui, stiamo andando a cercare di collegare i valori sia la stessa. Cosa sta succedendo? Vediamo se forse Valgrind ci può dare un suggerimento. 

Mi piace usare Valgrind Valgrind solo perché corre molto in fretta e ti dice se ci sono errori di memoria. Quando corriamo Valgrind sul codice, come si può vedere colpo here--Valgrind./binary_tree--and destra entrare. Si vede che non abbiamo avuto alcun errore di memoria, in modo che sembra che tutto va bene fino ad ora. Abbiamo alcuni problemi di memoria, che sappiamo, perché non siamo accadendo per liberare tutti i nostri nodi. Proviamo esecuzione GDB per vedere cosa sta realmente succedendo. Faremo gdb. / Binary_tree. E 'avviato bene. Mettiamo da un punto di interruzione su inserto. Corriamo. Sembra che non abbiamo mai chiamato inserto. Sembra che il problema era solo che quando ho cambiato qui in main - tutte queste chiamate da printf contiene - Non ho mai veramente cambiato questi chiamare inserto. Ora cerchiamo di fare un tentativo. Facciamo compilare. Tutto sembra buono lì. Ora provare a eseguirlo, vedere cosa succede. Va bene! Tutto sembra piuttosto buona. 

L'ultima cosa da pensare è, ci sono dei casi limite a questo foglietto? E si scopre che, beh, quello caso limite che è sempre interessante a cui pensare è, che cosa succede se il vostro albero è vuoto e si chiama questa funzione insert? Funzionerà? Bene, vediamo di fare un tentativo. - Binary_tree c. - Il modo in cui andremo a testare questa è, stiamo per andare in fondo alla nostra funzione principale, e piuttosto che il cablaggio questi nodi in questo modo, stiamo solo andando a commentare l'intera cosa, e invece di cablaggio dei nodi di noi stessi, possiamo in realtà solo andare avanti e cancellare tutto questo. Stiamo andando a fare tutto ciò che una chiamata a inserire. Quindi, cerchiamo di fare - invece di 5, 8, e 2, abbiamo intenzione di inserire 7, 3, e 9. E poi ci vogliono anche inserire 6 pure. Salva. Quit. Crea albero binario. Si compila tutti. Noi possiamo solo correre è come e vedere cosa succede, ma è anche sarà molto importante per fare in modo che Non ci sono errori di memoria, dal momento che questo è uno dei nostri casi limite che siamo a conoscenza. 

Facciamo in modo che funzioni bene sotto Valgrind, che faremo lanciando solamente Valgrind. / binary_tree. Sembra che in effetti hanno un errore da un contesto - abbiamo questa segmentation fault. Che cosa è successo? Valgrind realtà ci dice dove si trova. Zoom indietro un po '. Sembra che sta accadendo nella nostra funzione di inserimento, dove abbiamo una lettura valida di dimensione 4 a inserto, linea 60. Torniamo indietro e vedere cosa sta succedendo qui. Zoom indietro molto veloce. Voglio fare in modo che non va al bordo dello schermo, in modo che possiamo vedere tutto. Tirare che tra un po '. Va bene. Scorrere verso il basso, e il problema è proprio qui. Cosa succede se ci mettiamo e il nostro nodo corrente è già nullo, il nostro nodo padre è nullo, quindi se guardiamo in alto, proprio qui - se mai questo ciclo while viene eseguito in realtà perché il nostro valore corrente è nullo - la nostra radice è null in modo corrente è nullo - poi mai la nostra casa madre viene impostata al corrente o su un valore valido, così, genitore anche essere nullo. Abbiamo bisogno di ricordare per verificare che per il momento abbiamo venire qui, e iniziamo l'accesso valore del livello superiore. Allora, che cosa succede? Beh, se il genitore è nullo - if (NULL == genitore) - allora sappiamo che non ci deve essere nulla nella struttura. Dobbiamo cercare di inserirlo alla radice. Possiamo farlo semplicemente impostando la radice pari al nuovo nodo. Quindi a questo punto, in realtà non vogliono passare attraverso queste altre cose. Invece, proprio qui, si può fare sia un else-if-else, o potremmo combinare tutto qui in un altro, ma qui ci limiteremo a usare altro e farlo in quel modo. Ora, stiamo andando a test per assicurarsi che il nostro genitore non è nullo prima di allora in realtà cercando di accedere ai suoi campi. Questo ci aiuterà a evitare l'errore di segmentazione. Così, abbiamo smesso, zoom out, compilare, eseguire. 

Nessun errore, ma abbiamo ancora un sacco di perdite di memoria perché non liberare tutti i nostri nodi. Ma, se andiamo qui e guardiamo la nostra stampa, vediamo che, beh, sembra che tutti i nostri inserti stavano tornando vero, che è buono. Gli inserti sono tutte vere, e poi le chiamate alle contiene anche vero. 

Buon lavoro! Sembra che abbiamo scritto correttamente inserto. Questo è tutto quello che abbiamo per la specifica problema di questa settimana Set. Una sfida divertente a cui pensare è come si dovrebbe effettivamente andare in e libera tutti i nodi di questo albero. Possiamo farlo un certo numero di modi diversi, ma lascio a voi di sperimentare, e come una sfida divertente, cercare di fare in modo che si può fare in modo che tale relazione Valgrind non ha prodotto alcun errore e senza perdite. 

Buona fortuna per il problema di questa settimana insieme codifica di Huffman, e ci vediamo la prossima settimana! [CS50.TV]