[Powered by Google Translate] [Seção 7] [menos confortável] [Nate Hardison] [Harvard University] [Esta é CS50.] [CS50.TV] 

Bem-vindo à secção 7. Graças ao furacão Sandy, em vez de ter uma secção normal esta semana, estamos fazendo este passo a passo, através da seção de perguntas. Eu vou estar a seguir, juntamente com o conjunto de problemas 6 Especificação, e passando por todas as perguntas do A Seção de secção de Perguntas. Se houver alguma dúvida, por favor postar estes em CS50 discutir. 

Tudo bem. Vamos começar. Agora eu estou olhando para a página 3 da Especificação conjunto de problemas. Nós vamos primeiro começar a falar sobre árvores binárias uma vez que estes têm muita relevância para o conjunto desta semana - problema a codificação árvore Huffman. Uma das estruturas de dados primeiras falamos sobre CS50 foi a matriz. Lembre-se que uma matriz é uma seqüência de elementos - todos do mesmo tipo, - armazenados ao lado uns dos outros na memória. Se eu tiver uma matriz de inteiros que eu possa desenhar usando este estilo de caixas-números-inteiros - Vamos dizer que eu tenho 5 na primeira caixa, eu tenho sete no segundo, então tenho 8, 10, e 20 na caixa final. Coisas Lembre-se, os dois realmente boas sobre essa matriz são de que temos esse acesso e de tempo constante para qualquer elemento específico  na matriz, se sabemos seu índice. Por exemplo, se eu quiser pegar o terceiro elemento na matriz - no índice 2, usando o nosso sistema de indexação baseado em zero - Eu literalmente só tem que fazer um simples cálculo matemático, hop para essa posição na matriz, puxe o 8 que está armazenado lá, e eu sou bom para ir. 

Uma das coisas ruins sobre essa matriz - que falou sobre quando discutimos listas ligadas - é que se eu quiser inserir um elemento para essa matriz, Eu vou ter que fazer alguma mudança por aí. Por exemplo, a matriz isso aqui é na ordem de classificação - classificados em ordem crescente - 5, em seguida, 7, 8, em seguida, em seguida, 10, e depois 20 - mas se eu quiser inserir o número 9 para esta matriz, Eu vou ter que mudar alguns dos elementos a fim de tornar o espaço. Podemos chamar isso aqui. Vou ter que mover a 5, a 7 e, em seguida, a 8; criar um espaço onde posso colocar o 9, e, em seguida, a 10 e a 20 pode ir para a direita do 9. Este é um tipo de dor, porque no pior cenário - quando estamos tendo que inserir ou no início ou no final da matriz, dependendo de como estamos mudando - podemos acabar tendo que mudar todos os elementos que estamos actualmente a armazenar na matriz. 

Então, o que era a maneira de contornar isso? A maneira de contornar isso era para ir para o nosso método de lista encadeada, onde - em vez de armazenar os elementos 5, 7, 8, 10, e 20 todas próximas umas das outras na memória - o que, em vez fez foi armazená-los tipo de onde nos queria para armazená-los nestes nós Linked-lista que eu estou desenhando aqui, tipo de ad hoc. E, então, conectado-los em conjunto, utilizando estes ponteiros próximos. I pode ter um ponteiro a partir de 5 a 7, um ponteiro a partir da 7 à 8, um ponteiro a partir da 8 à 10, e, finalmente, um ponteiro da 10 à 20, e, em seguida, um ponteiro nulo no 20, indicando que não há nada de esquerda. O trade-off que temos aqui é que agora se pretende inserir o número 9 em nossa lista ordenada, tudo o que temos a fazer é criar um novo nó com 9, fio-lo para apontar para o local apropriado, e, em seguida, re-ligação do 8 a apontar para baixo para o 9. Isso é muito rápido, assumir que sabemos exatamente onde queremos inserir o 9. Mas o trade-off em troca para isso é que temos agora perdeu o acesso de tempo constante para qualquer elemento particular na nossa estrutura de dados. Por exemplo, se eu quero encontrar o quarto elemento nesta lista ligada, Eu vou ter que começar bem no início da lista e trabalhar o meu caminho através da contagem nó a nó até encontrar o quarto. 

A fim de obter um desempenho melhor acesso do que uma lista ligada - mas também manter alguns dos benefícios que tivemos em termos de tempo de inserção a partir de uma lista ligada - uma árvore binária está indo a necessidade de usar a memória um pouco mais. Em particular, em vez de ter apenas um ponteiro em um nó de árvore binária - como a lista ligada nó faz - vamos adicionar um segundo ponteiro para o nó de árvore binária. Em vez de ter apenas um ponteiro para o próximo elemento, vamos ter um ponteiro para uma criança esquerdo e um direito da criança. 

Vamos tirar uma foto para ver o que realmente parece. Mais uma vez, eu vou usar essas caixas e flechas. Um nó da árvore binária vai começar com apenas uma caixa simples. Vai ter um espaço para o valor, e depois também vai ter um espaço para a criança esquerda e direita da criança. Eu estou indo para classificá-los aqui. Nós vamos ter o filho esquerdo, e então nós vamos ter o filho direito. Há muitas maneiras diferentes de fazer isso. Às vezes para o espaço e conveniência, Eu, na verdade, desenhá-lo como eu estou fazendo aqui em baixo onde eu vou ter o valor no topo, e depois o filho da direita no canto inferior direito, e criança a esquerda no canto inferior esquerdo. Voltando a este diagrama superior, temos o valor no topo, então temos o ponteiro esquerdo criança, e depois temos o ponteiro criança direito. 

Na Especificação conjunto de problemas, falamos de desenhar um nó que tem um valor de 7, e um ponteiro-esquerdo criança que é nulo, e um ponteiro direito da criança, que é nulo. Nós pode escrever NULL capital no espaço de tanto a criança quanto a esquerda e direita da criança, ou podemos chamar esta barra diagonal através de cada uma das caixas, para indicar que é nula. Eu vou fazer isso só porque é mais simples. O que você vê aqui são duas formas de diagramação de um nó de árvore muito simples binário onde temos o valor 7 e ponteiros criança nulos. 

A segunda parte fala sobre como nossos especificação com listas ligadas - Lembre-se, temos apenas a segurar o primeiro elemento de uma lista para lembrar toda a lista - e da mesma forma, com uma árvore binária, só temos que segurar um ponteiro para a árvore , a fim de manter o controlo sobre a estrutura de dados inteira. Este elemento especial da árvore é chamado nó raiz da árvore. Por exemplo, se esse nó um - este nó que contém o valor 7 com ponteiros nulos lados esquerdo e direito da criança - eram o único valor em nossa árvore, então este seria o nosso nó raiz. É o início da nossa árvore. Podemos ver isso um pouco mais claramente, uma vez que comece a adicionar mais nós nossa árvore. Deixa-me tirar-se uma nova página. 

