[Powered by Google Translate] [Sección 7: máis cómodo]
[Rob Bowden] [Harvard University]
[Esta é CS50] [CS50.TV]
Todo ben. Entón, como eu dixen no meu correo electrónico,
iso vai ser unha sección binario-tree-intensivo.
Pero non hai que moitas cuestións.
Entón, nós estamos indo a probar extraer de cada pregunta
e entrar en detalles Dolores de todas as mellores formas de facer as cousas.
Así, ao comezo, pasamos por deseños de mostraxe de árbores binarias e outras cousas.
Entón, aquí, "Lembre que unha árbore binaria ten nos semellantes aos dunha lista ligada,
excepto en vez de un punteiro, hai dúas: unha para "neno" á esquerda
e un para a "neno" correcto ".
Así, unha árbore binaria é como unha lista ligada,
excepto a estrutura terá dous punteiros.
Hai árbores trinário, que van ter tres punteiros,
hai N-Ary árbores, que só ten un punteiro xenérico
que entón tes que malloc para ser grande abondo para ter
punteiros suficientes para todos os nenos posibles.
Entón árbore binaria só acontece de ter un número constante de dous.
Se queres, podes dar unha lista encadeada como unha árbore unário,
pero eu non creo que ninguén chama iso.
"Debuxe un diagrama de caixas-e-flechas dun nodo árbore binaria
contén o número favorito de Nate, 7, en que cada punteiro neno é nulo. "
Modo para iPad.
>> Vai ser moi sinxelo.
Nós só imos ter un nó, eu vou deseña-lo como un cadrado.
E eu vou chamar os valores aquí.
Polo tanto, o valor debe ser aquí,
e aquí nós imos ter o punteiro para a esquerda á esquerda e á dereita o punteiro á dereita.
E é moi así convenio para chamalo de esquerda e dereita, os nomes de punteiro.
Ambos van ser nulo.
Isto só vai ser nulo, e que só vai ser nulo.
Okay. Entón, de volta para aquí.
"Con unha lista ligada, tiñamos só para almacenar un punteiro
para o primeiro nodo da lista para lembrar a listaxe ligada, ou toda a lista.
Do mesmo xeito, con árbores, só temos que gardar un punteiro
a un único nodo, a fin de acordar a árbore enteira.
Este nodo é o calle "raíz" da árbore.
Construír sobre o seu diagrama de antes ou deseñar un novo
de tal forma que ten unha representación caixas-e-flechas dunha árbore binaria
co valor 7, a continuación, 3 na parte esquerda,
e despois 9, á dereita, e logo 6, á dereita da extremo 3 ".
Imos ver se eu lembro de todo isto na miña cabeza.
Polo tanto, esta vai ser a nosa raíz aquí.
Nós imos ter un punteiro en algún lugar, algo que chamaremos de raíz,
e está apuntando para este cara.
Agora, para facer un novo nodo,
o que temos, tres á esquerda?
Así, un novo nodo con 3, e apunta inicialmente nula.
Vou poñer N.
Agora queremos facer que vaia á esquerda, de 7.
Entón nós cambiar este punteiro para apuntar agora para este cara.
E nós facemos o mesmo. Queremos un 9 aquí
que, inicialmente, só di nulo.
Nós imos cambiar este punteiro punto, a 9,
e agora queren pór 6 á dereita de 3.
Entón, vai - facer un 6.
E este cara vai apuntar alí.
Okay. Entón, iso é todo o que nos pide para facelo.
>> Agora imos pasar por riba de algunha terminoloxía.
Nós xa falamos sobre como a raíz da árbore é o nó máis alto da árbore.
A unha contendo 7. Os nós na parte inferior da árbore son chamados as follas.
Calquera nodo que só ten nulo como os seus fillos é unha folla.
Por iso, é posible, a nosa árbore binaria é só un único nodo,
que unha árbore é unha folla, e é iso.
"O 'altura' da árbore é o número de saltos que ten que facer
para dende o principio de unha folla. "
Nós imos entrar en un segundo, a diferenza
entre árbores binarias saldadas e non saldadas,
pero, por agora, a altura total da árbore
Eu diría que é 3, aínda que, se contar o número de saltos
tes que facer para obter a 9, entón é realmente só unha altura de 2.
Agora esta é unha árbore binaria non balanceada,
pero nós falamos sobre equilibrada cando se chega a ser relevante.
Entón agora podemos falar sobre nós nunha árbore, en termos
en relación aos outros nós na árbore.
Polo tanto, agora temos os pais, fillos, irmáns, pais e descendentes.
San sentido moi común, o que significan.
Se preguntarmos - e pais.
Entón, o que é o pai de 3?
[Os alumnos] 7. Si >>. O pai vai só para ser o que apunta para ti.
Entón, o que son os nenos de 7?
[Os alumnos] 3 e 9. Si >>.
Teña en conta que "nenos" significa literalmente fillos,
para 6 non se aplica, porque é como un neto.
Pero, entón, se somos descendentes, entón o que son os descendentes de 7?
[Os alumnos] 3, 6 e 9. Si >>.
Os descendentes do nodo raíz vai ser todo na árbore,
excepto, talvez, o nó de raíz en si, se non quere considerar que un descendente.
E, finalmente, os devanceiros, polo que é a dirección oposta.
Entón, cales son os devanceiros de 6?
[Os alumnos] 3 e 7. Si >>. 9 non está incluído.
É só a liñaxe directa de volta á raíz
Vai ser os seus antepasados.
>> "Dicimos que unha árbore binaria é" listada ", para cada nó na árbore,
todos os seus descendentes no lado esquerdo teñen valores menores
e todos os da dereita teñen valores maiores.
Por exemplo, a árbore enriba é ordenada, pero non é o único arranxo posible ordenada. "
Antes de chegar a iso,
unha árbore binaria ordenada é tamén coñecido como unha árbore de busca binaria.
Aquí ocorrer de ser chamado dunha árbore binaria ordenada,
pero eu nunca oín-lo chamado dunha árbore binaria ordenada antes,
e nun quiz que son moito máis propensos a poñer árbore de busca binaria.
Son unha ea mesma cousa,
e é importante que recoñece a distinción entre árbore binaria e árbore de busca binaria.
Unha árbore binaria é só unha árbore que apunta a dúas cousas.
Cada nodo apunta a dúas cousas.
Non hai razoamento sobre os valores que apunta a.
Así como aquí, xa que é unha árbore de busca binaria,
sabemos que se vai cara á esquerda, de 7,
a continuación, todos os valores que poden posiblemente alcanzar
indo deixou de 7 ten que ser inferior a 7.
Nótese que todos os valores menores que 7 son 3 e 6.
Estas son todas á esquerda, de 7.
Ou tamén para a dereita, de 7, todo ten que ser maior que 7,
para 9 é para a dereita, de 7, por iso estamos ben.
Este non é o caso dunha árbore binaria,
para unha árbore binaria estándar, podemos ter só tres no cume, 7 á esquerda,
9 á esquerda, de 7, non hai ningunha ordenación de valores, en absoluto.
Agora, nós realmente non vai facer iso porque é tedioso e innecesario,
pero "tentar deseñar como moitas árbores ordenada como pode pensar
utilizando os números 7, 3, 9 e 6.
Cantos arranxos distintos existen? O que é a altura de cada un? "
>> Nós imos facer unha parella, pero a idea principal é,
é dicir, de ningún xeito unha representación singular dunha árbore binaria conteñen eses valores.
Todo o que necesitamos é unha árbore binaria que contén 7, 3, 6 e 9.
Outra posible válida sería a raíz é 3,
vaia á esquerda e 6, vaia á esquerda e 7,
cara á esquerda e está 9.
Que é unha árbore de busca binaria perfectamente válida.
Non é moi útil, porque é como unha lista ligada
e todos eses punteiros son só nulo.
Pero é unha árbore válido. Si?
[Estudante] Non valores teñen que ser maior do lado dereito?
Ou iso é -? Estes >> eu quixen ir por outro camiño.
Hai tamén - Si, imos cambiar isto.
9, 7, 6, 3. Boa captura.
El aínda ten que cumprir o que unha árbore de busca binaria é suposta facer.
Así, todo o que o lado esquerdo debe ser menor que calquera dato nodo.
Nós poderiamos só cambiar, por exemplo, este 6 e poñelas aquí.
Non, non podemos. Por que eu sigo facendo isto?
Imos facer - aquí é 6, aquí é 7, 6 puntos 3.
Esta aínda é unha árbore de busca binaria válido.
O que é malo se eu - imos ver se podo chegar a un acordo.
Si, está ben. Entón, o que está mal con esta árbore?
Eu creo que eu xa lle deu unha información de que hai algo de malo con el.
Por que eu sigo facendo isto?
Okay. Isto parece razoable.
Se olharmos para cada nodo, coma o 7, a continuación, á esquerda da Fig 7 é unha 3.
Polo tanto, temos tres, o único cara á dereita do 3 é un 6.
E se ollar para 6, a cousa á dereita do 6 é un 9.
Entón, por que iso non é unha árbore de busca binaria válida?
[Os alumnos] 9 é aínda a esquerda, de 7. Si >>.
Debe ser certo que todos os valores que poden ser posiblemente alcanzar, indo cara á esquerda, de 7 están a menos de 7.
Ir á esquerda, de 7, temos a 3 e aínda podemos chegar a 6,
aínda podemos chegar a 9, mais por ter pasado menos de 7,
non debe ser capaz de chegar a un número que é maior que 7.
Entón iso non é unha árbore de busca binaria válido.
>> Meu irmán realmente tiña unha pregunta da entrevista
que era basicamente iso, código só algo para validar
unha árbore é unha árbore de busca binaria,
e entón a primeira cousa que fixo foi só comprobar a ver
a esquerda e dereita son correctos, e despois repetir alí en baixo.
Pero non pode simplemente facelo, ten que manter o control
do feito de que, agora que eu fun deixar de 7,
todo neste sub debe ser inferior a 7.
O algoritmo correcto precisa manter o control
dos límites que os valores poden eventualmente caen dentro
Non imos pasar por todos eles.
Hai unha relación de recorrencia agradable,
aínda que non se chegase a eses, ou non imos chegar a estes,
definir cantos realmente son.
Polo tanto, hai 14 deles.
A idea de como faría iso matematicamente é como,
pode escoller calquera única de ser o nodo raíz,
e entón se eu incorporarse de 7 a ser o nodo raíz,
a continuación, hai, por exemplo, algúns números que poden ir ser o meu nó esquerdo,
e hai algúns números que pode ser o meu no dereito,
pero se eu tivera n números totais, o importe que pode ir á esquerda
máis o importe que pode ir á dereita e n - 1.
Así, os números restantes, eles teñen que ser capaces de ir, tanto á esquerda ou cara á dereita.
Parece difícil que, se eu poñer 3 primeiro, entón todo ten que ir á esquerda,
pero se eu poñer 7, entón algunhas cousas poden ir á esquerda e algunhas cousas poden ir cara á dereita.
E por '3 'primeiro eu quería dicir todo pode ir cara á dereita.
É realmente, só tes que pensar niso como,
cantas cousas poden ir no seguinte nivel da árbore.
E vén a ser 14, ou pode debuxar todos eles,
e entón vai ter 14.
>> Voltar aquí,
"Ordenou árbores binarias son legais porque podemos buscar por eles
dunha forma moi semellante á procura dun array ordenado.
Para iso, imos comezar na raíz e traballar nosa maneira para abaixo da árbore
para follas, comprobando os valores de cada nodo contra os valores que estamos a buscar.
Se o valor do nodo actual é menor que o valor que está a buscar,
vai ao lado dereito do neno do nodo.
Se non, vai para o fillo esquerdo do nodo.
Nalgún momento, quere atopar o valor que está a buscar, ou vai executar nun nulo,
indicando o valor non está na árbore. "
Eu teño que redeseñar a árbore que tiña antes, que vai levar un segundo.
Pero queremos mirar para arriba 6, 10, e un está na árbore.
Entón o que era, 7, 9, 3, 6. Okay.
Os números que quere ollar para arriba, queremos mirar para arriba 6.
Como funciona este algoritmo?
Ben, tamén temos algúns punteiro raíz para a nosa árbore.
E ir á raíz e dicir, é este valor igual ao valor que estamos buscando?
Entón, nós estamos mirando para 6, polo que non é igual.
Entón, siga indo, e agora podemos dicir, ok, entón 6 é inferior a 7.
Iso quere dicir que queremos ir á esquerda, ou queremos ir para a dereita?
[Estudante] Esquerda. Si >>.
É moito máis doado, todo o que tes que facer é tomar un nó posible da árbore
e entón non - en vez de tratar de pensar na súa cabeza,
Todo ben, se é menos, eu vou para a esquerda ou para ir á dereita,
só de ollar para esta foto, é moi claro que eu teño que ir á esquerda
este nodo é maior que o valor que eu estou buscando.
Entón vai cara á esquerda, agora estou no 3.
Eu quero - 3 é menor que o valor que eu estou a buscar, que é 6.
Entón, vai para a dereita, e agora eu rematar o 6,
que é o valor que eu estou buscando, así que eu voltar true.
O valor que vén eu vou buscar é 10.
Okay. Entón, 10, agora, vai - corte que - vai seguir a raíz.
Agora, 10 vai ser maior que 7, entón eu quero ollar para a dereita.
Vou vir para aquí, 10, vai ser maior que 9,
entón eu vou querer ollar para a dereita.
Eu veño aquí, pero aquí agora estou en nulo.
O que fago se eu acertar nulo?
[Estudante] Voltar falso? Si >>. Eu non atopei 10.
1 vai ser un caso case idéntico,
excepto que el só vai ser invertida, en vez de ollar
para o lado dereito, eu vou mirar para o lado esquerdo.
>> Agora eu creo que nós realmente chegar ao código.
Aquí é onde - abra o aparello CS50 e navegar no seu camiño,
pero pode tamén facelo só no espazo.
Probablemente é ideal para facelo no espazo,
porque podemos traballar no espazo.
"Primeiro imos ter unha nova definición de tipo para un nodo árbore binario que contén valores int.
Usando o boilerplate typedef abaixo,
crear unha nova definición de tipo para un nodo nunha árbore binaria.
Se queda preso. . . "Bla, bla, bla. Okay.
Entón, imos poñer o cliché aquí,
nó typedef struct, e no. Si, está ben.
Entón, cales son os campos que imos querer no noso nodo?
[Estudante] Int e despois dous punteiros?
>> Valor Int, dous punteiros? ¿Como escribir os punteiros?
[Estudante] struct. >> Eu debería facer zoom in Si, entón no struct * esquerda,
e struct node * dereita.
E lembre-se a discusión da última vez,
que iso non ten sentido, iso non ten sentido,
iso non ten sentido.
Debe de todo o que hai para definir esa estrutura recursiva.
Ok, entón é iso que a nosa árbore vai quedar.
Se fixésemos unha árbore trinário, a continuación, un nó pode parecer B1, B2, struct node * B3,
onde b é unha rama - na verdade, eu teño máis oído á esquerda, medio, á dereita, o que quere pero.
Nós só se preocupan binario, cara a dereita, esquerda.
"Agora declarar unha variable * mundial no a raíz da árbore."
Entón, nós non imos facelo.
Co fin de facer as cousas un pouco máis difícil e máis xeneralizado,
non teremos unha variable no global.
En vez diso, o principal que pode declarar todas as nosas cousas de nós,
e iso significa que a continuación, cando comezar a correr
nosa función contén ea nosa función de inserción,
en vez dos nosos contén función só usando esa variable no global,
Nós imos ter que tomar como un argumento a árbore que queremos que procesar.
Tendo a variable global era para facilitar as cousas.
Nós imos facer as cousas máis difíciles.
Agora tome un minuto só para facer este tipo de cousas,
onde dentro principal que pretende crear esta árbore, e iso é todo o que quere facer.
Tentar construír esta árbore na súa función principal.
>> Okay. Así, non é preciso nin ter construído a árbore de todo o camiño aínda.
Pero alguén ten algo que eu podería tirar para arriba
para mostrar como se podería comezar a construír esa árbore?
[Estudante] bater de alguén, tentando saír.
[Bowden] Calquera cómodo coa súa construción a árbore?
[Estudante] Claro. Non está feito. >> Está todo ben. Podemos só rematar -
Oh, vostede pode garda-lo? Hooray.
Polo tanto, temos aquí - Oh, eu estou un pouco cortados.
Estou zoom?
Aumentar o zoom, rolar para fóra. >> Eu teño unha pregunta. >> Si?
[Estudante] Cando define estrutura, son cousas como inicializar a algo?
[Bowden] Non >> Okay. Entón tería que iniciar -
[Bowden] Non Cando definir, ou cando declarar unha estrutura,
non é inicializar por defecto, que é exactamente como se declarar un int.
É exactamente a mesma cousa. É coma se cada un dos seus campos individuais
pode ter un valor de lixo na mesma. >> E é posible definir - ou declarar unha struct
de forma que non arrinque-la?
[Bowden] Si Entón, sintaxe de inicio atallo
vai parecer -
Hai dúas formas de facelo. Creo que debemos recompila-lo
para facer Clang seguro tamén fai iso.
A orde de argumentos que vén na estrutura,
puxo como a orde dos argumentos dentro destas claves.
Entón, se quere iniciar a 9 e deixou ser nulo e despois á dereita ser nulo,
sería 9, null, null.
A alternativa é, eo editor non lle gusta esta sintaxe,
e el pensa que quero un novo bloque,
pero a alternativa é algo así como -
aquí, eu vou poñelas nunha nova liña.
Pode dicir explicitamente, eu esquezo a sintaxe exacta.
Así, pode abordar explícitamente os polo nome, e dicir:
. Valor c ou. = 9. = NULL esquerda.
Estou supoñendo que estes precisan ser comas.
. Dereito = NULL, así desta forma non
realmente precisa saber a orde da estrutura,
e cando está lendo isto, é moito máis explícito
sobre o que o valor está inicializar a.
>> Isto acontece por ser unha das cousas que -
así, a maior parte, C + + é un superconjunto de C.
Pode incorporarse o código C, mover para C + +, e debe compilar.
Esta é unha das cousas que o C + + non soporta, para que as persoas tenden a non facelo.
Eu non sei se esa é a única razón pola que as persoas tenden a non facelo,
pero o caso en que eu precisaba usalo necesario para traballar con C + + e así eu non podería usar isto.
Outro exemplo de algo que non funciona co C + + é
como malloc retorna un "void *", tecnicamente,
pero pode só dicir o que quere que char * x = malloc,
e será convertido automaticamente para un char *.
Ese reparto automático non acontece en C + +.
Isto non sería compilar, e cómpre dicir explicitamente
char *, malloc, calquera que sexa, para lanza-lo para un char *.
Non hai moitas cousas que C e C + + discordan,
pero estes son dous.
Entón imos con esta sintaxe.
Pero aínda que non fose con esa sintaxe,
o que é - pode estar mal con iso?
[Estudante] Eu non teño eliminar a referencia é? Si >>.
Lembre-se de que a frecha ten unha dereference implícito,
e así, cando estamos lidando só con unha estrutura,
queremos usar. para chegar a unha dentro do campo da estrutura.
E a única vez que use a frecha é cando queremos facer -
ben, a frecha é equivalente á -
iso é o que significaría se eu usase frecha.
Todos os medios de frecha e, dereference iso, agora estou nunha estrutura, e podo obter o campo.
Ou obter o campo directamente ou dereference e obter o campo -
Eu creo que este debe ser o valor.
Pero aquí estou lidando con só unha estrutura, non un punteiro para unha estrutura,
e por iso non pode usar a frecha.
Pero este tipo de cousas que podemos facer para todos nós.
Oh, meu Deus.
Isto é de 6, 7 e 3.
Entón, podemos definir os ramos na nosa árbore, podemos ter 7 -
Podemos ter a súa esquerda debe apuntar a 3.
Entón, como imos facer iso?
[Estudantes, inintelixible] >> si. O enderezo do node3,
e se non ten enderezo, el só non sería compilar.
Pero lembre que estes son os punteiros para os nos próximos.
O dereito debe apuntar a 9,
e 3 debe apuntar sobre o dereito á 6.
Creo que iso é todo listo. Calquera comentarios ou preguntas?
[Estudante, inintelixible] A raíz vai ser 7.
Podemos só dicir no * PTR =
ou raíz, = node7.
>> Para os nosos propósitos, imos estar lidando coa inserción,
entón imos querer escribir unha función para introducir esta árbore binaria
e inserción é, inevitablemente, vai chamar malloc para crear un novo nodo a esta árbore.
Así, as cousas van estar confuso co feito de que algúns nós
Están na pila
e outros imos acabar na pila cando inserir-los.
Isto é perfectamente válido, pero a única razón
Nós somos capaces de facelo na pila
é porque é un exemplo tan artificial que sabemos
A árbore é suposta ser construído como 7, 3, 6, 9.
Se non ten iso, entón non teriamos a malloc en primeiro lugar.
Como veremos un pouco máis tarde, debemos ser malloc'ing.
Agora é perfectamente razoable para poñer na pila,
pero imos cambiar isto para unha aplicación de malloc.
Entón, cada un deles agora vai ser algo así como
* Node9 nodo = malloc (sizeof (nó)).
E agora imos ter que facer a nosa selección.
if (node9 == NULL) - Eu non quería que iso -
voltar 1, e entón podemos facer node9-> porque agora é un punteiro,
valor = 6, node9-> esquerda = NULL,
node9-> dereita = NULL,
e nós imos ter que facer isto para cada un deses nós.
Entón, en vez diso, imos poñelas dentro dunha función separada.
Imos chamalo de nodo * build_node,
e iso é un pouco semellante ao APIs nós fornecen para codificación de Huffman.
Nós dámoslle funcións inicializador para unha árbore
e desconstrutor "funcións" para as árbores e os mesmos para os bosques.
>> Entón aquí imos ter unha función de arranque
só construír un nó para nós.
E vai ser moi bonito exactamente como este.
E eu estou indo a ser preguiceiro e non cambiar o nome da variable,
aínda node9 non fai máis sentido.
Ah, eu creo que o valor do node9 non debería ser 6.
Agora podemos volver node9.
E aquí nós debe retornar nulo.
Todos coinciden en que a función build-a-no?
Entón agora podemos chamar de que a construción de calquera nodo cun dato valor e punteiros nulos.
Agora podemos chamar iso, podemos facer no * node9 = build_node (9).
E imos facer. . .
6, 3, 7, 6, 3, 7.
E agora queremos definir os punteiros mesmos,
só que agora todo está xa en termos de punteiros
entón non necesita máis o enderezo do.
Okay. Entón, cal é a última cousa que quero facer?
Hai un erro de verificación de que eu non estou facendo.
O que significa construír retorno no?
[Estudante, inintelixible] >> Yeah. Se malloc fallou, el vai voltar nulo.
Entón, eu estou indo a preguizosamente poñela aquí, en vez de facer unha condición para cada un.
Se (node9 == null, ou - aínda máis simple,
isto é equivalente a só se non node9.
Entón, se non node9, ou non node6, ou non node3, ou non node7, voltar 1.
Quizais devêssemos imprimir malloc fallou, ou algo así.
[Estudante] é falso igual a nulo, así como?
[Bowden] Calquera valor cero é falso.
Así nulo é un valor cero.
Cero é un valor de cero. Falso é un valor cero.
Calquera - practicamente os únicos dous valores cero son nulas e cero,
falsa é só de hash definido como cero.
Isto tamén se aplica se nós declarar variable global.
Se raíz * ó aquí,
entón - a cousa agradable sobre variables globais é que sempre teñen un valor inicial.
Iso non é verdade de funcións, como aquí dentro,
si temos, *, como no ou nodo.
Nós non temos idea do que x.Value, x.whatever,
ou poderiamos imprimir-los e eles poderían ser arbitraria.
Iso non é verdade de variables globais.
Raíz nodo ou nó.
Por defecto, todo o que é global, non explícitamente inicializada con algún valor,
ten un valor de cero, como o seu valor.
Entón, aquí, o nodo raíz *, non explícitamente inicia-lo a nada,
polo tanto, o seu valor por defecto será nulo, que é o valor cero de punteiros.
O valor por defecto de x vai significar que x.Value é cero,
x.left é nulo, e x.right é nulo.
Entón, unha vez que é unha estrutura, de todos os campos da estrutura serán os valores cero.
Nós non precisamos usar isto aquí, con todo.
[Alumno] As estruturas son diferentes do que outras variables, e as outras variables son
valores de lixo, que son ceros?
[Bowden] Outros valores tamén. Así, en x, x será cero.
Se é no ámbito global, que ten un valor inicial. Ok >>.
[Bowden] Ou o valor inicial que deu ou cero.
Eu creo que coida de todo isto.
>> Okay. Así, a próxima parte da pregunta é,
"Agora queremos escribir unha función chamada contén
cun prototipo de bool contén valor int. "
Non imos facer bool contén valor int.
O noso prototipo está indo ollar como
bool contén (valor int.
E entón nós tamén imos pasar a árbore
que debe ser a comprobación para ver se ten ese valor.
Entón no * árbore). Okay.
E entón podemos chamalo con algo,
quizais a xente vai querer printf ou algo así.
Contén 6, a nosa raíz.
Que debe regresar dunha ou verdadeiro,
mentres contén 5 raíz debe retornar falso.
Entón, tome un segundo para aplicar isto.
Podes facelo de calquera forma iterativa ou recursivamente.
O agradable sobre a forma que definir as cousas que
préstase a nosa solución recursiva moito máis fácil
que a forma global variable fixo.
Porque só temos contén valor int, entón non temos forma de recursão para abaixo subárvores.
Nós teriamos que ter unha función auxiliar separado que recurses as subárvores para nós.
Pero desde que cambiei o a tomar a árbore como un argumento,
que debería ser sempre, en primeiro lugar,
agora podemos recurse máis facilmente.
Entón iterativo ou recursivo, nós imos pasar por riba de ambos,
pero imos ver que remata recursivas por ser moi fácil.
Okay. Alguén ten algo que podemos traballar?
>> [Estudante] Eu teño unha solución iterativa. >> Todo ben, iterativo.
Ok, iso parece bo.
Entón, quero andar nos con el?
[Estudante] Claro. Entón eu definir unha variable tempo para obter o primeiro nó da árbore.
E entón eu só loop mentres tempo non nula igual,
por iso, mentres aínda estaba na árbore, eu creo.
E se o valor é igual ao valor de temperatura que está a apuntar cara,
a continuación, el retorna ese valor.
Se non, el verifica se está do lado dereito ou do lado esquerdo.
Se xa tivo unha situación na que non hai máis árbores,
a continuación, el retorna - sae do loop e retorna falso.
[Bowden] Okay. De xeito que parece bo.
Alguén ten algún comentario sobre calquera cousa?
Eu non teño comentarios corrección en todo.
O único que podemos facer é este cara.
Oh, que vai percorrer un pouco longo.
Vou corrixir isto. Okay.
>> Todos deben lembrar de como ternário funciona.
Hai, por suposto probas no pasado
que darlle unha función con un operador ternário,
e dicir, traducir iso, facer algo que non usa ternário.
Polo tanto, este é un caso moi común cando eu ía pensar en usar ternário,
onde se algunha condición definir unha variable para algo,
máis definido que a mesma variable para outra cousa.
Iso é algo que moi frecuentemente se pode converter este tipo de cousas
onde establecer esa variable para iso - ou, ben, iso é verdade? Entón este, senón isto.
[Estudante] O primeiro é se verdade, non?
[Bowden] Yeah. O xeito que eu sempre ler é, temperatura igual valor maior que o valor da temperatura,
entón isto, máis isto. É unha pregunta.
É maior? A continuación, faga o primeiro. Máis facer o segundo.
Eu case sempre - o colon, eu só - na miña cabeza, eu leo ​​como persoa.
>> Alguén ten unha solución recursiva?
Okay. Este imos - que podería xa ser grande,
pero estamos indo a facelo aínda mellor.
Esta é practicamente a mesma idea exacta.
É só que, así, quere explicar?
[Estudante] Claro. Entón, estamos asegurarse de que a árbore non é nulo, en primeiro lugar,
porque a árbore é nula, entón el vai voltar falso, porque non telo atopado.
E aínda hai unha árbore, imos para - nós primeiro comprobar que o valor é o nó actual.
Return true se se, e se non recurse nós á esquerda ou á dereita.
Di que o son perfecto? >> MM-hmm. (Acordo)
Así, conta que esta é case - estruturalmente moi semellante á solución iterativa.
É só que, no canto de recursão, tivemos un loop while.
É o caso base aquí onde árbore non fai nula igual
foi a condición baixo a cal saíu do loop while.
Son moi semellantes. Pero imos dar un paso adiante.
Agora, nós facemos o mesmo aquí.
Teña en conta que estamos volvendo o mesmo en ambas as liñas,
con excepción de un argumento é diferente.
Entón, nós imos facelo nun ternário.
Eu bati algo opción, e fixo un símbolo. Okay.
Entón imos voltar contén isto.
Isto está empezando a ser varias liñas, así, o zoom é.
Xeralmente, como unha cousa de estilo, eu non creo que moitas persoas
poñer un espazo despois da frecha, pero eu creo que se vostede é consistente, está todo ben.
Se o valor é menor que o valor de árbore, queremos recurse na esquerda árbore,
outra cousa que queremos recurse en dereito árbore.
Entón iso foi un paso de facer este ollar menor.
Paso dous de facer este ollar menor -
podemos separar isto para varias liñas.
Okay. Paso dous de facelo parecer menor está aquí,
entón o valor de retorno é igual ao valor de árbore, ou o que quere que contén.
>> Iso é unha cousa importante.
Eu non estou seguro se el dixo iso explicitamente en clase,
pero chámase curtocircuíto avaliación.
A idea aquí é valor == valor árbore.
Se iso é verdade, entón iso é verdade, e queremos "ou" o co que está aquí.
Así, sen sequera pensar sobre o que está aquí,
o que é a expresión enteira vai volver?
[Estudante] True? >> Si, porque certo de calquera cousa,
or'd - or'd ou certo con calquera cousa é necesariamente verdade.
Así, logo que vemos valor de retorno = valor árbore,
Nós só estamos indo para voltar certo.
Nin sequera vai recurse contén aínda por baixo da liña.
Podemos dar un paso adiante.
Árbore de retorno non nulo igual e todo iso.
El fixo unha función dunha liña.
Este é tamén un exemplo de avaliación curtocircuíto.
Pero agora é a mesma idea -
en vez de - por iso, se non nulo árbore fai igual - ou, ben,
se fai árbore nula igual, o que é o caso de mala,
a árbore é igual a nulo, entón a primeira condición vai ser falso.
Tan falso anded con calquera cousa vai ser o que?
[Estudante] False. Si >>. Esta é a outra metade do curtocircuíto de avaliación,
onde a árbore non nulo non igual, non estamos indo mesmo ir -
ou se fai árbore nula igual, non imos facer valor == valor árbore.
Nós só estamos indo para voltar inmediatamente falso.
O que é importante, pois, se non o fixo curtocircuíto avaliar,
a continuación, se árbore fai nulo igual, esta segunda condición vai culpa seg,
porque árbore-> valor dereferencing nulo.
Entón é iso. Pode facelo - cambiar unha vez máis.
Iso é unha cousa moi común tamén, non facer esta liña un con iso,
pero é algo común en condicións, é posible que non aquí,
pero (árvore! = NULL, e árbore-> valor valor ==), facer o que.
Esta é unha condición moi común, en que en vez de ter
para romper iso en dous IFS, onde, como é o nulo árbore?
Ok, non é nula, entón agora é o valor igual ao valor de árbore? Facelo.
En vez diso, esa condición, iso non vai seg culpa
porque vai saír se isto acontecer a ser nulo.
Ben, eu creo que a árbore é un punteiro completamente válido, aínda pode seg culpa,
pero non pode seg culpa a árbore é nula.
Se fose nulo, ía saír antes de lle dereferenced o punteiro en primeiro lugar.
[Estudante] É esta avaliación chamado preguiceiro?
>> [Bowden] Valoración preguiceiro é unha cousa separada.
Avaliación preguiceira é máis como lle preguntar a un valor,
preguntar para calcular un valor, tipo, pero non precisa del inmediatamente.
Entón, ata que realmente precisa del, non é valorada.
Esta non é exactamente a mesma cousa, pero no pset Huffman,
el di que "preguizosamente", escriben.
A razón para facermos iso é porque en realidade estamos buffer escrita -
non quero escribir bits individuais de cada vez,
ou máis individuais de unha vez, que en vez queren ter un pedazo de bytes.
A continuación, unha vez que temos un anaco de máis, entón imos escribir isto.
Aínda que pedir para el escribir - e fwrite e fread facer o mesmo tipo de cousas.
Elas suavizan o le e escribe.
Aínda que pedir para el escribir de inmediato, probablemente non.
E non pode estar seguro de que as cousas van ser escrito
ata que chamar hfclose ou o que sexa,
que, entón, di, está ben, eu estou pechando meu arquivo,
Isto significa que é mellor eu escribir todo o que eu non escribiu.
El non ten necesidade de escribir todo fóra
ata que está pechando o ficheiro, e entón el necesita.
Entón, iso é só o que preguiceiro - espera ata que iso ten que acontecer.
Este - ter 51 e vai entrar en máis detalles,
porque OCaml e todo en 51, todo é recursão.
Non existen solucións iterativo, basicamente.
Todo é recursividade, e avaliación preguiceira
vai ser importante para unha serie de circunstancias
onde, se non avaliar preguizosamente, iso significaría -
O exemplo é cadeas, que son infinitamente longo.
En teoría, pode pensar que os números naturais como un fluxo de 1-2-3-4-5-6-7,
Cousas tan preguizosamente avaliados están ben.
Se eu dixer que quero o número dez, entón eu podo avaliar, ata o número dez.
Se quere que o número centésimo, entón eu podo avaliar, ata o número centésimo.
Sen avaliación preguiceira, el vai avaliar todos os números inmediatamente.
Vostede está avaliando números infinitos, e iso non é só posible.
Entón, hai unha serie de circunstancias en que a avaliación preguiceiro
é só esencial para a obtención de cousas para traballar.
>> Agora queremos escribir inserción onde inserción será
Similarmente cambio na súa definición.
Entón agora é introducir bool (valor enteiro).
Imos cambiar isto para inserción bool (int valor, no da árbore *).
Estamos, en realidade, vai cambiar de novo aquí a pouco, imos ver por que.
E imos pasar build_node, só para os anacos del,
por riba de introducir de xeito que non ten que escribir un prototipo de función.
Que é un indicio de que está indo estar usando build_node na inserción.
Okay. Tomé un minuto para iso.
Eu creo que eu salvo a revisión se quere tirar de que,
ou, polo menos, eu fixen agora.
Eu quería unha lixeira quebra a pensar sobre a lóxica de inserción,
se non pode pensar niso.
Basicamente, só vai ser inserir nas follas.
Como, se eu introducir un, entón eu estou, inevitablemente, vai ser unha inserción -
Vou cambiar a negro - eu ser a inserción dun por aquí.
Ou se eu inserir 4, quero ser a inserción de catro aquí.
Polo tanto, non importa o que fai, vai ser a inserción de unha folla.
Todo o que tes que facer é repetir a árbore ata chegar ao nodo
que debe ser pai do nodo, o pai do novo nodo,
e despois cambiar o punteiro cara á esquerda ou dereita, dependendo do feito
que é maior que ou menor que o nodo actual.
Cambiar ese punteiro para apuntar para o novo nodo.
Entón iterar a árbore, facer o punto da folla para o novo nodo.
Tamén pensar sobre o motivo que prohibe o tipo de situación antes,
onde construíu a árbore binaria onde estaba correcto
se só ollou para un único nodo,
pero 9 foi á esquerda, de 7, se iterado para abaixo todo o camiño.
Entón, iso é imposible, neste escenario, xa que -
pensa sobre a inserción de 9 ou algo; no nó de primeira,
Vou ver 7 e eu só estou indo a ir á dereita.
Polo tanto, non importa o que fago, se eu estou indo para a inserción de unha folla,
e para unha folla utilizando o algoritmo axeitado,
que vai ser imposible para min para introducir 9 a esquerda, do 7 de
porque así que eu bater 7 Eu estou indo a ir á dereita.
Alguén ten algunha cousa para comezar?
[Estudante] fago. >> Suposto.
[Estudante, inintelixible]
[Outro alumno, inintelixible]
[Bowden] É apreciado. Okay. Queres explicar?
>> [Estudante] Unha vez que sabemos que fomos inserindo
novos nós no extremo da árbore,
Eu loop través da árbore iterativamente
ata que cheguei a un nodo que apuntou como nulo.
E entón eu decidir colocar-lo tanto no lado dereito ou do lado esquerdo
usando esa variable dereito, que me dixo onde poñelas.
E entón, esencialmente, eu fixen só que a última -
Nese punto no tempo para o novo nodo que estaba creando,
ou no lado esquerdo ou no lado dereito, de acordo co que o valor era certo.
Finalmente, defina o valor novo no co valor dos seus probas.
[Bowden] Ok, entón eu vexo un problema aquí.
Isto é como o 95% do camiño.
O problema que eu vexo, así, se alguén ve un problema?
Cal é a circunstancia en que quebran fóra do circuíto?
[Estudante] Si tempo é nulo? Si >>. Entón, como saír do loop é se tempo é nulo.
Pero o que fago aquí?
Eu temperatura dereference, que é inevitablemente nula.
Entón, a outra cousa que ten que facer non é só seguir ata tempo é nulo,
quere seguir o pai en todos os momentos.
Queremos tamén pai * no, creo que podemos manter isto nulo no primeiro.
Isto vai ter un comportamento estraño para a raíz da árbore,
pero nós imos chegar a iso.
Se o valor é maior do que calquera outra cousa, entón temperatura correcta tempo =.
Pero antes de facer ese pai, tempo =.
Ou os pais sempre vai temperatura igual? É ese o caso?
Se tempo non é nulo, entón eu vou mover para abaixo, non importa o que,
a un nodo para o cal tempo é o pai.
Entón pai vai ser temporal, e despois eu paso temporal inferior.
Agora temporal é nulo, pero puntos pai para o pai da cousa que é nulo.
Entón, aquí, eu non quero para definir dereito igual a 1.
Entón eu me mudei para a dereita, por iso, a dereita = 1,
e eu creo que tamén quere facer -
se se mover á esquerda, que pretende definir dereito igual a 0.
Ou ben, se non se mover á dereita.
Entón dereita = 0. O dereito = 1,
agora queremos facer o pai newNode punteiro dereito,
outra cousa que quero facer o pai newNode punteiro esquerdo.
Preguntas sobre iso?
Okay. Polo tanto, esta é a forma que - ben, en realidade, no canto de facelo,
Nós medio que esperaba que use build_node.
E entón newNode igual nulo, retorna false.
É iso. Agora, iso é o que espera que faga.
>> Isto é o que as solucións persoal facer.
Non estou de acordo con iso como o xeito "correcto" de facelo
pero iso é perfectamente ben e el vai funcionar.
Unha cousa que está un pouco raro agora
a árbore comeza como nula, pasamos a unha árbore nula.
Creo que depende de como define o comportamento pasar dunha árbore nula.
Eu creo que se pasar dunha árbore nula,
a continuación, engadir o valor para unha árbore nula
debe retornar só unha árbore, onde o único valor que é único no.
As persoas de acordo con iso? Vostede podería, se quixese,
se pasar dunha árbore nula
e quere inserir un valor para el, voltar falso.
É ata a definir iso.
Para facer a primeira cousa que eu dixen e despois -
así, vai ter problemas para facer iso, porque
sería máis doado se tivésemos un punteiro global para a cousa,
pero non, entón a árbore é nulo, non hai nada que poidamos facer sobre iso.
Podemos só retornar falso.
Entón, eu vou cambiar de inserción.
Nós tecnicamente podería cambiar isto aquí,
como está interactuando sobre as cousas,
pero eu vou cambiar de inserción para tomar un nodo árbore. **
Punteiros dobres.
O que significa isto?
En vez de xestionar punteiros para nós,
a cousa que eu vou estar manipulando é este punteiro.
Eu vou estar manipulando este punteiro.
Eu vou estar manipulando punteiros directamente.
Isto ten sentido, xa que, pensando cara abaixo -
Ben, agora que apunta a nulo.
O que quero facer é manipular este punteiro para apuntar para non nulo.
Eu quero que apunte cara ao meu novo nodo.
Se eu só manter o control de punteiros para os meus punteiros,
entón non necesita manter o control dun punteiro pai.
Eu podo só seguir a ver se o punteiro está a apuntar cara nulo,
e se o punteiro está a apuntar cara nulo,
muda-lo para apuntar para o nodo que quero.
E podo mudalo desde que eu teño un punteiro para o punteiro.
Imos ver iso agora.
Pode realmente facelo recursivamente moi facilmente.
Non queremos facer iso?
Si, nós facemos.
>> Imos ver iso de forma recursiva.
En primeiro lugar, o que é o noso caso base vai ser?
Case sempre o noso caso base, pero, en realidade, iso é medio complicado.
Primeiro de todo, se (árbore == NULL)
Eu creo que nós só estamos indo para voltar falso.
Isto é distinto do seu nulo árbore estar.
Este é o punteiro para o punteiro raíz sendo nula
o que significa que o punteiro raíz non existe.
Entón, aquí, se eu fai
* No - imos reutilizar ese.
* No raíz = NULL,
e entón eu vou chamar de inserción, facendo algo parecido,
inserir o 4 e raíz.
Así, e de raíz, a raíz é un nó *
despois & raíz vai ser un ** nodo.
Isto é válido. Neste caso, árbore, até aquí,
árbore non é nula - ou inserción.
Aquí. Árbore non é nulo; árbore * é nulo, o que é bo
porque a árbore * é nulo, entón eu podo manipulala lo
ata agora apuntan o que quero que apuntar.
Pero se a árbore é nula, isto significa que eu só vin aquí e dixo nulo.
Isto non ten sentido. Eu non podo facer nada con iso.
Se a árbore é nulo, retorna false.
Entón eu basicamente xa dixen que o noso caso base real.
E que é o que vai ser?
[Estudante, inintelixible]
[Bowden] Si Entón, se (* árbore == NULL).
Isto relaciónase co caso aquí
onde se meu punteiro vermello é o punteiro Estou centrado,
así como eu estou focado neste punteiro, agora eu estou focado neste punteiro.
Agora estou focado neste punteiro.
Entón, se o meu punteiro vermello, que é ** meu nó,
é nunca - se *, meu punteiro vermello, sempre nula,
iso significa que eu estou no caso en que eu estou focando un punteiro que apunta -
este é un punteiro que pertence a unha folla.
Eu quero cambiar este punteiro para apuntar para o meu novo nodo.
Voltar aquí.
O meu newNode será só no * n = build_node (valor)
entón n, se n = NULL, retorna false.
Outra cousa que quero cambiar o que o punteiro está a apuntar cara
agora a apuntar para o noso nodo recén construído.
Podemos realmente facer iso aquí.
En vez de dicir n, dicimos * = árbore a árbore *.
Todo o mundo entende isto? Que, por xestione punteiros para punteiro,
podemos cambiar punteiros nulos para apuntar para cousas que queremos que ligan.
Ese é o noso caso base.
>> Agora recorrencia noso, ou o noso recursão,
vai ser moi semellante a todos os outros recursões temos está a facer.
Nós imos querer inserir valor,
e agora eu vou usar ternário de novo, pero o que é a nosa condición será?
Que estamos á procura de decidir se queremos ir á esquerda ou dereita?
Imos facelo en etapas separadas.
If (valor <) o que?
[Alumno] O valor árbore?
[Bowden] Entón lembre que eu estou actualmente -
[Estudantes, inintelixible]
[Bowden] Si, iso aquí, imos dicir que esta frecha verde
é un exemplo do que é actualmente a árbore é un punteiro para este punteiro.
Entón iso significa que eu son un punteiro para un punteiro para 3.
O dereference dúas veces soaba ben.
O que eu - como fago isto?
[Estudante] Referencia no unha vez, e en seguida, facer frecha que xeito?
[Bowden] Entón (árbore *) é o dereference unha vez máis, - valor>
vai dar-me o valor do nodo que eu estou indirectamente apuntando.
Entón, eu tamén podo escribir ** tree.value se prefire.
Ou funciona.
Se é ese o caso, entón eu quero chamar inserir con valor.
E o que é o meu nó actualizados ** vai ser?
Eu quero ir para a esquerda, para tree.left ** vai ser miña esquerda.
E quero que o punteiro para esa cousa
de xeito que a esquerda acaba sendo o punteiro nulo,
Eu podo modificalo lo para apuntar para o meu novo nodo.
>> E outro caso pode ser moi similar.
Imos realmente facer que o meu ternário agora.
Insire valor se valor <(árbore **). Valor.
Entón queremos actualizar os nosos ** a esquerda,
mais queremos actualizar os nosos ** a dereita.
[Estudante] Será que obter o punteiro para o punteiro?
[Bowden] Lembre que - ** tree.right é unha estrela no.
[Estudante, inintelixible] >> Yeah.
** Tree.right é así punteiro ou algo así.
Así, tomando un punteiro para iso, que me dá o que quero
do punteiro para este cara.
[Estudante] Podemos ir unha vez máis por que estamos usando os dous punteiros?
[Bowden] Yeah. Entón - non, pode, e que a solución antes
Era unha forma de facelo sen facer dous punteiros.
Debe ser capaz de comprender a usar dous punteiros,
e esta é unha solución de limpeza.
Ademais, observe que, o que pasa se a miña árbore -
Qué acontece se miña raíz era nulo? Qué acontece se eu facer iso caso aquí?
Entón nodo raíz * = NULL, insira 4 en e raíz.
O que é raíz vai ser despois disto?
[Estudante, inintelixible] >> Yeah.
Valor da raíz vai ser 4.
Esquerdo de raíz vai ser nulo, seguro raíz vai ser nulo.
No caso de que non pase de raíz por enderezo
non se pode modificar raíz.
No caso de que a árbore - onde raíz era nulo,
Nós só tivemos que voltar falso. Non hai nada que poidamos facer.
Non podemos inserir un nodo nunha árbore baleira.
Pero agora podemos, nós só facer unha árbore baleira nunha árbore dun nodo.
Que normalmente é a forma esperada que suporía para traballar.
>> Ademais, esta é significativamente máis curto do que
tamén manter o control do seu pai, e así percorrer todo o camiño cara a abaixo.
Agora eu teño o meu pai, e eu só teño o meu punteiro dereito pai para o que sexa.
En vez diso, se facemos iso de forma iterativa, que sería a mesma idea con un loop while.
Pero, en vez de ter que xestione o meu punteiro pai,
en vez o meu punteiro actual sería a cousa
que eu estou modificando directamente para apuntar para o meu novo nodo.
Eu non teño que xestione o feito de que está a apuntar cara á esquerda.
Eu non teño que xestione o feito de que está a apuntar cara a dereita.
É só o que ese punteiro é, eu estou indo a configuralo para apuntar para o meu novo nodo.
Todo o mundo entende como funciona?
Se non, por que queremos facelo desta forma,
pero que, polo menos, esta funciona como unha solución?
[Estudante] Onde é que imos volver verdade?
[Bowden] Isto é probablemente aquí.
Se correctamente inserir-lo, voltar true.
Outra cousa, aquí imos querer volver retorno independentemente de inserción.
>> E o que hai de especial sobre esta función recursiva?
É cola recursiva, por iso, mentres nós compilar con algunha optimización,
vai recoñecer iso e nunca vai ter un estourido de pila a partir deste,
mesmo se a nosa árbore ten unha altura de 10 mil ou 10 millóns.
[Estudante, inintelixible]
[Bowden] Coido que fai iso en Dash - ou o que nivel de optimización
é necesario para unha recursão de cola para ser recoñecida.
Coido que recoñece - GCC e Clang
tamén teñen significados diferentes para os seus niveis de optimización.
Eu quero dicir que é DashO 2, a certeza de que vai recoñecer recursão de cola.
Pero nós - pode construír como un exemplo Fibonocci ou algo así.
Non é doado facer a proba con iso, porque é difícil construír
unha árbore binaria que é tan grande.
Pero si, eu creo que é DashO 2, que
Se compilar con DashO 2, el ha buscar recursão
e optimizar iso.
Imos volver - inserir, literalmente, a última cousa que precisa.
Imos volver para a inserción aquí
onde nós estamos indo facer a mesma idea.
Aínda vai ter o fallo de non ser capaz de tratar con todo
cando a raíz en si é nulo, ou a entrada de pasado é nulo,
pero, en vez de tratar con un punteiro pai,
imos aplicar a mesma lóxica dos punteiros mantendo a punteiros.
Aquí nós manter o noso nodo **, cur
e non precisa manter o control de máis correcto,
pero nó ** cur = árbore.
E agora o noso loop while será mentres cur * non nula igual.
Non é preciso manter o control de pais máis.
Non é preciso manter o control de esquerda e dereita.
E eu vou chamalo de tempo, porque xa estamos usando tempo.
Okay. Entón, se (valor> * tempo),
a continuación, e (* tempo) - dereito>
máis tempo = (* tempo) -> esquerda.
E agora, neste momento, tras este loop while,
Eu só fago iso porque quizais sexa máis fácil pensar iterativamente de forma recursiva,
pero despois deste loop while,
* Temp é o punteiro que desexa cambiar.
>> Antes tiñamos pai, e queriamos cambiar calquera pai ou nai esquerda a dereita,
pero se queremos cambiar dereito dos pais,
entón tempo * é dereito dos pais, e podemos mudalo directamente.
Entón, aquí, podemos facer * temp = newNode, e é iso.
Entón aviso, todo o que fixemos nesta era sacar liñas de código.
Co fin de seguir o pai en todo o que é o esforzo adicional.
Aquí, se nós só seguir o punteiro para o punteiro,
e mesmo que quería se librar de todas estas claves agora,
facela máis curta.
Agora é a solución exactamente o mesmo,
pero menos liñas de código.
Unha vez que comezar a recoñecer isto como unha solución válida,
tamén é máis fácil do que razoar sobre como, ok,
por que eu teño esta bandeira á dereita int?
O que significa isto? Oh, está significando que
Cada vez que vou ben, eu teño configure-lo,
outra cousa, se for aínda que, eu teño configuralo para cero.
Aquí, eu non teño a razón sobre iso, é só máis fácil de pensar.
Preguntas?
[Estudante, inintelixible] >> Yeah.
Ok, entón o último bit -
Eu creo que unha función sinxela e rápida que podemos facer é,
Imos - xuntos, eu creo, e tentar escribir un contén función
que non lle importa se é unha árbore de busca binaria.
Este contén función debe devolver True
en calquera lugar nesta árbore binaria xeral é o valor que estamos a buscar.
Entón, imos primeiro facer iso recursivamente e logo nós imos facelo de forma iterativa.
Nós realmente podemos só facelo xuntos, porque iso vai ser moi curto.
>> O que é o meu caso base vai ser?
[Estudante, inintelixible]
[Bowden] Entón, se (árbore == NULL), entón o que?
[Estudante] Voltar falso.
[Bowden] Else, así, eu non teño outro.
Se foi o meu caso outra base.
Valor [do estudante] árbore? Si >>.
Entón, se (árbore-> valor valor. ==
Teña en conta que estamos de volta ao * No non, no ** s?
Contén nunca vai ter usar un ** nodo,
unha vez que non está modificando de punteiros.
Nós só estamos atravesando eles.
Se isto acontecer, entón nós queremos voltar true.
Outra cousa que quere percorrer os nenos.
Polo tanto, non podemos razoar sobre todo para a esquerda é menos
e todo para a dereita e maior.
Entón o que está a nosa condición será aquí - ou, o que é que imos facer?
[Estudante, inintelixible] >> Yeah.
Retorno contén (valor, árbore-> esquerda)
ou contén (valor, árbore-> dereita). E é iso.
E en conta que hai algún tipo de avaliación de cortocircuíto,
onde se ocorrer de atopar o valor na árbore esquerda,
nunca necesitamos mirar para a árbore correcta.
Esa é a función enteira.
Agora imos facelo de forma iterativa,
que vai ser menos agradable.
Imos levar o comezo habitual do nodo actual * = árbore.
Mentres (act! = NULL).
Rapidamente vai ver un problema.
Se actual - aquí, se algunha vez saír desa,
entón, temos acabar de cousas para mirar, entón volva falso.
If (actual-> valor valor ==), retorna true.
Entón, agora, estamos nun lugar -
non sabemos se queremos ir á esquerda ou á dereita.
Entón, arbitrariamente, imos ir á esquerda.
Eu, obviamente, executar un problema onde eu completamente abandonado todo -
Eu sempre só comprobar no lado esquerdo dunha árbore.
Eu nunca vou comprobar todo o que é un dereito do neno de calquera cousa.
¿Como corrixir isto?
[Estudante] Ten que manter o control da esquerda e da dereita en unha pila.
[Bowden] Yeah. Entón, imos facelo
struct lista, no * n, e despois no ** próximo?
Eu creo que funciona ben.
Queremos ir máis á esquerda, ou imos - ata aquí.
Struct = Lista da lista, que vai comezar
fóra desta lista struct.
* Lista = NULL. Así que vai ser a nosa lista encadeada
de sub-árbores que pulamos.
Nós imos atravesar queda agora
pero desde que inevitablemente ten que volver para a dereita,
Nós imos manter o lado dereito dentro da nosa lista struct.
Entón nós imos ter new_list ou estrutura,
struct lista *, new_list = malloc (sizeof (lista)).
Vou ignorar verificación de erros que, pero ten que comprobar a ver se é nulo.
New_list o no que vai apuntar -
oh, é por iso que eu quería aquí. Vai apuntar unha lista struct segundo.
É así que conectado listas traballo.
Este é o mesmo como unha lista ligada int
excepto estamos só substituíndo int con * nodo.
É exactamente o mesmo.
Entón new_list, o valor do noso nodo new_list,
vai ser actual-> dereita.
O valor da nosa new_list-> seguinte vai ser a nosa lista orixinal,
e despois imos actualizar a nosa lista para apuntar para new_list.
>> Agora necesitamos algún tipo de forma de cousas tirando,
como temos atravesado toda a subárvore esquerda.
Agora necesitamos sacar algo de fóra,
como actual é nulo, nós non queremos só retornar falso.
Queremos agora tirar fóra a nosa nova lista.
Un xeito cómodo de facelo - Ben, en realidade, hai moitas maneiras de facelo.
Alguén ten algunha suxestión?
Onde eu debería facelo ou como eu debería facelo?
Nós só temos un par de minutos, pero algunha suxestión?
En vez de - unha forma, ao contrario da nosa condición de ser ao mesmo tempo,
o que estamos actualmente a analizar non é nulo,
en vez diso, imos continuar a ir ata a nosa propia lista é nulo.
Entón, se a nosa lista acaba sendo nula,
entón temos máis cousas para buscar, investigar.
Pero isto significa que a primeira cousa na nosa lista vai só para ser o primeiro en.
A primeira cousa que vai ser - non precisa ver iso.
Entón, lista-> n será a nosa árbore.
Lista-> seguinte vai ser nulo.
E agora, mentres que a lista non nula igual.
Cur vai tirar algo da nosa lista.
Entón actual vai igual lista-> n.
E entón lista vai igual lista-> n, ou lista-> seguinte.
Así se o valor é igual ao valor actual.
Agora podemos engadir tanto o punteiro noso dereito eo noso punteiro esquerdo
sempre que non é nulo.
Ata aquí, creo que debería ter feito isto en primeiro lugar.
Se (cur-> seguro! = NULL)
despois imos introducir o nó na nosa lista.
Se (cur-> esquerda), que é un pouco de traballo extra, pero está todo ben.
Se (cur-> esquerda! = NULL),
e imos introducir á esquerda na nosa lista ligada,
e que debe ser iso.
Repetimos - mentres temos algo na nosa lista,
temos outro no para ollar.
Entón, miramos para este nodo,
nós avanzamos nosa lista para a próxima.
Se ese nodo é o valor que estamos a buscar, podemos volver true.
Else introducir dúas subárvores nosa esquerda e á dereita,
sempre que non é nulo, na nosa lista
de xeito que, inevitablemente, pasar por riba deles.
Entón, se eles non foron nulos,
a nosa raíz punteiro apuntaba para dúas cousas,
a continuación, o primeiro, tirou algo para fóra para a nosa lista acaba sendo nulo.
E, entón, poñer dúas cousas de volta, agora a nosa lista de tamaño 2.
Entón imos facer un loop de volta e nós só estamos indo a tirar,
imos dicir, o punteiro esquerdo do noso nodo raíz.
E iso só vai continuar a suceder, nós imos acabar looping sobre todo.
>> Nótese que esta era significativamente máis complicado
na solución recursiva.
E eu xa dixen varias veces
que a solución recursiva ten normalmente moito máis en común coa solución iterativa.
Aquí é exactamente iso que a solución recursiva é facendo.
A única modificación é que en vez de implicitamente mediante a pila, a pila de programa,
como a súa forma de manter o control do que aínda precisa visitar,
agora ten que explicitamente usar unha lista ligada.
En ambos os casos está mantendo a par do que aínda precisa de a ser visitado.
No caso recursivo é só máis fácil, porque unha pila
é aplicado para ti como a pila do programa.
Nótese que esta lista ligada, é unha pila.
Todo o que pode poñer na pila
é inmediatamente o que nós imos retirar a pila para próxima visita.
Estamos fóra do tempo, pero algunha dúbida?
[Estudante, inintelixible]
[Bowden] Yeah. Entón, se temos a nosa lista ligada,
actual está indo a apuntar para este cara,
e agora nós estamos só avanzar nosa lista ligada a concentrar-se sobre este cara.
Estamos atravesando sobre a lista ligada nesa liña.
E entón eu creo que debemos liberar a nosa lista encadeada e outras cousas
unha vez antes de regresar verdadeiro ou falso, necesitamos
iterar sobre a nosa lista conexionada e sempre aquí, eu creo,
se actual dereito non é igual, engadir lo, entón agora queremos liberar
actual porque, así, que nos esquecemos completamente sobre a lista? Si
Entón é iso que queremos facer aquí.
Onde está o punteiro?
Cur era entón - queremos unha lista struct * 10 é igual a próxima lista.
Lista libre, list = tempo.
E no caso de que volvemos realidade, necesitamos iterar
sobre o resto da nosa lista ligada liberando cousas.
O agradable sobre a solución recursiva é liberar as cousas
significa só factorings popping fóra da pila que vai ocorrer para ti.
Entón, nós fomos algo que é como 3 liñas de difícil pensar sobre o código
a algo que é significativamente máis moitos de difícil pensar-sobre liñas de código.
Algunha pregunta?
Todo ben. Somos bos. Bye!
[CS50.TV]