[Powered by Google Translate] [Sección 7] [menos cómodo] [Nate Hardison] [Harvard University] [Esta é CS50.] [CS50.TV] 

Benvido á sección 7. Grazas ao furacán Sandy, en vez de ter unha sección normal esta semana estamos facendo este paso a paso, a través da sección de preguntas. Eu vou estar a seguir, xunto co conxunto de problemas 6 especificación, e pasando por todas as preguntas do A Sección de sección de Preguntas. Se hai algunha dúbida, por favor publicar estes en CS50 discutir. 

Todo ben. Imos comezar. Agora eu estou ollando para a páxina 3 da especificación conxunto de problemas. Nós imos primeiro comezar a falar sobre árbores binarias unha vez que estes teñen moita relevancia para o conxunto desta semana - problema a codificación árbore Huffman. Unha das estruturas de datos primeiras falamos sobre CS50 foi a matriz. Lembre que unha matriz é unha secuencia de elementos - todos do mesmo tipo, - almacenados xunto uns dos outros na memoria. Se eu tivera unha matriz de enteiros que eu poida deseñar usando este estilo de caixas números-enteiros - Imos dicir que eu teño 5 na primeira caixa, eu teño sete no segundo, entón teño 8, 10, e 20 na caixa final. Cousas Lembre, os dous realmente boas sobre esta matriz son de que temos ese acceso e de tempo constante para calquera elemento específico  na matriz, se sabemos seu índice. Por exemplo, se eu queira incorporarse o terceiro elemento na matriz - no índice 2, usando o noso sistema de indexación baseada en cero - Eu literalmente só tes que facer un simple cálculo matemático, hop para esa posición na matriz, puxe o 8 que está almacenado alí, e eu son bo para ir. 

Unha das cousas malas sobre esta matriz - que falou sobre cando discutimos listas ligadas - é que se eu queira inserir un elemento para esa matriz, Vou ter que facer algunha mudanza por aí. Por exemplo, a matriz iso aquí é na orde de clasificación - clasificados en orde crecente - 5, a continuación, 7, 8, a continuación, a continuación, 10, e despois 20 - pero se eu queira inserir o seu número 9 desta matriz, Vou ter que cambiar algúns dos elementos a fin de facer o espazo. Podemos chamar iso aquí. Vou ter que mover a 5, o 7 e, a continuación, a 8; crear un espazo onde podo poñer o 9, e, a continuación, a 10 ea 20 pode ir á dereita do 9. Este é un tipo de dor, porque no peor escenario - cando estamos tendo que introducir ou no inicio ou no final da matriz, dependendo de como estamos cambiando - podemos acabar tendo que cambiar todos os elementos que estamos actualmente a almacenar na matriz. 

Entón, o que era a maneira de evitar isto? O xeito de evitar isto era para ir ao noso método de lista encadeada, onde - en vez de almacenar os elementos 5, 7, 8, 10, e 20 todas próximas unhas das outras na memoria - o que, en vez fixo foi almacena-los tipo de onde nos queria para almacena-los nestes nós Linked-lista que eu estou deseñando aquí, tipo de ad hoc. E, entón, conectado-los en conxunto, utilizando estes punteiros próximos. I pode ter un punteiro a partir de 5 a 7, un punteiro a partir do 7 ao 8, un punteiro a partir do 8 ao 10, e, finalmente, un punteiro de 10 a 20, e, a continuación, un punteiro nulo no 20, indicando que non hai nada de esquerda. O trade-off que temos aquí é que agora se pretende introducir o número 9 na nosa lista ordenada, todo o que temos que facer é crear un novo nodo con 9, fío-lo para apuntar para o lugar apropiado, e, a continuación, re-conexión do 8 ao apuntar para abaixo para o 9. Isto é moi rápido, asumir que sabemos exactamente onde queremos inserir o 9. Pero o trade-off a cambio para iso é que temos agora perdeu o acceso de tempo constante para calquera elemento particular na nosa estrutura de datos. Por exemplo, se quero atopar o cuarto elemento nesta lista ligada, Vou ter que comezar ben no inicio da lista e traballar o meu camiño a través da conta no a nó ata atopar o cuarto. 

Co fin de obter un rendemento mellor acceso do que unha lista ligada - pero tamén manter algúns dos beneficios que tivemos en termos de tempo de inserción a partir dunha lista ligada - unha árbore binaria está indo a necesidade de usar a memoria un pouco máis. En particular, en vez de ter só un punteiro en un nó de árbore binaria - como a lista ligada nodo fai - imos engadir un segundo punteiro para o nó de árbore binaria. En vez de ter só un punteiro para o próximo elemento, imos ter un punteiro para un neno esquerdo e un dereito do neno. 

Imos tomar unha foto para ver o que realmente parece. Unha vez máis, eu vou usar esas caixas e frechas. Un nodo da árbore binaria vai comezar con só unha caixa simple. Vai ter un espazo para o valor, e despois tamén vai ter un espazo para o neno esquerda e dereita do neno. Eu estou indo a clasificalos los aquí. Nós imos ter o fillo esquerdo, e entón nós imos ter o fillo dereito. Hai moitas formas diferentes de facer iso. Ás veces para o espazo e conveniencia, Eu, en realidade, deseña-lo como eu estou facendo aquí abaixo onde eu vou ter o valor superior, e despois o fillo da dereita no ángulo inferior dereito, e neno á esquerda na parte inferior esquerda. Volvendo a este diagrama superior, temos o valor superior, entón temos o punteiro esquerdo neno, e despois temos o punteiro neno dereito. 

Na especificación conxunto de problemas, falamos de deseñar un nodo que ten un valor de 7, e un punteiro-esquerda neno que é nulo, e un punteiro dereito do neno, que é nulo. Nós pode escribir NULL capital no espazo de tanto o neno como a esquerda e dereita do neno, ou podemos chamar esta barra diagonal en cada unha das caixas, para indicar que é nula. Eu vou facer iso só porque é máis sinxelo. O que ve aquí son dúas formas de diagramação dun nodo árbore moi simple binario onde temos o valor 7 e punteiros neno nulos. 

A segunda parte fala sobre como os nosos especificación con listas ligadas - Lembre, temos só a soster o primeiro elemento dunha lista para lembrar a listaxe - e do mesmo xeito, con unha árbore binaria, só temos que soster un punteiro para a árbore , A fin de manter o control sobre a estrutura de datos enteira. Este elemento especial da árbore chámase nó raíz da árbore. Por exemplo, se ese nodo un - este nodo que contén o valor 7 con punteiros nulos lados esquerdo e dereito do neno - eran o único valor na nosa árbore, entón este sería o noso nodo raíz. É o inicio da nosa árbore. Podemos ver isto un pouco máis claramente, unha vez que comece a engadir máis nós a nosa árbore. Déixame sacar a unha nova páxina. 