Agora vamos desenhar uma árvore que tem 7 na raiz, e 3 dentro da criança à esquerda, e 9 no interior da criança direita. Novamente, isso é muito simples. Temos 7, desenhe um nó para o 3, um nó para 9, e eu estou indo para definir o ponteiro esquerdo criança de 7 a apontar para o nó contendo 3, e o ponteiro direito do filho do nó contendo 7 para o nó que contém 9. Agora, desde 3 e 9 não tem filhos, vamos definir todos os seus ponteiros filho para ser nulo. Aqui, a raiz da nossa árvore corresponde ao nó que contém o número 7. Você pode ver que, se tudo o que temos é um ponteiro para o nó raiz, então podemos caminhar através da nossa árvore e acessar nós tanto a criança - ambos os 3 e 9. Não há necessidade de manter ponteiros para cada nó na árvore. Tudo bem. Agora vamos adicionar um outro nó a este diagrama. Estamos indo para adicionar um nó contendo 6, e nós estamos indo para adicionar este como o filho direito do nó contendo 3. Para fazer isso, eu vou apagar esse ponteiro nulo no 3-nó e conectá-lo para apontar para o nó contendo 6. Tudo bem. 

Neste ponto, vamos falar sobre um pouco de terminologia. Para começar, a razão pela qual isso é chamado de uma árvore binária em particular é que tem dois ponteiros de crianças. Existem outros tipos de árvores que têm mais apontadores criança. Em particular, você fez um 'try' no Conjunto Problema 5. Você vai perceber que naquele tentativa, você teve 27 indicações diferentes para diferentes crianças - um para cada uma das 26 letras do alfabeto Inglês, e depois a 27 para o apóstrofo - assim, que é semelhante a um tipo de árvore. Mas aqui, já que é binário, só temos dois ponteiros da criança. 

Além deste nó raiz que falamos, Nós também estamos jogando em torno deste termo "criança". O que significa para um nó a ser um filho de outro nó? É, literalmente, significa que um nó filho é um filho de outro nó se que outro nó tem uma das suas crianças ponteiros definidas para apontar para esse nó. Para colocar isso em termos mais concretos, se 3 é apontada por um dos ponteiros criança de 7, em seguida, 3 é uma criança de 7. Se tivéssemos de descobrir o que os filhos de 7 são - bem, vemos que 7 tem um ponteiro para 3 e um ponteiro a 9, para 9 e 3 são as crianças de 7. Nove não tem filhos porque ponteiros seus filhos são nulos, e 3 tem apenas um filho, 6. Seis também não tem filhos, porque ambos os seus ponteiros são nulos, o que nós vamos chamar agora. 

Além disso, também falamos sobre os pais de um nó, e este é, como seria de esperar, o reverso desta descrição criança. Cada nó tem apenas um pai - em vez de dois, como você poderia esperar com os humanos. Por exemplo, a matriz de 3 a 7. O pai de 9 também é 7, o pai e de 6 a 3. Não há muito a ele. Nós também temos condições de falar sobre avós e netos, e, mais geralmente falamos sobre os antepassados e descendentes de um nó específico. O ancestral de um nó - ou antepassados, sim, de um nó - são todos os nós que estão no caminho da raiz para esse nó. Por exemplo, se eu estou olhando para o 6 nó, em seguida, os antepassados ​​vão ser o 3 eo 7. Os ancestrais de 9, por exemplo, são - se eu estou olhando para o nó 9 - em seguida, o antepassado de 9 é apenas 7. E descendentes são exatamente o contrário. Se eu quero olhar para todos os descendentes de 7, então eu tenho que olhar para todos os nós abaixo dela. Então, eu tenho 3, 9 e 6 todos como descendentes de 7. 

O prazo final que vamos falar é esta noção de ser um irmão. Irmãos - tipo de seguir junto com esses termos familiares - são nós que estão ao mesmo nível da árvore. Então, 3 e 9 são irmãos porque são ao mesmo nível na árvore. Ambos têm o mesmo pai, 7. O 6 não tem irmãos, porque 9 não têm filhos. E 7 não tem irmãos, porque é a raiz da nossa árvore, e há sempre apenas uma raiz. Para 7 ter irmãos não teria de ser um nó acima de 7. Teria de ser um pai de 7, caso em que 7 já não seria a raiz da árvore. Então que o pai novo, de 7 também teria de ter um filho, e que a criança seria, então, o irmão de 7. 

Tudo bem. Seguindo em frente. Quando começamos nossa discussão sobre árvores binárias, nós falamos sobre como nós íamos usá-los para ganhar uma vantagem sobre as duas matrizes e listas ligadas. E a maneira como vamos fazer isso é com esta propriedade encomenda. Dizemos que uma árvore binária é ordenada, de acordo com a especificação, se, para cada nó na nossa árvore, todos os seus descendentes à esquerda - a criança esquerda e todos os descendentes do filho esquerdo de - têm valores menores, e todos os nós da direita - o direito da criança e todos os descendentes de direito da criança de - ter nós mais do que o valor do nó atual que estamos olhando. Só para simplificar, vamos assumir que não há nós duplicados na nossa árvore. Por exemplo, nesta árvore que não estamos indo para lidar com o caso onde temos o valor 7 na raiz  e depois também temos o valor 7 em outras partes da árvore. Neste caso, você vai perceber que esta árvore é de fato ordenado. Temos o valor 7 na raiz. Tudo para a esquerda, de 7 - se eu desfazer todas essas pequenas marcas aqui - tudo para a esquerda, de 7 - a 3 e a 6 - esses valores estão a menos de 7, e tudo para a direita - o que é exatamente isso 9 - é maior do que 7. 

Esta não é a única árvore ordenados contendo estes valores, mas vamos desenhar um pouco mais deles. Há realmente um monte de maneiras que podemos fazer isso. Eu vou usar um atalho só para manter as coisas simples, onde - em vez de desenhar a todo caixas-e-flechas - Eu só vou para desenhar os números e adicionar setas conectando-los. Para começar, vamos escrever a nossa árvore original de novo, onde tivemos 7, e depois um 3, e depois 3 apontou para o direito à 6, e 7 teve um filho direito que tinha 9 anos. Tudo bem. O que é outra forma que podemos escrever esta árvore? Em vez de ter 3 ser o filho esquerdo de 7, também poderíamos ter a 6 ser o filho esquerdo de 7, e depois 3 ser o filho esquerdo do 6. Que seria parecido com esta árvore aqui onde eu tenho 7, depois 6, depois 3, e um 9 do lado direito. Nós também não temos que ter 7 como nosso nó raiz. Nós também poderíamos ter 6 como o nosso nó raiz. O que isso parece? Se vamos manter esta propriedade ordenada, tudo para a esquerda do 6 tem que ser menos do que isso. Há apenas uma possibilidade, e isso é 3. Mas, então, como o direito da criança de 6, temos duas possibilidades. Primeiro, pode-se ter a 7 e, em seguida, o 9, ou poderíamos chamar isso - como eu estou prestes a fazer aqui - onde temos o 9 como o direito da criança do 6, e em seguida a 7 como o filho esquerdo do 9. 

