[Powered by Google Translate] [Rozdział 7] [mniej wygodne]
[Nate Hardison] [Harvard University]
[To jest CS50.] [CS50.TV]
>> Witamy w sekcji 7.
Dzięki huraganu Sandy,
zamiast tego normalnie punkt tygodniu
robimy to walk-through, przez sekcję pytań.
Idę się podążać wraz z problemem Zestaw 6 specyfikacji,
i przechodząc przez wszystkie pytania
Sekcja części pytania.
Jeśli są jakieś pytania,
proszę umieszczać je na CS50 dyskutować.
>> Dobrze. Zaczynajmy.
Teraz patrzę na stronie 3 specyfikacji podanej problem.
Idziemy najpierw zacząć mówić o drzew binarnych
gdyż te mają wiele istotnych dla tego tygodnia zestaw problemów -
kodowanie Drzewo Huffman.
Jednym z pierwszych struktur danych rozmawialiśmy na CS50 była tablica.
Pamiętaj, że tablica jest kolejność elementów -
wszystkie tego samego rodzaju przechowywanych w prawo - obok siebie w pamięci.
Jeśli mam tablicę liczb całkowitych, które można rysować za pomocą tego pola-numbers-liczby całkowite styl -
Powiedzmy, że mam 5 w pierwszym polu, mam 7 w drugim,
wtedy mam 8, 10 i 20 w końcowym polu.
Pamiętaj, dwa naprawdę dobre rzeczy o tej tablicy
jest to, że mamy ten stały dostęp w czasie do konkretnego elementu
w tablicy, jeśli znamy jego indeks.
Na przykład, jeśli chcę złapać trzeci element w tablicy -
o indeksie 2 za pomocą naszego zera system indeksowania -
I dosłownie po prostu zrobić prosty matematyczny obliczeń
wskoczyć do tej pozycji w tablicy,
wyciągnij 8, który jest przechowywany tam,
a ja jestem dobry, aby przejść.
>> Jednym ze złych rzeczy o tej tablicy - że rozmawialiśmy o
kiedy rozmawialiśmy związane list -
to, że jeśli chcę wstawić element w tej tablicy
Będę musiał zrobić kilka przesuwanie się.
Na przykład, ta tablica tutaj
jest w posortowanych - sortowane w porządku rosnącym -
5, a następnie 7, a następnie 8, a następnie 10, a następnie 20 -
ale jeśli chcę wstawić numer 9 na tej tablicy
Będę musiał przenieść niektóre elementy w celu miejsca.
Możemy zwrócić na to tutaj.
Będę musiał przenieść 5, 7, a następnie 8;
stworzyć lukę, gdzie mogę umieścić 9,
, a następnie 10 do 20 może przejść do prawej na 9.
Jest to rodzaj bólu, bo w najgorszym przypadku -
kiedy masz wstawić albo na początku lub na końcu
w tablicy, w zależności jak mamy przesunięcie -
może się w końcu o przesunięcie wszystkich elementów
że jesteśmy obecnie przechowywania w tablicy.
>> Więc, co było sposobem obejścia tego?
Odwrotnie było to, aby przejść do naszej linked-list metody, gdzie -
zamiast przechowywania elementów 5, 7, 8, 10 i 20, wszystkie obok siebie w pamięci -
czego nie było, zamiast przechowywać je rodzaj gdziekolwiek chcieliśmy je przechowywać
w tych linked-list węzłów, które mam tu rysunek, rodzaj ad hoc.
A potem podłączyć je ze sobą za pomocą tych kolejnych wskaźników.
Mogę mieć wskaźnik od 5 do 7,
Wskaźnik od 7 do 8,
Wskaźnik od 8 do 10,
i wreszcie, wskaźnik z 10 do 20,
a następnie pusty wskaźnik na 20 wskazując, że nie ma nic.
Trade-off, że mamy tu
jest to, że teraz, jeśli chcemy wstawić numer 9 w naszym sortowanie listy,
wszystko, co musimy zrobić, to stworzyć nowy węzeł z 9,
podłączyć go do wskazywać na odpowiednim miejscu,
, a następnie ponownie do przewodu 8 w dół do punktu 9.
To dość szybko, zakładając dokładnie wiemy, gdzie chcemy wstawić 9.
Ale kompromis w zamian za to, że mamy teraz stracił stały dostęp w czasie
w jeden z elementów w naszej struktury danych.
Na przykład, jeśli chcę znaleźć czwarty element w tej połączonej listy,
Mam zamiar zacząć na samym początku listy
i mój sposób pracy poprzez liczenie węzła-by-węzeł, aż znajdę czwartą.
>> W celu uzyskania lepszej wydajności dostępu niż połączonej listy -
ale również zachować niektóre z korzyści, które mieliśmy
w zakresie podawania czasie z połączonej listy -
Drzewo binarne będzie trzeba użyć trochę więcej pamięci.
W szczególności, a nie tylko o jeden wskaźnik w binarnym węzeł drzewa -
jak linked-list node robi -
mamy zamiar dodać drugi wskaźnik do węzła drzewa binarnego.
Zamiast tylko o jeden wskaźnik do następnego elementu,
będziemy mieć wskaźnik do lewego dziecka i dziecka w prawo.
>> Miejmy narysować obrazek, aby zobaczyć, co to rzeczywiście wygląda.
Ponownie, mam zamiar wykorzystać te pola i strzały.
Binarnym węzeł drzewo zacząć od pudełka jest proste.
To będzie mieć miejsca na wartości,
a to też będzie mieć miejsce na lewej dziecka i prawo.
Mam zamiar opisać je tutaj.
Będziemy mieć lewe dziecko, a potem będziemy mieć prawo dziecka.
Istnieje wiele różnych sposobów, aby to zrobić.
Czasami o przestrzeń i wygodę,
Ja rzeczywiście wyciągnąć to jak robię na dole
gdzie będę mieć wartość w górę,
a następnie w prawo dziecka na prawej dolnej,
a lewa dziecko na dole po lewej stronie.
Wracając do tej góry diagramu
mamy wartość na samym szczycie
wtedy mamy lewej dzieci wskaźnik, a wtedy mamy prawo-dziecko wskaźnik.
>> W specyfikacji podanej Problem,
mówimy o rysunku węzeł, który ma wartość 7,
a następnie w lewo-dziecko wskaźnik, który jest pusty, i prawym dzieckiem wskaźnik, który jest pusty.
Możemy napisać NULL kapitału w miejsca do
zarówno po lewej i prawej dziecko dziecko lub możemy wyciągnąć ten przekątnej slash
w ramach każdego z pól, aby wskazać, że jest null.
Mam zamiar to zrobić tylko dlatego, że to prostsze.
Co można zobaczyć tutaj są dwa sposoby tworzenia diagramów bardzo prosty węzeł drzewa binarnego
gdzie mamy wartość 7 i null odnośniki podrzędne.
>> Druga część naszych rozmów o tym, jak w specyfikacji z powiązanych list -
pamiętaj, że mieliśmy tylko trzymać się pierwszego elementu na liście
zapamiętać całą listę -
i podobnie, z drzewa binarnego, tylko musi trzymać jeden wskaźnik do drzewa
W celu zachowania kontroli nad całej struktury danych.
Ten specjalny element drzewa nazywa Korzeń z drzewa.
Na przykład, jeśli jeden węzeł - węzeł zawierający wartość 7
przy zerowych wskaźników lewej i prawej dziecko -
były tylko wartości w naszym drzewie,
wówczas byłby to nasz węzeł główny.
To sam początek naszego drzewa.
Widzimy to trochę jaśniej raz zaczniemy dodawać kolejne węzły naszego drzewa.
Pozwól mi wyciągnąć nową stronę.
>> Teraz idziemy narysować drzewo, które ma 7 u nasady,
i 3 wewnątrz lewej dziecka i 9 wnętrzem prawej dziecka.
Ponownie, jest to całkiem proste.
Mamy 7, narysować węzeł 3, 9, do węzła
i mam zamiar ustawić lewy wskaźnik dzieci z 7 do punktu do węzła zawierającego 3,
i prawym dziecko wskaźnik węzła zawierających 7 do węzła zawierających 9.
Teraz, od 3 i 9 nie mają dzieci,
zamierzamy ustawić wszystkie swoje wskaźniki dzieci będą puste.
Tutaj, korzeń naszego drzewa odpowiada węzeł zawierający numer 7.
Można zobaczyć, że jeśli wszystko mamy, to wskaźnik do tego korzenia,
możemy następnie przejść przez naszego drzewa i dostęp zarówno węzły -
zarówno 3 i 9.
Nie trzeba się utrzymać wskaźniki do każdego węzła w drzewie.
Dobrze. Teraz mamy zamiar dodać kolejny węzeł na tym schemacie.
Mamy zamiar dodać węzeł zawierający 6,
i mamy zamiar dodać to jako prawego dziecka węzła zawierającego 3.
Aby to zrobić, mam zamiar usunąć tego pustego wskaźnika w 3-węzeł
i połączyć go zwrócić do węzła zawierającego 6. Dobrze.
>> W tym momencie, idziemy na trochę terminologii.
Aby rozpocząć, powód, dla którego jest to tzw drzewo binarne, w szczególności
jest to, że składa się z dwóch podrzędnych wskaźniki.
Istnieją inne gatunki drzew, które mają więcej wskaźników podrzędnych.
W szczególności, nie ", spróbuj" w secie Problem 5.
Można zauważyć, że w tym razem, trzeba było 27 różne wskaźniki do różnych dzieci -
jednym dla każdej z 26 liter alfabetu angielskiego,
, a następnie w 27 do apostrofu -
Tak więc, jest to podobne do rodzaju drzewa.
Ale tutaj, ponieważ jest to binarny, mamy tylko dwa podrzędne wskaźniki.
>> Oprócz tego korzenia, że ​​mówiliśmy,
mamy także rzucając wokół tego pojęcia "dziecko".
Co to oznacza dla jednego węzła na dziecko z innego węzła?
Dosłownie oznacza to, że węzeł dziecko jest dzieckiem innego węzła
jeśli inny węzeł ma jeden z jego wskazówkami dzieci określonych wskazać na tym węźle.
Aby umieścić to w bardziej konkretny sposób
jeśli 3 jest wskazywany przez jeden z wskaźników podrzędnych 7, a następnie 3 jest dzieckiem 7.
Gdybyśmy mieli się dowiedzieć, co dzieci 7 są -
dobrze, zobaczymy, że 7 ma wskaźnik do 3 i odnośnik, 9,
tak 9 i 3 to dzieci 7.
Dziewiątka nie ma dzieci, ponieważ jego wskaźniki dzieci są null,
i 3 ma tylko jedno dziecko, 6.
Six też nie ma dzieci, ponieważ zarówno jego wskaźniki są nieważne, co będziemy rysować teraz.
>> Dodatkowo, również o rodziców danego węzła,
i jest to, jak można się spodziewać, odwrotnością tego opisu dziecka.
Każdy węzeł ma tylko jednego rodzica - zamiast dwóch jak można się spodziewać z ludźmi.
Na przykład, macierzysty 3 jest 7.
Macierzysty 9 również 7 i dominującą 6 wynosi 3. Nie wiele.
Mamy również warunki do rozmowy o dziadków i wnuków,
i ogólnie mówimy o przodkach
i potomków danego węzła.
Przodkiem węzła - albo przodkowie raczej węzła -
są wszystkie węzły leżących na drodze od korzenia do tego węzła.
Na przykład, jeśli patrzę na węźle 6,
następnie przodkowie będą zarówno 3 i 7.
Przodkowie 9, na przykład, są - jeśli patrzę na węźle 9 -
następnie przodek 9 tylko 7.
I potomkowie są dokładnie odwrotne.
Jeśli chcesz spojrzeć na wszystko z potomków 7,
wtedy trzeba patrzeć na wszystkie węzły pod nim.
Tak, mam 3, 9 i 6 wszystko jako potomków 7.
>> Ostateczny termin, będziemy rozmawiać o to pojęcie jako rodzeństwo.
Rodzeństwo - Rodzaju po wzdłuż na tych warunkach rodzinnych -
są węzły są na tym samym poziomie w drzewie.
Więc, 3 i 9 są rodzeństwem Ponieważ są na tym samym poziomie, w drzewie.
Obaj mają tego samego rodzica, 7.
6 nie ma rodzeństwa, bo 9 nie mają dzieci.
I 7 nie mają rodzeństwa, ponieważ jest źródłem naszego drzewa,
i jest zawsze tylko 1 root.
Na 7 mieć rodzeństwa musiałaby być powyżej 7 węzła.
Nie musiałby być rodzicem 7, w tym przypadku 7 nie będzie już korzeniem drzewa.
Następnie, że nowa jednostka dominująca z 7 musiałby również mieć dziecko,
i to dziecko będzie wówczas rodzeństwo 7.
>> Dobrze. Idziemy dalej.
Kiedy zaczynaliśmy naszą dyskusję drzew binarnych,
Rozmawialiśmy o tym, jak mieliśmy zamiar wykorzystać je do
zyskać przewagę na obu tablicach i listach linked.
A sposób, w jaki zamierzamy zrobić to jest z tym zamawiającego.
Możemy powiedzieć, że drzewo binarne jest uporządkowane, zgodnie ze specyfikacją,
jeśli dla każdego węzła w naszym drzewie, wszystkie jego potomków po lewej -
lewa dziecko i wszystkie lewego dziecka potomków -
mają mniejsze wartości, i wszystkie węzły w prawo -
prawa dziecka i wszystko z prawa dziecka potomków -
mają węzły większe niż wartość bieżącego węzła, że ​​mamy do czynienia.
Tylko dla uproszczenia, będziemy zakładać, że nie ma żadnych zduplikowanych węzły naszego drzewa.
Na przykład, w tym drzewie nie będziemy zajmować się sprawą
gdzie mamy wartość 7 w katalogu głównym
a także mają wartość 7 w innych częściach drzewa.
W tym przypadku, można zauważyć, że to drzewo jest rzeczywiście zamówiłem.
Mamy wartość 7 w katalogu głównym.
Wszystko na lewo 7 -
jeśli cofnąć wszystkie z tych małych znaków tutaj -
Wszystko na lewo 7 - 3 i 6 -
wartości te są zarówno mniej niż 7, a wszystko w prawo - co jest właśnie to 9 -
jest większa niż 7.
>> To nie tylko zamówić drzewo zawierające tych wartości jest
ale narysujmy kilka więcej z nich.
Tu jest rzeczywiście cała masa sposobów, że możemy to zrobić.
Mam zamiar używać skrótów tylko zachować rzeczy proste, gdzie -
niż wyciągając całość pudełka-i-strzałki -
Idę wyciągnąć numery i dodać strzałki łączące je.
Aby rozpocząć, po prostu napisz do naszego oryginalnego drzewa ponownie gdzie mieliśmy 7, a następnie 3,
, a następnie 3 wskazał na prawo do 6,
i 7 miał prawo dziecka, które było 9.
Dobrze. Co znajduje się w inny sposób, że możemy napisać to drzewo?
Zamiast 3 być lewa dziecko 7,
moglibyśmy mieć 6 będzie lewo dziecko 7,
i 3 z lewej strony: z 6 dzieci.
To będzie wyglądać tego drzewa tu gdzie mam 7,
niż 6, a 3 i 9 na prawo.
My również nie mieć 7 jako naszego węzła głównego.
Możemy również 6 jako naszego węzła głównego.
Co by to wyglądało?
Jeśli chcemy utrzymać tę uporządkowaną nieruchomości,
Wszystko do lewej 6 musi być mniejsza niż.
Jest tylko jedna możliwość, a to 3.
Ale potem, jak po prawej dziecka 6, mamy dwie możliwości.
Po pierwsze, może to mieć na 7, a następnie 9
albo możemy wyciągnąć go - jak mam do zrobienia -
gdzie mamy 9 jako prawy podrzędny 6,
i 7, jak lewej dziecka z 9.
>> Teraz, 7 i 6, nie tylko są możliwe wartości korzenia.
Możemy mieć również 3 być w katalogu głównym.
Co się stanie, jeśli 3 jest źródłem?
Tutaj robi się trochę interesujące.
Trzy nie ma żadnych wartości, które są mniejsze niż to,
tak, że cała lewa strona drzewa jest tylko będzie null.
Nie będzie to coś tam.
W prawo, moglibyśmy wymienić rzeczy w porządku rosnącym.
Moglibyśmy mieć 3, potem 6, potem 7, potem 9.
Albo, możemy zrobić 3, potem 6, potem 9, potem 7.
Albo, możemy zrobić 3, potem 7, potem 6, potem 9.
Albo, 3, 7 - w rzeczywistości nie, nie możemy zrobić 7 więcej.
To nasza jedno tam.
Możemy zrobić, 9, a następnie od 9 możemy zrobić 6 i 7.
Albo, możemy zrobić 3, potem 9, potem 7, a następnie 6.
>> Jedną z rzeczy, zwrócić uwagę na o to
że te drzewa są trochę dziwnie wyglądające.
W szczególności, jeśli spojrzymy na 4 drzew po prawej stronie -
Będę krążyć je tutaj -
drzewa te wyglądają niemal identycznie jak połączonej listy.
Każdy węzeł ma tylko jedno dziecko,
i tak, że nie ma żadnych tego strukturę drzewa widzimy, że, na przykład,
w tym jednego drzewa samotny tu w lewym dolnym rogu.
Drzewa te są w rzeczywistości nazywa się zdegenerowanym drzew binarnych,
i porozmawiamy o nich więcej w przyszłości -
szczególnie jeśli pójdziesz na podjęcie innych kursów informatycznych.
Drzewa te są zdegenerowane.
Nie są one bardzo użyteczne, ponieważ rzeczywiście, struktura ta nadaje się
do wyszukiwania razy podobną do połączonej listy.
Nie mamy do skorzystania z dodatkowej pamięci - ten dodatkowy wskaźnik -
struktury, ponieważ są naszego Bad w ten sposób.
Zamiast iść i wyciągnąć binarne drzew, które mają 9 u nasady,
która jest ostateczna sprawa, że ​​mamy,
Jesteśmy natomiast w tym momencie, będziemy mówić trochę o tej drugiej kadencji
którego używamy, gdy mówimy o drzewach, co nazywa wysokość.
>> Wysokość drzewa jest odległość od korzenia do węzła najbardziej odległej,
lub raczej liczba przeskoków, które trzeba zrobić, aby
rozpocząć od korzenia, a następnie kończy się w najbardziej odległej węzła w drzewie.
Jeśli spojrzymy na niektóre z tych drzew, które mamy wyciągnąć tutaj,
widzimy, że jeśli weźmiemy to drzewo w lewym górnym rogu i zacząć na 3,
wtedy mamy do 1 hop aby dostać się do 6, drugi hop aby dostać się do 7,
a trzeci hop aby dostać się do 9.
Tak więc, to wysokość wynosi 3 drzewa.
Możemy zrobić to samo ćwiczenie dla innych drzew wymienionych z tym zielonym,
widzimy, że wysokość tych wszystkich drzew jest nawet 3.
To część tego, co sprawia, że ​​zdegenerowany -
ich wysokość jest mniejsza niż jednym liczby węzłów w całym drzewie.
Jeśli przyjrzymy się tym drugim drzewie, które jest otoczone z czerwonym, z drugiej strony,
widzimy, że najbardziej odległe węzły liściowe 6 i 9 -
pozostawia będąc te węzły, które nie mają dzieci.
Tak więc, w celu uzyskania z korzenia albo do 6, lub 9,
musimy mieć jeden węzeł, aby przejść do 7 sekund, a następnie hop aby dostać się do 9,
i również tylko drugiego węzła z 7, aby do 6.
Tak, wysokość tego drzewa tu jest tylko 2.
Możesz wrócić i zrobić to dla wszystkich innych drzew, które już wcześniej wspomniano
począwszy od 7 i 6,
a przekonasz się, że wysokość wszystkich tych drzew jest również 2.
>> Powodem rozmawialiśmy o nakazał drzewa binarne
i dlaczego są fajne, ponieważ możesz przeglądać je w
bardzo podobny sposób do poszukiwania na posortowanej tablicy.
To jest, gdy mówimy o coraz to lepszy czas odnośnika
na prostej listy powiązane.
Dzięki połączonej listy - jeśli chcesz, aby znaleźć konkretny element -
jesteś w najlepszym zrobić jakąś liniowej wyszukiwanie
gdzie zaczyna się na początku listy i hip jeden po drugim -
jeden węzeł przez jednego węzła -
całą listę, aż znajdziesz cokolwiek, czego szukasz.
Mając na uwadze, jeśli masz drzewo binarne, które jest zapisane w tej miłej formacie
rzeczywiście można dostać więcej binarnego wyszukiwania dzieje
gdzie dziel i rządź
i wyszukiwania odpowiedniej połowie drzewa w każdym kroku.
Zobaczmy, jak to działa.
>> Jeśli mamy - znów wrócić do naszego pierwotnego drzewa -
zaczynamy na 7, mamy 3 na lewo, 9 po prawej stronie,
i poniżej 3 mamy 6.
Jeśli chcemy wyszukać numer 6 w tym drzewie, chcemy rozpocząć w katalogu głównym.
Chcemy porównać wartość szukamy, powiedzmy 6,
do wartości przechowywanej w węźle, który mamy obecnie, patrząc na, 7,
okaże się, że 6 jest rzeczywiście mniej niż 7, tak, że możemy przenieść się w lewo.
Jeśli wartości 6 było większe niż 7, a nie będzie się już przesunięty w prawo.
Ponieważ wiadomo, że - z uwagi na strukturę drzewa naszego zamówionej binarnych -
wszystkie wartości poniżej 7 będą przechowywane w lewo 7,
nie ma potrzeby, aby niepokoić nawet przeglądając prawej stronie drzewa.
Gdy poruszamy się w lewo i jesteśmy teraz w węźle zawierającym 3,
możemy zrobić tego samego porównania ponownie gdy porównamy 3 i 6.
I okazuje się, że podczas 6 - wartość szukamy - jest większy niż 3,
można go do prawej strony węzła zawierającej 3.
Nie ma po lewej stronie tutaj, więc mogliśmy zignorować tego.
Ale my wiemy, że tylko dlatego, że patrzysz na samo drzewo,
i widzimy, że drzewo nie ma dzieci.
>> Jest również dość łatwe do wyszukania 6 w tym drzewie, jeśli robimy to sami jako ludzie,
ale niech śledzić ten proces mechanicznie jak komputer zrobi
naprawdę zrozumieć algorytm.
W tym momencie, jesteśmy teraz patrząc na węźle zawiera 6,
i szukamy wartości 6,
tak, rzeczywiście, znaleźliśmy odpowiedni węzeł.
Okazało się, że wartość 6 w naszym drzewie, a my możemy zatrzymać nasze poszukiwania.
W tym miejscu, w zależności od tego, co dzieje się,
możemy powiedzieć, tak, udało nam się znaleźć wartość 6, istnieje w naszym drzewie.
Lub, jeśli planujemy wstawić węzeł lub coś zrobić, możemy to zrobić w tym momencie.
>> Zróbmy kilka więcej odnośników, by zobaczyć jak to działa.
Spójrzmy na to, co się stanie, jeśli były, aby spróbować spojrzeć na wartość 10.
Gdybyśmy mieli patrzeć na wartość 10, moglibyśmy zacząć od korzenia.
Chcemy zobaczyć, że 10 jest większa niż 7, tak, że możemy przenieść się w prawo.
Chcemy dostać się do 9 i porównaj 9 do 10 i zobaczyć, że 9 jest rzeczywiście mniej niż 10.
Więc jeszcze raz, chcemy spróbować przenieść do prawej.
Ale w tym momencie, to zauważymy, że jesteśmy na pustym węzłem.
Nic tam nie ma. Nie ma nic, gdzie 10 powinno być.
To jest, gdzie można zgłosić awarię - że w istocie nie istnieje 10 w drzewie.
I w końcu, idziemy przez przypadku, gdy chcemy zajrzeć do 1 w drzewie.
Jest to podobne do tego, co się dzieje, jeśli przyjrzymy się 10, z wyjątkiem zamiast iść na prawo,
mamy zamiar iść w lewo.
Zacząć w 7 i zobaczyć, że 1 jest mniejsza niż 7, tak, że przesuwają się w lewo.
Docieramy do 3 i widzę, że 1 jest mniejsza niż 3, więc znów staramy się poruszać w lewo.
W tym momencie mamy zerowy węzła, więc ponownie możemy zgłosić awarię.
>> Jeśli chcesz dowiedzieć się więcej o drzew binarnych,
istnieje cała masa zabawnych małych problemów, które możesz zrobić z nimi.
Proponuję ćwiczenia rysunek z tych schematów jeden po drugim
i po przez wszystkich różnych etapów,
bo to przyjdzie w super-poręczny
nie tylko wtedy, gdy robisz się kodowania Huffmana zestaw problemów
ale także w przyszłych kursów -
tylko uczenie się, jak wyciągnąć te struktury danych i przemyśleć problemy
z pióra i papieru lub, w tym przypadku, iPad i rysik.
>> W tym momencie chociaż, mamy zamiar przenieść się do niektórych praktyk kodowania
i rzeczywiście grać z tych drzew binarnych i zobaczyć.
Mam zamiar wrócić do mojego komputera.
Dla tej części sekcji, zamiast uruchomić lub CS50 CS50 spacje,
Mam zamiar korzystać z urządzenia.
>> Po wraz z specyfikacją zestawu Problem,
Widzę, że mam do otwarcia urządzenia,
przejdź do folderu Dropbox, utwórz folder o nazwie Sekcja 7,
a następnie utworzyć plik o nazwie binary_tree.c.
Jedziemy. Mam urządzenie już otwarty.
Zamierzam wyciągnąć terminal.
Mam zamiar przejść do folderu Dropbox, utwórz katalog o nazwie section7,
i widzę, że jest zupełnie pusta.
Teraz mam zamiar otworzyć binary_tree.c.
Dobrze. Zaczynamy - pusty plik.
>> Wróćmy do specyfikacji.
Specyfikacja prosi, aby utworzyć nową definicję typu
dla węzła drzewa binarnego zawierającego wartości int -
podobnie jak wartości, które zbierało się w naszych diagramów wcześniej.
Zamierzamy to wykorzystać boilerplate typedef że zrobiliśmy tutaj
że należy uznać ze zbioru Problem 5 -
jeśli nie hash sposób stołowego podboju programu ortografii.
Należy również rozpoznać z zeszłotygodniowej sekcji
gdzie rozmawialiśmy o połączonych listach.
Mamy to typedef węzła struct,
i daliśmy tego węzła struct tę nazwę węzła struct uprzednią
tak, że możemy odwoływać się do niego, ponieważ my chcemy mieć wskaźniki węzła struct
w ramach naszej struktury, ale my wtedy otoczony to -
czy raczej zamknięty to - w typedef
tak, że później w kodzie, można odnieść się do tej struktury w danym węźle, a nie tylko z węzła struktury.
>> To ma być bardzo podobny do pojedynczo-linked definicji listy, które widzieliśmy w zeszłym tygodniu.
Aby to zrobić, po prostu zacząć od wypisując szablonowe.
Wiemy, że musimy mieć wartość całkowitą,
będziemy więc umieścić w wartość int, a następnie, zamiast tylko jeden wskaźnik do następnego elementu -
jak my z listy pojedynczo powiązanych -
będziemy mieć lewe i prawe wskaźniki podrzędne.
To całkiem proste, zbyt - struct node * lewy dziecko;
i węzeł struct * prawo dziecka;. Cool.
To wygląda na początek całkiem nieźle.
Wróćmy do specyfikacji.
>> Teraz musimy zadeklarować zmienną globalną * węzła do korzenia drzewa.
Jedziemy, aby ten globalny, tak jak my miał pierwszy wskaźnik w naszej listy również globalnej.
Tym, że w tak, że funkcje zapisu
nie mamy zachować przechodząc wokół tego korzenia -
jeśli zobaczymy, że jeśli nie chcę pisać tych funkcji rekurencyjnie,
to może być lepiej nawet przechodzi wokół jako globalne przede
i zamiast zainicjować go lokalnie w głównej funkcji.
Ale zrobimy to na całym świecie, aby rozpocząć.
Znowu damy kilka miejsc, i mam zamiar zadeklarować węzła głównego *.
Wystarczy upewnić się, że nie pozostawić niezainicjowanych, zamierzam go ustawić równy null.
Teraz, w głównej funkcji - co będziemy pisać naprawdę szybko tu -
int main (int argc, char * argv []) -
i mam zamiar rozpocząć deklarując mój argv tablicy jako const po prostu tak, że wiem,
, że te argumenty są argumentami, że prawdopodobnie nie chcesz zmodyfikować.
Jeśli chcę je zmodyfikować chyba powinienem być co ich kopii.
Zobaczysz, to dużo w kodzie.
Jest w porządku albo sposób. Dobrze jest pozostawić ją jako - pominąć const jeśli chcesz.
I zazwyczaj umieścić go w właśnie tak, że przypominam sobie
że chyba nie chcesz modyfikować te argumenty.
>> Jak zawsze, mam zamiar dołączenia zwrotny 0 wiersz na koniec main.
Tutaj będą zainicjować mój węzeł główny.
W obecnej chwili, mam wskaźnik, który jest ustawiony na null,
więc to wskazuje na nic.
Aby zacząć budować węzeł,
I najpierw trzeba przydzielić pamięci dla niego.
Mam zamiar to zrobić poprzez pamięć na stercie przy użyciu malloc.
Mam zamiar ustawić pierwiastek równy wynikowi malloc,
i mam zamiar użyć operatora sizeof do obliczenia wielkości węzła.
Powodem tego, że używam węzła sizeof w przeciwieństwie do, powiedzmy,
robi coś takiego - malloc (4 + 4 +4) lub malloc 12 -
to dlatego, że chcę moje kodu być możliwie zgodne.
Chcę być w stanie odebrać. Plik C, skompilować go na urządzeniu,
a następnie skompilować go na moim Macu 64-bitowym -
lub na zupełnie innej architektury -
i chcę to wszystko działać same.
>> Jeśli robię założenia dotyczące wielkości zmiennych -
rozmiar int lub wielkość wskaźnika -
to ja jestem również tworzenia założeń o rodzaju architektur
na którym mój kod może pomyślnie skompilować podczas uruchamiania.
Zawsze należy używać sizeof w przeciwieństwie do ręcznie zsumowanie pól struktury.
Innym powodem jest to, że może również być wyściółka że kompilator wprowadza do struktury.
Nawet zwykłe zsumowanie poszczególnych pól nie jest coś, zazwyczaj chcą robić to,
tak, usuń ten wiersz.
Teraz naprawdę zainicjować ten węzeł główny,
Będę musiał podłączyć wartości dla każdego z różnych dziedzin.
Na przykład, do wartości wiem Aby zainicjować do 7,
i teraz mam zamiar ustawić lewy dziecko być null
oraz prawo dziecka do być null. Great!
Zrobiliśmy tę część specyfikacji.
>> Specyfikacja w dół na dole strony 3 prosi mnie do stworzenia jeszcze trzy węzły -
jeden zawierający 3, jeden zawierający 6, a jeden z 9 -
a następnie podłączyć je tak, że wygląda dokładnie tak, jak naszym diagramie drzewa
że rozmawialiśmy wcześniej.
Zróbmy to dość szybko tutaj.
Zobaczysz, naprawdę szybko, że mam zamiar zacząć pisać kilka duplikatu kodu.
Zamierzam utworzyć węzeł * i będę nazywać trzy.
Mam zamiar ustawić go równa malloc (sizeof (node)).
Mam zamiar ustawić trzy-> value = 3.
Trzy -> left_child = NULL; trzy -> prawy _child = NULL; również.
To wygląda bardzo podobne do inicjowania korzenie, i to jest dokładnie to, co
Mam zamiar zrobić jeśli zacznę inicjowanie 6 i 9, jak również.
Zrobię to bardzo szybko tutaj - faktycznie, mam zamiar zrobić trochę kopiowania i wklejania,
i upewnić się, że - w porządku.
Teraz mam to skopiowane i mogę śmiało i ustawić to równe 6.
Widać, że to zajmuje trochę czasu i nie jest super-wydajny.
W tylko trochę, będziemy napisać funkcję, która zrobi to za nas.
Chcę, aby zastąpić to z 9, wymienić, że z 6.
>> Teraz mamy wszystkie nasze węzły tworzone i inicjalizowane.
Mamy nasz główny równy 7, lub zawierający wartość 7,
nasz węzeł zawierający 3, nasz węzeł zawierający 6, a nasz węzeł zawierający 9.
W tym momencie wszystko, co musimy zrobić, to wszystko drut.
Powodem, dla którego inicjowane wszystkie wskaźniki na null jest tak, że ja się upewnić, że
Nie mam żadnych niezainicjowane wskaźniki w tam przez przypadek.
A także, ponieważ w tym momencie mam tylko rzeczywiście połączyć węzły do ​​siebie -
do tych, które w rzeczywistości są one połączone - nie mam przejść i zrobić
się, że wszystkie wartości null są tam w odpowiednich miejscach.
>> Zaczynając od podstaw, wiem, że korzeń jest lewa dziecko jest 3.
Wiem, że korzeń prawo dziecko jest 9.
Po tym, tylko inne dziecko, które mi zostało martwić
Dziecko 3 jest w prawo, w odległości 6.
W tym momencie, to wszystko wygląda całkiem nieźle.
Będziemy usunąć niektóre z tych linii.
Teraz wszystko wygląda całkiem nieźle.
Wróćmy do naszych specyfikacji i zobaczyć, co mamy dalej robić.
>> W tym momencie musimy napisać wywołana funkcja "zawiera"
z prototypem "bool zawiera (wartość int)".
I ta zawiera funkcja będzie zwracać wartość true
jeśli drzewo wskazał nasz zmiennej globalnej głównym
zawiera wartość przekazywana do funkcji, a false w przeciwnym przypadku.
Idziemy do przodu i zrobić.
To będzie dokładnie tak, jak wyszukiwanie, że zrobiliśmy ręcznie na iPada tylko trochę wcześniej.
Zróbmy Powiększ w trochę i przewiń w górę.
Mamy zamiar umieścić tę funkcję tuż powyżej naszej głównej funkcji
tak, że nie trzeba robić jakichkolwiek prototypowania.
Więc, bool zawiera (wartość int).
Proszę bardzo. Jest nasza deklaracja boilerplate.
Wystarczy upewnić się, że będzie to skompilować,
Mam zamiar iść do przodu i po prostu ustawić go równe return false.
Teraz ta funkcja po prostu nie robić nic i zawsze podają, że
wartość, którą szukasz nie jest w drzewie.
>> W tym momencie, to chyba dobry pomysł -
ponieważ napisaliśmy całą masę kodu, a my nawet nie próbował go jeszcze badania -
aby upewnić się, że wszystko kompiluje.
Istnieje kilka rzeczy, które musimy zrobić, aby upewnić się, że będzie to naprawdę skompilować.
Najpierw sprawdź, czy używaliśmy żadnych funkcji w jakichkolwiek bibliotek, które nie zostały jeszcze zawarte.
Funkcje używaliśmy do tej pory są malloc,
a potem my także za pomocą tego typu - w ten niestandardowy typ zwany "bool' -
który znajduje się w standardowym pliku bool nagłówka.
Na pewno chcemy obejmują standardowe bool.h dla bool typu,
i chcemy też # include standardowy lib.h dla standardowych bibliotek
które obejmują malloc i wolne, i to wszystko.
Więc, pomniejszyć, zamierzamy zamknąć.
Spróbujmy i upewnić się, że to rzeczywiście nie kompilacji.
Widzimy, że to robi, więc jesteśmy na dobrej drodze.
>> Otwórzmy się binary_tree.c ponownie.
Kompiluje. Chodźmy na dół i upewnij się, że możemy wstawić kilka telefonów do naszej funkcji zawiera -
by upewnić się, że to jest wszystko dobrze.
Na przykład, niektóre nie kiedy w naszym drzewie wyszukiwań wcześniej
staraliśmy się spojrzeć wartości 6, 10 i 1, i wiedzieliśmy, że 6 było w drzewie,
10 nie był w drzewie, i 1 w nie albo drzewa.
Użyjmy te rozmowy przykładowe jako sposób, aby dowiedzieć się, czy
Nasza funkcja zawiera działa.
Aby to zrobić, zamierzam wykorzystać funkcję printf,
i zamierzamy wydrukować wynik wywołania zawiera.
Mam zamiar umieścić w ciąg "zawiera (% d) = bo
jedziemy do wtyczki w wartości, które będziemy szukać,
i =% s \ n "i użyć jej jako naszego łańcucha formatu.
Jesteśmy po prostu żeby zobaczyć - dosłownie wydrukować na ekranie -
co wygląda jak wywołanie funkcji.
W rzeczywistości nie jest to wywołanie funkcji.
To jest po prostu ciąg wyglądać jak wywołania funkcji.
>> Teraz mamy zamiar podłączyć wartości.
Będziemy próbować zawiera 6,
i co wtedy będziemy robić tutaj jest użyć tego operatora trójskładnikowych.
Zobaczmy - zawiera 6 - tak, teraz już zawarte 6 i jeśli zawiera 6 jest prawdziwe,
Ciąg, który mamy zamiar wysłać do% s znak formatu
będzie ciąg "true".
Miejmy przewijania nad trochę.
W przeciwnym razie, chcemy wysłać ciąg znaków "false", jeśli zawiera 6 zwraca false.
To jest trochę głupkowaty wygląd, ale I rysunek Równie dobrze ilustrują
co operator trójskładnikowych wygląda ponieważ nie widziałem go na chwilę.
To będzie ładny, wygodny sposób, aby dowiedzieć się, czy nasza funkcja zawiera działa.
Zamierzam przejść z powrotem na lewo,
i mam zamiar skopiować i wkleić ten wiersz kilka razy.
To zmieniło niektóre z tych wartości wokół,
więc będzie 1, i to będzie 10.
>> W tym momencie mamy ładny funkcja zawiera.
Mamy kilka testów i zobaczymy czy to wszystko działa.
W tym momencie mamy napisane trochę więcej kodu.
Czas rzucić się i upewnić się, że wszystko nadal kompiluje.
Zamknij się, a teraz niech spróbuj drzewo binarne ponownie.
Cóż, wygląda na to, że mamy błąd,
I mamy to wyraźnie deklarując funkcję biblioteczną printf.
Wygląda na to, musimy iść i # include standardio.h.
A z tym, wszystko powinno się skompilować. Jesteśmy dobrze.
Teraz spróbuj uruchomić binarne drzewo i zobaczyć, co się dzieje.
Oto jesteśmy. / Binary_tree,
i widzimy, że, jak się spodziewaliśmy -
ponieważ nie zawiera jeszcze wdrożone,
lub raczej, mamy po prostu w zamian fałszywe -
widzimy, że to jest po prostu powrót false dla wszystkich z nich,
tak, że wszystko pracuje na ogół dość dobrze.
>> Wróćmy i rzeczywiście wdrożyć zawiera w tym momencie.
Idę do przewijania, powiększania i -
pamiętaj, że algorytm stosowany było to, że rozpoczął się korzenia
, a następnie w każdym węźle spotykamy, mamy porównanie,
i na podstawie tego porównania, że ​​albo w lewo przejść dziecka lub prawej dziecka.
To będzie bardzo podobny do kodu binarnego wyszukiwania, które pisaliśmy wcześniej w tym okresie.
Kiedy zaczynamy, wiemy, że chcemy trzymać się aktualnego węzła
że mamy do czynienia, a bieżący węzeł ma być inicjowane węzła głównego.
A teraz mamy zamiar iść dalej w drzewie,
i pamiętaj, że nasz stan zatrzymania -
kiedy faktycznie przepracowanych poprzez przykład ręcznie -
było, gdy spotkaliśmy null węzła
nie wtedy, gdy patrzyliśmy na pustym dzieckiem
ale kiedy faktycznie przeniósł się do węzła w drzewie
i stwierdził, że jesteśmy na pustym węzłem.
Jedziemy do iteracji, aż dyskusja nie jest równa null.
I co my teraz zrobimy?
Będziemy sprawdzać, czy (bież -> wartość value ==)
to wiemy, że mamy rzeczywiście znaleźć węzeł, że szukasz.
Więc tutaj, możemy powrócić true.
W przeciwnym razie, chcemy zobaczyć, czy jest mniejsza niż wartość.
Jeśli bieżący węzeł wartość jest mniejsza od wartości szukamy,
będziemy poruszać się w prawo.
Więc dyskusja dyskusja = -> right_child, a inaczej, będziemy poruszać się w lewo.
poprz = cur -> left_child;. Całkiem proste.
>> Prawdopodobnie rozpoznaje pętlę, która wygląda bardzo podobnie do tego z
Wyszukiwanie binarne wcześniej w okresie, z wyjątkiem wtedy mamy do czynienia z niskim, średnim i wysokim.
Tutaj po prostu trzeba spojrzeć na wartości bieżącej,
więc jest ładne i proste.
Upewnijmy ten kod działa.
Po pierwsze, upewnij się, że kompiluje. Wygląda tak, jak to robi.
Spróbujmy uruchomić.
I rzeczywiście, drukuje się wszystko, czego oczekiwać.
Okazuje 6 w drzewie, nie znajdzie 10 bo 10 nie jest w drzewie,
i nie znajdzie 1 albo ponieważ 1 nie jest również w drzewie.
Fajnych rzeczy.
>> Dobrze. Wróćmy do naszych specyfikacji i zobaczyć co dalej.
Teraz chce dodać trochę więcej węzłów naszego drzewa.
Chce dodać 5, 2 i 8, i upewnij się, że nasza zawiera kod
nadal działa zgodnie z oczekiwaniami.
Chodźmy zrobić.
W tym miejscu, zamiast robić to irytujące kopiuj i wklej ponownie
niech napisać funkcję, aby rzeczywiście utworzyć węzeł.
Jeśli będziemy przewijać całą drogę do main, widzimy, że robiliśmy to
bardzo podobny kod w kółko za każdym razem, że chcemy utworzyć węzeł.
>> Miejmy napisać funkcję, która będzie faktycznie zbudować węzeł dla nas i zwrócić.
Mam zamiar nazwać build_node.
Zamierzam zbudować węzeł o określonej wartości.
Powiększanie tutaj.
Pierwszą rzeczą, jaką zrobię faktycznie stworzyć przestrzeń dla węzła na stercie.
Tak więc, węzeł * n = malloc (sizeof (node)); n - wartość> = wartość;
i tu mam zamiar zainicjować wszystkie pola się odpowiednie wartości.
A na samym końcu, ponownie nasz węzeł.
Dobrze. Należy zwrócić uwagę, że ta funkcja jest tu
będzie zwracają wskaźnik do pamięci, która została przydzielona sterty.
Co jest ładne o to, że ten węzeł już teraz -
musimy zadeklarować ją na stercie, ponieważ jeśli zadeklarował go na stos
nie będzie w stanie to zrobić w funkcji takich jak to.
Że pamięć wypadnie z zakresu
i będzie nieważna w przypadku próby dostępu do go później.
Ponieważ jesteśmy deklarowania sterty przydzielonej pamięci,
będziemy musieli zadbać o uwolnienie go później
dla naszego programu nie przeciekać żadnej pamięci.
Byliśmy punting na to wszystko inne w kodzie
tylko dla uproszczenia w momencie,
ale jeśli kiedykolwiek napisać funkcję, który wygląda tak
gdzie masz - niektórzy nazywają to malloc lub realloc wewnątrz -
Aby upewnić się, że można umieścić jakiś komentarz tutaj, który mówi
Hej, wiesz, zwraca sterty przydzielone węzeł zainicjowany z wartością Przekazana-in.
A potem chcesz się upewnić, że można umieścić w jakiejś notatce, która mówi
Rozmówca musi uwolnić zwrócony pamięć.
W ten sposób, jeśli ktoś kiedykolwiek idzie i korzysta z tej funkcji,
oni wiedzą, że to co oni wrócić z tej funkcji
w pewnym momencie musi być uwolniony.
>> Zakładając, że wszystko jest dobrze i dobre tutaj,
możemy iść w dół do naszego kodu i zastąpić wszystkie z tych linii tutaj
z połączeniami z naszej funkcji budowania węzła.
Zróbmy to naprawdę szybko.
Jedna część, że nie idziemy do zastąpienia jest ta część na dole
na dnie, gdzie rzeczywiście DRUTU węzły wskazać siebie
dlatego, że nie możemy zrobić w naszej funkcji.
Ale zróbmy root = build_node (7); node * trzy = build_node (3);
node * sześć = build_node (6); node * dziewięć = build_node (9),.
A teraz, chcieliśmy również dodać węzły do ​​-
node * pięć = build_node (5); node * osiem = build_node (8);
i to, co było drugim węźle? Zobaczymy tutaj. Chcieliśmy również dodać 2 -
node * dwa = build_node (2);.
Dobrze. W tym momencie wiemy, że mamy do 7, 3, 9 oraz 6
wszystkie podłączane odpowiednio, ale co 5, 8, a 2?
Aby utrzymać wszystko w odpowiedniej kolejności,
wiemy, że prawo dziecka trzy jest 6.
Tak więc, jeśli mamy zamiar dodać 5,
5 należy również po prawej stronie z drzewa, które jest źródłem 3,
tak 5 należy jak lewy dziecka 6.
Możemy to zrobić, mówiąc, sześć -> left_child = pięć;
, a następnie, jak 8 należy lewej dziecko 9, więc dziewięć -> left_child = osiem;
a następnie 2 jest lewym dzieckiem 3, więc możemy to zrobić tutaj - ci -> left_child = dwa,.
Jeśli nie nadążam wraz z tym, proponuję wyciągnąć go z siebie.
>> Dobrze. Ratujmy to. Wyjdźmy i upewnij się kompiluje,
a następnie możemy dodać w naszych zawiera połączeń.
Wygląda na to wszystko nadal kompiluje.
Chodźmy i dodać niektóre zawiera połączeń.
Ponownie, mam zamiar zrobić trochę kopiowania i wklejania.
Teraz szukać 5, 8 i 2. Dobrze.
Upewnijmy się, że to wszystko wygląda dobrze, spokojnie. Great! Zapisz i zamknij.
Teraz zróbmy, kompilacji i teraz niech uruchomić.
Z wyników, wygląda to wszystko działa po prostu miło i dobrze.
Great! Więc teraz mamy nasze obejmuje funkcje napisane.
Idźmy dalej i rozpocząć pracę na jak wstawić węzły w drzewie
ponieważ, jak robimy to teraz, rzeczy nie są bardzo ładne.
>> Jeśli wrócimy do specyfikacji,
prosi nas napisać funkcję o nazwie wstawić - znowu, wracając bool
do tego, czy moglibyśmy wstawić węzeł na drzewie -
a następnie wartość wstawić do drzewa jest określona jako
Jedynym argumentem dla naszej funkcji wstawiania.
Wrócimy prawda czy możemy rzeczywiście wstawić wartość węzła zawierającego do drzewa,
co oznacza, że ​​jeden, miał mało pamięci
a dwa, że ​​węzeł nie istnieje w drzewie, ponieważ -
pamiętaj, że nie będziemy mieć zduplikowane wartości w drzewie, tak aby rzeczy proste.
Dobrze. Powrót do kodu.
Otwórz. Powiększyć trochę, a następnie przewiń w dół.
Postawmy funkcję wstawić tuż nad zawiera.
Ponownie, to będzie się nazywać bool insert (wartość int).
Daj mu trochę więcej miejsca, a następnie, jako domyślny,
postawmy w zamian fałszywe na samym końcu.
Teraz na dnie, idziemy dalej i zamiast ręcznie budowy węzłów
w głównym sami i okablowanie je wskazać na siebie jak robimy,
będziemy polegać na naszej funkcji insert to zrobić.
Nie będzie polegać na naszej funkcji insert zbudować całe drzewo od podstaw jeszcze,
ale raczej będziemy się pozbyć tych linii - we'll zakomentować tych linii -
które budują węzły 5, 8 i 2.
I zamiast, będziemy wstawiać połączenia do naszej funkcji płytek
aby upewnić się, że to faktycznie działa.
Jedziemy.
>> Teraz mamy wykomentowane te linie.
Mamy tylko 7, 3, 9 i 6 w naszym drzewie w tym momencie.
Aby upewnić się, że to wszystko działa,
możemy pomniejszyć, aby nasze drzewa binarnego,
uruchom go, a widzimy, że zawiera teraz nam mówi, że jesteśmy całkowicie w prawo -
5, 8 i 2 nie są już w drzewie.
Wróć do kodu,
i jak mamy zamiar włożyć?
Pamiętaj, co robiliśmy, kiedy byliśmy naprawdę wstawienie 5, 8 i 2 wcześniej.
Graliśmy w tę grę Plinko gdzie zaczęliśmy u nasady,
zszedł jednego drzewa przez jeden po drugim
aż znaleźliśmy odpowiednią lukę,
a następnie połączone w węźle w odpowiednim miejscu.
Mamy zamiar zrobić to samo.
Jest to w zasadzie jak pisanie kodu, który użyliśmy w zawiera funkcję
w miejsce, gdzie znajduje się węzeł powinny być,
i jesteśmy po prostu będzie wstawić węzeł tam.
Zacznijmy robić.
>> Więc mamy węzeł * Cur = root, jesteśmy po prostu będzie śledzić zawiera kod
dopóki nie okaże się, że nie całkiem dla nas pracować.
Mamy zamiar przejść przez drzewa, podczas gdy bieżący element nie jest pusty,
i jeśli okaże się, że dyskusja ma wartość równą wartości, które staramy się wprowadzić -
także, to jest jeden z tych przypadków, w których nie można faktycznie wprowadzić węzeł
do drzewa, bo to oznacza, że ​​mamy duplikaty wartości.
Tutaj jesteśmy rzeczywiście będzie return false.
Teraz też, jeżeli bież wartość jest mniejsza niż wartość
teraz wiemy, że możemy przejść do prawej
ponieważ wartość należy w prawej połowie drzewa Cur.
W przeciwnym razie, będziemy poruszać się w lewo.
To w zasadzie nasze obejmuje funkcje tam.
>> W tym momencie, po zakończeniu tego pętlę while,
nasz wskaźnik bież zostanie skierowany na null
Jeśli funkcja nie została już zwrócona.
Mamy w związku z tym o CUR w miejscu, gdzie chcemy wstawić nowy węzeł.
Co pozostaje do zrobienia jest faktycznie zbudować nowy węzeł,
co możemy zrobić dość łatwo.
Możemy użyć naszej super przydatną funkcję węzła kompilacji,
i coś, czego nie zrobiliśmy wcześniej -
po prostu rodzaj uznał za pewnik, ale teraz będziemy robić, żeby upewnić się -
będziemy przetestować, aby upewnić się, że wartość zwracana przez nowego węzła był rzeczywiście
not null, ponieważ nie chcemy, aby uruchomić dostęp do tej pamięci, jeśli jest null.
Możemy sprawdzić, aby upewnić się, że nowy węzeł nie jest równa null.
Albo zamiast tego możemy po prostu sprawdzić, czy to rzeczywiście jest pusta,
i jeśli jest pusta, to możemy po prostu return false wcześnie.
>> W tym momencie musimy podłączyć nowy węzeł w jego odpowiednim miejscu w drzewie.
Jeśli spojrzymy na główne i gdzie byliśmy faktycznie okablowanie w wartościach przed,
widzimy, że sposób, w jaki to robimy, kiedy chcieliśmy umieścić 3 w drzewie
został nam dostęp lewego dziecka korzenia.
Kiedy przygotowaliśmy 9 w drzewie, mieliśmy dostęp do odpowiedniego dziecka korzenia.
Musieliśmy mieć wskaźnik do rodzica, aby umieścić nową wartość do drzewa.
Przewijanie z powrotem włożyć, że nie będzie dość pracy tutaj
ponieważ nie mamy wskaźnik nadrzędny.
Co chcemy w stanie nie jest, w tym momencie,
sprawdzić wartość rodziców i zobaczyć - dobrze, Boże,
Jeśli rodzic ma wartość mniejszą od aktualnej wartości,
to rodzic ma rację dziecko powinno być nowy węzeł;
inaczej, wniosek rodziców lewej dziecko powinno być nowy węzeł.
Ale nie mamy ten wskaźnik nadrzędny dość jeszcze.
>> Aby je zdobyć, jesteśmy rzeczywiście będzie musiał śledzić go jak przejść przez drzewa
i znaleźć odpowiednie miejsce w naszej pętli powyżej.
Możemy to zrobić poprzez przewijanie z powrotem do początku naszej funkcji płytek
i śledzenie innej zmiennej wskaźnik zwany rodzica.
Mamy zamiar ustawić go równa null początkowo
, a następnie za każdym razem przejść przez drzewa,
zamierzamy ustawić wskaźnik nadrzędny dopasować bieżący wskaźnik.
Ustaw rodzica równe Cur.
W ten sposób, za każdym razem przejść,
jedziemy do zapewnienia, że ​​prąd pobiera wskaźnik zwiększany
wskaźnik rodzic następująco - po prostu o jeden poziom wyżej niż obecny wskaźnik w drzewie.
Że wszystko wygląda całkiem nieźle.
>> Myślę, że jedyną rzeczą, która będziemy chcieli ustawić to budować węzła powracającego null.
W celu uzyskania zbudować węzeł faktycznie pomyślnie powrócić null,
musimy zmodyfikować ten kod,
bo tu, nigdy nie testowane, aby upewnić się, że malloc zwróciło ważny wskaźnik.
Tak więc, jeśli (n = NULL!), A następnie -
jeśli malloc zwróciło ważny wskaźnik, wtedy będziemy go zainicjować;
inaczej, po prostu wrócić i że zakończy się powrotem null dla nas.
Teraz wszystko wygląda całkiem nieźle. Upewnijmy się, to rzeczywiście kompiluje.
Producent drzewa binarnego, i oh, mamy pewne rzeczy się dzieje.
>> Mamy niejawna deklaracja funkcji zbudować węzeł.
Ponownie, z tych kompilatorów, mamy zamiar rozpocząć na szczycie.
Co to może oznaczać to, że dzwonię zbudować węzeł przed mam faktycznie zadeklarował go.
Wróćmy do kodu bardzo szybko.
Przewiń w dół, a na pewno wystarczy, moja funkcja insert jest zadeklarowana
powyżej funkcji budowania węzła
ale staram się używać zbudować węzeł wewnątrz wkładki.
Mam zamiar iść i skopiuj - a następnie wklej węzła drogi Funkcja budowania tu na górze.
W ten sposób, mam nadzieję, że będzie działać. Dajmy to jeszcze raz.
Teraz wszystko kompiluje. Wszystko jest dobrze.
>> Ale w tym momencie, nie mamy naprawdę nazywa naszą funkcję wstawiania.
Wiemy tylko, że kompiluje, więc chodźmy i umieścić kilka połączeń w.
Zróbmy to w naszej głównej funkcji.
Tutaj, wypowiedziało się 5, 8 i 2,
a następnie nie podłączać je tutaj.
Zróbmy niektóre zaproszenia wstawić,
i niech to też używał tego rodzaju rzeczy, które używane
kiedy zrobiliśmy te printf połączeń, aby upewnić się, że wszystko udało się prawidłowo włożona.
Mam zamiar skopiować i wkleić,
i zamiast zawiera zamierzamy zrobić wkładkę.
I zamiast 6, 10 i 1, będziemy używać 5, 8 i 2.
Powinno to wstawić 5, 8 i 2 do drzewa.
Skompilować. Wszystko jest dobrze. Teraz będziemy faktycznie uruchomić nasz program.
>> Wszystko wróciło false.
Tak, 5, 8 i 2 nie wychodzi, i wygląda na to zawiera nie znaleźli ich albo.
Co się dzieje? Miejmy pomniejszyć.
Pierwszym problemem było to, że wydawało się, insert return false,
i wygląda na to, że to dlatego, że zostawiliśmy w naszym powrocie rozmowy fałszywej
i nigdy tak naprawdę zwróciło true.
Możemy ustawić, że w górę.
Drugim problemem jest to, teraz, nawet jeśli robimy - zapisać to, zamknij to
uruchom make znowu nie skompilować, a następnie uruchomić go -
widzimy, że coś tu się stało.
5, 8 i 2 nie zostały nadal obecny w drzewie.
Więc, co się dzieje?
>> Rzućmy okiem na to w kodzie.
Zobaczymy, czy uda nam się to.
Zaczynamy rodzic nie jest null.
Ustawiamy aktualny wskaźnik równy wskaźnika głównego,
i będziemy pracować naszą drogę w dół drzewa.
Jeśli bieżący węzeł nie jest pusta, to wiemy, że możemy przenieść w dół trochę.
Wyznaczamy naszą wskaźnik nadrzędny równa obecnej wskaźnik,
Sprawdziłem wartość - jeśli wartości są takie same, wróciliśmy false.
Jeśli wartości są mniej przenieśliśmy się do prawa;
inaczej, przesunął się na lewo.
Następnie budujemy węzeł. Będę powiększyć trochę.
I tutaj mamy zamiar spróbować podłączyć się wartości na ten sam.
Co się dzieje? Zobaczmy, czy ewentualnie Valgrind może dać nam wskazówkę.
>> Lubię używać tylko dlatego Valgrind Valgrind naprawdę szybko biegnie
oraz informuje, czy są jakieś błędy pamięci.
Kiedy uruchomić Valgrind na kodzie,
jak widać prawo hit here--Valgrind./binary_tree--and wejść.
Widać, że nie ma żadnego błędu pamięci, więc wygląda na to, że wszystko jest w porządku, tak daleko.
Mamy pewne przecieki pamięci, którą znamy, bo nie jesteśmy
dzieje się uwolnić żadnego z naszych węzłów.
Spróbujmy uruchomiony GDB zobaczyć, co się właściwie dzieje.
Zrobimy gdb. / Binary_tree. To zyski w górze dobrze.
Ustawmy punkt załamania na wkładce.
Przyjrzyjmy się.
Wygląda na to, nigdy tak naprawdę nazywa się wkładka.
To wygląda jak problem był tak, że gdy zmienił tutaj w main -
wszystkie z tych połączeń od printf zawiera -
Nigdy nie zmieniły one wywołać wkładkę.
Teraz spróbować. Miejmy skompilować.
Wszystko wygląda dobrze tam. Teraz spróbuj uruchomić go, zobacz co się dzieje.
W porządku! Wszystko wygląda całkiem dobre.
>> Ostatnią rzeczą, aby myśleć o to, czy są jakieś przypadki krawędzi do tej wstawki?
I okazuje się, że dobrze, że jeden przypadek krawędź jest zawsze ciekawe, aby myśleć o
jest, co się dzieje, jeśli drzewo jest puste i wywołać tę funkcję wstawić?
To będzie działać? Cóż, spróbować.
- Binary_tree c. -
Sposób będziemy testować to, idziemy na dół do naszej głównej funkcji,
i zamiast okablowania tych węzłów aż takiego,
jesteśmy po prostu będzie do ustosunkowania się całą rzecz,
i zamiast okablowanie węzłów siebie,
rzeczywiście możemy pójść dalej i usunąć wszystko.
Będziemy robić wszystko wezwanie do wstawienia.
Więc zróbmy - zamiast 5, 8 i 2, idziemy wstawić 7, 3 i 9.
A potem my także chcemy wstawić 6, jak również.
Zapisz. Quit. Producent drzewa binarnego.
To wszystko kompiluje.
Możemy po prostu uruchomić go jak jest i zobaczyć, co się dzieje,
ale to również będzie bardzo ważne, aby upewnić się, że
nie mamy żadnych błędów pamięci,
ponieważ jest to jeden z naszych przypadków krawędzi, które znamy temat.
>> Upewnijmy się, że działa dobrze pod Valgrind,
co będziemy robić po prostu działa Valgrind. / binary_tree.
Wygląda na to, że rzeczywiście posiada jeden błąd z jednym kontekście -
mamy ten segmentation fault.
Co się stało?
Valgrind rzeczywiście mówi nam gdzie to jest.
Pomniejszyć trochę.
Wygląda, że ​​to się dzieje w naszej funkcji wstawiania
gdzie mamy nieprawidłowy odczytu wielkości 4 na wkładce, line 60.
Wróćmy i zobaczyć, co się tu dzieje.
Pomniejsz naprawdę szybkie.
Chcę się upewnić, że to nie idzie się do krawędzi ekranu, dzięki czemu możemy zobaczyć wszystko.
Wyciągnij, że w trochę. Dobrze.
Przewiń w dół, a problem jest tutaj.
Co się dzieje, jeśli mamy w dół, a nasz aktualny węzeł jest już pusty,
nasz węzeł nadrzędny jest zerowy, więc jeśli przyjrzymy się na samej górze, tu -
jeśli nie to pętla faktycznie wykonuje
ponieważ nasza obecna wartość jest null - nasz korzeń jest zerowy, więc dyskusja jest null -
potem nie nasz rodzic pobiera ustawiony na cur lub do prawidłowej wartości,
tak, to rodzic będzie też null.
Musimy pamiętać, aby sprawdzić, że
przez czas mamy tu i zaczynamy dostęp rodzica wartość.
Więc co się dzieje? Cóż, jeśli rodzic jest null -
if (NULL == rodzic) - to wiemy, że
nie musi być wszystko w drzewie.
Musimy się starać, aby wstawić go w katalogu głównym.
Możemy to zrobić, po prostu ustawiając korzeń równą nowego węzła.
Potem w tym miejscu, że w rzeczywistości nie chcą przejść przez te inne rzeczy.
Zamiast tu, możemy zrobić albo else-if-else,
albo możemy połączyć wszystko tutaj w inny,
ale tu będziemy po prostu użyć innego i zrobić to w ten sposób.
Teraz mamy zamiar przetestować, aby upewnić się, że nasz rodzic nie jest null
wcześniej faktycznie próbuje uzyskać dostęp do swoich pól.
To pomoże nam uniknąć błędu segmentacji.
Więc zamknąć, pomniejszyć, skompilować, uruchomić.
>> Żadnych błędów, ale nadal mamy kilka wycieków pamięci
ponieważ nie wszystkich naszych uwolnić węzłów.
Ale, jeśli idziemy tu i patrzymy na naszego wydruku
widzimy, że dobrze, wygląda jak wszystkie nasze wkładki wracali true, co jest dobre.
Wkładki są prawdziwe,
a następnie odpowiednie zawiera rozmowy są prawdziwe.
>> Dobra robota! To wygląda tak, jakbyśmy pomyślnie zapisane wkładkę.
To wszystko mamy na ten tydzień specyfikacji określone problem.
One zabawa wyzwanie aby myśleć o to jak można faktycznie przejść w
i wolne wszystkie węzły w tym drzewie.
Można to zrobić na wiele różnych sposobów,
ale ja zostawiam to do ciebie, aby eksperymentować,
i jako wyzwanie zabawy, spróbuj i upewnić się, że można mieć pewność,
że sprawozdanie to Valgrind nie zwraca żadnych błędów i nie ma wycieków.
>> Powodzenia w tym tygodniu zestaw kodowania Huffmana problemu,
i do zobaczenia w przyszłym tygodniu!
[CS50.TV]