Agora imos debuxar unha árbore que ten 7 na raíz, e 3 dentro do neno á esquerda, e 9 no interior do neno dereita. De novo, iso é moi sinxelo. Temos 7, debuxe un nó para o 3, un nó para 9, e eu estou indo a definir o punteiro esquerdo neno de 7 a apuntar para o nodo que contén 3, E o punteiro dereito do fillo do nodo que contén 7 para o nodo que contén 9. Agora, desde 3 e 9 non ten fillos, imos definir os seus punteiros fillo para ser nulo. Aquí, a raíz da nosa árbore corresponde ao nodo que contén o número 7. Podes ver que, se todo o que temos é un punteiro para o nodo raíz, entón podemos camiñar a través da nosa árbore e acceder nós tanto o neno - ambos os 3 e 9. Non hai necesidade de manter punteiro a cada nó na árbore. Todo ben. Agora imos engadir outro nodo a este diagrama. Estamos indo para engadir un nodo que contén 6, e nós estamos indo para engadir este como o fillo dereito do nodo contén 3. Para facer isto, eu vou borrar este punteiro nulo no 3-no e conecta-lo para apuntar para o nodo que contén 6. Todo ben. 

Neste punto, imos falar sobre un pouco de terminoloxía. Para comezar, a razón pola que iso é chamado dunha árbore binaria en particular é que ten dous punteiros de nenos. Existen outros tipos de árbores que teñen máis enlaces neno. En particular, fixo un 'try' no Conxunto Problema 5. Vostede vai entender que aquel intento, tivo 27 indicacións distintas para os diferentes nenos - un para cada unha das 26 letras do alfabeto inglés, e despois a 27 para o apóstrofo - así, que é semellante a un tipo de árbore. Pero aquí, xa que é binario, só temos dous punteiros do neno. 

Ademais deste nodo raíz que falamos, Nós tamén estamos xogando en torno a este termo "neno". O que significa para un nodo a un fillo de outro no? É, literalmente, significa que un nodo fillo é un fillo de outro no que outro nó ten unha das súas nenos punteiros definidas para apuntar a este nodo. Para poñer isto en termos máis concretos, 3 é apuntada por un dos punteiros neno de 7, a continuación, 3 é un neno de 7. Se tivésemos de descubrir o que os fillos de 7 son - ben, vemos que 7 ten un punteiro para 3 e un punteiro a 9, para 9 e 3 son os nenos de 7. Nove non ten fillos porque punteiros seus fillos son nulos, e 3 ten só un fillo, 6. Seis tampouco ten fillos, porque ambos os punteiros son nulos, o que nós imos chamar agora. 

Ademais, tamén falamos sobre os pais dun nodo, e este é, como sería de esperar, o reverso desta descrición neno. Cada nodo ten só un pai - en vez de dous, como podería esperar cos humanos. Por exemplo, a matriz de 3 a 7. O pai de 9 tamén é 7, o pai e de 6 a 3. Non hai moito a el. Tamén temos condicións de falar avós e netos, e, máis xeralmente falamos sobre os antepasados e descendentes dun nodo específico. O ancestral dun nodo - ou antepasados, si, un nó - son todos os nós que están no camiño da raíz para este nodo. Por exemplo, se eu estou ollando para o 6, a continuación, os antepasados ​​van ser o 3 eo 7. Os devanceiros de 9, por exemplo, son - se eu estou ollando para o nodo 9 - a continuación, o antepasado de 9 é só 7. E descendentes son exactamente o contrario. Se quero ollar para todos os descendentes de 7, entón eu teño que mirar para todos os nós, abaixo dela. Entón, eu teño 3, 9 e 6 todos como descendentes de 7. 

O prazo final que imos falar é esta noción de ser un irmán. Irmáns - tipo de seguir xunto con estes termos familiares - son nos que están ao mesmo nivel da árbore. Entón, 3 e 9 son irmáns porque son ao mesmo nivel na árbore. Ambos teñen o mesmo pai, 7. O 6 non ten irmáns, porque 9 non teñen fillos. E 7 non ten irmáns, porque é a raíz da nosa árbore, e sempre hai só unha raíz. Para 7 ter irmáns non tería que ser un nodo por riba de 7. Tería que ser un pai de 7, caso en que 7 xa non sería a raíz da árbore. Entón que o pai novo, de 7 tamén tería que ter un fillo, e que o neno sería, entón, o irmán de 7. 

Todo ben. Seguindo adiante. Cando comezamos a nosa discusión sobre árbores binarias, falamos de como nós iamos usalos para gañar unha vantaxe sobre os dous matrices e listas ligadas. E a forma como imos facelo é con esta propiedade pedido. Dicimos que unha árbore binaria é ordenada, de acordo coa especificación, se, para cada nodo na nosa árbore, todos os seus descendentes á esquerda - o neno esquerda e todos os descendentes do fillo esquerdo de - teñen valores menores, e todos os nós da dereita - o dereito do neno e todos os descendentes de dereito do neno a - ter nós máis que o valor do nodo actual que estamos mirando. Só para simplificar, imos asumir que non hai nos duplicados na nosa árbore. Por exemplo, nesta árbore que non estamos indo para xestionar o caso onde temos o valor 7 na raíz  e despois tamén temos o valor 7 noutras partes da árbore. Neste caso, vai entender que esta árbore é de feito ordenado. Temos o valor 7 na raíz. Todo para a esquerda, de 7 - se eu desfacer todas esas pequenas marcas aquí - todo á esquerda, de 7 - 3 ea 6 - eses valores están a menos de 7, e todo para a dereita - o que é exactamente iso 9 - é maior que 7. 

Esta non é a única árbore ordenados conteñen estes valores, pero imos deseñar un pouco máis deles. Hai realmente unha morea de formas que podemos facer iso. Vou usar un atallo só para manter as cousas simples, onde - en vez de deseñar a todo caixas-e-flechas - Eu só vou para deseñar os números e engadir frechas conectando-los. Para comezar, imos escribir a nosa árbore orixinal de novo, onde tivemos 7, e despois un 3, e despois 3 apuntou para o dereito á 6, e 7 tivo un fillo dereito que tiña 9 anos. Todo ben. O que é outra forma que podemos escribir esta árbore? En vez de ter 3 ser o fillo esquerdo de 7, Tamén poderiamos ter a 6 ser o fillo esquerdo de 7, e despois 3 ser o fillo esquerdo do 6. Que sería coma esta árbore aquí onde eu teño 7, despois 6, despois 3, e un 9 do lado dereito. Tamén non hai que ter 7 como o noso nodo raíz. Tamén poderiamos ter 6 como o noso nodo raíz. O que isto parece? Se imos manter esta propiedade ordenada, todo á esquerda do 6 ten que ser menos do que iso. Hai só unha posibilidade, e iso é 3. Pero, entón, como o dereito do neno de 6, temos dúas posibilidades. En primeiro lugar, pódese ter a 7 e, a continuación, o 9, ou poderiamos chamar iso - como eu estou a piques de facer aquí - onde temos o 9 como o dereito do neno o 6, e logo a 7 como o fillo esquerdo do 9. 

