[Powered by Google Translate] [Sekcja 7: More Comfortable] [Rob Bowden] [Harvard University] [To jest CS50] [CS50.TV] Dobrze. Tak jak powiedziałem w moim e-mail, to będzie binary-tree-intensywny sekcji. Ale nie ma, że ​​wiele pytań. Więc będziemy próbować wyciągać na każde pytanie i idź do bolesnego szczegółowo wszystkich najlepszych sposobów robienia rzeczy. Tak więc na samym początku, idziemy poprzez rysunki próbkowania drzew binarnych i rzeczy. Więc tutaj, "Pamiętaj, że drzewo binarne ma węzły podobne do tych z połączonej listy, chyba zamiast jednego wskaźnika są dwa: jeden dla lewego "dziecko" i jeden dla dziecka "prawej". " Więc drzewo binarne jest jak połączonej listy, z wyjątkiem struktury będzie miał dwa wskaźniki. Jest trójkowy drzewa, które będą mieć trzy wskaźniki, są N-ary drzew, które po prostu mają ogólny wskaźnik że musieli malloc być wystarczająco duże, aby tyle wskaźniki do wszystkich możliwych dzieci. Więc drzewo binarne okazuje się mieć stałą liczbę dwóch. Jeśli chcesz, możesz podać połączonej listy jako jednoargumentowej drzewa, ale nie sądzę, że ktoś nazywa go. "Narysuj pola-i-strzałki schemat węzła drzewa binarnego zawierającą ulubiony numer Nate'a, 7, gdzie każdy wskaźnik dziecko jest null. " Więc iPad mode. 

To będzie bardzo proste. My tylko będziemy mieć węzeł, narysuję go jako plac. A ja będę czerpać wartości tutaj. Więc wartość pójdzie tu, i tu będziemy mieć lewy wskaźnik na lewo i prawo wskaźnik po prawej stronie. I to jest bardzo wiele, więc konwencja nazwać to po lewej i prawej stronie, nazwy wskaźnika. Obie te będą nieważne. To będzie po prostu pusty, i że będzie po prostu null. Okay. Więc z powrotem tutaj. "Dzięki połączonej listy, mieliśmy tylko do przechowywania wskaźnika do pierwszego węzła na liście, aby zapamiętać całą listę, lub całą listę. Podobnie, z drzew, tylko do przechowywania wskaźnik w pojedynczym węźle, aby pamiętać całego drzewa. Ten węzeł jest calle 'root' z drzewa. Opierać się na diagramie z przed lub narysować nową takie, że masz skrzynie-i-strzałki Przedstawienie binarne drzewo o wartość 7, a następnie w 3 w lewo , a następnie 9 na prawo, a następnie 6 na prawo od 3 ". Zobaczmy, czy dobrze pamiętam to wszystko w mojej głowie. Więc to będzie nasz główny tutaj. Zjemy wskaźnik gdzieś, coś, co my nazywamy pierwiastek i to wskazuje na tego faceta. Teraz, aby utworzyć nowy węzeł, co mamy, 3 na lewo? Więc nowy węzeł z 3, i to początkowo wskazuje null. Ja po prostu postawić N. Teraz chcemy, aby to przejść z lewej 7. Więc zmienić ten wskaźnik do teraz wskazywać na tego faceta. I robimy to samo. Chcemy 9 tutaj które początkowo po prostu mówi null. Mamy zamiar zmienić ten wskaźnik, punkt do 9, i chcemy obecnie umieścić 6 do 3 prawa. Więc to będzie - zrób 6. I że facet będzie wskazywać tam. Okay. Więc to wszystko wymaga od nas uwagi. 

A teraz chodźmy na niektóre terminologii. Już rozmawialiśmy o tym, jak korzeń drzewa jest najwyżej położony węzeł w drzewie. Jeden zawierający 7. Węzły na dole drzewa nazywane są liście. Każdy węzeł, który ma tylko null jako jego dzieci jest liść. Tak to jest możliwe, jeśli nasze drzewo binarne jest tylko jeden węzeł, że drzewo jest liść, i to jest to. "'Height' z drzewa jest liczba przeskoków musisz dokonać aby dostać się z góry na liściu ". Zajmiemy się w sekundy, różnica między symetrycznych i niesymetrycznych drzew binarnych, ale teraz, całkowita wysokość tego drzewa Chciałbym powiedzieć, to 3, chociaż jeśli policzyć ilość chmielu trzeba zrobić, aby dostać się do 9, to jest to naprawdę tylko wysokość 2. Teraz jest to niesymetryczne drzewo binarne, ale my rozmawialiśmy o zrównoważony, gdy robi się istotne. Więc teraz możemy mówić o węzły w drzewie w kategoriach w stosunku do innych węzłów w drzewie. Więc mamy teraz rodzice, dzieci, rodzeństwo, przodków i potomków. Są one dość zdrowego rozsądku, co one oznaczają. Jeśli pytamy - to rodziców. Więc co jest rodzicem 3? [Studenci] 7. >> Tak. Rodzic jest po prostu będzie, co wskazuje na ciebie. Więc co to dzieci 7? [Studenci] 3 i 9. >> Tak. Zauważ, że "dzieci" oznacza dosłownie dzieci, tak 6 nie stosuje się, bo to jak wnuka. Ale potem, jeśli pójdziemy potomków, więc co to potomkowie 7? [Studenci] 3, 6 i 9. >> Tak. Potomkami węzła głównego będzie wszystko w drzewie, wyjątkiem może sam węzeł główny, jeśli nie chcesz, aby uznać, że potomek. I wreszcie, przodkowie, więc jest to w przeciwnym kierunku. Więc jakie są przodkowie 6? [Studenci] 3 i 7. >> Tak. 9 nie jest włączony. To jest po prostu bezpośredni rodowód powrotem do korzeni będzie wasi przodkowie. 

"Mówimy, że drzewo binarne jest" uporządkowane ", jeśli dla każdego węzła w drzewie, wszystkich jego potomków po lewej mają mniejsze wartości i wszystkie te na prawo mają większe wartości. Na przykład, wyżej drzewa zarządza, ale to nie jest możliwe tylko uporządkowanym ułożeniem. " Zanim przejdziemy do tego, sortowane Drzewo binarne jest również znany jako binarne drzewo wyszukiwania. Tu zdarzyć się nazywając ją uporządkowaną drzewa binarnego, ale nigdy nie słyszałem, że nazywa zamówić drzewo binarne przed, oraz quiz jesteśmy znacznie bardziej prawdopodobne umieścić drzewo binarne wyszukiwania. Oni są jednym i tym samym, i to jest ważne, aby rozpoznać różnicę między drzewa binarnego i drzewa wyszukiwania binarnego. Drzewo binarne jest tylko drzewo, które wskazuje na dwie rzeczy. Każdy węzeł wskazuje na dwie rzeczy. Nie ma żadnego uzasadnienia o wartościach, że wskazuje. Tak jak tutaj, ponieważ jest to drzewo binarne wyszukiwanie, Wiemy, że jeśli pójdziemy na lewo od 7, następnie wszystkie wartości, które możemy ewentualnie dotrzeć przechodząc lewej 7 musi być mniejsza niż 7. Należy zauważyć, że wszystkie wartości są mniejsze niż 7 3 i 6. Te są po lewej stronie 7. Jeśli idziemy na prawo od 7, wszystko musi być większa niż 7, tak 9 jest na prawo od 7, więc jesteśmy dobrzy. To nie przypadek binarne drzewo jest dla zwykłego drzewa binarny może po prostu mieć 3 na górze, 7 w lewo, 9 do 7 w lewo, nie ma uporządkowania wartości ogóle. Teraz, nie będzie faktycznie to zrobić, bo to nudne i niepotrzebne, ale "staramy się wyciągnąć tyle zamówionych drzew jak można myśleć za pomocą numerów 7, 3, 9, i 6. Ile odrębne ustalenia są tam? Co jest wysokość każdego? " 