Agora, 7 e 6 não são os únicos valores possíveis para a raiz. Nós também poderíamos ter 3 estar na raiz. O que acontece se 3 é a raiz? Aqui, as coisas ficam um pouco mais interessante. Três não possui valores que são menos do que isto, modo que o lado esquerdo inteiro da árvore é apenas vai ser nulo. Não vai ser nada lá. Para a direita, podemos listar as coisas em ordem crescente. Poderíamos ter 3, e depois 6, depois 7, em seguida, 9. Ou, poderíamos fazer 3, depois 6, depois 9, depois 7. Ou, poderíamos fazer 3, depois 7, depois 6, depois 9. Ou, 3, 7 - na verdade, não, não podemos fazer um 7 mais. Essa é a nossa única coisa lá. Podemos fazer 9, e depois a partir do 9 podemos fazer 6 e 7. Ou, pode-se fazê-3, e depois 9, em seguida, 7, e, em seguida, 6. 

Uma coisa de chamar a atenção aqui é que estas árvores são um pouco esquisito. Em particular, se olharmos para as quatro árvores no lado direito - Vou circular-los, aqui - estas árvores parecem quase exatamente como uma lista ligada. Cada nó tem apenas um filho, e assim não temos nada disso estrutura de árvore que vemos, por exemplo,  nesta árvore um solitário aqui na parte inferior esquerda. Estas árvores são chamadas realmente degenerada árvores binárias, e nós vamos falar sobre estes mais no futuro - especialmente se você continuar a fazer cursos de ciências outros computadores. Estas árvores são degenerados. Eles não são muito úteis, pois, de fato, essa estrutura se presta  a pesquisa de vezes semelhantes aos de uma lista ligada. Nós não temos de aproveitar a memória extra - este ponteiro extra - por causa da nossa estrutura ser ruim assim. Ao invés de ir e tirar as árvores binárias que têm nove na raiz, que é o caso final que teria, estamos em vez disso, neste momento, vou falar um pouco sobre esse outro termo que usamos ao falar sobre as árvores, que é chamado a altura. 

A altura de uma árvore é a distância a partir da raiz para o nó de mais distante, ou melhor, o número de saltos que você teria que fazer a fim de começar a partir da raiz e depois acabam no nó mais distante na árvore. Se olharmos para algumas dessas árvores que temos desenhado aqui, podemos ver que, se tomarmos esta árvore no canto superior esquerdo e começamos a 3, então nós temos que fazer um salto para chegar ao 6, um segundo salto para chegar ao 7, e um terceiro hop para chegar ao 9. Então, a altura da árvore é de 3. Nós podemos fazer o mesmo exercício para as outras árvores descritas com este verde, e podemos ver que a altura de todas estas árvores é também verdade 3. Isso é parte do que os torna degenerada - que a sua altura é apenas um a menos que o número de nós em toda a árvore. Se olharmos para esta outra árvore que é cercada com vermelho, por outro lado, vemos que os nós mais distantes da folha são o 6 eo 9 - o deixa de ser os nós que não têm filhos. Assim, a fim de obter a partir do nó de raiz, quer a 6 ou a 9, temos que fazer um salto para chegar ao 7 e, em seguida, um segundo salto para chegar ao 9, e do mesmo modo, apenas o salto de um segundo a partir do 7 para obter a 6. Assim, a altura desta árvore aqui é apenas 2. Você pode voltar e fazer isso para todas as outras árvores que previamente discutido começando com o 7 e a 6, e você verá que a altura de todas as árvores também é 2. 

A razão pela qual temos falado sobre ordenou árvores binárias e por que eles são legais porque você pode procurar por elas em uma forma muito semelhante à procura de um array ordenado. Este é o lugar onde se fala de conseguir que o tempo de pesquisa melhorada sobre a lista ligada simples. Com uma lista ligada - se você quiser encontrar um elemento particular - você está no melhor vai fazer algum tipo de busca linear onde você começa no início de uma lista de e-hop um-por-um - um nó, um nó - toda a lista até encontrar o que você está procurando. Considerando que, se você tem uma árvore binária que está armazenado neste formato agradável, você pode realmente ficar mais de uma busca binária acontecendo onde você dividir e conquistar e pesquisa através da metade apropriada da árvore de cada etapa. Vamos ver como isso funciona. 

Se temos - de novo, voltando a nossa árvore original - começamos a 7, que têm 3, à esquerda, à direita 9, e sob a 3 temos a 6. Se quisermos buscar o número 6 na árvore, nós iniciar na raiz. Nós comparar o valor que estamos procurando, digamos 6, para o valor armazenado no nó que nós estamos procurando, aos 7, descobrir que 6 é de fato menor que 7, então nós mover para a esquerda. Se o valor de 6 tinha sido superior a 7, que teria lugar movido para a direita. Como sabemos que - devido à estrutura da nossa árvore binária ordenada - todos os valores de menos do que 7 vão ser armazenadas para a esquerda, de 7, não há necessidade de incomodar mesmo olhando pelo lado direito da árvore. Uma vez que se mover para a esquerda e agora estamos no nó contendo 3, nós podemos fazer isso de novo mesma comparação, onde se compara o 3 eo 6. E descobrimos que, enquanto 6 - o valor que estamos procurando - é maior do que 3, que pode ir para o lado direito do nó contendo 3. Não há lado esquerdo aqui, portanto, poderia ter ignorado isso. Mas só sabemos que porque nós estamos olhando para a própria árvore, e podemos ver que a árvore não tem filhos. 

Também é muito fácil olhar para cima 6 nesta árvore se estamos fazendo a nós mesmos como seres humanos, mas vamos acompanhar esse processo mecanicamente como um computador faria para realmente entender o algoritmo. Neste ponto, estamos agora olhando para um nó que contém 6, e nós estamos olhando para o valor 6, assim, na verdade, nós encontramos o nó apropriado. Encontramos o valor 6 em nossa árvore, e nós podemos parar a nossa busca. Neste ponto, dependendo do que está acontecendo, podemos dizer, sim, nós encontramos o valor 6, que existe na nossa árvore. Ou, se estamos planejando para inserir um nó ou fazer algo, nós podemos fazer isso neste momento. 