Agora, 7 e 6 non son os únicos valores posibles para a raíz. Tamén poderiamos ter 3 estar na raíz. Qué acontece se 3 é a raíz? Aquí, as cousas están un pouco máis interesante. Tres non ten valores que son menos que isto, Así que o lado esquerdo enteiro da árbore é só vai ser nulo. Non vai ser nada alí. Á dereita, podemos enumerar as cousas en orde crecente. Poderiamos ter 3, e logo 6, despois 7, a continuación, 9. Ou, poderiamos facer 3, despois 6, despois 9, despois 7. Ou, poderiamos facer 3, despois 7, despois 6, despois 9. Ou, 3, 7 - na verdade, non, non podemos facer un 7 máis. Esa é a nosa única cousa alí. Podemos facer 9, e despois dende o 9 podemos facer 6 e 7. Ou, pode-se facer-3, e logo 9, a continuación, 7, e, a continuación, 6. 

Unha cousa de chamar a atención aquí é que estas árbores son un pouco esquisito. En particular, se olharmos para as catro árbores no lado dereito - Vou circular-los, aquí - estas árbores parecen case exactamente como unha lista ligada. Cada nodo ten só un fillo, e así non temos nada diso estrutura de árbore que vemos, por exemplo,  nesta árbore un solitario aquí na parte inferior esquerda. Estas árbores son chamadas realmente dexenerada árbores binarias, e nós imos falar sobre estes máis futuro - especialmente se seguir a facer cursos de ciencias outros computadores. Estas árbores son dexenerados. Eles non son moi útiles, pois, de feito, esa estrutura se presta  a procura de veces semellantes aos dunha lista ligada. Nós non temos aproveitar a memoria extra - este punteiro extra - por mor da nosa estrutura ser malo así. En vez de ir e tirar as árbores binarias que nove na raíz, Que é o caso final que tería, estamos en vez diso, neste momento, vou falar un pouco sobre ese outro termo que usan ao falar sobre as árbores, que se chama a altura. 

A altura dunha árbore é a distancia a partir da raíz para o nó de máis distante, ou mellor, o número de saltos que tería que facer a fin de comezar a partir da raíz e despois acaban no nodo máis distante na árbore. Se miramos para algunhas destas árbores que temos deseñado aquí, podemos ver que, se tomamos esta árbore na esquina superior esquerda e comezamos a 3, entón temos que facer un salto para chegar ao 6, un segundo salto para chegar ao 7, e un terceiro hop para chegar ao 9. Entón, a altura da árbore é de 3. Podemos facer o mesmo exercicio para as outras árbores descritas con este verde, e podemos ver que a altura de todas estas árbores é tamén certo 3. Isto é parte do que os fai dexenerada - que a súa altura é só un a menos que o número de nós en toda a árbore. Se olharmos para esta outra árbore que está rodeada con vermello, por outra banda, vemos que os nós máis distantes da folla son o 6 eo 9 - o deixa de ser os nós que non teñen fillos. Así, a fin de obter a partir do nó de raíz, tanto a 6 ou 9, temos que facer un salto para chegar ao 7 e, a continuación, un segundo salto para chegar ao 9, e do mesmo xeito, só o salto de un segundo a partir do 7 para obter a 6. Así, a altura desta árbore aquí é só 2. Vostede pode volver e facelo para todas as outras árbores que previamente discutido comezando co 7 e a 6, e podes ver que a altura de todas as árbores tamén é 2. 

A razón pola que temos falado sobre ordenou árbores binarias e por que son legais porque pode buscar por eles en unha forma moi semellante á procura dun array ordenado. Este é o lugar onde se fala de conseguir que o tempo de busca mellorada sobre a lista ligada simple. Cunha lista ligada - se quere atopar un elemento particular - está no mellor vai facer algún tipo de busca lineal onde comeza o inicio dunha lista de correo-hop un-por-un - un nó, un nó - toda a lista ata atopar o que está a procurar. Considerando que, se ten unha árbore binaria que está almacenado neste formato agradable, realmente pode ser máis de unha busca binaria suceder onde dividir e conquistar e investigación a través da metade apropiada da árbore de cada etapa. Imos ver como funciona isto. 

Se temos - de novo, volvendo a nosa árbore orixinal - comezamos a 7, que teñen 3, á esquerda, á dereita 9, e baixo a 3 temos a 6. Se queremos buscar o número 6 na árbore, nós iniciar na raíz. Nós comparar o valor que estamos a buscar, digamos 6, ao valor almacenado no nodo que nós estamos a buscar, aos 7, descubrir que 6 é de feito menor que 7, entón mover á esquerda. Se o valor de 6 fora superior a 7, que tería lugar movido cara á dereita. Como sabemos que - debido á estrutura da nosa árbore binaria ordenada - todos os valores menos que 7 serán almacenadas á esquerda, de 7, non hai necesidade de incomodar mesmo mirando polo lado dereito da árbore. Unha vez que se mover á esquerda e agora estamos no nodo que contén 3, podemos facelo de novo mesmo comparación, onde se compara o 3 eo 6. E descubrimos que, mentres 6 - o valor que estamos a buscar - é maior que 3, que pode ir para o lado dereito do nodo contén 3. Non hai á esquerda aquí, polo tanto, podería ter ignorado iso. Pero só sabemos que xa nós estamos mirando para a propia árbore, e podemos ver que a árbore non ten fillos. 

Tamén é moi fácil mirar para arriba 6 nesta árbore estamos facendo a nós mesmos como seres humanos, pero imos seguir ese proceso mecánicamente como un ordenador faría para realmente entender o algoritmo. Neste punto, estamos agora mirando para un nodo que contén 6, e nós estamos mirando para o valor 6, así, en verdade, atopamos o no apropiado. Atopamos o valor 6 na nosa árbore, e podemos deixar a nosa procura. Neste punto, dependendo do que está a suceder, podemos dicir, si, atopamos o valor 6, que existe na nosa árbore. Ou, se estamos a planear para inserir un nodo ou facer algo, podemos facelo neste momento. 