Zrobimy kilka, ale główną ideą jest, jest to w żaden sposób wyjątkowy reprezentacji drzewa binarnego zawierającego te wartości. Wszystko, czego potrzebujesz to trochę drzewo binarne, które zawiera 7, 3, 6 i 9. Inny możliwy będzie ważne jeden korzeń 3 iść w lewo i to jest 6, idź w lewo i to jest 7, iść w lewo i to jest 9. To jest całkowicie poprawny drzewo wyszukiwania binarnego. To nie jest bardzo przydatne, bo to jest jak połączonej listy i wszystkie te wskaźniki są po prostu null. Ale to jest ważne drzewo. Tak? [Student] Czy nie wartości muszą być większe z prawej strony? Czy jest to -? >> To chciałem przejść na inny sposób. Jest też - tak, niech przełączyć to. 9, 7, 6, 3. Dobry chwyt. Nadal ma słuchać co search drzewo binarne ma robić. Tak więc na lewo Wszystko musi być mniejsza niż w danym węźle. Moglibyśmy po prostu przenieść, powiedzmy, ten 6 i umieścić go tutaj. Nie, nie możemy. Dlaczego wciąż to robi? Zróbmy - tutaj jest 6, tutaj jest 7, 6 punktów do 3. To jest nadal ważne drzewo wyszukiwania binarnego. Co jest nie tak jeśli ja - zobaczymy czy uda mi się wymyślić rozwiązania. Tak, w porządku. Więc co jest nie tak z tego drzewa? Chyba już wam wskazówkę, że coś jest nie tak z nim. Dlaczego wciąż to robi? Okay. Wygląda to rozsądne. Jeśli przyjrzeć się każdego węzła, jak 7, a następnie w lewo 7 jest 3. Więc mamy 3, rzecz z prawej 3 jest 6. I jeśli patrzeć na 6, w prawo, co 6 jest 9. Więc dlaczego nie jest to ważne drzewo wyszukiwania binarnego? [Studentów] 9 ciągle do lewej 7. >> Tak. To musi być prawda, że ​​wszystkie wartości można ewentualnie dotrzeć idąc z lewej 7 mniej niż 7. Jeśli idziemy na lewo od 7, mamy do 3 i możemy jeszcze dostać się do 6, można jeszcze dostać się do 9, ale już po mniej niż 7, nie powinniśmy być w stanie dotrzeć do wielu, które jest większe niż 7. Więc to nie ważne jest drzewo binarne wyszukiwania. 

Mój brat miał w rzeczywistości pytanie wywiad że był w zasadzie, po prostu kod do czegoś w celu weryfikacji czy drzewo to drzewo binarne wyszukiwanie, więc pierwszą rzeczą, jaką zrobił, było po prostu sprawdzić jeśli lewy i prawy są poprawne, a następnie iteracyjne tam. Ale nie możesz po prostu zrobić, masz do śledzenia z faktu, że teraz, kiedy już odszedł na lewo od 7, wszystko w tym poddrzewie musi być mniejsza niż 7. Algorytm poprawne musi śledzić w granicach, które może ewentualnie wartości mieszczą w. Nie będzie przejść przez wszystkie z nich. Jest miły stosunek nawrót, mimo, że nie dostał się do tych, czy nie będą się do nich, określenie, ile faktycznie istnieją. Tak więc istnieje 14 z nich. Pomysł w jaki sposób to zrobić matematycznie jest jak, można wybrać dowolny pojedynczy jeden, który będzie głównym węzłem, a następnie, jeśli wybiorę 7 jest węzeł główny, to nie są, powiedzmy, niektóre numery, które mogą go mieć mój lewy węzeł, i jest kilka numerów, które mogą być moje prawo węzeł Ale jeśli mam całkowitą liczbę n, to kwota, która może iść w lewo plus kwota, która może iść w prawo jest n - 1. Tak liczb pozostałych, muszą być w stanie przejść albo w lewo lub w prawo. Trudno, że jeśli mogę umieścić 3 pierwszy wtedy wszystko musi iść w lewo, ale jeśli mogę umieścić 7, to niektóre rzeczy mogą pójść w lewo i niektóre rzeczy mogą iść w prawo. Oraz '3 pierwszy "Chciałem wszystko może iść w prawo. To naprawdę, po prostu trzeba myśleć o tym, jak, jak wiele rzeczy może pójść na następnym poziomie drzewa. I to wychodzi się 14, lub można wyciągnąć wszystkich z nich, a dostaniesz 14. 

Wracając tu, "Zamówione binarne drzewa są fajne, bo można je przeglądać w bardzo podobny sposób do poszukiwania na posortowanej tablicy. Aby to zrobić, możemy zacząć od korzenia i wypracować sobie drogę w dół drzewa na liściach, sprawdzając każdy węzeł systemu wartości w odniesieniu do wartości mamy poszukujących. Jeśli bieżący węzeł wartość jest mniejsza od wartości szukamy, przejść obok węzła prawego dziecka. W przeciwnym razie przejdź do węzła lewego dziecka. W pewnym momencie, to albo będzie wartość, której szukasz, lub będziesz uruchomić do null, wskazując wartość nie jest w drzewie. " Muszę przerysować drzewo mieliśmy wcześniej, to zajmie chwilę. Ale chcemy patrzeć, czy 6, 10, i 1 są w drzewie. Więc co to było, 7, 9, 3, 6. Okay. Numery, które chcesz wyszukać, chcemy spojrzeć 6. Jak to działa algorytm? Cóż, mamy też trochę wskaźnik roota do naszego drzewa. I pójdziemy do korzenia i powiedzieć, czy jest to wartość równa wartości jesteśmy w poszukiwaniu? Więc szukamy 6, więc to nie jest równe. Więc wracamy, i teraz możemy powiedzieć, ok, więc 6 jest mniejsza niż 7. Czy to znaczy, że chcemy, aby przejść w lewo, czy chcemy iść na prawo? [Student] Lewy. >> Tak. Jest to znacznie łatwiejsze, wszystko co musisz zrobić, to wyciągnąć jedną możliwą węzła drzewa a następnie don't - zamiast starać się myśleć w głowie, dobrze, jeśli jest mniejsza, mam iść na lewo lub przejdź prawo, po prostu patrząc na to zdjęcie, to jest jasne, że muszę iść na lewo jeśli węzeł jest większy niż wartość szukam. Więc idź na lewo, teraz jestem w 3. Chcę - 3 jest mniejsza niż wartość Szukam, który jest 6. Idziemy więc w prawo, a teraz kończy się na 6, która jest wartością Szuka, więc zwróci true. Następna wartość Idę szukać jest 10. Okay. Więc 10, teraz będzie - obciąć, że - podąży korzenia. Teraz, 10 będzie większa niż 7, więc chcę spojrzeć w prawo. Mam zamiar przyjechać tu, 10 będzie większa niż 9, więc będę chciał spojrzeć w prawo. Przychodzę tutaj, ale tutaj teraz jestem na null. Co mam zrobić, jeśli uderzę null? [Student] Powrót fałsz? >> Tak. Nie mogę znaleźć 10. 1 będzie niemal identyczny przypadek, oprócz tego, że po prostu będzie odwrócony; zamiast szukać w dół z prawej strony, mam zamiar spojrzeć na lewą stronę. 

Teraz myślę, że rzeczywiście dostać się do kodu. Oto, gdzie - otwarcie CS50 urządzenie i nawigować drogę tam, ale możesz też zrobić to w przestrzeni. To chyba idealny to zrobić w przestrzeni, , ponieważ można pracować w przestrzeni. "Najpierw musimy nową definicję typu dla węzła drzewa binarnego zawierającego wartości int. Korzystanie boilerplate typedef poniżej utworzyć nową definicję typu dla węzła w drzewa binarnego. Jeśli utkniesz. . . "Bla, bla, bla. Okay. Więc postawmy boilerplate tutaj typedef struct node, i węzeł. Tak, w porządku. Więc jakie są pola Będziemy chcieli w naszym węźle? [Student] Int a następnie dwa wskaźniki? Int >> wartość, dwa wskaźniki? Jak napisać wskaźniki? [Student] Struct. >> Należy powiększyć Tak, więc węzeł struct * w lewo, i struct node * prawo. I pamiętam dyskusję z ostatniej chwili że to nie ma sensu, to nie ma sensu, to nie ma sensu. Musisz tam wszystko w celu zdefiniowania tego rekursywnego struct. Ok, więc to co nasze drzewo będzie wyglądać. Jeśli zrobiliśmy trinary drzewo, wówczas węzeł może wyglądać jak B1, B2, struct node * B3, gdzie b jest oddział - faktycznie, mam więcej to słyszeli, lewy, środkowy, prawy, ale nieważne. Interesują nas tylko binarne, więc w prawo, w lewo. "Teraz zadeklarować zmienną globalną * węzła do korzenia drzewa." Więc nie będziemy tego robić. W celu rzeczy nieco trudniejsze i bardziej uogólnione, nie będziemy mieć zmienną globalną węzła. Zamiast tego, w głównym będziemy deklarować wszystkie węzłów rzeczy, a to oznacza, że ​​poniżej, kiedy zaczną nasza funkcja zawiera i nasza funkcja insert, zamiast naszych obejmuje funkcje, tylko przy użyciu tej zmiennej globalnej węzła, będziemy mieć to przyjąć jako argument na drzewo, że chcemy go przetworzyć. Mając zmienną globalną miało to łatwiejsze. Wracamy do rzeczy trudniejsze. Teraz weź minut lub tak po prostu zrobić coś takiego, gdzie wewnątrz Głównym chcesz stworzyć z tego drzewa, i to wszystko, co chcę zrobić. Spróbuj zbudować to drzewo w głównej funkcji. 