Vamos fazer pesquisas mais algumas só para ver como isso funciona. Vejamos o que acontece se fôssemos tentar e olhar para cima o valor 10. Se estivéssemos a olhar para cima o valor 10, que iria começar na raiz. Nós vemos que 10 é maior que 7, assim que nós mover para a direita. Teríamos a 9 e comparar 9 ao 10 e veja que 9 é realmente inferior a 10. Então, novamente, que ia tentar se mover para a direita. Mas, neste ponto, a gente percebe que estamos em um nó nulo. Não há nada lá. Não há nada que o 10 deve ser. Este é o lugar onde nós podemos relatar falha - que na verdade não há 10 na árvore. E, finalmente, vamos percorrer o caso em que estamos a tentar procurar uma na árvore. Isto é semelhante ao que acontece quando olhamos para cima 10, exceto em vez de ir para a direita, estamos indo para ir para a esquerda. Nós começamos no 7 e ver que uma é inferior a 7, de modo que se mover para a esquerda. Chegamos ao 3 e ver que 1 é menor do que 3, portanto, mais uma vez, tentar mover para a esquerda. Neste ponto temos um nó nulo, então, novamente, podemos denunciar o fracasso. 

Se você quer aprender mais sobre árvores binárias, há um monte de diversão pequenos problemas que você pode fazer com eles. Eu sugiro praticar o desenho de estes diagramas um-por-um e depois através de todos os passos diferentes, porque isso virá a super-acessível não apenas quando você está fazendo a Huffman conjunto de problemas de codificação mas também em cursos futuros - apenas aprender a tirar essas estruturas de dados e pensar os problemas com caneta e papel, ou, neste caso do iPad, e caneta. 

Neste ponto, porém, vamos passar a fazer alguma prática de codificação e realmente jogar com essas árvores binárias e ver. Vou voltar para o meu computador. Para esta parte da seção, em vez de usar CS50 CS50 Executar ou espaços, Eu vou usar o aparelho. 

Após juntamente com a especificação do conjunto de problemas, Eu vejo que eu tenho que abrir o aparelho, ir para a minha pasta Dropbox, crie uma pasta chamada Seção 7, e, então, criar um arquivo chamado binary_tree.c. Aqui vamos nós. Eu tenho o aparelho já está aberta. Eu vou puxar um terminal. Eu estou indo para ir para a pasta Dropbox, crie um diretório chamado Seção 7, e ver que é totalmente vazio. Agora vou abrir binary_tree.c. Tudo bem. Aqui vamos nós - arquivo vazio. 

Vamos voltar com a especificação. A especificação pede para criar uma nova definição de tipo para um nó de árvore binária contendo valores int - assim como os valores que tirou em nossa diagramação antes. Nós vamos usar esse clichê typedef que fizemos aqui que você deve reconhecer de Conjunto de Problemas 5 - se você fez o caminho tabela hash do programa conquistando o speller. Você também deve reconhecê-lo da seção da semana passada onde falamos sobre listas ligadas. Temos este typedef de um nó de estrutura, e demos a este nó struct este nome de nó struct previamente para que possamos, em seguida se referem a ele, uma vez que vai querer ter ponteiros nó struct como parte de nossa estrutura, mas nós então cercaram isso - ou antes, esta fechada - em um typedef de modo que, no final do código, que pode se referir a essa estrutura como apenas um nó em vez de um nó de estrutura. 

Isso vai ser muito semelhante à definição de lista individualmente-vinculado que vimos na semana passada. Para fazer isso, vamos começar por escrever o clichê. Nós sabemos que temos que ter um valor inteiro, então vamos pôr em valor int, e depois, em vez de ter apenas um ponteiro para o próximo elemento - como fizemos com isoladamente ligados listas - vamos ter ponteiros criança esquerdo e direito. Isso é muito simples também - struct filho do nó * esquerda; e struct nó filho direito *;. Cool. Isso parece um bom começo. Vamos voltar com a especificação. 

Agora precisamos declarar uma variável * mundial nó para a raiz de uma árvore. Nós vamos fazer este global como fizemos ponteiro primeiro em nossa lista ligada também global. Este foi, de modo que nas funções que escrevem não temos de manter esta passando em torno de raiz - mas vamos ver que se você quer escrever estas funções de forma recursiva, talvez seja melhor não mesmo passá-lo em torno de como uma empresa global, em primeiro lugar e, em vez inicializá-lo localmente na sua função principal. Mas, vamos fazê-lo globalmente para começar. Mais uma vez, vamos dar um par de espaços, e eu vou declarar uma raiz * nó. Só para ter certeza que eu não deixe este não inicializado, eu estou indo para defini-la igual a null. Agora, na função principal - o que vamos escrever muito rapidamente aqui - int main (int argc, const char * argv []) - e eu vou começar declarando minha matriz argv como const só assim que eu sei que esses argumentos são argumentos que eu provavelmente não querem modificar. Se eu quiser modificá-los eu provavelmente deveria estar fazendo cópias deles. Você vai ver muito isso no código. É bom de qualquer maneira. É bom deixá-lo como - omitir a const se você gostaria. Eu normalmente colocá-lo em apenas para que eu me lembrar  que eu provavelmente não querem modificar esses argumentos. 

Como sempre, eu estou indo para incluir este retorno 0 no final do principal. Aqui, vou iniciar o meu nó de raiz. Tal como está agora, eu tenho um ponteiro que está definido como nulo, por isso está apontando para o nada. A fim de realmente começar a construir o nó, Eu primeiro preciso alocar memória para ele. Eu vou fazer isso, fazendo memória na pilha usando malloc. Eu estou indo para definir raiz igual ao resultado de malloc, e eu vou usar o operador sizeof para calcular o tamanho de um nó. A razão que eu uso nó sizeof ao contrário de, digamos, fazer algo assim - malloc (4 + 4 +4) ou malloc 12 - é porque eu quero o meu código para ser o mais compatível possível. Eu quero ser capaz de tomar isso. Arquivo c, compilá-lo no aparelho, e depois compilá-lo no meu 64-bit Mac - ou sobre uma arquitectura completamente diferente - e eu quero isso tudo para o mesmo trabalho. 

Se eu estou fazendo suposições sobre o tamanho de variáveis ​​- o tamanho de um int ou o tamanho de um ponteiro - então eu também estou fazendo suposições sobre os tipos de arquiteturas em que o meu código pode compilar com êxito quando for executado. Sempre use sizeof ao contrário manualmente soma dos campos de estruturas. A outra razão é que também pode haver preenchimento que o compilador coloca na estrutura. Mesmo apenas somar os campos individuais não é algo que você normalmente quer fazer, assim, apagar a linha. Agora, para realmente inicializar este nó raiz, Eu vou ter de ligar os valores para cada um dos seus diferentes campos. Por exemplo, para o valor que eu sei que eu quero para inicializar a 7, e agora eu estou indo para definir o filho esquerdo de ser nulo e do direito da criança a ser também nulo. Ótimo! Nós fizemos isso parte da especificação. 