Imos facer buscas algunhas só para ver como funciona isto. Vexamos o que pasa se fósemos probar e mirar para arriba o valor 10. Se estivésemos a mirar para arriba o valor 10, que ía comezar na raíz. Vemos que 10 é maior que 7, así que mover á dereita. Teriamos a 9 e comparar 9 ao 10 e mira que 9 é realmente inferior a 10. Entón, de novo, que ía tentar mover á dereita. Pero, neste punto, a xente entende que estamos nun nodo nulo. Non hai nada alí. Non hai nada que o 10 debe ser. Este é o lugar onde podemos informar fallo - que en realidade non hai 10 na árbore. E, finalmente, imos percorrer o caso en que estamos a tentar buscar unha na árbore. Isto é semellante ao que acontece cando miramos cara arriba 10, excepto en vez de ir para a dereita, Estamos indo para ir á esquerda. Nós comezamos no 7, e ver que unha é inferior a 7, de xeito que se mover cara á esquerda. Chegamos ao 3 e ver que 1 é menor que 3, polo tanto, unha vez máis, tentar mover á esquerda. Neste punto temos un nodo nulo, entón, de novo, podemos denunciar o fracaso. 

Se queres saber máis sobre árbores binarias, hai unha morea de diversión pequenos problemas que pode facer con eles. Eu suxiro facer o deseño destes diagramas un-por-un e despois a través de todos os pasos diferentes, porque iso virá a super-accesible non só cando está facendo a Huffman conxunto de problemas de codificación pero tamén en cursos futuros - só aprender a sacar esas estruturas de datos e reflexionar sobre os problemas con pluma e papel, ou, neste caso do iPad, e pluma. 

Neste punto, porén, imos pasar a facer algunha práctica de codificación e realmente xogar con esas árbores binarias e ver. Vou volver para o meu ordenador. Para esta parte da sección, en vez de usar CS50 CS50 Executar ou espazos, Vou usar o aparello. 

Tras xunto coa especificación do conxunto de problemas, Eu vexo que eu teño que abrir o dispositivo, ir á miña carpeta Dropbox, cree unha carpeta chamada Sección 7, e, entón, crear un arquivo chamado binary_tree.c. Aquí imos nós. Eu teño o aparello xa está aberta. Vou tirar un terminal. Eu estou indo a ir á carpeta Dropbox, cree un directorio chamado Sección 7, e ver que é totalmente baleiro. Agora vou abrir binary_tree.c. Todo ben. Aquí imos nós - Arquivo baleiro. 

Imos volver con especificación. A especificación pide para crear unha nova definición de tipo para un nodo árbore binaria conteñen valores int - así como os valores que sacou na nosa diagramação antes. Nós imos usar ese cliché typedef que fixemos aquí que ten que recoñecer de conxunto de problemas 5 - se fixo o camiño táboa hash do programa conquistando o Speller. Tamén debe recoñece-lo da sección da semana pasada onde falamos sobre listas ligadas. Temos este typedef dun nodo de estrutura, e demos a este nodo struct este nome de nodo struct previamente para que poidamos, a continuación refírense a el, xa que vai querer ter punteiros nodo struct como parte da nosa estrutura, pero entón cercaron iso - ou antes, esta pechada - nun typedef de xeito que, ao final do código, que pode referirse a esa estrutura como só un nó no canto dun nodo de estrutura. 

Isto vai ser moi semellante á definición de lista individualmente-vinculado que vimos a semana pasada. Para iso, imos comezar por escribir o cliché. Sabemos que temos que ter un valor enteiro, entón imos poñer en valor int, e despois, no canto de ter só un punteiro para o próximo elemento - como fixemos co illadamente conectados listas - imos ter punteiros neno esquerdo e dereito. Isto é moi sinxelo tamén - struct fillo do nodo * esquerda; e struct nodo fillo dereito *;. Cool. Isto parece un bo comezo. Imos volver con especificación. 

Agora necesitamos declarar unha variable * mundial no a raíz dunha árbore. Nós imos facer este global como fixemos punteiro primeiro na nosa lista ligada tamén global. Este foi, de xeito que nas funcións que escriben non temos que manter esta pasando en torno a raíz - pero imos ver que se quere escribir estas funcións de forma recursiva, quizais sexa mellor non mesmo pasalo en torno a como unha empresa global, en primeiro lugar e, en vez arrincar-lo localmente na súa función principal. Pero, imos facelo globalmente para comezar. Unha vez máis, imos dar un par de espazos, e eu vou declarar unha raíz * nodo. Só para estar seguro que non deixe este non inicializar, eu estou indo a define-la igual a null. Agora, na función principal - o que imos escribir moi rapidamente aquí - int main (int argc, const char * argv []) - e eu vou comezar declarando miña matriz argv como const só así que eu sei que estes argumentos son argumentos que eu probablemente non queren modificar. Se eu queira modificalo los eu probablemente debería estar facendo copias deles. Vai ver moito iso no código. É bo de calquera maneira. É bo deixalo como - omitir a const se desexa. Eu normalmente poñelas só para que eu me lembrar  que probablemente non queren modificar eses argumentos. 

Como sempre, eu estou indo a incluír este retorno 0 ao final do principal. Aquí, vou comezar o meu nó de raíz. Tal e como está agora, eu teño un punteiro que está definido como nulo, por iso está a apuntar cara a nada. A fin de que realmente comezar a construír o nó, Eu primeiro teño reservar memoria para el. Eu vou facer iso, facendo memoria na pila empregando malloc. Eu estou indo para definir raíz igual ao resultado de malloc, e eu vou usar o operador sizeof para calcular o tamaño dun nodo. A razón que eu uso no sizeof ao contrario, digamos, facer algo así - malloc (4 + 4 +4) ou malloc 12 - é porque quero o meu código para ser o máis compatible posible. Eu quero ser capaz de tomar isto. Arquivo c, recompila-lo no seu dispositivo, e despois recompila-lo no meu 64-bit Mac - ou sobre unha arquitectura completamente diferente - e quero que todo para o mesmo traballo. 

Se eu estou facendo suposicións sobre o tamaño de variables - o tamaño dun int ou o tamaño dun punteiro - entón eu tamén estou facendo suposicións sobre os tipos de arquitecturas en que o meu código pode compilar con éxito cando sexa executado. Sempre use sizeof ao contrario manualmente suma dos campos de estruturas. A outra razón é que tamén pode haber recheo que o compilador pon na estrutura. Mesmo só sumar os campos individuais non é algo que normalmente quere facer, así, eliminar a liña. Agora, para realmente iniciar este nodo raíz, Vou ter que conectar os valores de cada un dos seus diferentes campos. Por exemplo, para o valor que sei que quero para arrincar 7, e agora eu estou indo a definir o fillo esquerdo de ser nulo e do dereito do neno a ser tamén nulo. Gran! Nós fixemos iso parte da especificación. 