Okay. Więc nie trzeba nawet skonstruowali drzewie przez całą drogę jeszcze. Ale każdy ma coś mogłem podciągnąć pokazać, jak można by rozpocząć budowę taką choinkę? [Student] Ktoś banging, próbując się wydostać. [Bowden] Każdy komfortowo z ich budowy drzewa? [Student] Jasne. To nie jest zrobione. >> Jest dobrze. Możemy po prostu skończyć - oh, można go zapisać? Brawo. Więc tutaj mamy - Och, jestem nieco obcięte. Mam powiększony? Powiększyć, przewinąć się. >> Mam pytanie. >> Tak? [Student] Po zdefiniowaniu struktury, są takie rzeczy jak inicjowany do niczego? [Bowden] L. >> Okay. Więc trzeba by zainicjować - [Bowden] L. Podczas definiowania lub podczas deklarowania struct, to nie jest inicjowany domyślnie to tylko jak jeśli zadeklarować int. To jest dokładnie to samo. To tak, jakby każdego z poszczególnych pól może mieć wartość śmieci w nim. >> I to jest możliwe do zdefiniowania - lub zadeklarować struct w sposób, który to robi zainicjować je? [Bowden] Tak. Więc, składnia inicjalizacji skrót będzie wyglądać - Są dwa sposoby, możemy to zrobić. Myślę, że powinniśmy go skompilować aby upewnić się, dzyń również to robi. Kolejność argumentów, że jest w tej struktury, umieścić jak kolejność argumentów wewnątrz tych klamrach. Więc jeśli chcesz zainicjować go 9 i lewo jest nieważna i następnie w prawo być null, byłoby 9, null, null. Alternatywą jest, a redaktor nie lubi tej składni, i myśli, chcę nowy blok, ale alternatywą jest coś takiego jak - tutaj, włożę go na nowej linii. Można jawnie powiedzieć, nie pamiętam dokładnej składni. Więc można wyraźnie uwzględnią je po imieniu i powiedzieć, . Wartość c lub. = 9,. Lewy = NULL. Zgaduję, te muszą być przecinki. . Prawo = NULL, więc w ten sposób nie zrobić rzeczywiście trzeba znać kolejność struct, i kiedy to czytasz, jest dużo bardziej wyraźne o tym, co jest wartością jest inicjowany. 

Dzieje się to za jedną z rzeczy, które - tak, w przeważającej części, C + + jest rozszerzeniem C Możesz wziąć kod C, przenieść go do C + +, i powinno się skompilować. To jest jedna z tych rzeczy, że C + + nie obsługują, więc ludzie starają się nie robić. Nie wiem czy to tylko dlatego ludzie starają się nie robić, ale w przypadku, gdy potrzebowałem go używać potrzebny do pracy z C + + i tak nie mogę tego użyć. Innym przykładem, że coś nie działa w C + + jest jak malloc zwraca "void *," technicznie, , ale można po prostu powiedzieć, char * x = malloc cokolwiek, i zostanie ona automatycznie rzutować na char *. Że automatyczne cast nie zdarza się w C + +. To nie byłoby skompilować, i jawnie trzeba powiedzieć char *, malloc, cokolwiek, by rzucić go na char *. Nie ma zbyt wielu rzeczy, C i C + + nie zgadzają się, ale to są dwa. Więc idziemy z tym składni. Ale nawet jeśli nie byliśmy z tym składni co to jest - może być w tym złego? [Student] I nie trzeba dereference go? >> Tak. Pamiętaj, że strzałka jest niejawna dereference, a więc gdy jesteśmy po prostu do czynienia z struct, chcemy wykorzystać. aby dostać się w środku pola struktury. I tylko raz używamy strzałki jest wtedy, gdy chcemy zrobić - dobrze, strzałka jest równoważne - to co by to oznaczało, gdyby kiedyś strzałkę. Wszystkie środki strzałka, dereference to, teraz jestem w struct, i mogę to pole. Albo dostać pole bezpośrednio lub nieprawidłowego i inne pola - Myślę, że to powinno być napięcie. Ale tutaj mam do czynienia tylko z struct, a nie wskaźnik do struktury, a więc nie można użyć strzałki. Ale takie rzeczy możemy zrobić dla wszystkich węzłów. O mój Boże. Jest 6, 7, i 3. Następnie możemy skonfigurować oddziały w naszym drzewie, możemy mieć 7 - Możemy mieć, jego lewy powinien wskazywać na 3. Więc jak to zrobić? [Studenci, niezrozumiały] >> Tak. Adres node3, a jeśli nie ma adresu, to po prostu nie skompilować. Ale pamiętaj, że są to wskaźniki do kolejnych węzłów. Prawo to powinno wskazywać na 9, i 3 powinny być skierowane na prawo do 6. Myślę, że to wszystko. Wszelkie uwagi lub pytania? [Student, niezrozumiały] korzeń będzie 7. Możemy tylko powiedzieć węzeł * ptr = lub root = & node7. 

Dla naszych celów, będziemy mieć do czynienia z wkładką, więc będziemy chcieli napisać funkcję, aby dodać do tego drzewa binarnego i wkładka jest nieuchronnie zamiar zadzwonić malloc utworzyć nowy węzeł tego drzewa. Więc wszystko się bałagan z tym, że niektóre węzły Obecnie na stosie i pozostałe węzły są skończy się na stercie kiedy włożyć. Jest to całkowicie prawidłowy, ale jedynym powodem jesteśmy w stanie to zrobić na stosie ponieważ jest to taki dobry przykład, że wiemy drzewa ma być wykonane, 7, 3, 6, 9. Jeżeli nie są w tym, że to nie ma malloc w pierwszej kolejności. Jak zobaczymy nieco później, powinniśmy malloc'ing. Teraz jest to całkowicie uzasadnione umieścić na stosie, ale zmieńmy to do wykonania malloc. Tak więc każdy z nich jest teraz będzie coś jak node * node9 = malloc (sizeof (node)). A teraz będziemy musieli zrobić naszą kontrolę. if (node9 == NULL) - nie chcę, że - zwraca 1, a następnie możemy zrobić node9-> bo teraz to jest wskaźnik, wartość = 6, node9-> lewy = NULL, node9-> prawy = NULL, i będziemy musieli zrobić, że dla każdego z tych węzłów. Zamiast więc, postawmy go wewnątrz osobnej funkcji. Nazwijmy to węzeł * build_node, i jest nieco podobny do API Zapewniamy Huffmana. Dajemy Ci funkcje inicjatora dla drewna i Deconstructor "funkcje" w odniesieniu do tych samych drzew i do lasów. 

