[Powered by Google Translate] [Seção 7: Mais Confortável]
[Rob Bowden] [Harvard University]
[Esta é CS50] [CS50.TV]
Tudo bem. Então, como eu disse no meu e-mail,
isso vai ser uma seção binário-tree-intensivo.
Mas não há que muitas questões.
Então, nós estamos indo para tentar extrair de cada pergunta
e entrar em detalhes dolorosa de todas as melhores maneiras de fazer as coisas.
Assim, logo no início, passamos por desenhos de amostragem de árvores binárias e outras coisas.
Então, aqui, "Lembre-se que uma árvore binária tem nós semelhantes aos de uma lista ligada,
exceto em vez de um ponteiro, há duas: uma para "criança" à esquerda
e um para a "criança" certo ".
Assim, uma árvore binária é como uma lista ligada,
exceto a estrutura vai ter dois ponteiros.
Há árvores trinário, que vão ter três ponteiros,
existem N-ary árvores, que só tem um ponteiro genérico
que então você tem que malloc para ser grande o suficiente para ter
ponteiros suficientes para todas as crianças possíveis.
Então árvore binária só acontece de ter um número constante de dois.
Se você quiser, você pode dar uma lista encadeada como uma árvore unário,
mas eu não acho que ninguém chama isso.
"Desenhe um diagrama de caixas-e-flechas de um nó de árvore binária
contendo o número favorito de Nate, 7, em que cada ponteiro criança é nulo. "
Modo para iPad.
>> Vai ser bastante simples.
Nós só vamos ter um nó, eu vou desenhá-lo como um quadrado.
E eu vou chamar os valores aqui.
Portanto, o valor deverá ser aqui,
e aqui nós vamos ter o ponteiro para a esquerda à esquerda e à direita o ponteiro à direita.
E é muito assim convenção para chamá-lo de esquerda e direita, os nomes de ponteiro.
Ambos vão ser nulo.
Isso só vai ser nulo, e que só vai ser nulo.
Okay. Então, de volta para aqui.
"Com uma lista ligada, tínhamos apenas para armazenar um ponteiro
para o primeiro nó na lista para lembrar toda a lista ligada, ou toda a lista.
Da mesma forma, com árvores, só temos que armazenar um ponteiro
a um único nó, a fim de lembrar a árvore inteira.
Este nodo é o calle "raiz" da árvore.
Construir sobre o seu diagrama de antes ou desenhar um novo
de tal forma que você tem uma representação caixas-e-flechas de uma árvore binária
com o valor 7, em seguida, 3 no lado esquerdo,
e depois 9, à direita, e em seguida 6, à direita da extremidade 3 ".
Vamos ver se eu consigo me lembrar de tudo isso na minha cabeça.
Portanto, esta vai ser a nossa raiz aqui.
Nós vamos ter algum ponteiro em algum lugar, algo que chamaremos de raiz,
e ele está apontando para esse cara.
Agora, para fazer um novo nó,
o que temos, três à esquerda?
Assim, um novo nó com 3, e aponta inicialmente nula.
Vou colocar N.
Agora nós queremos fazer com que vá para a esquerda, de 7.
Então nós mudar este ponteiro para apontar agora para esse cara.
E nós fazemos o mesmo. Queremos um 9 aqui
que, inicialmente, apenas diz nulo.
Nós vamos mudar este ponteiro ponto, a 9,
e agora queremos colocar 6 à direita de 3.
Então, ele vai - fazer um 6.
E esse cara vai apontar lá.
Okay. Então, isso é tudo o que nos pede para fazer.
>> Agora vamos passar por cima de alguma terminologia.
Nós já falamos sobre como a raiz da árvore é o nó mais alto da árvore.
A uma contendo 7. Os nós na parte inferior da árvore são chamados as folhas.
Qualquer nó que só tem nulo como seus filhos é uma folha.
Por isso, é possível, se a nossa árvore binária é apenas um único nó,
que uma árvore é uma folha, e é isso.
"O 'altura' da árvore é o número de saltos que você tem que fazer
para obter a partir do topo de uma folha. "
Nós vamos entrar, em um segundo, a diferença
entre árvores binárias balanceadas e não balanceadas,
mas, por agora, a altura total da árvore
Eu diria que é 3, embora, se você contar o número de saltos
você tem que fazer a fim de obter a 9, então é realmente apenas uma altura de 2.
Agora esta é uma árvore binária não balanceada,
mas nós conversamos sobre equilibrada quando se chega a ser relevante.
Então agora podemos falar sobre nós em uma árvore, em termos
em relação aos outros nós na árvore.
Portanto, agora temos os pais, filhos, irmãos, antepassados ​​e descendentes.
São sentido bastante comum, o que eles significam.
Se perguntarmos - É pais.
Então, o que é o pai de 3?
[Os alunos] 7. Sim >>. O pai está indo só para ser o que aponta para você.
Então, o que são as crianças de 7?
[Os alunos] 3 e 9. Sim >>.
Observe que "crianças" significa literalmente filhos,
para 6 não se aplica, porque é como um neto.
Mas, então, se formos descendentes, então o que são os descendentes de 7?
[Os alunos] 3, 6 e 9. Sim >>.
Os descendentes do nó raiz vai ser tudo na árvore,
exceto, talvez, o nó de raiz em si, se você não quer considerar que um descendente.
E, finalmente, os ancestrais, por isso é a direção oposta.
Então, quais são os ancestrais de 6?
[Os alunos] 3 e 7. Sim >>. 9 não está incluído.
É apenas a linhagem direta de volta à raiz
vai ser seus antepassados.
>> "Dizemos que uma árvore binária é" ordenada ", se para cada nó na árvore,
todos os seus descendentes no lado esquerdo têm valores menores
e todos os da direita têm valores maiores.
Por exemplo, a árvore acima é ordenada, mas não é o único arranjo possível ordenada. "
Antes de chegarmos a isso,
uma árvore binária ordenada é também conhecido como uma árvore de pesquisa binária.
Aqui nós acontecer de ser chamando de uma árvore binária ordenada,
mas eu nunca ouvi-lo chamado de uma árvore binária ordenada antes,
e em um quiz que são muito mais propensos a colocar árvore de busca binária.
Eles são uma ea mesma coisa,
e é importante que você reconhece a distinção entre árvore binária e árvore de busca binária.
Uma árvore binária é apenas uma árvore que aponta para duas coisas.
Cada nó aponta para duas coisas.
Não há raciocínio sobre os valores que ele aponta para.
Assim como aqui, já que é uma árvore de busca binária,
nós sabemos que se vá para a esquerda, de 7,
em seguida, todos os valores que podem possivelmente alcançar
indo deixou de 7 tem que ser inferior a 7.
Note-se que todos os valores menores do que 7 são 3 e 6.
Essas são todas para a esquerda, de 7.
Se formos para a direita, de 7, tudo tem que ser maior do que 7,
para 9 é para a direita, de 7, por isso estamos bem.
Este não é o caso de uma árvore binária,
para uma árvore binária regulares, podemos ter apenas três no topo, 7 para a esquerda,
9 para a esquerda, de 7, não há nenhuma ordenação de valores, em absoluto.
Agora, nós realmente não vai fazer isso porque é tedioso e desnecessário,
mas "tentar desenhar como muitas árvores ordenadas como você pode pensar
utilizando os números 7, 3, 9, e 6.
Quantos arranjos distintos existem? O que é a altura de cada um? "
>> Nós vamos fazer um casal, mas a idéia principal é,
isto é, de modo algum uma representação singular de uma árvore binária contendo esses valores.
Tudo o que precisamos é de uma árvore binária que contém 7, 3, 6 e 9.
Outra possível válida seria a raiz é 3,
vá para a esquerda e é 6, vá para a esquerda e é 7,
para a esquerda e é 9.
Que é uma árvore de pesquisa binária perfeitamente válida.
Não é muito útil, porque é como uma lista ligada
e todos esses ponteiros são apenas nulo.
Mas é uma árvore válido. Sim?
[Estudante] Não os valores têm que ser maior do lado direito?
Ou isso é -? Estes >> eu quis ir por outro caminho.
Há também - sim, vamos mudar isso.
9, 7, 6, 3. Boa captura.
Ele ainda tem que obedecer o que uma árvore de busca binária é suposto fazer.
Assim, tudo o que o lado esquerdo tem de ser menor que qualquer dado nó.
Nós poderíamos apenas mudar, por exemplo, este 6 e colocá-lo aqui.
Não, não podemos. Por que eu continuo fazendo isso?
Vamos fazer - aqui é 6, aqui é 7, 6 pontos a 3.
Esta ainda é uma árvore de busca binária válido.
O que é errado se eu - vamos ver se consigo chegar a um acordo.
Sim, está bem. Então, o que está errado com esta árvore?
Eu acho que eu já lhe deu uma dica de que há algo de errado com ele.
Por que eu continuo fazendo isso?
Okay. Isso parece razoável.
Se olharmos para cada nó, como o 7, em seguida, para a esquerda da Fig. 7 é uma 3.
Portanto, temos três, a única coisa para a direita de 3 é um 6.
E se você olhar para 6, a coisa à direita do 6 é um 9.
Então, por que isso não é uma árvore de busca binária válida?
[Os alunos] 9 é ainda para a esquerda, de 7. Sim >>.
Deve ser verdade que todos os valores que podem ser possivelmente alcançar, indo para a esquerda, de 7 estão a menos de 7.
Se ir para a esquerda, de 7, temos a 3 e ainda podemos chegar a 6,
ainda podemos chegar a 9, mas por ter passado menos de 7,
não deve ser capaz de chegar a um número que é maior do que 7.
Então isso não é uma árvore de busca binária válido.
>> Meu irmão realmente tinha uma pergunta da entrevista
que era basicamente isso, código apenas algo para validar
se uma árvore é uma árvore de busca binária,
e então a primeira coisa que ele fez foi apenas verificar para ver
se a esquerda e direita estão corretas, e depois repetir lá em baixo.
Mas você não pode simplesmente fazer isso, você tem que manter o controle
do fato de que, agora que eu fui deixado de 7,
tudo neste sub deve ser inferior a 7.
O algoritmo correto precisa manter o controle
dos limites que os valores podem eventualmente caem dentro
Nós não vamos passar por todos eles.
Há uma relação de recorrência agradável,
embora não se tenha chegado a esses, ou não vamos chegar a esses,
definir quantos realmente são.
Portanto, há 14 deles.
A idéia de como você faria isso matematicamente é como,
você pode escolher qualquer um única de ser o nó raiz,
e então se eu pegar de 7 a ser o nó raiz,
em seguida, há, por exemplo, alguns números que podem ir ser meu nó esquerdo,
e há alguns números que pode ser meu nó direito,
mas se eu tiver n números totais, o montante que pode ir para a esquerda
mais o montante que pode ir para a direita é n - 1.
Assim, os números restantes, eles têm que ser capazes de ir, quer para a esquerda ou para a direita.
Parece difícil que, se eu colocar 3 primeiro, então tudo tem que ir para a esquerda,
mas se eu colocar 7, então algumas coisas podem ir a esquerda e algumas coisas podem ir para a direita.
E por '3 'primeiro eu queria dizer tudo pode ir para a direita.
É realmente, você só tem que pensar nisso como,
quantas coisas podem ir no próximo nível da árvore.
E vem a ser 14, ou você pode desenhar todos eles,
e então você vai ter 14.
>> Voltando aqui,
"Ordenou árvores binárias são legais porque podemos procurar por eles
de uma forma muito semelhante à procura de um array ordenado.
Para isso, vamos começar na raiz e trabalhar nossa maneira para baixo da árvore
para folhas, verificando os valores de cada nó contra os valores que estamos procurando.
Se o valor do nó atual é menor do que o valor que está procurando,
você vai ao lado direito da criança do nó.
Caso contrário, você vai para o filho esquerdo do nó.
Em algum momento, você quer encontrar o valor que você está procurando, ou você vai correr em um nulo,
indicando o valor não está na árvore. "
Eu tenho que redesenhar a árvore que tínhamos antes, que vai levar um segundo.
Mas queremos olhar para cima se 6, 10, e um está na árvore.
Então o que era, 7, 9, 3, 6. Okay.
Os números que você quer olhar para cima, queremos olhar para cima 6.
Como funciona esse algoritmo?
Bem, também temos alguns ponteiro raiz para a nossa árvore.
E nós ir à raiz e dizer, é este valor igual ao valor que estamos procurando?
Então, nós estamos olhando para 6, por isso não é igual.
Então, continue indo, e agora podemos dizer, ok, então 6 é inferior a 7.
Isso quer dizer que nós queremos ir para a esquerda, ou queremos ir para a direita?
[Estudante] Esquerda. Sim >>.
É muito mais fácil, tudo que você tem a fazer é tirar um nó possível da árvore
e então você não - em vez de tentar pensar em sua cabeça,
Tudo bem, se é menos, eu vou para a esquerda ou para ir à direita,
só de olhar para esta foto, é muito claro que eu tenho que ir para a esquerda
se este nó é maior do que o valor que eu estou procurando.
Então você vai para a esquerda, agora estou no 3.
Eu quero - 3 é menor do que o valor que eu estou procurando, que é 6.
Então, vá para a direita, e agora eu acabar no 6,
que é o valor que eu estou procurando, assim que eu retornar true.
O valor que vem eu vou procurar é 10.
Okay. Então, 10, agora, vai - corte que - vai seguir a raiz.
Agora, 10 vai ser maior do que 7, então eu quero olhar para a direita.
Eu vou vir para cá, 10, vai ser maior do que 9,
então eu vou querer olhar para a direita.
Eu venho aqui, mas aqui agora estou em nulo.
O que eu faço se eu acertar nulo?
[Estudante] Retornar falso? Sim >>. Eu não encontrei 10.
1 vai ser um caso quase idêntico,
exceto que ele só vai ser invertida, em vez de olhar
para o lado direito, eu vou olhar para o lado esquerdo.
>> Agora eu acho que nós realmente chegar ao código.
Aqui é onde - abra o aparelho CS50 e navegar no seu caminho,
mas você pode também fazê-lo apenas no espaço.
Provavelmente é ideal para fazê-lo no espaço,
porque podemos trabalhar no espaço.
"Primeiro vamos precisar de uma nova definição de tipo para um nó de árvore binário contendo valores int.
Usando o boilerplate typedef abaixo,
criar uma nova definição de tipo para um nó em uma árvore binária.
Se você ficar preso. . . "Blá, blá, blá. Okay.
Então, vamos colocar o clichê aqui,
nó typedef struct, e nó. Sim, está bem.
Então, quais são os campos que vamos querer em nosso nó?
[Estudante] Int e depois dois ponteiros?
>> Valor Int, dois ponteiros? Como faço para escrever os ponteiros?
[Estudante] Struct. >> Eu deveria fazer zoom in Sim, então nó struct * esquerda,
e struct node * direita.
E lembre-se a discussão da última vez,
que isso não faz sentido, isso não faz sentido,
isso não faz sentido.
Você precisa de tudo o que há para definir essa estrutura recursiva.
Ok, então é isso que nossa árvore vai ficar.
Se fizéssemos uma árvore trinário, em seguida, um nó pode parecer b1, b2, struct node * b3,
onde b é um ramo - na verdade, eu tenho mais ouvido à esquerda, meio, à direita, o que quer mas.
Nós só se preocupam com binário, para direita, esquerda.
"Agora declarar uma variável * mundial nó para a raiz da árvore."
Então, nós não vamos fazer isso.
A fim de tornar as coisas um pouco mais difícil e mais generalizado,
não teremos uma variável nó global.
Em vez disso, no principal que irá declarar todas as nossas coisas de nós,
e isso significa que a seguir, quando começar a correr
nossa função contém e nossa função de inserção,
em vez de nossos contém função apenas usando essa variável nó global,
nós vamos ter que tomar como um argumento a árvore que nós queremos que ele processar.
Tendo a variável global era para facilitar as coisas.
Nós vamos fazer as coisas mais difíceis.
Agora pegue um minuto apenas para fazer esse tipo de coisa,
onde dentro de principal que pretende criar esta árvore, e isso é tudo que você quer fazer.
Tentar construir esta árvore em sua função principal.
>> Okay. Assim, você não precisa nem ter construído a árvore de todo o caminho ainda.
Mas alguém tem algo que eu poderia puxar para cima
para mostrar como se poderia começar a construir essa árvore?
[Estudante] bater de alguém, tentando sair.
[Bowden] Qualquer confortável com a sua construção da árvore?
[Estudante] Claro. Ele não é feito. >> Está tudo bem. Nós podemos apenas terminar -
Oh, você pode salvá-lo? Hooray.
Portanto, temos aqui - oh, eu estou um pouco cortados.
Estou zoom?
Aumentar o zoom, rolar para fora. >> Eu tenho uma pergunta. >> Sim?
[Estudante] Quando você define estrutura, são coisas como inicializado para alguma coisa?
[Bowden] Não. >> Okay. Então você teria que inicializar -
[Bowden] Não. Quando você definir, ou quando você declarar uma estrutura,
não é inicializado por padrão, que é exatamente como se você declarar um int.
É exatamente a mesma coisa. É como se cada um dos seus campos individuais
pode ter um valor de lixo na mesma. >> E é possível definir - ou declarar uma struct
de uma forma que ele não inicializa-la?
[Bowden] Sim. Então, sintaxe de inicialização atalho
vai parecer -
Há duas maneiras de fazer isso. Acho que devemos compilá-lo
para fazer Clang certeza também faz isso.
A ordem de argumentos que vem na estrutura,
você colocou como a ordem dos argumentos dentro destas chaves.
Então, se você quiser inicializar a 9 e deixou ser nulo e depois à direita ser nulo,
seria 9, null, null.
A alternativa é, eo editor não gosta esta sintaxe,
e ele pensa que eu quero um novo bloco,
mas a alternativa é algo como -
aqui, eu vou colocá-lo em uma nova linha.
Você pode dizer explicitamente, eu esquecer a sintaxe exata.
Assim, você pode abordar explicitamente os pelo nome, e dizer:
. Valor c, ou. = 9. = NULL esquerda.
Eu estou supondo que estes precisam ser vírgulas.
. Direito = NULL, assim desta forma você não
realmente precisa saber a ordem da estrutura,
e quando você estiver lendo isto, é muito mais explícito
sobre o que o valor está sendo inicializado para.
>> Isto acontece por ser uma das coisas que -
assim, para a maior parte, C + + é um superconjunto de C.
Você pode pegar o código C, movê-lo para C + +, e deve compilar.
Esta é uma das coisas que o C + + não suporta, para que as pessoas tendem a não fazê-lo.
Eu não sei se essa é a única razão pela qual as pessoas tendem a não fazê-lo,
mas o caso em que eu precisava usá-lo necessário para trabalhar com C + + e assim eu não poderia usar isso.
Outro exemplo de algo que não funciona com o C + + é
como malloc retorna um "void *", tecnicamente,
mas você pode apenas dizer o que quer que char * x = malloc,
e ele será automaticamente convertido para um char *.
Esse elenco automático não acontece em C + +.
Isso não seria compilar, e você precisa dizer explicitamente
char *, malloc, qualquer que seja, para lançá-lo para um char *.
Não há muitas coisas que C e C + + discordam,
mas esses são dois.
Então vamos com esta sintaxe.
Mas mesmo que não fosse com essa sintaxe,
o que é - pode estar errado com isso?
[Estudante] Eu não preciso excluir a referência é? Sim >>.
Lembre-se de que a seta tem uma dereference implícito,
e assim, quando estamos lidando apenas com uma estrutura,
queremos usar. para chegar a uma dentro do campo da estrutura.
E a única vez que use a seta é quando nós queremos fazer -
bem, a seta é equivalente à -
isso é o que teria significado se eu usasse seta.
Todos os meios de seta é, dereference isso, agora estou em uma estrutura, e eu posso obter o campo.
Ou obter o campo diretamente ou dereference e obter o campo -
Eu acho que este deve ser o valor.
Mas aqui eu estou lidando com apenas uma estrutura, não um ponteiro para uma estrutura,
e por isso não pode usar a seta.
Mas esse tipo de coisa que podemos fazer para todos nós.
Oh, meu Deus.
Isto é de 6, 7 e 3.
Então, podemos definir os ramos em nossa árvore, podemos ter 7 -
Podemos ter, a sua esquerda deve apontar a 3.
Então, como vamos fazer isso?
[Estudantes, ininteligível] >> sim. O endereço do node3,
e se você não tem endereço, então ele só não seria compilar.
Mas lembre-se que estes são os ponteiros para os nós próximos.
O direito deve apontar a 9,
e 3 deve apontar sobre o direito à 6.
Acho que isso é tudo pronto. Quaisquer comentários ou perguntas?
[Estudante, ininteligível] A raiz vai ser 7.
Podemos apenas dizer nó * ptr =
ou raiz, = & node7.
>> Para nossos propósitos, vamos estar lidando com a inserção,
então vamos querer escrever uma função para inserir esta árvore binária
e inserção é, inevitavelmente, vai chamar malloc para criar um novo nó para esta árvore.
Assim, as coisas vão ficar confuso com o fato de que alguns nós
Estão actualmente na pilha
e outros nós vamos acabar na pilha quando inseri-los.
Isso é perfeitamente válido, mas a única razão
nós somos capazes de fazer isso na pilha
é porque é um exemplo tão artificial que sabemos
a árvore é suposto ser construído como 7, 3, 6, 9.
Se não tem isso, então não teríamos a malloc em primeiro lugar.
Como veremos um pouco mais tarde, devemos ser malloc'ing.
Agora é perfeitamente razoável para colocar na pilha,
mas vamos mudar isso para uma implementação de malloc.
Então, cada um deles agora vai ser algo como
* node9 nó = malloc (sizeof (nó)).
E agora nós vamos ter que fazer a nossa seleção.
if (node9 == NULL) - Eu não queria que isso -
retornar 1, e então nós podemos fazer node9-> porque agora é um ponteiro,
valor = 6, node9-> esquerda = NULL,
node9-> direita = NULL,
e nós vamos ter que fazer isso para cada um desses nós.
Então, em vez disso, vamos colocá-lo dentro de uma função separada.
Vamos chamá-lo de nó * build_node,
e isso é um pouco semelhante ao APIs nós fornecemos para codificação de Huffman.
Nós damos-lhe funções inicializador para uma árvore
e desconstrutor "funções" para as árvores e os mesmos para as florestas.
>> Então aqui nós vamos ter uma função de inicialização
apenas construir um nó para nós.
E vai ficar muito bonito exatamente como este.
E eu estou indo para ser preguiçoso e não mudar o nome da variável,
embora node9 não faz mais sentido.
Ah, eu acho que o valor do node9 não deveria ter sido 6.
Agora podemos voltar node9.
E aqui nós deve retornar nulo.
Todos concordam em que a função build-a-nó?
Então agora podemos chamar de que a construção de qualquer nó com um dado valor e ponteiros nulos.
Agora nós podemos chamar isso, podemos fazer nó * node9 = build_node (9).
E vamos fazer. . .
6, 3, 7, 6, 3, 7.
E agora queremos definir os ponteiros mesmos,
só que agora tudo está já em termos de ponteiros
então não precisa mais o endereço do.
Okay. Então, qual é a última coisa que eu quero fazer?
Há um erro de verificação de que eu não estou fazendo.
O que significa construir retorno nó?
[Estudante, ininteligível] >> Yeah. Se malloc falhou, ele vai retornar nulo.
Então, eu estou indo para preguiçosamente colocá-la aqui, em vez de fazer uma condição para cada um.
Se (node9 == null, ou - ainda mais simples,
isto é equivalente a apenas se não node9.
Então, se não node9, ou não node6, ou não node3, ou não node7, retornar 1.
Talvez devêssemos imprimir malloc falhou, ou algo assim.
[Estudante] é falso igual a nulo, bem como?
[Bowden] Qualquer valor zero é falso.
Assim nulo é um valor zero.
Zero é um valor de zero. Falso é um valor zero.
Qualquer - praticamente os únicos dois valores zero são nulas e zero,
falsa é apenas de hash definido como zero.
Isso também se aplica se nós declarar variável global.
Se tinha raiz * nó aqui,
então - a coisa agradável sobre variáveis ​​globais é que eles sempre têm um valor inicial.
Isso não é verdade de funções, como aqui dentro,
se temos, *, como nó ou nodo.
Nós não temos idéia do que x.Value, x.whatever,
ou poderíamos imprimi-los e eles poderiam ser arbitrária.
Isso não é verdade de variáveis ​​globais.
Raiz para nó ou nodo.
Por padrão, tudo o que é global, se não explicitamente inicializada com algum valor,
tem um valor de zero, como o seu valor.
Então, aqui, o nó raiz *, não explicitamente inicializá-lo a nada,
portanto, seu valor padrão será nulo, que é o valor zero de ponteiros.
O valor padrão de x vai significar que x.Value é zero,
x.left é nulo, e x.right é nulo.
Então, uma vez que é uma estrutura, de todos os campos da estrutura serão os valores zero.
Nós não precisamos usar isso aqui, no entanto.
[Aluno] As estruturas são diferentes do que outras variáveis, e as outras variáveis ​​são
valores de lixo, que são zeros?
[Bowden] Outros valores também. Assim, em x, x será zero.
Se é no escopo global, que tem um valor inicial. Ok >>.
[Bowden] Ou o valor inicial que você deu ou zero.
Eu acho que cuida de tudo isso.
>> Okay. Assim, a próxima parte da pergunta é,
"Agora queremos escrever uma função chamada contém
com um protótipo de bool contém valor int. "
Nós não vamos fazer bool contém valor int.
Nosso protótipo está indo olhar como
bool contém (valor int.
E então nós também vamos passar a árvore
que deve ser a verificação para ver se ele tem esse valor.
Então nó * árvore). Okay.
E então podemos chamá-lo com algo como,
talvez a gente vai querer printf ou algo assim.
Contém 6, nossa raiz.
Que deve retornar uma, ou verdadeiro,
enquanto contém 5 raiz deve retornar falso.
Então, tome um segundo para implementar isso.
Você pode fazer isso de qualquer forma iterativa ou recursivamente.
A coisa agradável sobre a maneira que nós definir as coisas é que
presta-se a nossa solução recursiva muito mais fácil
do que a forma global variável fez.
Porque se só temos contém valor int, então não temos forma de recursão para baixo subárvores.
Nós teríamos que ter uma função auxiliar separado que recurses as subárvores para nós.
Mas desde que mudei-o a tomar a árvore como um argumento,
que deveria ter sido sempre, em primeiro lugar,
agora podemos recurse mais facilmente.
Então iterativo ou recursivo, nós vamos passar por cima de ambos,
mas vamos ver que termina recursivas por ser bastante fácil.
Okay. Alguém tem algo que podemos trabalhar?
>> [Estudante] Eu tenho uma solução iterativa. >> Tudo bem, iterativo.
Ok, isso parece bom.
Então, quero andar nos com ele?
[Estudante] Claro. Então eu definir uma variável temp para obter o primeiro nó da árvore.
E então eu só em loop enquanto temp não nula igual,
por isso, enquanto ainda estava na árvore, eu acho.
E se o valor for igual ao valor de temperatura que está a apontar para,
em seguida, ele retorna esse valor.
Caso contrário, ele verifica se ele está do lado direito ou do lado esquerdo.
Se você já teve uma situação em que não há mais árvores,
em seguida, ele retorna - ele sai do loop e retorna falso.
[Bowden] Okay. De modo que parece bom.
Alguém tem algum comentário sobre qualquer coisa?
Eu não tenho comentários correção em tudo.
A única coisa que podemos fazer é esse cara.
Oh, que vai percorrer um pouco comprido.
Eu vou corrigir isso. Okay.
>> Todos devem se lembrar de como ternário funciona.
Há, certamente testes no passado
que dar-lhe uma função com um operador ternário,
e dizer, traduzir isso, fazer alguma coisa que não usa ternário.
Portanto, este é um caso muito comum de quando eu iria pensar em usar ternário,
onde se alguma condição definir uma variável para alguma coisa,
mais definido que a mesma variável para outra coisa.
Isso é algo que muito freqüentemente pode ser transformado em esse tipo de coisa
onde definir essa variável para isso - ou, bem, isso é verdade? Então este, senão isso.
[Estudante] O primeiro é se verdade, certo?
[Bowden] Yeah. A maneira que eu sempre ler é, temperatura igual valor maior que o valor da temperatura,
então isto, mais isto. É uma pergunta.
É maior? Em seguida, faça a primeira coisa. Mais fazer o segundo.
Eu quase sempre - o cólon, eu só - na minha cabeça, eu leio como pessoa.
>> Alguém tem uma solução recursiva?
Okay. Este vamos - que poderia já ser grande,
mas estamos indo para torná-lo ainda melhor.
Esta é praticamente a mesma idéia exata.
É só que, bem, você quer explicar?
[Estudante] Claro. Então, estamos certificando-se de que a árvore não é nulo em primeiro lugar,
porque se a árvore é nula, então ele vai retornar falso, porque não tê-lo encontrado.
E se ainda há uma árvore, vamos para - nós primeiro verificar se o valor é o nó atual.
Return true se for, e se não recurse nós à esquerda ou à direita.
Diz que o som apropriado? >> Mm-hmm. (Acordo)
Assim, notar que esta é quase - estruturalmente muito semelhante à solução iterativa.
É só que, em vez de recursão, tivemos um loop while.
E o caso base aqui onde árvore não faz nula igual
foi a condição sob a qual saiu do loop while.
Eles são muito semelhantes. Mas vamos dar um passo adiante.
Agora, nós fazemos a mesma coisa aqui.
Note que estamos retornando a mesma coisa em ambas as linhas,
com exceção de um argumento é diferente.
Então, nós vamos fazer isso em um ternário.
Eu bati algo opção, e fez um símbolo. Okay.
Então vamos voltar contém isso.
Isso está começando a ser várias linhas, bem, o zoom é.
Geralmente, como uma coisa de estilo, eu não acho que muitas pessoas
colocar um espaço após a seta, mas eu acho que se você for consistente, está tudo bem.
Se o valor for menor que o valor de árvore, queremos recurse na esquerda árvore,
outra coisa que queremos recurse em direito árvore.
Então isso foi um passo de fazer este olhar menor.
Passo dois de fazer este olhar menor -
podemos separar isso para várias linhas.
Okay. Passo dois de fazê-lo parecer menor está aqui,
então o valor de retorno é igual ao valor de árvore, ou o que quer que contém.
>> Isso é uma coisa importante.
Eu não tenho certeza se ele disse isso explicitamente em sala de aula,
mas é chamado de curto-circuito avaliação.
A idéia aqui é valor == valor árvore.
Se isso é verdade, então isso é verdade, e nós queremos "ou" aquilo com o que está aqui.
Assim, sem sequer pensar sobre o que está aqui,
o que é a expressão inteira vai voltar?
[Estudante] True? >> Sim, porque verdadeiro de qualquer coisa,
or'd - or'd ou verdadeiro com qualquer coisa é necessariamente verdade.
Assim, logo que vemos valor de retorno = valor árvore,
nós apenas estamos indo para retornar verdadeiro.
Nem mesmo vai recurse contém ainda abaixo da linha.
Podemos dar um passo adiante.
Árvore de retorno não nulo igual e tudo isso.
Ele fez uma função de uma linha.
Este é também um exemplo de avaliação curto-circuito.
Mas agora é a mesma idéia -
em vez de - por isso, se não nulo árvore faz igual - ou, bem,
se faz árvore nula igual, o que é o caso de má,
se a árvore é igual a nulo, então a primeira condição vai ser falso.
Tão falso anded com qualquer coisa vai ser o que?
[Estudante] False. Sim >>. Esta é a outra metade do curto-circuito de avaliação,
onde se a árvore não nulo não igual, então não estamos indo mesmo ir -
ou se faz árvore nula igual, então não vamos fazer valor == valor árvore.
Nós apenas estamos indo para retornar imediatamente falso.
O que é importante, pois, se não o fez curto-circuito avaliar,
em seguida, se árvore faz nulo igual, esta segunda condição vai culpa seg,
porque árvore-> valor é dereferencing nulo.
Então é isso. Pode fazer isso - mudar uma vez mais.
Isso é uma coisa muito comum também, não fazer esta linha um com isso,
mas é uma coisa comum em condições, talvez não aqui,
mas se (árvore! = NULL, e árvore-> valor valor ==), fazer o que.
Esta é uma condição muito comum, em que em vez de ter
para quebrar isso em dois ifs, onde, como, é o nulo árvore?
Ok, não é nula, então agora é o valor igual ao valor de árvore? Fazer isso.
Em vez disso, essa condição, isso nunca vai seg culpa
porque ele vai sair se isso acontecer a ser nulo.
Bem, eu acho que se a árvore é um ponteiro completamente inválido, ele ainda pode seg culpa,
mas não pode seg culpa se a árvore é nula.
Se fosse nulo, ele iria sair antes de você dereferenced o ponteiro em primeiro lugar.
[Estudante] É esta avaliação chamado preguiçoso?
>> [Bowden] Avaliação preguiçoso é uma coisa separada.
Avaliação preguiçosa é mais como você perguntar para um valor,
você perguntar para calcular um valor, tipo, mas você não precisa dele imediatamente.
Então, até que você realmente precisa dele, ele não é avaliada.
Esta não é exatamente a mesma coisa, mas no pset Huffman,
ele diz que "preguiçosamente", escrevem.
A razão para fazermos isso é porque na verdade estamos buffer a escrita -
não quero escrever bits individuais de cada vez,
ou bytes individuais de uma vez, que em vez querem ter um pedaço de bytes.
Em seguida, uma vez que temos um pedaço de bytes, então vamos escrever isso.
Mesmo que você pedir para ele escrever - e fwrite e fread fazer o mesmo tipo de coisa.
Elas suavizam o lê e escreve.
Mesmo que você pedir para ele escrever de imediato, provavelmente não.
E você não pode ter certeza de que as coisas vão ser escrito
até que você chamar hfclose ou o que seja,
que, então, diz, está bem, eu estou fechando meu arquivo,
isso significa que é melhor eu escrever tudo o que eu ainda não escreveu.
Ele não tem necessidade de escrever tudo fora
até que você está fechando o arquivo, e então ele precisa.
Então, isso é apenas o que preguiçoso - ele espera até que isso tem que acontecer.
Este - ter 51 e você vai entrar em mais detalhes,
porque OCaml e tudo em 51, tudo é recursão.
Não existem soluções iterativo, basicamente.
Tudo é recursividade, e avaliação preguiçosa
vai ser importante para uma série de circunstâncias
onde, se você não avaliar preguiçosamente, isso significaria -
O exemplo é correntes, que são infinitamente longo.
Em teoria, você pode pensar que os números naturais como um fluxo de 1-2-3-4-5-6-7,
Coisas tão preguiçosamente avaliados estão bem.
Se eu disser que quero o número dez, então eu posso avaliar, até o número dez.
Se eu quiser que o número centésimo, então eu posso avaliar, até o número centésimo.
Sem avaliação preguiçosa, então ele vai tentar avaliar todos os números imediatamente.
Você está avaliando números infinitos, e isso não é apenas possível.
Então, há uma série de circunstâncias em que a avaliação preguiçoso
é apenas essencial para a obtenção de coisas para trabalhar.
>> Agora queremos escrever inserção onde inserção vai ser
similarmente mudança na sua definição.
Então agora é inserir bool (valor inteiro).
Vamos mudar isso para inserção bool (int valor, nó da árvore *).
Estamos, na verdade, vai mudar de novo daqui a pouco, vamos ver por que.
E vamos passar build_node, apenas para os pedaços dele,
acima de inserir de modo que não tem que escrever um protótipo de função.
Que é um indício de que você está indo estar usando build_node na inserção.
Okay. Tome um minuto para isso.
Eu acho que eu salvo a revisão se você quiser puxar de que,
ou, pelo menos, eu fiz agora.
Eu queria uma ligeira quebra para pensar sobre a lógica de inserção,
se você não pode pensar nisso.
Basicamente, você só vai ser inserir nas folhas.
Como, se eu inserir um, então eu estou, inevitavelmente, vai ser uma inserção -
Eu vou mudar para o preto - eu ser a inserção de um por aqui.
Ou se eu inserir 4, eu quero ser a inserção de quatro aqui.
Portanto, não importa o que você faça, você vai ser a inserção de uma folha.
Tudo que você tem a fazer é repetir a árvore até chegar ao nó
que deve ser pai do nó, o pai do novo nó,
e depois alterar o ponteiro para a esquerda ou direita, dependendo do facto
que é maior do que ou menor do que o nó actual.
Alterar esse ponteiro para apontar para o novo nó.
Então iterar a árvore, fazer o ponto da folha para o novo nó.
Também pensar sobre o motivo que proíbe o tipo de situação antes,
onde construiu a árvore binária onde estava correto
se você só olhou para um único nó,
mas 9 foi para a esquerda, de 7, se você iterado para baixo todo o caminho.
Então, isso é impossível, neste cenário, uma vez que -
pensa sobre a inserção de 9 ou algo; no nó de primeira,
Vou ver 7 e eu só estou indo para ir para a direita.
Portanto, não importa o que eu faço, se eu estou indo para a inserção de uma folha,
e para uma folha utilizando o algoritmo adequado,
que vai ser impossível para mim para inserir 9 para a esquerda, de 7 de
porque assim que eu bater 7 Eu estou indo para ir para a direita.
Alguém tem alguma coisa para começar?
[Estudante] eu faço. >> Claro.
[Estudante, ininteligível]
[Outro aluno, ininteligível]
[Bowden] É apreciado. Okay. Quer explicar?
>> [Estudante] Uma vez que sabemos que fomos inserindo
novos nós na extremidade da árvore,
Eu loop através da árvore iterativamente
até que cheguei a um nó que apontou como nulo.
E então eu decidi colocá-lo tanto no lado direito ou no lado esquerdo
usando essa variável direito, que me disse onde colocá-lo.
E então, essencialmente, eu fiz apenas que a última -
Nesse ponto nó temp para o novo nó que estava criando,
ou no lado esquerdo ou no lado direito, de acordo com o que o valor era certo.
Finalmente, defina o valor novo nó com o valor de seus testes.
[Bowden] Ok, então eu vejo um problema aqui.
Isto é como 95% do caminho.
O problema que eu vejo, bem, se alguém ver um problema?
Qual é a circunstância em que eles quebram fora do circuito?
[Estudante] Se temp é nulo? Sim >>. Então, como você sair do loop é se temp é nulo.
Mas o que eu faço aqui?
Eu temperatura dereference, que é inevitavelmente nula.
Então, a outra coisa que você precisa fazer não é apenas acompanhar até temp é nulo,
você quer acompanhar o pai em todos os momentos.
Queremos também pai * nó, acho que podemos manter isso em nulo no primeiro.
Isso vai ter um comportamento estranho para a raiz da árvore,
mas nós vamos chegar a isso.
Se o valor é maior do que qualquer outra coisa, então temperatura certa temp =.
Mas antes de fazer esse pai, temp =.
Ou os pais sempre vai temperatura igual? É esse o caso?
Se temp não é nulo, então eu vou mover para baixo, não importa o que,
a um nó para o qual temp é o pai.
Então pai vai ser temporário, e depois eu passo temporário para baixo.
Agora temporário é nulo, mas pontos pai para o pai da coisa que é nulo.
Então, aqui, eu não quero para definir direito igual a 1.
Então eu me mudei para a direita, por isso, se a direita = 1,
e eu acho que você também quer fazer -
se você se mover para a esquerda, que pretende definir direito igual a 0.
Ou então, se você nunca se mover para a direita.
Então direita = 0. Se o direito = 1,
agora queremos fazer o pai newNode ponteiro direito,
outra coisa que quero fazer o pai newNode ponteiro esquerdo.
Perguntas sobre isso?
Okay. Portanto, esta é a maneira que nós - bem, na verdade, em vez de fazer isso,
Nós meio que esperava que você use build_node.
E então se newNode igual nulo, retorna false.
É isso. Agora, isso é o que espera que você faça.
>> Isto é o que as soluções pessoal fazer.
Não concordo com isso como o jeito "certo" de fazer isso
mas isso é perfeitamente bem e ele vai funcionar.
Uma coisa que está um pouco estranho agora é
se a árvore começa como nula, passamos em uma árvore nula.
Acho que depende de como você define o comportamento de passar em uma árvore nula.
Eu acho que se você passar em uma árvore nula,
em seguida, inserir o valor para uma árvore nula
deve retornar apenas uma árvore, onde o único valor que é único nó.
As pessoas concordam com isso? Você poderia, se quisesse,
se você passar em uma árvore nula
e você quer inserir um valor para ele, retornar falso.
É até você para definir isso.
Para fazer a primeira coisa que eu disse e depois -
bem, você vai ter problemas para fazer isso, porque
seria mais fácil se tivéssemos um ponteiro global para a coisa,
mas nós não, então se a árvore é nulo, não há nada que possamos fazer sobre isso.
Nós podemos apenas retornar falso.
Então, eu vou mudar de inserção.
Nós tecnicamente poderia mudar isso aqui,
como ele está interagindo sobre as coisas,
mas eu vou mudar de inserção para tomar um nó de árvore. **
Ponteiros duplos.
O que isso significa?
Em vez de lidar com ponteiros para nós,
a coisa que eu vou estar manipulando é este ponteiro.
Eu vou estar manipulando este ponteiro.
Eu vou estar manipulando ponteiros diretamente.
Isso faz sentido, uma vez que, pensar para baixo -
bem, agora isso aponta para nulo.
O que eu quero fazer é manipular este ponteiro para apontar para não nulo.
Eu quero que ele aponte para o meu novo nó.
Se eu apenas manter o controle de ponteiros para os meus ponteiros,
então não precisa manter o controle de um ponteiro pai.
Eu posso apenas acompanhar para ver se o ponteiro está apontando para nulo,
e se o ponteiro está apontando para nulo,
mudá-lo para apontar para o nó que eu quero.
E eu posso mudá-lo desde que eu tenho um ponteiro para o ponteiro.
Vamos ver isso agora.
Você pode realmente fazê-lo recursivamente muito facilmente.
Não queremos fazer isso?
Sim, nós fazemos.
>> Vamos ver isso de forma recursiva.
Primeiro, o que é o nosso caso base vai ser?
Quase sempre o nosso caso base, mas, na verdade, isso é meio complicado.
Primeiro de tudo, se (árvore == NULL)
Eu acho que nós apenas estamos indo para retornar falso.
Isto é diferente de seu nulo árvore estar.
Este é o ponteiro para o ponteiro raiz sendo nula
o que significa que o ponteiro raiz não existe.
Então, aqui, se eu fizer
* nó - vamos reutilizar esse.
* Nó raiz = NULL,
e então eu vou chamar de inserção, fazendo algo parecido,
inserir em 4 e raiz.
Assim, e de raiz, se a raiz é um nó *
depois & raiz vai ser um ** nó.
Isto é válido. Neste caso, árvore, até aqui,
árvore não é nula - ou inserção.
Aqui. Árvore não é nulo; árvore * é nulo, o que é bom
porque se a árvore * é nulo, então eu posso manipulá-lo
até agora apontam para o que eu quero que ele apontar.
Mas se a árvore for nula, isso significa que eu só vim aqui e disse nulo.
Isso não faz sentido. Eu não posso fazer nada com isso.
Se a árvore é nulo, retorna false.
Então eu basicamente já disse o que o nosso caso base real.
E o que é que vai ser?
[Estudante, ininteligível]
[Bowden] Sim. Então, se (* árvore == NULL).
Isso se relaciona com o caso aqui
onde se meu ponteiro vermelho é o ponteiro Estou focado,
assim como eu estou focado neste ponteiro, agora eu estou focado neste ponteiro.
Agora estou focado neste ponteiro.
Então, se meu ponteiro vermelho, que é ** meu nó,
é nunca - se *, meu ponteiro vermelho, é sempre nula,
isso significa que eu estou no caso em que eu estou focando um ponteiro que aponta -
este é um ponteiro que pertence a uma folha.
Eu quero mudar este ponteiro para apontar para o meu novo nó.
Volte aqui.
Meu newNode será apenas nó * n = build_node (valor)
então n, se n = NULL, retorna false.
Outra coisa que quero mudar o que o ponteiro está apontando para
agora a apontar para o nosso nó recém-construído.
Nós podemos realmente fazer isso aqui.
Em vez de dizer n, dizemos * = árvore se a árvore *.
Todo mundo entende isso? Que, por lidar com ponteiros para ponteiros,
nós podemos mudar ponteiros nulos para apontar para coisas que queremos que eles apontam.
Esse é o nosso caso base.
>> Agora recorrência nosso, ou o nosso recursão,
vai ser muito semelhante a todos os outros recursões temos vindo a fazer.
Nós vamos querer inserir valor,
e agora eu vou usar ternário de novo, mas o que é a nossa condição vai ser?
O que é que estamos à procura de decidir se queremos ir para a esquerda ou direita?
Vamos fazê-lo em etapas separadas.
If (valor <) o que?
[Aluno] O valor árvore?
[Bowden] Então lembre-se que eu estou atualmente -
[Estudantes, ininteligível]
[Bowden] Sim, isso aqui, vamos dizer que esta seta verde
é um exemplo de que árvore é atualmente, é um ponteiro para este ponteiro.
Então isso significa que eu sou um ponteiro para um ponteiro para 3.
O dereference duas vezes soava bem.
O que eu - como eu faço isso?
[Estudante] Referência no uma vez, e em seguida, fazer seta que maneira?
[Bowden] Então (árvore *) é o dereference uma vez, - valor>
vai dar-me o valor do nó que eu estou indiretamente apontando.
Então, eu também posso escrever ** tree.value se você preferir.
Ou funciona.
Se for esse o caso, então eu quero chamar inserir com valor.
E o que é meu nó atualizados ** vai ser?
Eu quero ir para a esquerda, de modo tree.left ** vai ser minha esquerda.
E eu quero que o ponteiro para essa coisa
de modo que se a esquerda acaba sendo o ponteiro nulo,
Eu posso modificá-lo para apontar para o meu novo nó.
>> E outro caso pode ser muito similar.
Vamos realmente fazer que o meu ternário agora.
Insira valor se valor <(árvore **). Valor.
Então nós queremos atualizar nossos ** para a esquerda,
mais queremos atualizar nossos ** para a direita.
[Estudante] Será que obter o ponteiro para o ponteiro?
[Bowden] Lembre-se que - ** tree.right é uma estrela nó.
[Estudante, ininteligível] >> Yeah.
** Tree.right é assim ponteiro ou algo assim.
Assim, tomando um ponteiro para isso, que me dá o que eu quero
do ponteiro para esse cara.
[Estudante] Podemos ir mais uma vez por que estamos usando os dois ponteiros?
[Bowden] Yeah. Então - não, você pode, e que a solução antes
Era uma maneira de fazê-lo sem fazer dois ponteiros.
Você precisa ser capaz de entender usando dois ponteiros,
e esta é uma solução de limpeza.
Além disso, observe que, o que acontece se a minha árvore -
o que acontece se minha raiz era nulo? O que acontece se eu fazer isso caso aqui?
Então nó raiz * = NULL, insira 4 em e raiz.
O que é raiz vai ser depois disto?
[Estudante, ininteligível] >> Yeah.
Valor da raiz vai ser 4.
Esquerdo de raiz vai ser nulo, certo raiz vai ser nulo.
No caso em que não passe de raiz por endereço,
não foi possível modificar raiz.
No caso em que a árvore - onde raiz era nulo,
nós apenas tivemos que retornar falso. Não há nada que possamos fazer.
Nós não podemos inserir um nó em uma árvore vazia.
Mas agora nós podemos, nós apenas fazer uma árvore vazia em uma árvore de um nó.
Que normalmente é a maneira esperada que é suposto para trabalhar.
>> Além disso, esta é significativamente mais curto do que
também manter o controle do pai, e assim você percorrer todo o caminho para baixo.
Agora eu tenho o meu pai, e eu só tenho o meu ponteiro direito pai para o que seja.
Em vez disso, se fizermos isso de forma iterativa, que seria a mesma idéia com um loop while.
Mas, em vez de ter que lidar com o meu ponteiro pai,
em vez meu ponteiro atual seria a coisa
que eu estou modificando diretamente para apontar para o meu novo nó.
Eu não tenho que lidar com o fato de que ele está apontando para a esquerda.
Eu não tenho que lidar com o fato de que ele está apontando para a direita.
É só o que esse ponteiro é, eu estou indo para configurá-lo para apontar para o meu novo nó.
Todo mundo entende como funciona?
Se não, por que queremos fazê-lo desta forma,
mas que, pelo menos, esta funciona como uma solução?
[Estudante] Onde é que vamos voltar verdade?
[Bowden] Isso é provavelmente aqui.
Se corretamente inseri-lo, retornar true.
Outra coisa, aqui nós vamos querer voltar retornos independentemente de inserção.
>> E o que há de especial sobre esta função recursiva?
É cauda recursiva, por isso, enquanto nós compilar com alguma otimização,
ele vai reconhecer isso e você nunca vai ter um estouro de pilha a partir deste,
mesmo se a nossa árvore tem uma altura de 10 mil ou 10 milhões.
[Estudante, ininteligível]
[Bowden] Eu acho que ele faz isso em Dash - ou o que nível de otimização
é necessário para uma recursão de cauda para ser reconhecida.
Eu acho que ele reconhece - GCC e Clang
também têm significados diferentes para os seus níveis de otimização.
Eu quero dizer que é DashO 2, a certeza de que ele vai reconhecer recursão de cauda.
Mas nós - você pode construir como um exemplo Fibonocci ou algo assim.
Não é fácil fazer o teste com isso, porque é difícil construir
uma árvore binária que é tão grande.
Mas sim, eu acho que é DashO 2, que
se você compilar com DashO 2, ele irá procurar por recursão
e otimizar isso.
Vamos voltar - inserir, literalmente, a última coisa que ele precisa.
Vamos voltar para a inserção aqui
onde nós estamos indo fazer a mesma idéia.
Ele ainda vai ter a falha de não ser capaz de lidar com todo
quando a raiz em si é nulo, ou a entrada de passado é nulo,
mas, em vez de lidar com um ponteiro pai,
vamos aplicar a mesma lógica dos ponteiros mantendo a ponteiros.
Se aqui nós manter nosso nó **, cur
e não precisa manter o controle de mais certo,
mas nó ** cur = & árvore.
E agora o nosso loop while vai ser enquanto cur * não nula igual.
Não precisa manter o controle de pais mais.
Não precisa manter o controle de esquerda e direita.
E eu vou chamá-lo de temp, porque nós já estamos usando temp.
Okay. Então, se (valor> * temp),
em seguida, & (* temp) - direito>
mais temp = & (* temp) -> esquerda.
E agora, neste momento, após este loop while,
Eu só faço isso porque talvez seja mais fácil pensar iterativamente de forma recursiva,
mas depois deste loop while,
* Temp é o ponteiro que deseja alterar.
>> Antes tínhamos pai, e queríamos mudar qualquer pai ou mãe esquerda para a direita,
mas se queremos mudar direito dos pais,
então temp * é direito dos pais, e nós podemos mudá-lo diretamente.
Então, aqui, nós podemos fazer * temp = newNode, e é isso.
Então aviso, tudo o que fizemos nesta era tirar linhas de código.
A fim de acompanhar o pai em tudo o que é o esforço adicional.
Aqui, se nós apenas acompanhar o ponteiro para o ponteiro,
e mesmo que queria se livrar de todas essas chaves agora,
torná-la mais curta.
Esta agora é a solução exatamente o mesmo,
mas menos linhas de código.
Uma vez que você começar a reconhecer isso como uma solução válida,
também é mais fácil do que raciocinar sobre como, ok,
por que eu tenho esta bandeira à direita int?
O que significa isso? Oh, está significando que
cada vez que eu vá para a direita, eu preciso defini-lo,
outra coisa, se eu for embora, eu preciso configurá-lo para zero.
Aqui, eu não tenho a razão sobre isso, é apenas mais fácil de pensar.
Perguntas?
[Estudante, ininteligível] >> Yeah.
Ok, então no último bit -
Eu acho que uma função fácil e rápida que podemos fazer é,
Vamos - juntos, eu acho, e tentar escrever um contém função
que não se importa se é uma árvore de busca binária.
Este contém função deve retornar true
se em qualquer lugar nesta árvore binária geral é o valor que estamos procurando.
Então, vamos primeiro fazer isso recursivamente e depois nós vamos fazê-lo de forma iterativa.
Nós realmente podemos apenas fazê-lo juntos, porque isso vai ser muito curto.
>> O que é o meu caso base vai ser?
[Estudante, ininteligível]
[Bowden] Então, se (árvore == NULL), então o que?
[Estudante] Retornar falso.
[Bowden] Else, bem, eu não preciso do outro.
Se foi o meu caso outra base.
Valor [do estudante] árvore? Sim >>.
Então, se (árvore-> valor valor. ==
Observe que estamos de volta ao * nó não, nó ** s?
Contém nunca vai precisar usar um ** nó,
uma vez que não está modificando de ponteiros.
Nós apenas estamos atravessando eles.
Se isso acontecer, então nós queremos retornar true.
Outra coisa que quiser percorrer as crianças.
Portanto, não podemos raciocinar sobre se tudo para a esquerda é menos
e tudo para a direita é maior.
Então o que está a nossa condição vai ser aqui - ou, o que é que vamos fazer?
[Estudante, ininteligível] >> Yeah.
Retorno contém (valor, árvore-> esquerda)
ou contém (valor, árvore-> direita). E é isso.
E notar que há algum tipo de avaliação de curto-circuito,
onde se acontecer de encontrar o valor na árvore esquerda,
nós nunca precisamos olhar para a árvore certa.
Essa é a função inteira.
Agora vamos fazê-lo de forma iterativa,
que vai ser menos agradável.
Vamos levar o começo habitual do nó atu * = árvore.
Enquanto (act! = NULL).
Rapidamente vai ver um problema.
Se atual - aqui, se alguma vez sair dessa,
então, temos acabar de coisas para olhar, então retorne falso.
If (atual-> valor valor ==), retorna true.
Então, agora, nós estamos em um lugar -
não sabemos se queremos ir para a esquerda ou direita.
Então, arbitrariamente, vamos ir para a esquerda.
Eu, obviamente, executar em um problema onde eu completamente abandonado tudo -
Eu sempre apenas verificar do lado esquerdo de uma árvore.
Eu nunca vou verificar tudo o que é um direito da criança de qualquer coisa.
Como faço para corrigir isso?
[Estudante] Você tem que manter o controle da esquerda e da direita em uma pilha.
[Bowden] Yeah. Então, vamos torná-lo
struct lista, nó * n, e depois nó ** próximo?
Eu acho que funciona bem.
Queremos ir mais à esquerda, ou vamos - até aqui.
Struct = lista da lista, ele vai começar
fora nesta lista struct.
* Lista = NULL. Assim que vai ser a nossa lista encadeada
de sub-árvores que nós pulamos.
Nós vamos atravessar resta agora,
mas desde que inevitavelmente precisa voltar para a direita,
Nós vamos manter o lado direito dentro da nossa lista struct.
Então nós vamos ter new_list ou estrutura,
struct lista *, new_list = malloc (sizeof (lista)).
Eu vou ignorar verificação de erros que, mas você deve verificar para ver se é nulo.
New_list o nó que vai apontar -
oh, é por isso que eu queria aqui. Vai apontar para uma lista struct segundo.
É assim que ligado listas trabalho.
Este é o mesmo como uma lista ligada int
exceto estamos apenas substituindo int com * nó.
É exatamente o mesmo.
Então new_list, o valor do nosso nó new_list,
vai ser atu-> direita.
O valor da nossa new_list-> próxima vai ser a nossa lista original,
e depois vamos atualizar nossa lista para apontar para new_list.
>> Agora precisamos de algum tipo de forma de puxar as coisas,
como temos atravessado toda a subárvore esquerda.
Agora precisamos tirar algo de fora,
como atu é nulo, nós não queremos apenas retornar falso.
Queremos agora puxar fora a nossa nova lista.
Uma maneira conveniente de fazer isso - bem, na verdade, há várias maneiras de fazer isso.
Alguém tem uma sugestão?
Onde eu deveria fazer isso ou como eu deveria fazer isso?
Nós só temos um par de minutos, mas alguma sugestão?
Em vez de - uma forma, ao invés de nossa condição de ser ao mesmo tempo,
o que estamos actualmente a analisar não é nulo,
em vez disso, vamos continuar a ir até a nossa própria lista é nulo.
Então, se a nossa lista acaba sendo nula,
então nós temos mais coisas para procurar, pesquisar.
Mas isso significa que a primeira coisa na nossa lista está indo só para ser o primeiro nó.
A primeira coisa que vai ser - já não precisa ver isso.
Então, lista-> n será nossa árvore.
lista-> próxima vai ser nulo.
E agora, enquanto a lista não nula igual.
Cur vai puxar algo da nossa lista.
Então atu vai igual lista-> n.
E então lista vai igual lista-> n, ou lista-> seguinte.
Assim se o valor é igual ao valor atu.
Agora podemos acrescentar tanto o ponteiro nosso direito e nosso ponteiro esquerdo
contanto que eles não são nulos.
Até aqui, acho que deveria ter feito isso em primeiro lugar.
Se (cur-> certo! = NULL)
depois vamos inserir o nó em nossa lista.
Se (cur-> esquerda), isso é um pouco de trabalho extra, mas está tudo bem.
Se (cur-> esquerda! = NULL),
e vamos inserir a esquerda em nossa lista ligada,
e que deve ser isso.
Repetimos - enquanto temos algo em nossa lista,
temos outro nó para olhar.
Então, olhamos para esse nó,
nós avançamos nossa lista para a próxima.
Se esse nó é o valor que estamos procurando, nós podemos retornar true.
Else inserir ambas as subárvores nossa esquerda e à direita,
enquanto eles não são nulos, em nossa lista
de modo que, inevitavelmente, passar por cima deles.
Então, se eles não foram nulos,
se a nossa raiz ponteiro apontava para duas coisas,
em seguida, no primeiro, tirou algo para fora de modo a nossa lista acaba sendo nulo.
E, então, colocar duas coisas de volta, agora nossa lista é de tamanho 2.
Então nós vamos fazer um loop de volta e nós apenas estamos indo para puxar,
vamos dizer, o ponteiro esquerdo do nosso nó raiz.
E isso só vai continuar acontecendo, nós vamos acabar looping sobre tudo.
>> Note-se que esta era significativamente mais complicado
na solução recursiva.
E eu já disse várias vezes
que a solução recursiva tem normalmente muito mais em comum com a solução iterativa.
Aqui é exatamente isso que a solução recursiva é fazendo.
A única alteração é a de que em vez de implicitamente utilizando a pilha, a pilha de programa,
como a sua forma de manter o controle do que nós ainda precisa visitar,
agora você tem que explicitamente usar uma lista ligada.
Em ambos os casos você está mantendo a par do que ainda precisa de nó a ser visitado.
No caso recursivo é apenas mais fácil, porque uma pilha
é implementado para você como a pilha do programa.
Note-se que esta lista ligada, é uma pilha.
Tudo o que basta colocar na pilha
é imediatamente o que nós vamos retirar a pilha para próxima visita.
Estamos fora do tempo, mas alguma dúvida?
[Estudante, ininteligível]
[Bowden] Yeah. Então, se temos a nossa lista ligada,
atual está indo para apontar para esse cara,
e agora nós estamos apenas avançar nossa lista ligada a concentrar-se sobre esse cara.
Estamos atravessando sobre a lista ligada nessa linha.
E então eu acho que devemos libertar a nossa lista encadeada e outras coisas
uma vez antes de retornar verdadeiro ou falso, precisamos
iterar sobre a nossa lista ligada e sempre aqui, eu acho,
se atu direito não é igual, adicioná-lo, então agora nós queremos libertar
atu porque, bem, que nós esquecemos completamente sobre a lista? Sim.
Então é isso que nós queremos fazer aqui.
Onde está o ponteiro?
Cur era então - nós queremos uma lista struct * 10 é igual a próxima lista.
Lista livre, list = temp.
E, no caso em que retornar verdadeiro, precisamos iterar
sobre o restante de nossa lista ligada liberando coisas.
A coisa agradável sobre a solução recursiva é libertar as coisas
significa apenas factorings popping fora da pilha que vai acontecer para você.
Então, nós fomos de algo que é como 3 linhas de difícil de pensar sobre o código-
a algo que é significativamente mais muitos de difícil pensar-sobre linhas de código.
Mais alguma pergunta?
Tudo bem. Nós somos bons. Bye!
[CS50.TV]