A especificación para abaixo na parte inferior da páxina 3 me pide para crear tres máis nós - un contendo 3, un contendo 6, e un 9 - e, a continuación, conecta-los de xeito que parece exactamente como o noso diagrama de árbore que estabamos falando anteriormente. Imos facelo ben rápido aquí. Vai ver moi rapidamente que eu vou comezar a escribir unha morea de código duplicado. Eu estou indo para crear un nó * e eu vou chamalo de tres. Eu estou indo a define-la igual a malloc (sizeof (nó)). Eu estou indo para definir tres-> valor = 3. Tres -> left_child = NULL; tres -> dereito _child = NULL; tamén. Isto parece moi semellante ao inicializar a raíz, e iso é o que Vou ter que facer se eu comezar a arrincar 6 e 9 tamén. Vou facelo moi rapidamente aquí - na verdade, eu vou facer unha copia pouco e pegar, e asegúrese de que - todo ben.  Agora, eu teño que copiar e podo ir adiante e establecer esta igual a 6. Podes ver que iso leva tempo e non é super-eficiente. En só un pouco, imos escribir unha función que vai facelo por nós. Quero substituír iso cun 9, substitúa que, cun 6. 

Agora temos todos os nosos nós creado e inicializar. Temos a nosa raíz definido igual a 7, ou que contén o valor 7, nosa nodo contén 3, o noso nodo que contén 6, e contén o nodo 9. Neste punto, todo o que temos que facer é todo o fío cara arriba. A razón de eu inicializar os punteiros como nulo é só para que eu estar seguro de que Eu non teño os punteiros non inicializados alí por accidente. E tamén porque, neste momento, eu só teño que realmente conectar os nós para o outro - para os que están realmente ligadas a - Eu non teño que pasar e facer seguro de que todos os nulos están alí nos lugares apropiados. 

A partir da raíz, sei que fillo esquerda da raíz é 3. Sei que fillo dereito da raíz é 9. Despois diso, o fillo único outro que me queda para se preocupar É dereito do neno 3, que é 6. Neste punto, todo parece moi bo. Nós imos eliminar algunhas destas liñas. Agora todo parece moi bo. Imos volver para a nosa especificación e ver o que temos que facer a continuación. 

Neste punto, debemos escribir unha función chamada "contén" con un prototipo de 'contén bool (valor enteiro). E este contén función devolverá true  a árbore apuntada pola nosa variable raíz global  contén o valor pasado para a función e falso en caso contrario. Imos adiante e facelo. Este vai ser exactamente como a investigación que fixemos coa man no iPad un pouco atrás. Imos zoom un pouco e vai cara arriba. Nós imos poñer esta función logo enriba a nosa función principal de modo que non hai que facer calquera tipo de prototipado. Entón, bool contén (valor enteiro). Alí imos nós. Non é a nosa declaración cliché. Só para ter seguro que isto vai compilar, Eu estou indo a ir adiante e configure-lo igual a voltar falso. Neste momento esta función só non vai facer nada e sempre relatan que o valor que estamos a buscar non está na árbore. 

Neste punto, pode ser unha boa idea - desde que escribín unha morea de código e non temos sequera intentou proba-lo aínda - para asegurarse de que todo compila. Hai un par de cousas que temos que facer para estar seguro de que iso realmente vai compilar. Primeiro, vexa se estamos usando todas as funcións en calquera biblioteca que aínda non foron incluídas. As funcións que usan ata agora son malloc, e entón nós tamén está a usar este tipo - este tipo fóra do estándar chamado 'bool' - que está incluído no ficheiro de cabeceira estándar bool. Nós sempre queremos incluír bool.h estándar para o tipo bool, e nós tamén queremos # include lib.h estándar para as bibliotecas estándar que inclúen malloc, e libre, e todo iso. Entón, zoom out, imos deixar de fumar. Imos tentar e ter seguro de que iso realmente fixo a compilación. Vemos que fai, entón estamos no camiño correcto. 

Imos abrir binary_tree.c novo. El compila. Imos descender e estar seguro de que imos introducir algunhas chamadas nosa función contén - só para que seguro que iso é todo moi ben. Por exemplo, cando fixemos algunhas investigacións na nosa árbore máis cedo, intentamos buscar os 6 valores en 10, e 1, e nós sabiamos que era 6 na árbore, 10 non estaba na árbore, e 1 non estaba na árbore ou. Imos usar as chamadas de mostras, como forma de descubrir se ou non nosa función contén funciona. Co fin de facer iso, eu vou usar a función printf, e nós estamos indo para imprimir o resultado da chamada contén. Vou poñer unha cadea "contén (% d) = porque  imos activar o valor que imos buscar, e =% s \ n "e usar isto como a nosa secuencia de formato. Nós só imos ver - literalmente imprimir na pantalla - o que parece ser unha chamada de función. Isto non é realmente a chamada de función.  Esta é só unha secuencia deseñado para parecerse a unha chamada de función. 

Agora, imos chamar os valores. Nós imos tratar contén o 6, e entón o que imos facer aquí é usar o operador ternário. Imos ver - contén 6 - así, agora contiña 6 e contén 6 é certa, a cadea que imos enviar o carácter de formato% s vai ser a cadea "true". Imos rolar un pouco máis. En caso contrario, queremos enviar a string "false" se contén seis retorno falsos. Isto é un pouco tolo bonito, pero eu creo que eu podería moi ben ilustrar o que o operador ternário parece, xa que non vin el por algún tempo. Esta será unha forma agradable, útil para descubrir a nosa función contén funciona. Eu estou indo a rolar de volta cara á esquerda, e eu vou copiar e pegar esta liña algunhas veces. El cambiou algúns deses valores ao redor, polo que este vai ser un, e iso vai ser 10. 

Neste punto, temos unha función contén agradable. Temos algunhas probas, e imos ver se esta todo funciona. Neste punto, teño escrito algúns códigos máis. Tempo para saír fóra e asegúrese de que todo aínda compila. Sae fóra, e agora imos tratar de facer árbore binaria de novo. Ben, parece que temos un erro, E nós temos esta declarar explicitamente a función de biblioteca printf. Parece que temos que ir e # include standardio.h. E, con iso, todo debe compilar. Estamos todos ben. Agora imos tratar de correr árbore binaria e ver o que acontece. Aquí estamos nós,. / Binary_tree, e vemos que, como se esperaba - porque non teñen implementado contén aínda, ou mellor, acabamos de poñer no return false - vemos que está só retornando teito para todos eles, Entón iso é todo traballo para a maior parte bastante ben. 