A especificação para baixo na parte inferior da página 3 me pede para criar três mais nós - um contendo 3, um contendo 6, e um com 9 - e, em seguida, conectá-los de modo que parece exatamente como o nosso diagrama de árvore que estávamos falando anteriormente. Vamos fazer isso bem rápido aqui. Você vai ver muito rapidamente que eu vou começar a escrever um monte de código duplicado. Eu estou indo para criar um nó * e eu vou chamá-lo de três. Eu estou indo para defini-la igual a malloc (sizeof (nó)). Eu estou indo para definir três-> valor = 3. Três -> left_child = NULL; três -> direito _child = NULL; também. Isso parece bastante semelhante ao inicializar a raiz, e isso é exatamente o que Eu vou ter que fazer se eu começar a inicializar 6 e 9 também. Eu vou fazer isso muito rapidamente aqui - na verdade, eu vou fazer uma cópia pouco e colar, e certifique-se de que eu - tudo bem.  Agora, eu tenho que copiar e eu posso ir em frente e definir esta igual a 6. Você pode ver que isso leva algum tempo e não é super-eficiente. Em apenas um pouco, vamos escrever uma função que vai fazer isso por nós. Quero substituir isso com um 9, substitua que, com um 6. 

Agora temos todos os nossos nós criado e inicializado. Temos nossa raiz definido igual a 7, ou que contém o valor 7, nossa nó contendo 3, nosso nó que contém 6, e contendo o nó 9. Neste ponto, tudo o que temos a fazer é tudo o fio para cima. A razão de eu inicializado todos os ponteiros como nulo é apenas para que eu ter certeza de que Eu não tenho os ponteiros não inicializados lá por acidente. E também porque, neste momento, eu só tenho que realmente conectar os nós para o outro - para os que estão realmente ligadas a - Eu não tenho que passar e fazer certeza de que todos os nulos estão lá nos lugares apropriados. 

A partir da raiz, eu sei que filho esquerdo da raiz é 3. Eu sei que filho direito da raiz é 9. Depois disso, o filho único outro que me resta para se preocupar É direito da criança 3, que é 6. Neste ponto, tudo parece muito bom. Nós vamos excluir algumas dessas linhas. Agora tudo parece muito bom. Vamos voltar para a nossa especificação e ver o que nós temos que fazer a seguir. 

Neste ponto, temos de escrever uma função chamada "contém" com um protótipo de 'contém bool (valor inteiro). E este contém função vai retornar true  se a árvore apontada por nossa variável raiz global  contém o valor passado para a função e falso caso contrário. Vamos em frente e fazer isso. Este vai ser exatamente como a pesquisa que fizemos com a mão no iPad um pouco atrás. Vamos zoom em um pouco e vá para cima. Nós vamos colocar esta função logo acima a nossa função principal de modo que não temos que fazer qualquer tipo de prototipagem. Então, bool contém (valor inteiro). Lá vamos nós. Não é a nossa declaração clichê. Só para ter certeza que isso vai compilar, Eu estou indo para ir em frente e configurá-lo igual a retornar falso. Neste momento esta função só não vai fazer nada e sempre relatam que o valor que estamos procurando não está na árvore. 

Neste ponto, é provavelmente uma boa idéia - desde que escrevi um monte de código e não temos sequer tentou testá-lo ainda - para se certificar de que tudo compila. Há um par de coisas que temos que fazer para ter certeza de que isso realmente vai compilar. Primeiro, veja se estamos usando todas as funções em qualquer biblioteca que ainda não foram incluídas. As funções que usamos até agora são malloc, e então nós também vindo a utilizar este tipo - este tipo fora do padrão chamado 'bool' - que está incluído no arquivo de cabeçalho padrão bool. Nós definitivamente queremos incluir bool.h padrão para o tipo bool, e nós também queremos # include lib.h padrão para as bibliotecas padrão que incluem malloc, e livre, e tudo isso. Então, zoom out, vamos parar de fumar. Vamos tentar e ter certeza de que isso realmente fez a compilação. Vemos que ele faz, então estamos no caminho certo. 

Vamos abrir binary_tree.c novamente. Ele compila. Vamos descer e ter certeza de que vamos inserir algumas chamadas para nossa função contém - só para ter certeza que isso é tudo muito bem. Por exemplo, quando fizemos algumas pesquisas em nossa árvore mais cedo, tentamos procurar os 6 valores em 10, e 1, e nós sabíamos que era 6 na árvore, 10 não estava na árvore, e 1 não estava na árvore ou. Vamos usar as chamadas de amostras, como forma de descobrir se ou não nossa função contém está funcionando. A fim de fazer isso, eu vou usar a função printf, e nós estamos indo para imprimir o resultado da chamada para contém. Eu vou colocar em uma string "contém (% d) = porque  vamos ligar o valor que vamos procurar, e =% s \ n "e usar isso como nossa seqüência de formato. Nós só vamos ver - literalmente imprimir na tela - o que parece ser uma chamada de função. Isto não é realmente a chamada de função.  Esta é apenas uma seqüência projetado para parecer com uma chamada de função. 

Agora, vamos ligar os valores. Nós vamos tentar contém em 6, e então o que vamos fazer aqui é usar o operador ternário. Vamos ver - contém 6 - assim, agora eu continha 6 e se contém 6 é verdadeira, a string que vamos enviar para o caráter de formato% s vai ser a string "true". Vamos rolar mais um pouco. Caso contrário, queremos enviar a string "false" se contém seis retornos falsos. Isto é um pouco pateta bonito, mas eu acho que eu poderia muito bem ilustrar o que o operador ternário parece, uma vez que não vi ele por algum tempo. Esta será uma forma agradável, útil para descobrir se a nossa função contém está funcionando. Eu estou indo para rolar de volta para a esquerda, e eu vou copiar e colar essa linha algumas vezes. Ele mudou alguns desses valores ao redor, por isso este vai ser um, e isso vai ser 10. 

Neste ponto, temos uma função contém agradável. Nós temos alguns testes, e vamos ver se esta tudo funciona. Neste ponto, tenho escrito alguns códigos mais. Tempo para sair fora e certifique-se de que tudo ainda compila. Saia fora, e agora vamos tentar fazer árvore binária novamente. Bem, parece que temos um erro, E nós temos esta declarar explicitamente a função de biblioteca printf. Parece que temos que ir e # include standardio.h. E, com isso, tudo deve compilar. Estamos todos bem. Agora vamos tentar correr árvore binária e ver o que acontece. Aqui estamos nós,. / Binary_tree, e vemos que, como se esperava - porque não têm implementado contém ainda, ou melhor, acabamos de colocar no return false - vemos que ele está apenas retornando falso para todos eles, Então isso é tudo trabalho para a maior parte bastante bem. 