Więc będziemy mieć funkcję inicjatora wystarczy zbudować węzeł dla nas. I to będzie wyglądało prawie dokładnie tak, jak to. A ja nawet będzie leniwy i nie zmieniać nazwy zmiennej, chociaż node9 ma sensu już. Och, myślę, że jego wartość node9 nie powinno było 6. Teraz możemy wrócić node9. I tu powinniśmy wrócić null. Wszyscy zgadzają się, że funkcja build-węzłów? Więc teraz możemy po prostu zadzwonić, że aby zbudować dowolny węzeł o podanej wartości i wskazówki null. Teraz możemy wywołać, że możemy zrobić węzeł * node9 = build_node (9). I zróbmy. . . 6, 3, 7, 6, 3, 7. A teraz chcemy ustawić te same wskaźniki, chyba teraz wszystko jest już w zakresie wskaźników więc nie trzeba już adres. Okay. Więc co jest ostatnią rzeczą jaką chcesz zrobić? Jest sprawdzania błędów, że nie robię. Co zbudować powrót węzła? [Student, niezrozumiały] >> Tak. Jeśli malloc nie, powróci, null. Więc mam zamiar umieścić go leniwie tu zamiast z tym warunek dla każdego. Jeśli (node9 == NULL, lub - jeszcze prostsze, odpowiada to tylko jeśli nie node9. Więc jeśli nie node9 lub nie node6 lub nie node3 lub nie node7, powrót 1. Może powinniśmy wydrukować malloc nie powiodło się, czy coś takiego. [Student] Czy false równa null, jak również? [Bowden] Każda wartość zerowa jest fałszywa. Więc null jest wartość zerowa. Zero to zero. False jest wartość zerowa. Wszelkie - dość dużo tylko 2 wartości zerowe są nieważne i zero, false jest tylko hash definiowana jako zero. Dotyczy to również, jeśli nie deklarują zmienną globalną. Jeśli mieliśmy rdzenia * węzła tu, następnie - Ciekawą rzeczą jest to, że zmienne globalne zawsze mają wartość początkową. To nie prawda funkcji, jak wewnątrz tutaj jeśli mamy, na przykład, node * lub x węzła. Nie mamy pojęcia, co x.value, x.whatever, albo możemy je wydrukować i mogą być dowolne. To nie prawda ze zmiennych globalnych. Więc węzeł główny lub x węzła. Domyślnie, wszystko to jest globalne, jeśli nie jawnie zainicjowane pewną wartość, ma wartość zero, jako wartości. Więc tutaj, root * węzeł, nie jawnie zainicjować go do niczego, więc jego wartość domyślna będzie wartość null, która jest zerowa wartość wskaźników. Domyślna wartość x będzie oznaczać, że x.value jest zero, x.left jest null, a x.right jest null. Tak, ponieważ jest to struct, wszystkie pola tej struktury będą wartości zerowe. Nie trzeba używać, że tutaj, choć. [Ilustracja] elemencie są różne od innych zmiennych, a inne zmienne są wartości śmieci; są zer? [Bowdena] Inne wartości też. Więc w x, x będzie równa zeru. Jeśli to jest w zakresie globalnym, ma wartość początkową. >> Okay. [Bowden] Albo wartość początkowa dałeś go lub zero. Myślę, że zajmuje się tym wszystkim. 

Okay. Więc następnym część pytania pyta "Teraz chcemy napisać funkcję o nazwie zawiera z prototypem bool zawiera wartość typu int. " Nie będziemy robić bool zawiera wartość typu int. Nasz prototyp będzie wyglądać bool zawiera (wartość typu int. A potem mamy również zamiar przekazać go na drzewo że należy sprawdzanie, czy ma tę wartość. Więc node * drzewo). Okay. I wtedy możemy nazwać to coś w stylu: być może będziemy chcieli printf lub czegoś. Zawiera 6, nasz główny. To powinno zwrócić jeden lub prawdziwe, natomiast zawiera 5 root powinien return false. Więc weź sekund do realizacji tego. Można to zrobić albo iteracyjnie lub rekurencyjnie. Zaletą sposobu mamy ustawić rzeczy jest to, że to nadaje się do naszego rekurencyjnego rozwiązania jest znacznie łatwiejsze niż globalna zmienna sposób zrobił. Bo jeśli mamy tylko wartości int zawiera, to nie mają możliwości rekurencji dół poddrzewa. Musielibyśmy mieć oddzielną funkcję pomocnika, który recurses dół poddrzewa dla nas. Ale od kiedy zmienił go do podjęcia drzewo jako argument, które należy zawsze w pierwszej kolejności, teraz możemy recurse łatwiej. Więc iteracyjne lub rekurencyjne, pójdziemy na obu, ale zobaczymy, że cykliczne kończy się całkiem proste. Okay. Czy ktoś ma coś, co możemy pracować? 

[Student] Mam iteracyjne rozwiązanie. >> Dobra, wielokrotnie. Dobra, to wygląda dobrze. Więc, chcesz iść z nami przez to? [Student] Jasne. Tak ustawić zmienną temp zdobyć pierwszy węzeł drzewa. A potem po prostu zapętlone podczas temp nie równa null, więc gdy był jeszcze w drzewie, tak myślę. I jeśli wartość jest równa wartości, że temperatura jest wskazanie, następnie zwraca tę wartość. W innym przypadku, to sprawdza czy nie jest po prawej lub lewej stronie. Jeśli kiedykolwiek sytuacji, w której nie ma już drzewa, wówczas zwraca - wychodzący z pętli i zwraca false. [Bowden] Dobra. Tak, że wydaje się być dobra. Ktoś ma jakieś uwagi na temat czegokolwiek? Nie mam żadnych uwag poprawności w ogóle. Jedna rzecz, którą możemy zrobić, to ten facet. Oh, to się go trochę wydłużone. Zrobię to w górę. Okay. 

Każdy powinien pamiętać, jak potrójny działa. Istnieją na pewno zostały quizy w przeszłości że ci funkcji z operatora trójskładnikowych i powiedzieć, przetłumaczyć, zrobić coś, co nie używa trójskładnikowych. Więc to jest bardzo częstym przypadkiem, kiedy Myślę korzystać trójskładnikowych gdzie jeśli jakiś warunek ustawić zmienną do czegoś, jeszcze ustawić tą samą zmienną, do czegoś innego. To coś, co bardzo często może być przekształcony w tego rodzaju rzeczy gdzie ustawić zmienną do tego - czy dobrze, czy to prawda? Wtedy to, jeszcze to. [Student] Pierwszy to czy prawda, prawda? [Bowden] Tak. Sposób zawsze czytać to, temp. wynosi wartość większą niż wartość temp, wtedy to jeszcze to. To zadaje pytanie. Czy jest większy? Następnie wykonaj pierwszą rzeczą. Jeszcze zrobić drugą rzeczą. I prawie zawsze - dwukropek, po prostu - w mojej głowie, czytałem jak jeszcze. 

Czy ktoś ma rekurencyjne rozwiązanie? Okay. Ten będziemy - może być już wielki, ale mamy zamiar zrobić to jeszcze lepiej. To jest prawie tak samo dokładny pomysł. To jest po prostu, no, chcesz wyjaśnić? [Student] Jasne. Jesteśmy więc upewnić się, że drzewo nie jest null pierwsze, bo jeśli drzewo jest null, a następnie to się zwróci false, ponieważ nie znalazłem. A jeśli jest jeszcze drzewo, wchodzimy - musimy najpierw sprawdzić, czy wartość bieżącego węzła. Zwraca true, jeśli jest, a jeśli nie mamy recurse na lewo lub prawo. Czy nie brzmi to właściwe? >> Mm-hmm. (Umowa) Tak więc zauważyć, że jest to praktycznie - strukturalnie bardzo podobne do rozwiązania iteracyjnego. Tyle, że zamiast rekurencji, mieliśmy pętli while. I bazowym tutaj gdzie drzewa nie równa wartości null był stan, w którym rozstaliśmy się z pętli while. Są bardzo podobne. Ale idziemy do pójścia krok dalej. Teraz możemy zrobić to samo tutaj. Wskazówka Wracamy samo w obu tych liniach, wyjątkiem jeden argument jest inny. Więc mamy zamiar sprawić, że w trójskładnikowych. I coś uderzyć opcji, i to symbol. Okay. Więc mamy zamiar wrócić zawiera tego. To zaczyna być wiele linii, dobrze, powiększony jest. Zazwyczaj, pod względem stylistycznym rzeczy, nie sądzę, wielu ludzi postawić spację po strzałki, ale myślę, że jeśli jesteś konsekwentny, to dobrze. Jeżeli wartość jest mniejsza od wartości drzewa, chcemy recurse na lewej drzewa, else chcemy rekursja po prawej drzewa. Tak, że był jednym z krokiem co to wygląda mniejsze. Kroku drugiego co to wygląda mniejsze - możemy oddzielić to na wielu liniach. Okay. Krok drugi z co wyglądają mniejsze jest tutaj, więc wartość zwracana równa wartości drzewa, lub zawiera cokolwiek. 

To jest ważne. Nie jestem pewien, czy powiedział to wyraźnie w swojej klasie, ale to się nazywa zwarcie oceny. Chodzi o to, wartość == wartość drzewa. Jeśli to prawda, to jest prawda, a my chcemy "albo" że z tym, co jest tutaj. Więc nawet nie myśląc o to, co jest tutaj, co jest całe wyrażenie zamiar wrócić? [Student] True? >> Tak, bo prawda o niczym, or'd - czy prawdziwe or'd z niczego jest to prawda. Tak szybko, jak widzimy wartości zwracanej = wartość drzewa, jesteśmy po prostu wrócą prawdziwe. Nawet nie będzie rekursja zawiera ponadto wzdłuż linii. Możemy podjąć ten jeden krok dalej. Drzewo powrót nie równy null, a wszystko to robi. To sprawiło, że jedna linia funkcji. Jest to również przykład oceny zwarcia. Ale teraz jest sam pomysł - zamiast - więc jeśli drzewo nie jest równa null - ani dobrze, jeśli drzewo jest równa null, który jest zły przypadek, jeśli drzewo jest równy null, a następnie pierwszy warunek będzie fałszywy. Tak fałszywe anded z czymkolwiek będzie, co? [Student] False. >> Tak. To jest druga połowa oceny zwarcia, gdzie jeśli drzewo nie jest równa null, wówczas nie będziemy nawet iść - lub jeśli drzewo nie równe NULL, to nie będziemy robić wartość == wartość drzewa. Jesteśmy po prostu się do natychmiastowego zwrotu false. Co jest ważne, ponieważ jeśli nie zrobił zwarcie oceny, następnie, jeśli drzewo jest równa null, to drugi warunek będzie winy seg, bo drzewo-> wartość dereferencji null. Więc to jest to. Może to - zmieniać raz na. To jest bardzo często rzeczą także, nie czyniąc tę ​​jedną linię z tego, ale to jest coś wspólnego w warunkach, może nie tu, ale jeśli (drzewo! = NULL, a tree-> wartość value ==), zrobić cokolwiek. Jest to bardzo częste schorzenie, gdzie zamiast podzielenie na dwie ifs, gdzie chce, jest zerowy drzewo? Ok, to nie jest null, to teraz jest to wartość równa wartości drzewo? To zrobić. Zamiast tego, ten stan, to nigdy nie seg winy ponieważ będzie to przebić, czy to dzieje się null. Cóż, myślę, że jeśli drzewo jest całkowicie nieprawidłowy wskaźnik, to może jeszcze seg winy, ale nie może seg błędu, jeśli drzewo jest null. Gdyby to był zerowy, to wybuchnie przed kiedykolwiek dereferencjonowane wskaźnik w pierwszej kolejności. [Student] Czy to tzw leniwy ocena? 

[Bowden] Lazy ocena jest osobna sprawa. Lazy ocena jest bardziej jak poprosić o wartości, poprosić, aby obliczyć wartość, rodzaj, ale nie trzeba go natychmiast. Więc dopóki rzeczywiście trzeba, to nie jest oceniany. To nie jest dokładnie to samo, ale w Huffman PSET, mówi, że my "leniwie" pisać. Powodem robimy to dlatego, że jesteśmy faktycznie buforowanie zapisu - Nie chcemy pisać poszczególnych bitów na raz, lub pojedynczych bajtów na raz, zamiast tego chce się kawałek bajtów. Następnie raz mamy kawałek bajtów, wtedy piszemy go. Nawet jeśli zapytać go napisać - i fwrite i fread zrobić tego samego rodzaju rzeczy. Oni buforować Twój czyta i pisze. Nawet jeśli prosi ją napisać od razu, to prawdopodobnie nie będzie. I nie możesz być pewien, że wszystko będzie napisane czasu wywołania hfclose czy cokolwiek to jest, która następnie mówi, dobrze, jestem zamykania mój plik, to oznacza, że ​​lepiej napisać wszystko, że nie pisałem jeszcze. To nie ma potrzeby pisania wszystkiego aż zamykamy plik, a następnie musi. Tak, że tylko to, co leniwy - to czeka, aż ma się wydarzyć. To - podejmuje 51, a dojdziesz do niego w sposób bardziej szczegółowy, bo OCaml i wszystko w 51, wszystko jest rekurencja. Nie ma iteracyjnego rozwiązania, w zasadzie. Wszystko jest rekurencja i leniwa ewaluacja będzie ważne dla wielu okolicznościach gdzie, jeśli nie leniwie ocenia, że ​​myśli - Przykład strumienie, które są nieskończenie długo. W teorii można myśleć liczb naturalnych jako strumień 1-2-3-4-5-6-7, Tak leniwie ocenianych rzeczy są w porządku. Jeśli powiem, że chcę dziesiątą cyfrę, wtedy mogę ocenić do dziesiątego numeru. Jeśli chcę setnej numer, to mogę ocenić do setnej liczby. Bez leniwej ewaluacji, to jest to postaram się ocenić wszystkie numery natychmiast. Jesteś oceny nieskończenie wiele liczb, i to nie tylko możliwe. Tak więc istnieje wiele sytuacji, w której ocena leniwy jest po prostu konieczne do uzyskania rzeczy do pracy. 

Teraz chcemy napisać wkładkę gdzie wkładka będzie Podobnie zmieniają się w jego definicji. Więc teraz to bool insert (int value). Mamy zamiar zmienić na bool wkładką (wartość int, node * drzewo). Jesteśmy rzeczywiście się zmieni, że ponownie w nieco, zobaczymy dlaczego. I przejdźmy build_node, tylko dla heck tego, powyżej wstawić więc nie mamy napisać prototyp funkcji. Która jest znak, że masz zamiar używać build_node w płytki. Okay. Poświęć chwilę na to. Myślę, że uratował rewizję, jeśli chcesz wyciągnąć z tego, lub, przynajmniej, ja teraz. Chciałem nieznaczne przerwy myśleć o logice wkładką, jeśli nie można myśleć. Zasadniczo będzie tylko kiedykolwiek wkładając w liściach. Podoba Ci się, jeśli mogę wstawić 1, to się nieuchronnie będzie wstawienie 1 - Zmienię na czarno - ll być wstawienie 1 tutaj. Albo jeśli wstawić 4, chcę być wstawienie 4 tutaj. Więc nie ma znaczenia, co robisz, masz zamiar być wstawienie na liściu. Wszystko co musisz zrobić, to iteracyjne w dół drzewa, aż dojdziesz do węzła To powinno być węzła rodzica, nowy węzła rodzica, a następnie zmienić jego lewego lub prawego kursora, w zależności od tego, czy jest większa lub mniejsza od bieżącego węzła. Zmienić ten wskaźnik do punktu do nowego węzła. Więc iteracyjne dół drzewa sprawiają, że punkt skrzydła do nowego węzła. Także myślę, że o tym, dlaczego zabrania typu sytuacji przed, gdzie zbudował drzewo binarne, gdzie to było prawidłowe jeśli tylko spojrzał na jednym węźle, ale 9 było z lewej 7 jeśli powtórzyć w dół do oporu. Tak, że to niemożliwe w tym scenariuszu, ponieważ - myślę o włożeniu 9 lub coś; w węźle pierwszy, Idę zobaczyć 7 i mam zamiar iść na prawo. Więc nie ma znaczenia, co zrobić, jeśli mam wstawienie przechodząc do liścia, liścia i za pomocą odpowiedniego algorytmu to będzie dla mnie niemożliwe włóż 9 z lewej 7 bo jak tylko uderzyć 7 mam zamiar iść na prawo. Czy ktoś ma coś na początek? [Student] ja. >> Jasne. [Student, niezrozumiały] [Inny student, niezrozumiały] [Bowden] Jest doceniana. Okay. Chcesz wyjaśnić? 

[Student] Ponieważ wiemy, że były wstawianie nowych węzłów na koniec, drzewa I przelotowe drzewie iteracyjnie dopóki nie wróciłem do węzła, który wskazał na null. A następnie postanowiłem umieścić albo na prawej lub lewej zastosowaniem właściwej zmiennej, to powiedział mi, gdzie go umieścić. A potem, w istocie, Zrobiłem że ostatni - które wskazują temperatury węzła do nowego węzła tworzącego go, albo z lewej strony lub z prawej strony, w zależności od tego, co było w prawo wartość. Wreszcie mogę ustawić nową wartość węzła do wartości jego testowania. [Bowden] Okay, więc widzę jeden problem tutaj. Jest to 95%, jak na drodze. Jeden problem, że widzę, dobrze, czy ktoś jeszcze zobaczyć jakiś problem? Co to jest okoliczność, w ramach którego wyrwać się z pętli? [Student] Jeśli temperatura jest null? >> Tak. Więc jak wyrwać się z pętli, jeśli temperatura jest null. Ale co mam zrobić tutaj? I temp dereference, który jest nieunikniony null. Tak więc inne rzeczy trzeba zrobić, to nie tylko śledzić aż temp jest null, chcesz śledzić dominującej w każdej chwili. Chcemy również rodzica * węzła, myślę, że możemy zachować na NULL na początku. To będzie mieć dziwne zachowanie dla korzenia drzewa, ale dojdziemy do tego. Jeśli wartość jest większa niż cokolwiek, to temp = temp prawo. Ale zanim to zrobimy, rodzic temp =. A rodzice zawsze będzie równy temp? Czy to przypadek? Jeśli temperatura nie jest pusta, to mam zamiar przejść w dół, nie wiem co, do węzła, dla którego temperatura jest rodzicem. Więc rodzic będzie temp, a następnie przenieść temp dół. Teraz temperatura jest null, ale zwraca rodzica do rodzica z rzeczy, która jest null. Więc tu, nie chcę, aby ustawić prawa równa 1. Więc przeniosłem się w prawo, więc jeśli prawo = 1, i myślę, że również chcesz zrobić - Jeśli przeniesiesz się w lewo, chcesz ustawić prawa równe 0. Albo jeśli kiedykolwiek przesunąć w prawo. Więc prawo = 0. Jeśli prawo = 1, Teraz chcemy, aby nadrzędny prawą newnode wskaźnika, else chcemy macierzysty lewy newnode wskaźnika. Pytania na temat tego? Okay. Więc to jest sposób - dobrze, właściwie, zamiast robić to, my pół spodziewać korzystanie build_node. A jeśli newnode równa null, zwraca fałsz. To jest to. Teraz, to jest to, czego spodziewaliśmy Ci zrobić. 

To właśnie pracownicy rozwiązują zrobić. Nie zgadzam się z tym, jak "prawo" sposób będzie o nim ale to jest w porządku i będzie działać. Jedna rzecz, że to trochę dziwne, teraz jest jeśli drzewo zaczyna się za nieważną, przekazujemy w pustym drzewie. Myślę, że to zależy od tego, w jaki sposób zdefiniować zachowanie przechodzącą w pustym drzewie. Myślę, że jeśli przejdą w pustym drzewie, następnie wpisując wartość w pustym drzewie Należy po prostu wrócić na drzewo, gdzie jedyną wartością jest to, że jeden węzeł. Czy ludzie się z tym zgodzić? Można, jeśli chcesz, jeśli przejdą w pustym drzewie i chcesz wstawić wartość do niego, return false. To do ciebie, aby określić, że. Aby to zrobić, pierwszą rzeczą, powiedziałem, a następnie - dobrze, będziesz mieć problemy robi, że ze względu byłoby łatwiej, gdybyśmy mieli globalny wskaźnik do rzeczy, ale nie, więc jeśli drzewo jest pusty, nic nie możemy zrobić. Możemy po prostu return false. Więc mam zamiar zmienić wkładkę. Jesteśmy technicznie może po prostu zmienić to właśnie tutaj, jak to jest iteracja rzeczy, ale mam zamiar zmienić wkładkę do podjęcia węzeł drzewa **. Podwójne wskaźniki. Co to znaczy? Zamiast zajmować się wskaźniki do węzłów co mam zamiar manipulować to jest wskaźnik. Mam zamiar manipulować ten wskaźnik. Idę do manipulowania wskaźniki bezpośrednio. Ma to sens, ponieważ myślę o dół - no, teraz to wskazuje na null. Co chcę zrobić jest manipulować ten wskaźnik, aby wskazywał nie null. Chcę zwrócić do mojego nowego węzła. Jeżeli po prostu śledzić wskaźniki do moich wskazówek, wtedy nie trzeba śledzić wskaźnik dominującej. Mogę tylko śledzić, czy wskaźnik wskazuje na null, i jeśli wskaźnik wskazuje na null, zmienić, aby wskazać węzeł chcę. I mogę to zmienić, ponieważ mam wskaźnik do wskaźnika. Zobaczmy tego teraz. Rzeczywiście można to zrobić rekurencyjnie dość łatwo. Czy chcemy, aby to zrobić? Tak, wiemy. 

Zobaczmy to rekurencyjnie. Po pierwsze, co jest naszym bazowym będzie? Prawie zawsze naszym bazowym, ale faktycznie, jest to rodzaj trudne. First things first, if (drzewo == NULL) Myślę, że jesteśmy po prostu będzie return false. To różni się od drzewa puste. Jest to wskaźnik wskaźnikiem głównym rygorem co oznacza, że ​​wskaźnik root nie istnieje. Tak więc i tutaj, jeśli mam zrobić * node - niech tylko ponownie to. Node * root = NULL, i mam zamiar zadzwonić wkładkę wykonując coś jak, wstaw 4 w & korzenia. Więc i root, jeśli korzeń jest * node wtedy i korzeń będzie ** węzła. To jest ważne. W tym przypadku, drzewo, tutaj, drzewo nie jest null - lub wkładka. Tutaj. Drzewo nie jest null; drzewo * jest null, co jest w porządku bo jeśli drzewo * jest null, a następnie można manipulować do teraz wskazać co chcę wskazać. Ale jeśli drzewo jest null, co oznacza, że ​​po prostu przyszedł tutaj i powiedział null. To nie ma sensu. Nie mogę nic zrobić z tym. Jeśli drzewo jest null, zwraca fałsz. Więc w zasadzie już powiedział, co nasza prawdziwa bazowym jest. A co to będzie? [Student, niezrozumiały] [Bowden] Tak. Więc jeśli (* drzewo == NULL). To odnosi się do przypadku tutaj gdzie jeśli mój czerwony wskaźnik jest wskaźnikiem Ja koncentruje się na, tak jakbym koncentrowały się na tym wskaźniku, teraz jestem koncentruje się na tym wskaźniku. Teraz jestem skoncentrowany na tym wskaźnikiem. Więc jeśli mój czerwony wskaźnik, który jest moim ** węzłów, jest zawsze - jeśli *, mój czerwony wskaźnik, jest zawsze pusty, to oznacza, że ​​jestem w przypadku gdy jestem koncentrując się na wskaźnik, który wskazuje - jest to wskaźnik, że należy do liści. Chcę zmienić ten wskaźnik do punktu do nowego węzła. Wracaj tutaj. Mój newnode będzie tylko węzeł * n = build_node (wartość) następnie n, jeśli n = NULL, zwraca fałsz. Else chcemy zmienić to, co jest obecnie wskaźnik wskazując do teraz zwrócić do naszego nowo wybudowanego węzła. Rzeczywiście możemy zrobić tutaj. Zamiast mówić n mówimy * drzewo = jeśli drzewa *. Wszyscy rozumieją, że? Że zajmując się wskaźniki do wskaźników, możemy zmienić zerowe wskaźniki wskazać na rzeczy, które chcemy im wskazać. To nasza sprawa bazy. 

Teraz nasz nawrotu, lub nasz rekursji, będzie bardzo podobny do wszystkich innych rekursji robiliśmy. Będziemy chcieli, aby wstawić wartość, i teraz mam zamiar używać trójskładnikowej ponownie, ale to, co jest nasz stan będzie? Co to jest to, czego szukamy, aby zdecydować, czy chcemy iść w lewo czy w prawo? Zróbmy to w oddzielnych etapach. Jeśli (wartość <) co? [Student] drzewie jego wartość? [Bowden] Więc pamiętaj, że jestem obecnie - [Studenci, niezrozumiały] [Bowden] Tak, tak, właśnie tutaj, powiedzmy, że ta zielona strzałka przykład, co obecnie jest drzewo, jest wskaźnik do wskaźnika. To znaczy, że jestem wskaźnik do wskaźnika do 3. Dereference dwukrotnie brzmi dobrze. Co ja - jak to zrobić? [Student] dereference raz, a następnie do arrow ten sposób? [Bowden] Tak (drzewo *) jest dereference raz -> wartość ma dać mi wartość węzła, że ​​jestem pośrednio wskazując. Więc mogę też napisać to ** tree.value jeśli wolisz. Albo działa. Jeśli tak jest, to chcę zadzwonić wstawić z wartością. A jakie jest moje aktualizowane node ** będzie? Chcę iść na lewo, więc tree.left ** będzie moja lewa. I chcę, wskaźnik do tej rzeczy tak, że jeśli w lewo kończy się pusty wskaźnik, Można zmodyfikować go zwrócić do mojego nowego węzła. 

I innym przypadku może być bardzo podobne. Miejmy faktycznie sprawiają, że mój trójskładnikowych teraz. Wstawianie wartości, jeśli wartość <(drzewo. **) Wartość. Następnie chcemy zaktualizować nasze ** w lewo, else chcemy zaktualizować nasze ** w prawo. [Student] Czy aby uzyskać wskaźnik do wskaźnika? [Bowden] Pamiętaj, że - ** tree.right jest węzeł star. [Student, niezrozumiały] >> Tak. ** Tree.right jest jak ten wskaźnik, czy coś. Więc biorąc wskaźnik do tego, że daje mi to, co chcę wskaźnika do tego faceta. [Student] Czy możemy wrócić jeszcze raz, dlaczego są za pomocą dwóch wskaźników? [Bowden] Tak. Tak więc - nie można, i że przed rozwiązaniem był sposób z tym nie robiąc dwa wskaźniki. Musisz być w stanie zrozumieć, przy użyciu dwóch wskaźników, i jest to rozwiązanie do czyszczenia. Zauważ też, że to, co się stanie, gdy drzewo - co się stanie, jeśli mój korzeń null? Co się dzieje, jeśli mam zrobić w tej sprawie tutaj? Więc node * root = NULL, włóż 4 do & korzenia. Co to jest korzeń będzie po tym? [Student, niezrozumiały] >> Tak. Wartość korzeń będzie 4. Lewy korzeń będzie null, prawy korzeń będzie null. W przypadku, gdy nie graniowej według adresu, nie możemy modyfikować korzeń. W przypadku, gdy drzewa - gdzie korzeń null po prostu musieliśmy wrócić false. Nic nie mogliśmy zrobić. Nie możemy wstawić do pustego węzła drzewa. Ale teraz możemy, my po prostu zrobić pustą drzewa do drzewa jeden-węzła. Który jest zwykle oczekiwany sposób, to powinno działać. 

Ponadto, jest to znacznie krótszy niż również śledzenie rodzica i tak iteracyjne dół całą drogę. Teraz mam rodziców, a ja po prostu mam wskaźnik właściwej nadrzędnego do cokolwiek. Zamiast tego, jeśli zrobiliśmy to iteracyjnie, to będzie ten sam pomysł z pętlą while. Ale zamiast do czynienia z moim wskaźnikiem dominującej, zamiast mój obecny wskaźnik byłoby rzeczą że jestem bezpośrednią modyfikację zwrócić do mojego nowego węzła. Nie mam do czynienia z tym, czy to, wskazując na lewo. Nie mam do czynienia z tym, czy to, wskazując na prawo. To tylko, co to jest wskaźnik, mam zamiar ustawić go zwrócić do mojego nowego węzła. Wszyscy rozumieją, jak to działa? Jeśli nie, dlaczego chcemy to zrobić w ten sposób, ale przynajmniej, że to działa jak rozwiązanie? [Student] Gdzie wrócimy prawda? [Bowden] To chyba tu. Jeśli poprawnie włożyć, zwróci true. Indziej, tu będziemy chcieli zwrotu tego, co wraca wsadowych. 

A co jest szczególnego w tej funkcji rekurencyjnej? To jest ogon recursive, tak długo, jak skompilować z niektórych optymalizacji, będzie uznać, że i nigdy nie dostanie przepełnienie stosu z tego, nawet jeśli nasze drzewo ma wysokość 10.000 lub 10 mln euro. [Student, niezrozumiały] [Bowden] Myślę, że robi to w Dash - lub co poziom optymalizacji jest wymagane dla rekursji ogonowej uznawane. Myślę, że uznaje - GCC i Clang mieć różne znaczenia dla ich poziomu optymalizacji. Chcę powiedzieć, że to Dasho 2, na pewno, że będzie rozpoznawać ogon rekursji. Ale - można skonstruować jak przykład Fibonocci czy coś. To nie jest łatwe do sprawdzenia się z tym, bo to jest trudne do skonstruowania drzewo binarne, które jest tak duże. Ale tak, myślę, że to Dasho 2, że jeśli skompilować Dasho 2, trafi ona do rekursji ogonowej i optymalizacji, które obecnie. Wróćmy do - włożyć dosłownie ostatnią rzeczą, potrzebuje. Wróćmy do wkładki tutaj gdzie mamy zamiar zrobić ten sam pomysł. Będzie nadal mają wadę, nie jest w stanie w pełni obsługiwać gdy korzeń sam jest null lub obok wejścia jest null, ale zamiast postępowania z wskaźnika macierzystego niech stosować tę samą logikę wskazówek prowadzących do wskaźników. Jeśli tu utrzymać nasz węzeł ** dyskusja, i nie musimy śledzić prawo już, ale node ** bież = & drzewo. A teraz nasza pętla będzie natomiast dyskusja * nie jest równa null. Nie trzeba śledzić rodziców już. Nie trzeba śledzić lewo i prawo. I nazwijmy go temp, ponieważ jesteśmy już przy użyciu temperatury. Okay. Więc jeśli (wartość> * temp) następnie & (* temp) -> prawy else temp = & (* temp) -> w lewo. Teraz, w tym momencie, po tej pętli, Robię tylko to, bo być może łatwiej jest myśleć o iteracyjnie niż rekurencyjnie, ale po tej pętli while, * Temp jest wskaźnik chcemy zmienić. 

Zanim mieliśmy rodziców, i chcieliśmy zmienić albo lewo dominującą bądź rodzica w prawo, ale jeśli chcemy zmienić prawo rodzica, następnie * temp jest prawo rodzica, i możemy ją zmienić bezpośrednio. Więc tu, możemy zrobić * temp = newnode, i to jest to. Więc wypowiedzenia, wszystko zrobiliśmy w to wykupienie linii kodu. Aby śledzić dominującej we wszystkim, co jest dodatkowym wysiłkiem. Tutaj, jeśli tylko śledzić wskaźnik do wskaźnika, i nawet gdybyśmy chcieli pozbyć się wszystkich tych nawiasach klamrowych teraz sprawiają, że wygląda krótszy. To teraz jest dokładnie to samo rozwiązanie, ale mniej linii kodu. Po uruchomieniu uznając to jako ważnego rozwiązania, jest to także łatwiejsze do rozumu o niż jak, dobrze, dlaczego mam tę flagę na int prawo? Co to znaczy? Och, to co oznacza, że za każdym razem, idź w prawo, trzeba ustawić go, else if I idź w lewo trzeba ustawić go na zero. Tutaj, nie mam powodu, aby o tym, to po prostu łatwiej myśleć. Pytania? [Student, niezrozumiały] >> Tak. Ok, więc w ostatnim bit - Chyba jeden szybki i łatwy funkcji możemy zrobić to, let's - razem, myślę, spróbuj pisać zawiera funkcję co nie obchodzi mnie, czy to jest drzewo binarne wyszukiwania. Zawiera funkcja powinna zwrócić wartość true jeśli gdziekolwiek w tym ogólnym drzewa binarnego jest wartość szukamy. Więc najpierw zrobić go rekurencyjnie i zrobimy to iteracyjnie. Rzeczywiście możemy tylko robić to razem, bo to będzie bardzo krótki. 

Co to jest moja sprawa baza będzie? [Student, niezrozumiały] [Bowden] Więc jeśli (drzewo == NULL), to co? [Student] Return false. [Bowden] Else, dobrze, nie potrzebują innego. Jeśli był mój drugi wariant podstawowy. [Animacja] Drzewa wartość? >> Tak. Więc jeśli (tree-> wartość wartość. == Wskazówka wracamy do węzła * nie, węzeł ** s? Zawiera nie będzie trzeba używać A ** węzłów, ponieważ nie modyfikujemy wskaźniki. My tylko przemierzając je. Jeśli tak się stanie, to chcemy, aby powrócić true. Else chcemy przechodzić dzieci. Więc nie możemy rozumować, czy wszystko z lewej jest mniejsza i wszystko, co po prawej stronie jest większa. Więc co jest nasz stan będzie tutaj - lub, co my teraz zrobimy? [Student, niezrozumiały] >> Tak. Powrót zawiera (wartość, drzewo-> lewy) lub zawiera (wartość, drzewo-> prawy). I to jest to. I zauważyć jest jakaś zwarcie oceny, gdzie, jeśli zdarzy nam się znaleźć wartość w lewym drzewie nigdy nie trzeba szukać w odpowiednim drzewie. To jest cała funkcja. Teraz zróbmy to iteracyjnie, który będzie mniej miły. Weźmiemy zwykły początek węzła * cur drzewa =. Chociaż (bież! = NULL). Szybko żeby zobaczyć problem. Jeśli cur - tu, jeśli kiedykolwiek wyrwać się z tego, następnie mamy zabrakło rzeczy do obejrzenia, więc return false. Jeśli (bież-> wartość value ==) zwraca true. Więc teraz, jesteśmy na miejscu - nie wiemy, czy chcemy, aby przejść w lewo lub w prawo. Tak arbitralnie, po prostu idź w lewo. Mam oczywiście uruchomić do problemu gdzie byłem całkowicie opuszczonego wszystko - Ja zawsze tylko sprawdzić lewą stronę drzewa. I nigdy nie będzie sprawdzać wszystko, co jest prawo dziecka do wszystkiego. Jak mogę to naprawić? [Student] Musisz śledzić na lewo i prawo w stosie. [Bowden] Tak. Więc zróbmy to struct lista, node * n, a następnie węzeł ** dalej? Myślę, że działa dobrze. Chcemy iść na lewo, lub let's - tutaj. Struct lista = lista, będzie to początek się na tej liście struktury. * List = NULL. Tak, że będzie naszej listy z poddrzew że mamy pomijane. Będziemy przechodzić w lewo teraz, ale ponieważ nieuchronnie muszą wrócić do prawej, Będziemy trzymać prawej strony wewnątrz naszej liście struktury. Wtedy będziemy mieć new_list lub struct, struct lista * new_list = malloc (sizeof (lista)). Zamierzam ignorować błędów sprawdzania, ale trzeba sprawdzić, czy jest to null. New_list węzeł to będzie wskazywać na - oh, dlatego chciałem się tutaj. To będzie wskazywać na drugiej liście struktury. To jest po prostu, jak związane pracę list. Jest takie samo jak związane listy int chyba my tylko z węzła wymiany int *. To jest dokładnie to samo. Więc new_list, wartość naszego węzła new_list, będzie bież-> prawo. Wartość naszej new_list-> next będzie nasz pierwszy list, a następnie będziemy aktualizować naszą listę, aby wskazać new_list. 

Teraz musimy jakiś sposób rzeczy ciągnie, jak mamy ruch cała lewica poddrzewa. Teraz trzeba wyciągnąć rzeczy z niego, jak dyskusja jest null, a my nie chcemy po prostu return false. Chcemy teraz wyciągnąć na zewnątrz w naszej nowej listy. Wygodny sposób to zrobić - no, rzeczywiście, jest wiele sposobów na zrobienie tego. Ktoś ma pomysł? Gdzie należy zrobić lub jak mam to zrobić? Mamy tylko kilka minut, ale wszelkie sugestie? Zamiast - w jeden sposób, a nie jest warunkiem naszego a, co mamy obecnie, patrząc na nie jest zerowa, zamiast będziemy nadal iść aż nasza lista sama w sobie jest null. Jeśli więc nasza lista kończy się null, wtedy mamy zabrakło rzeczy szukać, przeszukiwać. Ale to oznacza, że ​​pierwszą rzeczą, na naszej liście jest tylko będzie pierwszy węzeł. Pierwszą rzeczą będzie - już nie trzeba zobaczyć. Więc list-> n będzie naszym drzewem. list-> next będzie null. A teraz, gdy lista nie równa NULL robi. Cur będzie wyciągnąć coś z naszej listy. Tak więc dyskusja będzie równego lista-> n. I wtedy lista będzie równego list-> n, lub list-> next. Więc jeśli wartość bież równa wartość. Teraz możemy dodać zarówno nasze prawo i nasz wskaźnik lewy wskaźnik tak długo, jak nie są one nieważne. Tu, chyba powinniśmy byli zrobić, że w pierwszej kolejności. Jeśli (bież-> right! = NULL) wtedy będziemy wkładać tego węzła do naszej listy. Jeśli (bież-> left), jest to trochę dodatkowej pracy, ale to jest w porządku. Jeśli (bież-> left! = NULL), i mamy zamiar włożyć w lewo do naszej listy, i to powinno być to. Mamy iteracyjne - tak długo, jak mamy coś w naszej liście, mamy kolejny węzeł, aby przyjrzeć. Więc patrzymy na tym węźle, możemy przejść na naszą listę do następnego. Jeśli ten węzeł to wartość, której szukamy, możemy powrócić true. Else wstawić zarówno nasze lewego i prawego poddrzewa, tak długo, jak nie jesteś null, na naszej liście tak, że nieuchronnie nad nimi. Tak więc, jeśli nie były one null, jeśli nasz wskaźnik główny wskazał na dwie rzeczy, następnie na pierwszy wjechaliśmy coś więc nasza lista kończy się null. A następnie kładziemy dwie rzeczy z powrotem, więc teraz nasza lista jest wielkości 2. Następnie jedziemy do pętli z powrotem, a my po prostu się do ciągnięcia, powiedzmy, lewy wskaźnik naszego węzła głównego. I to po prostu zachować dzieje; skończymy pętli na wszystko. 

Należy zauważyć, że jest to znacznie trudniejsze w rekurencyjnego rozwiązania. I mówiłem wiele razy że recursive rozwiązanie ma zazwyczaj wiele wspólnego z iteracyjnego rozwiązania. Tutaj jest to dokładnie to, co recursive rozwiązanie robi. Jedyną zmianą, że zamiast pośrednio użyciu stosu, stos programu, jako sposób śledzenie co węzły nadal trzeba odwiedzić, teraz trzeba jawnie użyć połączonej listy. W obu przypadkach są śledzenie co węzeł musi być jeszcze odwiedził. W cyklicznej przypadku jest to po prostu łatwiejsze, ponieważ stos realizowane jest dla Ciebie, jak na stosie programu. Należy zauważyć, że w tym związane z wykazu, stos. Cokolwiek po prostu umieścić na stosie jest natychmiast, co będziemy ściągać stos odwiedzić następny. Jesteśmy poza czasem, ale jakieś pytania? [Student, niezrozumiały] [Bowden] Tak. Więc jeśli mamy listę, Prąd będzie wskazywać na tego faceta, a teraz jesteśmy po prostu pogłębianie połączonej listy skupić się na tego faceta. Jesteśmy przemierzając ponad połączonej listy w tej linii. I wtedy myślę, powinniśmy uwolnić naszej listy i rzeczy raz przed powrotem prawdziwe lub fałszywe, musimy iterować naszej listy i zawsze tu, jak sądzę, jeśli bież prawo nie jest równe, dodaj go, więc teraz chcemy uwolnić dyskusja, ponieważ dobrze, nie mieliśmy zupełnie zapomnieć o tej liście? Tak. Więc to jest to, co chcemy zrobić. Gdzie jest wskaźnik? Cur wtedy - chcemy listy struct * 10 równa listę następny. Darmowa lista list = temp. A w przypadku, gdy wrócimy prawda, musimy iteracyjne w pozostałej części naszej listy uwolnienie rzeczy. Zaletą rozwiązania jest rekurencyjnej uwalniając rzeczy oznacza tylko popping factorings ze stosu, który wydarzy się na Ciebie. Tak zaszliśmy z czymś, co jest jak 3 liniach trudno myśleć-o kodzie do czegoś, co jest znacznie wiele więcej trudno myśleć-o linii kodu. Więcej pytań? Dobrze. Jesteśmy dobrzy. Bye! [CS50.TV]