Imos volver e realmente aplicar contén neste momento. Eu estou indo a rolar para abaixo, aumentar o zoom, e - Lembre, o algoritmo que usan foi que comezou no nodo raíz e en cada nodo que atopamos, facemos unha comparación, e en base a que a comparación que quere pasar ao fillo esquerdo ou dereito para o neno. Isto vai parecer moi semellante ao código de búsqueda binaria que escribimos no inicio do prazo. Cando comezamos, nós sabemos que queremos soster o nodo actual que estamos mirando, eo nodo actual vai ser inicializar a nó raíz. E agora, imos continuar a árbore, e lembre que a nosa condición de deixar -  cando efectivamente traballadas a través do exemplo a man - foi cando atopou un nodo nulo, non cando miramos para un neno nulo, pero cando realmente mudou-se para un nó na árbore e descubriu que estamos nun nodo nulo. Estamos indo para iterar ata actual non é igual a nulo. E que é o que imos facer? Nós imos comprobar se (cur -> valor valor ==) entón sabemos que temos en realidade, o nodo que estamos a buscar. Entón, aquí, podemos volver true. En caso contrario, queremos a ver se ou non o valor é menor que o valor. Se o valor do nodo actual é menor que o valor que está a buscar, imos pasar para a dereita. Entón, cur = actual -> right_child, e se non, nós estamos indo para mover á esquerda. actual actual = -> left_child;. Moi sinxelo. 

Probablemente recoñece o lazo que se parece moi semellante a este de busca binaria no inicio do prazo, agás a continuación estabamos lidando con baixa, media e alta. Aquí, só temos que ollar para un valor actual, por iso é bo e sinxelo. Imos ter a certeza de que este código está funcionando. En primeiro lugar, asegúrese de que compila. Parece que fai. Imos tentar executa-lo. E, de feito, ela mostra todo o que esperabamos. Atopa 6 na árbore, non atopa 10, porque 10 non está na árbore, e non se atope unha ou porque non é unha tamén na árbore. Cousas legais. 

Todo ben. Imos volver para a nosa especificación e ver o que está próximo. Agora, quere engadir nós algúns para a nosa árbore. El quere engadir 5, 2 e 8, e asegúrese de que a nosa contén código aínda funciona como se esperaba. Imos facelo. Neste punto, en vez de facer a copia irritante e pegar de novo, imos escribir unha función para realmente crear un nó. Se rolar todo o camiño para o inicio, vemos que temos está a facer esta código moi semellante e outra vez cada vez que queremos crear un nó. 

Imos escribir unha función que realmente construír un nó para nós e para devolve-lo. Vou chamalo build_node. Vou construír un nó cun valor específico. Zoom aquí. O primeiro que vou facer é, en realidade, crear espazo para o nodo na pila. Así, o nó * n = malloc (sizeof (nó)); n - valor> = valor; e despois aquí, eu estou indo só para arrincar todos os campos para valores apropiados. E ao final, imos voltar a nosa nodo. Todo ben. Unha cousa a notar é que esta función aquí vai voltar un punteiro para a memoria que foi alocada chea. O que é legal sobre iso é que este nodo agora - temos que declaralo lo na pila porque se declarou na pila non sería capaz de facelo nesta función como esta. Que a memoria vai fóra do alcance e sería válido se intentamos acceder a ela máis tarde. Unha vez que estamos declarando pila alocada de memoria, imos ter que coidar de liberar-lo máis tarde para o noso programa para non baleirar calquera memoria. Fomos punting en que a calquera outra cousa no código só por mor da simplicidade na época, pero se xa escribir unha función parecida con esta onde ten - algúns chaman un malloc ou realloc dentro - quere estar seguro de que poñer algún tipo de comentario por aquí que di: ei, vostede sabe, retorna un nó pila alocada inicializar o valor pasado-in. E entón quere estar seguro de que poñer en algún tipo de nota que di o chamador debe liberar a memoria volveu. Desta forma, se alguén non vai e utiliza esa función, eles saben que o que reciben de volta que a función nalgún momento terá que ser liberado. 

Asumindo que todo está ben e bo aquí, podemos ir para abaixo no noso código e substituír todas estas liñas aquí con chamadas a nosa función de construción. Imos facelo moi rapidamente. A única parte que non estamos indo para substituír é esa parte aquí na parte inferior onde realmente conectar os nós para apuntar para o outro, porque non podemos facer na nosa función. Pero, imos facer raíz = build_node (7); nodo * tres = build_node (3); nó * seis = build_node (6); nodo * nove = build_node (9);. E agora, nós tamén quería engadir nós para - nó * cinco = build_node (5); nodo * oito = build_node (8); e cal foi o outro no? Imos ver aquí. Queriamos tamén engadir un 2 - nó * dous = build_node (2);. Todo ben. Neste punto, sabemos que temos o 7, o 3, o 9, e os 6 todo ligado de forma adecuada, pero que sobre o 5, o 8, eo 2? Para manter todo en orde apropiada, sabemos que neno dereita tres é 6. Entón, se nós imos engadir a 5, a 5 tamén pertence ao lado dereito da árbore dos cales 3 é a raíz, así como 5 pertenza o neno esquerda de 6. Podemos facer isto por dicir, seis -> left_child = cinco; e, a continuación, a 8 pertenza como o fillo esquerdo de 9, para nove -> left_child = oito; e 2 é o fillo esquerdo de tres, para que poidamos facelo aquí - te -> left_child = dous;. Se non chegou a seguir, xunto con iso, eu sugiro que retirala la só. 

Todo ben. Imos salvar este. Imos saír e asegurarse de que compila, e entón podemos engadir ás nosas chamadas contén. Parece que todo aínda compila. Imos entrar e engadir en algunhas contén chamadas. Unha vez máis, eu vou facer un pouco de copiar e pegar. Agora imos buscar 5, 8 e 2. Todo ben. Imos estar seguro de que todo isto parece ser bo aínda. Gran! Gardar e saír. Agora imos facer, compilar, e agora imos realizar. A partir dos resultados, parece que todo está funcionando moi agradable e ben. Gran! Entón, agora temos os nosos contén función escrito. Imos seguir adiante e comezar a traballar en como inserir nós na árbore unha vez que, como estamos facendo agora, as cousas non son moi bonitas. 