Vamos voltar e realmente implementar contém neste momento. Eu estou indo para rolar para baixo, aumentar o zoom, e - lembre-se, o algoritmo que usamos foi que começou no nó raiz e em cada nó que encontramos, fazemos uma comparação, e com base em que a comparação que quer passar para o filho esquerdo ou direito para a criança. Isso vai parecer muito semelhante ao código de busca binária que escrevemos no início do prazo. Quando começamos, nós sabemos que queremos segurar o nó atual que estamos olhando, eo nó atual vai ser inicializado para o nó raiz. E agora, vamos continuar com a árvore, e lembre-se que a nossa condição de parar -  quando efectivamente trabalhadas através do exemplo à mão - foi quando encontrou um nó nulo, não quando olhamos para uma criança nulo, mas quando nós realmente mudou-se para um nó na árvore e descobriu que estamos em um nó nulo. Nós estamos indo para iterar até atu não é igual a nulo. E o que é que vamos fazer? Nós vamos testar se (cur -> valor valor ==), então sabemos que temos na verdade, o nó que estamos procurando. Então, aqui, nós podemos retornar true. Caso contrário, queremos para ver se ou não o valor é menor que o valor. Se o valor do nó atual é menor do que o valor que está procurando, vamos passar para a direita. Então, cur = atual -> right_child, e caso contrário, nós estamos indo para mover para a esquerda. atu atu = -> left_child;. Muito simples. 

Você provavelmente reconhece o laço que se parece muito semelhante a este de busca binária no início do prazo, exceto em seguida estávamos lidando com baixa, média e alta. Aqui, só temos de olhar para um valor atual, por isso é bom e simples. Vamos ter certeza que esse código está funcionando. Primeiro, certifique-se que compila. Parece que ele faz. Vamos tentar executá-lo. E, de fato, ela mostra tudo o que esperávamos. Ele encontra 6 na árvore, não encontra 10, porque 10 não está na árvore, e não se encontrar uma ou porque não é uma também na árvore. Coisas legais. 

Tudo bem. Vamos voltar para a nossa especificação e ver o que está próximo. Agora, ele quer adicionar nós mais alguns para a nossa árvore. Ele quer adicionar 5, 2 e 8, e certifique-se de que a nossa contém código ainda funciona como o esperado. Vamos fazer isso. Neste ponto, ao invés de fazer a cópia irritante e colar novamente, vamos escrever uma função para realmente criar um nó. Se rolar todo o caminho para o principal, vemos que temos vindo a fazer esta código muito semelhante e outra vez cada vez que queremos criar um nó. 

Vamos escrever uma função que realmente construir um nó para nós e para devolvê-lo. Eu vou chamá-lo build_node. Eu vou construir um nó com um valor específico. Zoom aqui. A primeira coisa que vou fazer é, na verdade, criar espaço para o nó na pilha. Assim, o nó * n = malloc (sizeof (nó)); n - valor> = valor; e depois aqui, eu estou indo só para inicializar todos os campos para valores apropriados. E no final, vamos voltar nossa nó. Tudo bem. Uma coisa a notar é que esta função aqui vai retornar um ponteiro para a memória que foi alocada montão. O que é legal sobre isso é que este nó agora - temos que declará-lo na pilha porque, se declarou na pilha não seria capaz de fazê-lo nesta função como esta. Que a memória iria fora do escopo e seria inválido se tentamos acessá-lo mais tarde. Uma vez que estamos declarando pilha alocada de memória, vamos ter que cuidar de libertar-lo mais tarde para o nosso programa para não vazar qualquer memória. Fomos punting em que para qualquer outra coisa no código apenas por causa da simplicidade na época, mas se você já escrever uma função parecida com esta onde você tem - alguns chamam de um malloc ou realloc dentro - você quer ter certeza de que você colocar algum tipo de comentário por aqui que diz: ei, você sabe, retorna um nó pilha alocada inicializado com o valor passado-in. E então você quer ter certeza de que você colocar em algum tipo de nota que diz o chamador deve liberar a memória voltou. Dessa forma, se alguém nunca vai e usa essa função, eles sabem que o que recebem de volta do que a função em algum ponto terá de ser libertado. 

Assumindo que tudo está bem e bom aqui, podemos ir para baixo em nosso código e substituir todas estas linhas aqui com chamadas para nossa função nó de construção. Vamos fazer isso muito rapidamente. A única parte que não estamos indo para substituir é essa parte aqui na parte inferior onde realmente conectar os nós para apontar para o outro, porque que não podemos fazer em nossa função. Mas, vamos fazer raiz = build_node (7); nó * três = build_node (3); nó * seis = build_node (6); nó * nove = build_node (9);. E agora, nós também queria adicionar nós para - nó * cinco = build_node (5); nó * oito = build_node (8); e qual foi o outro nó? Vamos ver aqui. Queríamos também adicionar um 2 - nó * dois = build_node (2);. Tudo bem. Neste ponto, sabemos que temos o 7, o 3, o 9, e os 6 todo ligado de forma adequada, mas que sobre o 5, o 8, eo 2? Para manter tudo em ordem apropriada, sabemos que criança direita três é 6. Então, se nós vamos adicionar a 5, a 5 também pertence ao lado direito da árvore dos quais 3 é a raiz, assim como 5 pertence a criança esquerda de 6. Nós podemos fazer isto por dizer, seis -> left_child = cinco; e, em seguida, a 8 pertence como o filho esquerdo de 9, de modo nove -> left_child = oito; e 2 é o filho esquerdo de três, para que possamos fazer isso aqui - te -> left_child = dois;. Se você não chegou a acompanhar, juntamente com isso, eu sugiro que você retirá-la sozinho. 

Tudo bem. Vamos salvar este. Vamos sair e se certificar de que compila, e então nós podemos adicionar em nossas chamadas contém. Parece que tudo ainda compila. Vamos entrar e adicionar em algumas contém chamadas. Mais uma vez, eu vou fazer um pouco de copiar e colar. Agora vamos procurar 5, 8 e 2. Tudo bem. Vamos ter certeza de que tudo isso parece ser bom ainda. Ótimo! Salvar e sair. Agora vamos fazer, compilar, e agora vamos executar. A partir dos resultados, parece que tudo está funcionando muito agradável e bem. Ótimo! Então, agora nós temos nossos contém função escrito. Vamos seguir em frente e começar a trabalhar em como inserir nós na árvore uma vez que, como estamos fazendo agora, as coisas não são muito bonitas. 