Se volvemos para a especificación, que nos pide para escribir unha función chamada introducir - de novo, retornando un bool para se ou non poderiamos engadir o nodo na árbore - e, a continuación, o valor para introducir na árbore é especificado como o único argumento para a nosa función de inserción. Volveremos realidade se podería de feito introducir o valor do nodo que contén na árbore, o que significa que un tiña suficiente memoria, e dous, que o nodo xa non existe na árbore desde entón - Lembre, non imos ter valores duplicados na árbore, só para facer as cousas simples. Todo ben. De volta para o código. Abre-se. Zoom un pouco, a continuación, vai para abaixo. Imos poñer a función de inserción logo enriba os contén. Unha vez máis, que vai ser chamado de inserción bool (valor enteiro). Dele un pouco máis espazo, e entón, como un estándar, imos poñer en return false ao final. Agora, na parte inferior, imos adiante e en vez de construír manualmente os nós na principal nós mesmos e fiación-los para apuntar para o outro como nós estamos facendo, imos confiar na nosa función de inserción para facelo. Non imos contar coa nosa función de inserción para construír a árbore enteira a partir de cero aínda, pero nós imos nos librar destas liñas - imos comentar as liñas - que construír os 5 nós, 8 e 2. E en vez diso, imos introducir chamadas nosa función de inserción para estar seguro de que isto realmente funciona. Aquí imos nós. 

Agora que xa comentou estas liñas. Nós só temos 7, 3, 9 e 6 na nosa árbore neste momento. Para asegurarse de que todo está funcionando, podemos reducir, facer a nosa árbore binaria, executa-lo, e podemos ver que contén agora está nos dicindo que está totalmente seguro - 5, 8, e 2 non na árbore. Voltar para o código, e como é que imos inserir? Teña en conta que o que fixemos cando estabamos realmente a inserción de 5, 8 e 2 anteriormente. Nós xogamos este xogo Plinko onde comezamos na raíz, descendeu a unha árbore por un por un ata atopamos a fenda adecuado, e, entón, con fío no nó no lugar apropiado. Nós imos facer o mesmo. Isto é basicamente como escribir o código que usan no contén función para atopar o lugar onde o nodo debe ser, e entón nós só estamos indo a introducir o nó alí mesmo. Imos comezar a facelo. 

Polo tanto, temos un nó * cur = raíz; nós só estamos indo a seguir o contén código ata descubrir que non funciona moi ben para nós. Nós imos pasar por árbore, mentres que o elemento actual non é nulo, e atopar o valor que actual é igual ao valor que estamos intentando introducir - ben, este é un dos casos en que non podería realmente introducir o no para a árbore, porque iso significa que temos un valor duplicado. Aquí estamos indo realmente para voltar falso. Agora outra cousa, o valor actual é menor que o valor, agora sabemos que imos pasar para a dereita  porque o valor pertence a metade dereita da árbore cur. Se non, nós estamos indo para mover á esquerda. Iso é basicamente nosos contén función alí. 

Neste punto, unha vez que teñamos completado esta loop while, noso punteiro actual vai estar apuntando para null a función non retorno. Estamos, polo tanto, ter cur no lugar onde desexa inserir o novo nodo. O que queda por facer é realmente construír o novo nodo, o que podemos facer moi facilmente. Podemos usar o noso super-accesíbel función do nó de construción, é algo que non fixemos antes - que só un tipo de levou para concedida, pero agora imos facer só para ter seguro - imos probar para estar seguro de que o valor de retorno polo novo nodo foi realmente non nulo, porque nós non queremos comezar a acceder á memoria é nulo. Podemos probar para estar seguro de que novo no non é igual a nulo. Ou en vez diso, podemos só ver se realmente é nulo, e é nulo, entón podemos simplemente voltar falso cedo. 

Neste punto, é preciso conectarse novo no no seu lugar axeitado na árbore. Se miramos cara atrás, principal e onde estabamos realmente fiación en valores antes, vemos que o xeito no que nós estabamos facendo iso cando quería poñer 3 na árbore foi acessamos o fillo esquerdo de raíz. Cando poñemos nove na árbore, tivemos que acceder ao fillo dereito da raíz. Tiñamos que ter un punteiro para o pai, a fin de poñer un novo valor para a árbore. Rolando de volta para introducir, que non vai moito traballar aquí porque non temos un punteiro pai. O que se quere ser capaz de facer é, neste punto, comprobar o valor do pai e ver - ben, caramba, o valor do pai é menor que o valor actual, entón o neno o dereito dos pais debe ser o novo nodo; en caso contrario, fillo esquerdo do pai debe ser o novo nodo. Pero, non temos este punteiro pai aínda. 

A fin de obtê-lo, nós imos mesmo ter que segui-lo como nós atravesamos a árbore e atopar o lugar axeitado no noso loop anterior. Podemos facelo por desprazamento de volta ata o cumio da nosa función de inserción e seguimento doutra variable punteiro chamado pai. Nós imos define-lo igual a nulo, inicialmente, e entón cada vez que pasar pola árbore, imos definir o punteiro pai para coincidir co punteiro actual. Establecer pai igual a cur. Deste xeito, cada vez que pasar, imos garantir que, como o punteiro actual é incrementado o punteiro pai segue - só un nivel máis elevado do que o punteiro actual na árbore. Iso todo parece moi bo. 

Eu creo que o único que imos querer axustar é esta compilación nulo nó de retorno. A fin de obter construír no realmente con éxito voltar nulo, Nós imos ter que modificar este código, porque aquí, nunca probado para garantir que malloc retornou un punteiro válido. Así, (n = NULL!), A continuación, - se malloc retornou un punteiro válido, entón imos arrincar-lo; en caso contrario, imos voltar e que vai acabar volvendo nulo para nós. Agora todo parece moi bo. Imos ter a certeza de que isto realmente compila. Facer árbore binaria, e Oh, nós temos algunhas cousas a ocorrer aquí. 

Temos unha declaración implícita da función construír no. De novo, con estes compiladores, imos comezar na parte superior. O que ten que dicir é que eu estou chamando construír no antes de realmente declarado. Imos volver ao código moi rapidamente. Rolar para abaixo, e con certeza, a miña función de inserción é declarado enriba da función do nó de construción, pero eu estou tentando usar construír no interior de inserción. Eu vou entrar e copia - e despois pega o camiño de construción función do nó aquí arriba. Desta forma, espero que funcione. Imos dar estoutro ir. Agora todo compila. Todo é bo. 

Pero neste momento, non temos realmente chamou a función de inserción. Nós só sabemos que compila, entón imos entrar e poñer algunhas chamadas dentro Imos facelo na nosa función principal. Aquí, nós comentada 5, 8 e 2, e, despois, non conecta-los aquí. Imos facer algunhas chamadas para introducir, e imos usar o mesmo tipo de material que usamos cando fixemos estas chamadas printf para estar seguro de que todo o que se introducir correctamente. Vou copiar e pegar, e en vez de conter imos facer de inserción. E, en vez de 6, 10 e 1, imos usar 5, 8 e 2. Isto débese Esperanza introducir 5, 8, e dous para a árbore. Compilar. Todo é bo. Agora imos executar o noso programa. 

Todo volveu falso. Entón, 5, 8 e 2 non foi, e parece que contén non pensou ningunha delas. O que está a suceder? Imos diminuír o zoom. O primeiro problema foi que introducir parecía retornar falso, e parece que iso é porque saímos na nosa chamada de retorno falso, e nós nunca realmente retornou certo. Podemos configurar isto. O segundo problema é que, agora mesmo que facer - gardar este, deixar isto, executar o make novo, telo compilar, a continuación, executa-lo - vemos que algo máis pasou aquí. O 5, 8, e 2 foron aínda non atopou na árbore. Entón, o que está a suceder? 

Imos dar un ollo niso no código. Imos ver se podemos descubrir iso. Comezamos co pai non ser nulo. Nós ajustamos o punteiro actual coincide co punteiro raíz, e nós imos traballar o noso camiño a través da árbore. Se o nodo actual non é nulo, entón sabemos que podemos mover un pouco para abaixo. Montar noso punteiro pai para ser igual ao actual do punteiro, comprobar o valor - se os valores son os mesmos que retornou falso. Se os valores son menos nos cambiamos para a dereita; en caso contrario, mudouse para a esquerda. Entón, imos construír un nó. Vou ampliar un pouco. E aquí, nós imos tratar conectar os valores a ser o mesmo. O que está a suceder? Imos ver se posiblemente Valgrind pode dar unha información. 

Eu gusto de usar Valgrind só porque Valgrind moi rapidamente executado e dille se hai erros de memoria. Cando corremos Valgrind no código, como podes ver hit here--Valgrind./binary_tree--and dereito entrar. Vostede ve que non ten ningún erro de memoria, polo que parece que está todo ben ata agora. Temos algúns derrames de memoria, que sabemos, porque non somos pasando para liberar calquera dos nosos nós. Imos tentar executar GDB para ver o que está realmente a suceder. Nós imos facer gdb. / Binary_tree. El iniciou-se moi ben. Imos definir un punto de ruptura na inserción. Imos correr. Parece que nunca realmente chamado de inserción. Parece que o problema era só que cando eu mudei para aquí en principal - todas esas chamadas de printf contén - Eu nunca realmente cambiou destes para chamar de inserción. Agora imos dar unha oportunidade. Imos compilar. Todo parece bo alí. Agora imos tratar de executa-lo, ver o que acontece. Todo ben! Todo parece moi bo alí. 

A última cousa a pensar é, existen casos de punta a esta entrada? E ocorre que, así, o caso de borde que sempre é interesante para pensar , o que pasa se a súa árbore está baleira e chamar esa función de inserción? Será que vai funcionar? Ben, imos dar unha oportunidade. - Binary_tree c. - A maneira que nós imos probar que é, estamos indo a ir ata a nosa función principal, e ao contrario de fiación eses nós así, Nós só estamos indo a comentar a cousa toda, e en vez de fiación ata os nós de nós mesmos, podemos realmente ir adiante e eliminar todo isto. Nós imos facer todo o que unha chamada para introducir. Entón, imos facer - en vez de 5, 8 e 2, imos introducir 7, 3 e 9. E entón nós tamén quere inserir 6 tamén. Gardar. Saír. Facer árbore binaria. Todo compila. Podemos só executa-lo como está e ver o que acontece, pero tamén vai ser moi importante para asegurarse de que non temos ningún erros de memoria, unha vez que este é un dos nosos casos de punta que nós coñecemos. 

Imos estar seguro de que funciona ben baixo Valgrind, o que faremos simplemente executando Valgrind. / binary_tree. Parece que, de feito, un erro dun contexto - temos esa fallo de segmento. ¿Qué pasou? Valgrind realmente nos di onde está. Zoom para fóra un pouco. Parece que está a suceder na nosa función de inserción, onde temos unha lectura incorrecta de tamaño 4 a inserción, liña 60. Imos volver e ver o que está a suceder aquí. Diminuír o zoom moi rápido. Eu quero estar seguro de que non vai para o bordo da pantalla, para que poidamos ver todo. Puxe que un pouco. Todo ben. Rolar para abaixo, e que o problema está aquí. Qué acontece se nós descermos eo noso nodo actual xa é nulo, noso nodo pai é nulo, polo que se miramos cara o cumio, aquí - se isto non loop while realmente executa porque o seu valor actual é nulo - a nosa raíz é nula a actual é nulo - entón nunca o noso pai está configurado para actual ou para un valor válido, así, o pai tamén será nulo. Necesitamos recordar para comprobar que no momento en que chegar aquí, e comezar a acceder valor do pai. Entón, o que ocorre? Ben, o pai é nulo - if (pai == NULL) -, entón sabemos que non debe haber nada na árbore. Debemos estar intentando inserir-lo na raíz. Podemos facelo definindo só a raíz igual ao novo nodo. Entón, neste momento, nós realmente non quero pasar por esas outras cousas. En vez diso, aquí, podemos facer unha ou outra cousa se else, ou podemos combinar todo aquí en outra persoa, pero aquí imos usar máis e facelo desa maneira. Agora, imos probar para estar seguro de que o noso pai non é nulo antes, entón realmente intentando acceder os seus campos. Isto vai axudar a evitar a fallo de segmento. Entón, nós paramos, zoom out, compilar, executar. 

Sen erros, pero aínda temos unha morea de derrames de memoria porque non liberar calquera dos nosos nós. Pero se somos aquí e vai para a impresión, vemos que, así, parece que todos os nosos insercións foron retornando certo, o que é bo. As pastillas son todas verdadeiras, e despois as chamadas pertinentes contén tamén son certas. 

Bo traballo! Parece que temos escrito con éxito inserción. Isto é todo o que temos para esta semana Especificación conxunto de problemas. Un reto divertido pensar é como realmente ir e libre de todos os nós desta árbore. Podemos facer un número de xeitos diferentes, pero vou deixar isto para vostede experimentar, e como un reto divertido, probar e asegurarse de que pode que seguro que este informe Valgrind amosa erros e sen vazamentos. 

Boa sorte no partido desta semana problema Huffman, e imos ver semana que vén! [CS50.TV]