Se voltarmos para a especificação, que nos pede para escrever uma função chamada inserir - novamente, retornando um bool para se ou não poderíamos inserir o nó na árvore - e, em seguida, o valor para inserir na árvore é especificado como o único argumento para a nossa função de inserção. Voltaremos verdade se poderia de fato inserir o valor do nó contendo na árvore, o que significa que, um, tinha memória suficiente, e dois, que o nó já não existe na árvore desde então - Lembre-se, nós não vamos ter valores duplicados na árvore, só para fazer as coisas simples. Tudo bem. De volta para o código. Abra-se. Zoom em um pouco, em seguida, vá para baixo. Vamos colocar a função de inserção logo acima os contém. Mais uma vez, ele vai ser chamado de inserção bool (valor inteiro). Dê-lhe um pouco mais espaço, e então, como um padrão, vamos colocar em return false no final. Agora, na parte inferior, vamos em frente e em vez de construir manualmente os nós na principal nós mesmos e fiação-los para apontar para o outro como nós estamos fazendo, vamos confiar na nossa função de inserção para fazer isso. Nós não vamos contar com nossa função de inserção para construir a árvore inteira a partir do zero ainda, mas nós vamos nos livrar dessas linhas - vamos comentar as linhas - que construir os 5 nós, 8 e 2. E em vez disso, vamos inserir chamadas para nossa função de inserção para ter certeza de que isso realmente funciona. Aqui vamos nós. 

Agora que já comentou estas linhas. Nós só temos 7, 3, 9 e 6 em nossa árvore neste momento. Para se certificar de que tudo está funcionando, podemos diminuir o zoom, fazer a nossa árvore binária, executá-lo, e podemos ver que contém agora está nos dizendo que está totalmente certo - 5, 8, e 2 já não se na árvore. Volte para o código, e como é que vamos inserir? Lembre-se o que fizemos quando estávamos realmente a inserção de 5, 8 e 2 anteriormente. Nós jogamos esse jogo Plinko onde começamos na raiz, desceu a uma árvore por um por um até encontrarmos a brecha adequado, e, então, com fio no nó no local apropriado. Nós vamos fazer a mesma coisa. Isto é basicamente como escrever o código que usamos no contém função para encontrar o local onde o nó deve ser, e então nós apenas estamos indo para inserir o nó ali mesmo. Vamos começar a fazer isso. 

Portanto, temos um nó * cur = raiz; nós apenas estamos indo para acompanhar o contém código até descobrir que ele não funciona muito bem para nós. Nós vamos passar pela árvore, enquanto o elemento atual não é nulo, e se encontrar o valor que atu é igual ao valor que estamos tentando inserir - bem, este é um dos casos em que não poderia realmente inserir o nó para a árvore, porque isso significa que temos um valor duplicado. Aqui nós estamos indo realmente para retornar falso. Agora outra coisa, se o valor atu é menor do que o valor, agora sabemos que vamos passar para a direita  porque o valor pertence a metade direita da árvore cur. Caso contrário, nós estamos indo para mover para a esquerda. Isso é basicamente nossos contém função ali. 

Neste ponto, uma vez que tenhamos concluído esta loop while, nosso ponteiro atu vai estar apontando para null se a função não tenha retornado. Estamos, portanto, ter cur no local onde deseja inserir o novo nó. O que resta a ser feito é realmente construir o novo nó, o que podemos fazer muito facilmente. Podemos usar o nosso super-acessível função do nó de construção, e algo que não fizemos antes - que apenas um tipo de levou para concedido, mas agora vamos fazer só para ter certeza - vamos testar para ter certeza de que o valor retornado pelo novo nó foi realmente não nulo, porque nós não queremos começar a acessar a memória se ele é nulo. Nós podemos testar para ter certeza de que novo nó não é igual a nulo. Ou em vez disso, podemos apenas ver se ele realmente é nulo, e se é nulo, então podemos simplesmente retornar falso cedo. 

Neste ponto, é preciso ligar novo nó no seu local adequado na árvore. Se olharmos para trás, principal e onde estávamos realmente fiação em valores antes, vemos que a forma como nós estávamos fazendo isso quando queria colocar 3 na árvore foi acessamos o filho esquerdo de raiz. Quando colocamos nove na árvore, nós tivemos que acessar o filho direito da raiz. Tínhamos que ter um ponteiro para o pai, a fim de colocar um novo valor para a árvore. Rolando de volta para inserir, que não vai muito trabalhar aqui porque não temos um ponteiro pai. O que se quer ser capaz de fazer é, neste ponto, verificar o valor do pai e ver - bem, caramba, se o valor do pai é menor do que o valor atual, então a criança o direito dos pais deve ser o novo nó; caso contrário, filho esquerdo do pai deve ser o novo nó. Mas, não temos este ponteiro pai ainda. 

A fim de obtê-lo, nós vamos mesmo ter que segui-lo como nós atravessamos a árvore e encontrar o local apropriado no nosso loop acima. Podemos fazer isso por rolagem de volta até o topo da nossa função de inserção e acompanhamento de outra variável ponteiro chamado de pai. Nós vamos defini-lo igual a nulo, inicialmente, e então cada vez que passar pela árvore, vamos definir o ponteiro pai para coincidir com o ponteiro atual. Definir pai igual a cur. Desta forma, cada vez que passar, vamos garantir que, como o ponteiro atual é incrementado o ponteiro pai segue - apenas um nível mais elevado do que o ponteiro atual na árvore. Isso tudo parece muito bom. 

Eu acho que a única coisa que vamos querer ajustar é esta compilação nulo nó de retorno. A fim de obter construir nó realmente com sucesso retornar nulo, nós vamos ter que modificar esse código, porque aqui, nós nunca testados para garantir que malloc retornou um ponteiro válido. Assim, se (n = NULL!), Em seguida, - se malloc retornou um ponteiro válido, então vamos inicializá-lo; caso contrário, vamos retornar e que vai acabar retornando nulo para nós. Agora tudo parece muito bom. Vamos ter certeza que isso realmente compila. Fazer árvore binária, e oh, nós temos algumas coisas acontecendo aqui. 

Nós temos uma declaração implícita da função construir nó. Novamente, com estes compiladores, vamos começar no topo. O que tem de dizer é que eu estou chamando construir nó antes de eu realmente declarado. Vamos voltar ao código muito rapidamente. Rolar para baixo, e com certeza, a minha função de inserção é declarado acima da função do nó de construção, mas eu estou tentando usar construir nó dentro de inserção. Eu vou entrar e cópia - e depois cole o caminho de construção função do nó aqui no topo. Dessa forma, espero que funcione. Vamos dar este outro ir. Agora tudo compila. Tudo é bom. 

Mas neste momento, não temos realmente chamou a função de inserção. Nós só sabemos que ele compila, então vamos entrar e colocar algumas chamadas dentro Vamos fazer isso em nossa função principal. Aqui, nós comentada 5, 8 e 2, e, depois, não conectá-los aqui. Vamos fazer algumas chamadas para inserir, e vamos também usar o mesmo tipo de material que usamos quando fizemos essas chamadas printf para ter certeza de que tudo que se inserir corretamente. Vou copiar e colar, e em vez de contém vamos fazer de inserção. E, em vez de 6, 10 e 1, vamos usar 5, 8 e 2. Isto deve esperançosamente inserir 5, 8, e dois para a árvore. Compilar. Tudo é bom. Agora vamos rodar o nosso programa. 

Tudo voltou falso. Então, 5, 8 e 2 não foi, e parece que contém não achou nenhuma delas. O que está acontecendo? Vamos diminuir o zoom. O primeiro problema foi que inserir parecia retornar falso, e parece que isso é porque saímos na nossa chamada de retorno falso, e nós nunca realmente retornou verdadeiro. Podemos configurar isso. O segundo problema é que, agora mesmo que fazer - salvar este, parar isso, executar o make novamente, tê-lo compilar, em seguida, executá-lo - vemos que algo mais aconteceu aqui. O 5, 8, e 2 foram ainda nunca encontrada na árvore. Então, o que está acontecendo? 

Vamos dar uma olhada nisso no código. Vamos ver se podemos descobrir isso. Começamos com o pai não ser nulo. Nós ajustamos o ponteiro atual igual ao ponteiro raiz, e nós vamos trabalhar o nosso caminho através da árvore. Se o nó atual não é nulo, então sabemos que podemos mover um pouco para baixo. Montamos nosso ponteiro pai para ser igual ao atual do ponteiro, verificou o valor - se os valores são os mesmos que retornou falso. Se os valores são menos nos mudamos para a direita; caso contrário, mudou-se para a esquerda. Então, vamos construir um nó. Eu vou ampliar um pouco. E aqui, nós vamos tentar conectar os valores a ser o mesmo. O que está acontecendo? Vamos ver se possivelmente Valgrind pode nos dar uma dica. 

Eu gosto de usar Valgrind só porque Valgrind muito rapidamente executado e diz-lhe se existem erros de memória. Quando corremos Valgrind no código, como você pode ver hit here--Valgrind./binary_tree--and direito entrar. Você vê que não tem nenhum erro de memória, por isso parece que está tudo bem até agora. Temos alguns vazamentos de memória, que sabemos, porque não somos acontecendo para libertar qualquer um dos nossos nós. Vamos tentar executar GDB para ver o que está realmente acontecendo. Nós vamos fazer gdb. / Binary_tree. Ele iniciou-se muito bem. Vamos definir um ponto de ruptura na inserção. Vamos correr. Parece que nós nunca realmente chamado de inserção. Parece que o problema era só que quando eu mudei para cá em principal - todas essas chamadas de printf contém - Eu nunca realmente mudou destes para chamar de inserção. Agora vamos dar uma chance. Vamos compilar. Tudo parece bom lá. Agora vamos tentar executá-lo, ver o que acontece. Tudo bem! Tudo parece muito bom lá. 

A última coisa a se pensar é, existem casos de ponta a esta inserção? E acontece que, bem, o caso de borda que é sempre interessante para pensar sobre é, o que acontece se a sua árvore está vazia e você chamar essa função de inserção? Será que vai funcionar? Bem, vamos dar uma chance. - Binary_tree c. - A maneira que nós vamos testar este é, estamos indo para ir até a nossa função principal, e ao invés de fiação esses nós se assim, nós apenas estamos indo para comentar a coisa toda, e em vez de fiação até os nós de nós mesmos, nós podemos realmente ir em frente e apagar tudo isso. Nós vamos fazer tudo o que uma chamada para inserir. Então, vamos fazer - em vez de 5, 8 e 2, vamos inserir 7, 3 e 9. E então nós também deseja inserir 6 também. Salvar. Sair. Fazer árvore binária. Tudo compila. Nós podemos apenas executá-lo como está e ver o que acontece, mas também vai ser muito importante para se certificar de que não temos quaisquer erros de memória, uma vez que este é um dos nossos casos de ponta que nós conhecemos. 

Vamos ter certeza de que ele funciona bem sob Valgrind, o que faremos simplesmente executando Valgrind. / binary_tree. Parece que, de facto, um erro de um contexto - temos essa falha de segmentação. O que aconteceu? Valgrind realmente nos diz onde está. Zoom para fora um pouco. Parece que está acontecendo em nossa função de inserção, onde temos uma leitura inválido de tamanho 4 a inserção, linha 60. Vamos voltar e ver o que está acontecendo aqui. Diminuir o zoom muito rápido. Eu quero ter certeza de que ele não vai para a borda da tela, para que possamos ver tudo. Puxe que em um pouco. Tudo bem. Rolar para baixo, e que o problema está aqui. O que acontece se nós descermos e nosso nó atual já é nulo, nosso nó pai é nulo, por isso, se olhamos para o topo, aqui - se isso nunca loop while realmente executa porque o nosso valor atual é nulo - a nossa raiz é nula para atu é nulo - então nunca nosso pai é configurado para atu ou para um valor válido, assim, o pai também será nulo. Precisamos lembrar para verificar que no momento em que chegar aqui, e começar a acessar valor do pai. Então, o que acontece? Bem, se o pai é nulo - if (pai == NULL) -, então nós sabemos que não deve haver qualquer coisa na árvore. Devemos estar tentando inseri-lo na raiz. Podemos fazer isso definindo apenas a raiz igual ao novo nó. Então, neste ponto, nós realmente não quero passar por essas outras coisas. Em vez disso, aqui, nós podemos fazer uma ou outra coisa-se-else, ou podemos combinar tudo aqui em uma outra pessoa, mas aqui vamos usar mais e fazê-lo dessa maneira. Agora, vamos testar para ter certeza de que o nosso pai não é nulo antes, então realmente tentando acessar seus campos. Isso vai nos ajudar a evitar a falha de segmentação. Então, nós paramos, zoom out, compilar, executar. 

Sem erros, mas ainda temos um monte de vazamentos de memória porque não libertar qualquer um dos nossos nós. Mas, se formos até aqui e vá para a impressão, vemos que, bem, parece que todos os nossos inserções foram retornando verdadeiro, o que é bom. As pastilhas são todas verdadeiras, e depois as chamadas apropriadas contém também são verdadeiras. 

Bom trabalho! Parece que temos escrito com sucesso inserção. Isso é tudo o que temos para esta semana Especificação conjunto de problemas. Um desafio divertido de pensar é como você realmente ir em e livre de todos os nós desta árvore. Podemos fazer um certo número de maneiras diferentes, mas vou deixar isso para você experimentar, e como um desafio divertido, tentar e ter certeza de que você pode ter certeza que este relatório Valgrind retorna sem erros e sem vazamentos. 

Boa sorte no jogo desta semana problema Huffman, e vamos ver semana que vem! [CS50.TV]