[Powered by Google Translate] [Odjeljak 7] [Manje Ugodno]
[Nate Hardison] [Sveučilište Harvard]
[Ovo je CS50.] [CS50.TV]
>> Dobrodošli na odsjeku sedam.
Zahvaljujući uragan Sandy
umjesto da normalan dio ovaj tjedan,
radimo to prolazna, kroz dio pitanja.
Ja ću biti sljedeće zajedno s problemom Set 6 Specifikacija,
i prolazi kroz sva pitanja u
Odsjek Pitanja dijelu.
Ako postoje bilo kakva pitanja,
molimo objaviti na CS50 raspravljati.
>> Dobro,. Počnimo.
Trenutno sam u potrazi na stranici 3. specifikacija problema Set.
Idemo prvo početi govoriti o binarnih stabala
od onih koji imaju puno važnosti za ovotjednom problema setu -
kodiranje Huffman stablo.
Jedan od prvih struktura podataka razgovarali smo o na CS50 je niz.
Imajte na umu da je niz je niz elemenata -
sve iste vrste - pohranjeni tik jedna do druge u memoriji.
Ako imam cijeli niz koji sam može izvući koristi ovu kutije-brojevi-integers stil -
Recimo imam 5 u prvom kutiji, imam sedam u drugom,
onda sam 8, 10 i 20 u zadnjoj kutiji.
Podsjetimo, dvije stvarno dobre stvari o tom obilju
su da imamo ovu konstanta-time pristup bilo kojeg elementa
u nizu, ako znamo svoj indeks.
Na primjer, ako želim da zgrabite treći element u nizu -
na indeksu 2 pomoću naše nula-based indeksni sustav -
Doslovno sam samo morati napraviti jednostavan matematički izračun,
hop na toj poziciji u polju,
izvucite 8 koja je tamo pohranjena,
i ja sam dobar to ići.
>> Jedna od loših stvari o tom obilju - da smo razgovarali o tome
kada smo razgovarali vezane liste -
je da ako želim umetnuti element u ovom nizu,
Ja ću morati napraviti neke kreće oko.
Na primjer, ovo polje ovdje
je u sortiraju bi - sortirani uzlaznim redoslijedom -
5, a zatim 7, zatim 8, od 10, a zatim 20 -
ali ako želim umetnuti broj 9 u ovom polju,
Ja ću morati prebaciti neke od elemenata kako bi prostor.
Možemo nacrtati ovo ovdje.
Ja ću morati premjestiti 5, 7, i onda 8;
stvoriti jaz gdje mogu staviti 9,
i onda 10 i 20 može ići desno od devet.
To je vrsta boli, jer u najgorem slučaju -
kada imamo umetnuti bilo na početku ili na kraju
od polja, ovisno o tome koliko smo kreće -
možemo završiti s prebaciti sve elemente
trenutno radimo na čuvanje u polju.
>> Dakle, ono što je bio način oko ovoga?
Način oko ovoga je da ide na naš linked-list metoda gdje -
umjesto spremanja elemente 5, 7, 8, 10 i 20 sve pored drugoga u sjećanju -
ono što smo umjesto toga nije bio pohraniti ih vrsta gdje god smo htjeli da ih pohraniti
u tim povezana-popis čvorova koje crtam ovdje, kakav ad hoc.
I onda smo ih spojiti zajedno pomoću ovih sljedećoj naputke.
Mogu imati pokazivač od 5 do 7,
pokazivač od 7. do 8,
pokazivač od 8 do 10,
i na kraju, pokazivač od 10 do 20,
i onda null pointer na 20 što pokazuje da nema ništa lijevo.
Trgovinski-off koji imamo ovdje
je da sada, ako želimo umetnuti broj 9 u našoj sortirati popis,
sve što morate učiniti je stvoriti novi čvor s 9,
ga spojiti do točke na odgovarajuće mjesto,
a zatim ponovno žice 8 ukazati do 9.
To je prilično brzo, pod pretpostavkom da znamo točno gdje želimo umetnuti devet.
No, trade-off, u zamjenu za to da sada smo izgubili konstanta-time pristup
za određeni element u našoj strukture podataka.
Na primjer, ako želim pronaći četvrti element u ovom povezanom popisu,
Ja ću morati početi na samom početku popisa
i raditi svoj put kroz računajući čvor-by-čvor dok sam pronaći četvrti jednom.
>> Kako bi dobili bolji pristup performanse od povezane liste -
ali i zadržati neke od prednosti koje smo imali
u smislu unosa vremenu iz povezane liste -
binarno stablo će se morati koristiti malo više memorije.
Konkretno, umjesto da samo imaju jedan pokazivač u binarnom stablu čvor -
kao linked-liste čvor ne -
idemo dodati drugi pokazivač binarnog stabla čvor.
Umjesto da samo ima jedan pokazivač na sljedeći element,
idemo imati pokazivač na lijevoj djeteta i pravo djeteta.
>> Ajmo nacrtati sliku kako bi vidjeli što to zapravo izgleda.
Opet, ja ću koristiti ove kutije i strijele.
Binarno stablo čvor će krenuti sa samo jednostavnim kutiji.
To će imati prostor za vrijednosti,
i onda to također će imati prostora za lijevu djeteta i pravo djeteta.
Ja ću ih označiti ovdje.
Mi ćemo imati lijevu dijete, a onda ćemo imati pravo dijete.
Postoji mnogo različitih načina ovo.
Ponekad za prostor i praktičnost,
Ja sam zapravo ću ga izvući kao radim ovdje na dnu
gdje ću imati vrijednost na vrhu,
i onda pravo djeteta na donjem desnom,
i lijevo dijete na donjem lijevom.
Vraćajući se ovom gornjem dijagramu,
imamo vrijednost na samom vrhu,
onda imamo lijevo-dijete pokazivač, a zatim imamo pravo-dijete pokazivač.
>> U specifikaciji Problem Set,
govorimo o izradi čvor koji ima vrijednost 7,
i onda lijevo-dijete pokazivač da je nula, a desno dijete pokazivač koji je null.
Mi može pisati kapitala NULL u prostoru za
i lijevo dijete i pravo dijete, ili možemo izvući ovu dijagonale crtu
kroz svaki od kutije pokazuju da je ništavan.
Ja ću učiniti da samo zato što je jednostavnije.
Ono što vidite ovdje su dva načina dijagrama vrlo jednostavan čvor binarnog stabla
gdje imamo vrijednost 7 i null dijete upućuje.
>> Drugi dio naših specifikacija razgovora o tome s povezanim listama -
zapamtite, samo mi morali držati na prvi element u popisu
zapamtiti cijeli popis -
a isto tako, s binarno stablo, imamo samo držati na jednom pokazivač na stablu
kako bi zadržali kontrolu nad cijelom strukturom podataka.
Ova posebna element stabla se zove korijen čvor stabla.
Na primjer, ako je to jedan čvor - to čvor koji sadrži vrijednost 7
s null lijeve i desne pokazivače dijete -
bili jedina vrijednost u našem stablu,
onda će to biti naša čvor korijen.
To je vrlo početak našeg stabla.
Možemo vidjeti ovo malo jasnije kada ćemo početi dodavanjem više čvorova našem stablu.
Dopustite mi podići novu stranicu.
>> Sada ćemo izvući stablo koje ima sedam u korijenu,
i 3 unutar lijevog djeteta, i 9 unutrašnju stranu desnog djeteta.
Opet, to je prilično jednostavan.
Imamo sedam, nacrtati čvor za tri, čvor za 9,
i ja ću postaviti lijevo-dijete pokazivač od 7 do točke do čvora sadrži tri,
i desno dijete pokazivač čvora sadrži sedam do čvora sadrži devet.
Sada, budući da tri i devet nemaju djecu,
idemo postaviti sve svoje dijete upućuje biti nula.
Evo, korijen našeg stabla odgovara čvor koji sadrži broj 7.
Možete vidjeti da ako je sve što imamo je pokazivač na taj čvor korijena,
tada možemo prošetati kroz naš stabla i pristupiti oba djeteta čvorova -
i 3 i 9.
Nema potrebe za održavanje upućuje na svaki čvor na stablu.
Dobro,. Sada ćemo dodati još jedan čvor na ovom dijagramu.
Mi ćemo dodati čvor koji sadrži 6,
a mi ćemo dodati to kao pravo dijete čvora sadrži tri.
Da bi to učinili, ja ću izbrisati taj null pokazivač u 3-čvor
i spojiti se ukazati na čvoru sadrži šest. Dobro,.
>> U ovom trenutku, idemo preko malo terminologije.
Za početak, razlog da se to zove binarno stablo posebice
je da ima dva djeteta upućuje.
Postoje i druge vrste drveća koje imaju više djece naputke.
Konkretno, jesi 'probati' u problem Set 5.
Primijetit ćete da je u tom pokušaju, što je 27 različitih upućuje na različite djece -
jedan za svaki od 26 slova u engleske abecede,
, a zatim 27. za apostrofa -
tako, da je slična vrsti drveta.
Ali ovdje, jer to je binarni, imamo samo dva djeteta upućuje.
>> Osim toga korijen čvor koji smo govorili,
mi smo također je bacio oko ovog pojma 'dijete'.
Što to znači za jedan čvor da se dijete drugog čvora?
To doslovno znači da čvor dijete je dijete drugog čvora
ako je ta druga čvor ima jednu od svojih dječjih upućuje postavljene ukazati na tom čvoru.
Da bi se to u više konkretnim uvjetima,
ako je ukazao na tri strane jednog djeteta upućuje na sedam, a zatim tri je dijete sedam.
Ako bismo shvatiti što djeca 7 su -
dobro, vidjet ćemo da 7 ima pokazivač na tri i upustvo na devet,
pa 9 i 3 su djeca 7.
Devet nema djece, jer njeni dijete pokazivače su nula,
i 3 ima samo jedno dijete, šest.
Šest također nema djece, jer obje njegove naputke su null, koje ćemo izvući upravo sada.
>> Osim toga, mi također govoriti o roditeljima određenog čvora,
i to je, kao što očekujete, suprotno od ovog djeteta opisa.
Svaki čvor ima samo jednog roditelja - umjesto dva kao što ste mogli očekivati ​​s ljudima.
Na primjer, roditelj tri je sedam.
Roditelj od 9 je također sedam, a roditelj 6 je tri. Nije puno za njega.
Također imamo uvjete za razgovor o djedova i unučadi,
i općenito govorimo o precima
i potomci određenom čvoru.
Predak od čvora - ili preci, bolje rečeno, od čvora -
su svi čvorovi koji se nalaze na putu od korijena do tog čvora.
Na primjer, ako gledam čvora 6,
onda preci će biti i tri i sedam.
Preci 9, na primjer, su - ako gledam čvora 9 -
onda predak 9 je samo sedam.
A potomci su upravo obrnuta.
Ako želim da pogledate sve od potomaka 7,
onda moram gledati na sve čvorove ispod njega.
Dakle, imam 3, 9 i 6 sve kao potomaka sedam.
>> Konačni termin koji ćemo govoriti o je taj pojam kao sestru.
Braća - vrste nakon zajedno na tim obiteljskim uvjetima -
su čvorovi koji su na istoj razini u stablo.
Dakle, 3 i 9 su braća i sestre, jer su na istoj razini u stablo.
Obojica imaju isti roditelj, sedam.
U 6 nema braće i sestara, jer devet nema djece.
I sedam nema braće i sestara, jer je korijen našeg stabla,
i tu je uvijek samo jedan korijen.
Za sedam braće i sestara imati tu bi trebala biti čvor iznad sedam.
Tu bi trebala biti roditelj 7, u kojem slučaju 7 više ne bi korijen stabla.
Zatim taj novi roditelj 7 će također imati dijete,
i da dijete tada će biti sestru sedam.
>> Dobro,. Premještanje na.
Kad smo započeli našu raspravu binarnih stabala,
smo razgovarali o tome kako da ćemo ih koristiti za
dobiti prednost nad oba polja i povezane liste.
A način na koji ćemo učiniti da je s ovim naručivanja imovine.
Kažemo da binarno stablo je naredio, prema specifikaciji,
ako za svaki čvor u našem stablu, svim svojim potomcima na lijevo -
lijevo dijete, a sve s lijeve strane djeteta potomaka -
imaju manje vrijednosti, a sve od čvorova na desnoj strani -
pravo djeteta, a sve pravo djeteta potomaka -
imati čvorove veće od vrijednosti tekućeg čvora da smo u potrazi na.
Samo zbog jednostavnosti, idemo pretpostaviti da ne postoje nikakvi duple čvorove u našem stablu.
Na primjer, u ovom stablu nećemo se baviti s tim slučajem
gdje imamo vrijednost 7 u korijenu
i onda mi također imaju vrijednost 7 drugdje u stablo.
U ovom slučaju, primijetit ćete da je to stablo doista naredio.
Imamo vrijednost 7 u korijenu.
Sve na lijevoj 7 -
ako sam poništiti sve od tih malih maraka ovdje -
sve s lijeve strane 7 - 3 i 6 -
te vrijednosti su manje od sedam, a sve kako bi desno - što je upravo to 9 -
je veći od 7.
>> Ovo nije jedini naredio stablo sadrži ove vrijednosti,
ali ajmo izvući malo više od njih.
Tu je zapravo cijela hrpa načina na koje možemo to učiniti.
Ja ću koristiti stenogram samo držati jednostavne stvari gdje -
nego izvlači cijeli kutije-i-strelice -
Samo ću izvući brojeve i dodati strelice ih povezuju.
Za početak, samo ćemo pisati svoju izvornu stablo opet gdje smo imali sedam, a zatim tri,
i od 3 ukazao natrag na pravo na 6,
i 7 imao pravo djeteta koje je devet.
Dobro,. Što je još jedan način na koji smo mogli napisati ovo drvo?
Umjesto tri biti lijevo dijete od 7,
mi također mogli imati šest biti lijevo dijete od 7,
i onda 3 biti lijevo dijete od šest.
To će izgledati ovako stabla ovdje gdje sam dobio 7,
zatim 6, a zatim 3 i 9 na desnoj strani.
Mi također ne moraju imati 7 kao naš korijen čvor.
Također smo mogli imati šest kao naš korijen čvor.
Što bi to izgledati?
Ako ćemo zadržati ovaj naredio imovine,
sve do lijevo od 6 mora biti manji od njega.
Postoji samo jedna mogućnost, a to je tri.
Ali onda kao pravi dijete 6, imamo dvije mogućnosti.
Prvo, mogli smo imati sedam, a zatim devet,
ili smo mogli izvući - kao što sam o to učiniti ovdje -
gdje imamo 9 kao pravo dijete od 6,
a zatim 7 kao lijeve dijete od 9 godina.
>> Sada, 7 i 6 nisu samo moguće vrijednosti za korijen.
Također smo mogli imati tri biti u korijenu.
Što će se dogoditi ako 3 je u korijenu?
Evo, stvari se malo zanimljivo.
Tri nema nikakve vrijednosti koje su manje od njega,
tako da cijela lijeva strana stablo samo će biti nula.
Tu neće biti ništa tamo.
Za pravo, mogli smo popis stvari u uzlaznom redoslijedu.
Mi smo mogli imati tri, a zatim 6, a zatim sedam, a zatim devet.
Ili, mogli bismo napraviti tri, zatim šest, zatim devet, zatim sedam.
Ili, mogli bismo napraviti tri, zatim sedam, zatim šest, zatim devet.
Ili, 3, 7 - zapravo nema, ne možemo napraviti sedam više.
To je naša jedna stvar tamo.
Mi možemo učiniti devet, a zatim od devet možemo učiniti šest, a zatim sedam.
Ili, možemo napraviti 3, a zatim 9, a zatim 7, a zatim 6.
>> Jedna stvar za privući vašu pažnju ovdje
da ova stabla su malo čudan.
Konkretno, ako ćemo gledati na četiri stabla na desnoj strani -
Ja ću ih obići, ovdje -
ova stabla izgledaju gotovo točno kao povezane liste.
Svaki čvor ima samo jedno dijete,
pa mi nemamo bilo koju od ove stablo poput strukture koje vidimo, na primjer,
u tom jednom usamljenom stablu ovamo na dnu lijevo.
Ove stabla su zapravo zove izrod binarnih stabala,
pa ćemo razgovarati o tim više u budućnosti -
pogotovo ako idete na poduzeti druge tečajeve informatike.
Ove stabla su izrod.
Oni nisu vrlo koristan, jer, doista, ova struktura posuđuje sama
na traženje puta slične onoj povezane liste.
Mi ne bi iskoristiti dodatne memorije - ovaj dodatni pokazivač -
zbog naše strukture biti loše na ovaj način.
Umjesto ići na i izvući binarnih stabala koja imaju devet u korijenu,
koja je konačna slučaj da imamo,
mi smo umjesto toga, u ovom trenutku, ide na razgovor malo o ovom drugom roku
da mi koristimo kada govorimo o stablima, koji se zove visina.
>> Visina stabla je udaljenost od korijena do najviše dalekoj čvora,
odnosno broj skokova da bi trebala napraviti kako bi se
početi od korijena i onda završiti na najviše dalekoj čvor u stablu.
Ako gledamo na neke od tih stabala koje smo izvučeni ovdje,
možemo vidjeti da ako uzmemo ovo drvo u gornjem lijevom kutu, a mi početi na tri,
onda moramo napraviti jedan skok doći do 6, drugi hop doći do sedam,
i trećina hop doći do devet.
Dakle, visina ovog stabla je tri.
Mi možemo učiniti istu vježbu za drugim stabala navedenih u ovom zelenom,
i vidimo da je visina svih tih stabala je također istina 3.
To je dio onoga što ih čini izrod -
da je njihova visina je samo jedan manje od broja čvorova u cijelom stablu.
Ako gledamo na ovom drugom stablu koji je okružen s crvenom, s druge strane,
vidimo da su najviše udaljene list čvorovi su 6 i 9 -
ostavlja se ti čvorovi koje nemaju djecu.
Dakle, kako bi se iz korijena čvor na bilo 6 ili 9,
moramo napraviti jedan skok doći do 7, a zatim drugi hop doći do 9,
i isto tako, samo drugi hop od sedam doći do šest.
Dakle, visina ovog stabla ovdje je samo 2.
Možete se vratiti i to za sve ostale stabala koje smo ranije razgovarali
s početkom u 7 i 6,
i vidjet ćete da je visina svih tih stabala je također dva.
>> Razlog što smo govorili o naručio binarnih stabala
i zašto su cool jer možete pretraživati ​​kroz njih u
vrlo sličan način u potrazi preko sortirani niz.
Ovo je mjesto gdje govorimo o dobivanju taj poboljšani pretraživanja vremena
preko jednostavnog povezane liste.
Uz povezane liste - ako želite pronaći određeni element -
ti si u najboljem će učiniti nekakvu linearnog pretraživanja
gdje se na početku popisa i hop jedan po jedan -
jedan čvor po jedan čvor -
kroz cijeli popis dok ne pronađete ono što ste tražili.
Budući da, ako imate binarnog stabla koji je pohranjen u ovoj lijepoj formatu,
zapravo možete dobiti više od binarnog pretraživanja događa
gdje ste podijeli pa vladaj
i traži kroz odgovarajuće polovice stabla na svakom koraku.
Idemo vidjeti kako se to radi.
>> Ako imamo - opet, ide natrag u naš originalni stabla -
smo započeli u 7, imamo 3 na lijevoj strani, 9 na desnoj strani,
i ispod 3 imamo šest.
Ako želimo tražiti broj 6 u ovoj stabla, da ćemo započeti u korijenu.
Želimo usporediti vrijednost smo u potrazi za, recimo 6,
na vrijednost pohranjena u čvoru koji mi trenutno gledamo, 7,
Smatraju da je doista šest manje od 7, tako da bismo se presele na lijevoj strani.
Ako je vrijednost 6 bio veći od sedam, što bi umjesto toga su se preselili u desno.
Budući da znamo da je - s obzirom na strukturu našeg naredio binarno stablo -
sve vrijednosti manje od 7 će biti pohranjeni na lijevoj 7,
nema potrebe da se čak i gnjaviti gleda kroz desnoj strani stabla.
Nakon što smo se presele na lijevoj strani, a mi smo sada na čvoru sadrži tri,
možemo učiniti da istu usporedbu opet gdje smo usporedili tri i šest.
I mi smo pronašli da dok 6 - vrijednost tražimo - veći od 3,
možemo ići na desnoj strani čvor sadrži tri.
Nema lijeva strana ovdje, tako da smo mogli ignorirati to.
No, mi samo znamo da zato tražimo na samog stabla,
i možemo vidjeti da je stablo nema djece.
>> To je također prilično lako gledati 6 u ovom stablu ako radimo to sami kao ljudi,
ali ajmo slijediti ovaj proces mehanički poput računala će učiniti
stvarno razumjeti algoritam.
U ovom trenutku, mi smo sada gleda na čvoru koji sadrži 6,
i mi smo u potrazi za vrijednost 6,
tako je, doista, pronašli smo odgovarajući čvor.
Našli smo vrijednost 6 u našem stablu, a možemo prestati tražiti.
U ovom trenutku, ovisno o tome što se događa,
možemo reći, da smo našli vrijednost 6, to postoji u našem stablu.
Ili, ako ćemo planira umetnuti čvor ili učiniti nešto, što možemo učiniti da se u ovom trenutku.
>> Učinimo par više dohvate samo da vidim kako to ide.
Pogledajmo što se događa ako smo probati i pogledati vrijednost 10.
Ako smo bili pogledati vrijednost 10, što bi početi u korijenu.
Želimo vidjeti da 10 je veći od 7, tako da bismo se presele na desno.
Želimo doći do devet i usporedite 9 do 10 i vidjeti da je 9 doista manje od 10.
Pa opet, mi bismo pokušati pomaknuti udesno.
No, u ovom trenutku, mi bismo primijetiti da smo na null čvor.
Tu nema ništa. Nema ništa gdje 10 bi trebao biti.
Ovo je mjesto gdje možemo prijaviti neuspjeh - da je zaista ne 10 u stablo.
I na kraju, idemo kroz slučaj gdje smo pokušavate pogledati jedan u stablo.
To je slično onome što se događa ako ćemo gledati do 10, osim umjesto da ide desno,
idemo ići na lijevoj strani.
Krećemo u 7 i vidjeti da je jedan manje od 7, tako da smo se presele na lijevoj strani.
Mi smo dobili na tri i vidjeti da je jedan manje od tri, pa opet ćemo pokušati da se presele na lijevoj strani.
U ovom trenutku imamo null čvor, tako da opet možemo prijaviti neuspjeh.
>> Ako želite saznati više o binarnih stabala,
postoje cijela hrpa zabavnih malih problema koje možete učiniti s njima.
Predlažem trenirao crtež iz ovih dijagrama jedan po jedan
i nakon kroz sve različite korake,
jer to će doći u super-zgodan
ne samo kada radite problema Huffman encoding set
ali iu budućim tečajevima -
samo učenje kako izvući ove strukture podataka i misliti kroz probleme
s olovku i papir ili, u ovom slučaju, iPad i olovka.
>> U ovom trenutku ipak, idemo da se presele na napraviti neke praksu kodiranja
i zapravo igraju s ovih binarnih stabala i vidjeti.
Ja ću se vratiti preko moje računalo.
Za ovaj dio članka, umjesto korištenja CS50 CS50 Run ili prostora,
Ja ću koristiti aparat.
>> Nakon zajedno sa specifikacijom Problem Set,
Vidim da sam trebao otvoriti aparat,
ići na moj Dropbox mapu, stvoriti mapu pod nazivom Odjeljak 7,
, a zatim stvoriti datoteku pod nazivom binary_tree.c.
Ovdje ćemo ići. Imam aparat već otvoren.
Idem podići terminal.
Ja idem na Dropbox mapu, napraviti direktorij pod nazivom section7,
i vidjeti da je potpuno prazna.
Sada ću otvoriti binary_tree.c.
Dobro,. Ovdje ćemo ići - praznu datoteku.
>> Vratimo se na specifikaciji.
Specifikacija pita za stvaranje novog tipa definiciju
za binarnom stablu čvor koji sadrži int vrijednosti -
baš kao i vrijednostima koje smo izvukao u naš dijagrame prije.
Mi ćemo koristiti ovaj predloženi typedef da smo učinili ovdje
koji bi trebali prepoznati iz problema Set 5 -
ako nisi ljestve stol način osvajanje Speller programa.
Vi bi također trebali prepoznati ga iz prošlotjednog dijelu
gdje smo razgovarali o povezanim listama.
Moramo to typedef struct od čvora,
a mi smo dati ovaj struct node ovo ime struct čvora unaprijed
tako da mi onda može odnositi na njega jer ćemo želite imati pokazivače struct čvor
kao dio naše struct, ali smo onda sam okružen ovo -
odnosno, prilaže ovo - u typedef
tako da, kasnije u kodu, možemo se odnose na ovaj struct samo kao čvor umjesto struct čvora.
>> To će biti vrlo sličan pojedinačno-linked list definiciji da smo vidjeli prošli tjedan.
Da biste to učinili, neka je samo započeti pisanje predloženi.
Mi znamo da moramo imati cjelobrojne vrijednosti
pa ćemo staviti u int vrijednosti, a zatim, umjesto da samo jedan pokazivač na sljedeći element -
kao što smo učinili s pojedinačno povezanih s popisa -
idemo imati lijevo i desno dijete upućuje.
To je prilično jednostavan previše - struct node * lijevo dijete;
i rekonstruirati čvor * desno dijete;. Cool.
To izgleda kao prilično dobar početak.
Vratimo se na specifikaciji.
>> Sada trebamo proglasiti globalnu varijablu čvor * za korijen stabla.
Mi ćemo napraviti ovo globalno baš kao što smo napravili prvi pokazivač u našem povezane liste i globalne.
To je bilo tako da je u funkcijama koje smo napisali
ne morate se držati prolazi oko tog korijena -
iako ćemo vidjeti da ako ne želite pisati ove funkcije rekurzivno,
to bi moglo biti bolje da nije ni to zaobići kao globalni na prvom mjestu
i umjesto da ga inicijalizirati lokalno u glavnom funkciji.
No, mi ćemo to učiniti na globalnoj razini za početak.
Opet, mi ćemo dati nekoliko mjesta, a ja ću proglasiti čvor * korijen.
Samo kako bi bili sigurni da ne ostavljaju to nepokrenute, ja ću ga postaviti jednaka null.
Sada, u glavnoj funkciji - koji ćemo pisati stvarno brzo ovdje -
int main (int argc, const char * argv []) -
i ja ću početi proglašenja moj argv lepezu kao const samo tako da znam
da su ti argumenti su argumenti da sam vjerojatno ne žele mijenjati.
Ako želim ih mijenjati i vjerojatno bi trebao biti stvaranje kopije.
Vidjet ćete to puno u kodu.
To je u redu bilo koji način. To je u redu da ga ostavite kao - izostaviti const ako želite.
Ja obično ga staviti u samo tako da sam se podsjetiti
da sam vjerojatno ne želite mijenjati te tvrdnje.
>> Kao i uvijek, ja ću uključiti ovu povratnu 0 crtu na kraju glavni.
Evo, ja ću inicijalizirati moj čvor korijen.
Kao što stoji upravo sada, imam pokazivač koji je postavljen na nulu,
tako da je ukazujući na ništa.
Da bi se zapravo početi izgradnja čvora,
Prvi put sam je potrebno alocirati memoriju za njega.
Ja ću učiniti da izradi sjećanje na hrpu pomoću malloc.
Ja ću postaviti korijen jednak rezultat malloc,
a ja ću koristiti sizeof operatora za izračunavanje veličine čvora.
Razlog zbog kojeg sam koristiti sizeof čvor, za razliku od, recimo,
radiš nešto ovako - malloc (4 + 4 +4) ili malloc 12 -
je zato što želim da moja koda biti kompatibilan moguće.
Želim biti u mogućnosti iskoristiti ovu. C datoteku, prevesti ga na aparatu,
, a zatim ga prevesti na mom 64-bitni Mac -
ili na potpuno različitoj arhitekturi -
i želim to sve raditi isto.
>> Ako sam stvaranje pretpostavki o veličini varijabli -
veličina int ili veličini pokazivač -
onda sam i stvaranje pretpostavki o vrstama arhitekture
na kojoj moj broj uspješno može sastaviti kada pokrenuti.
Uvijek koristite sizeof za razliku od ručno zbrajanjem struct polja.
Drugi razlog je da postoji također može biti padding da je prevodilac stavlja u struct.
Čak i samo zbrajanjem pojedinačnih polja nije nešto što se obično žele učiniti,
tako, izbrisati tu liniju.
Sada, stvarno inicijalizirati ovaj čvor korijen,
Ja ću morati priključiti u vrijednosti za svaki od svojih različitih područja.
Na primjer, za vrijednost znam želim inicijalizirati na sedam,
i za sada ću postaviti lijevo dijete biti nula
i desno dijete također biti nula. Sjajno!
Učinili smo taj dio specifikacija.
>> Specifikacija dolje na dnu stranice 3 me pita za stvaranje tri više čvorova -
jedan sadrži tri, jedan sadrži šest, a jedan sa 9 -
i onda ih spojiti gore tako da izgleda baš kao naš stabla dijagrama
da smo pričali o ranije.
Ajmo to prilično brzo ovdje.
Vidjet ćete stvarno brzo, da ću početi pisati hrpa duple koda.
Ja ću stvoriti čvor * a ja ću ga nazvati tri.
Ja ću ga postaviti jednaka malloc (sizeof (čvor)).
Ja ću postaviti tri-> value = 3.
Tri -> left_child = NULL; tri -> desno _child = NULL; kao dobro.
To izgleda prilično slično inicijalizacije korijen, a to je upravo ono što
Ja ću morati učiniti ako počnem inicijalizacije 6 i 9 kao dobro.
Učinit ću to jako brzo ovdje - zapravo, ja ću učiniti malo kopirati i zalijepiti,
i pobrinite se da sam - u redu.
Sada, ja sam dobio ga kopirati, a ja mogu ići naprijed i postaviti to jednako šest.
Možete vidjeti da to traje neko vrijeme i nije super-učinkovit.
U samo malo, mi ćemo napisati funkciju koja će to učiniti za nas.
Želim zamijeniti ovaj sa 9, zamijenite da sa šest.
>> Sada imamo sve naše čvorova stvorio i inicijalizirana.
Imamo naš korijen postavljen jednak 7, ili sadrže vrijednost 7,
naš čvor koji sadrži tri, naš čvor koji sadrži šest, a naš čvor koji sadrži devet.
U ovom trenutku, sve što morate učiniti je žica sve gore.
Razlog zbog kojeg sam inicijalizira sve upućuje na nulu je samo tako da sam siguran da bi
Nemam nikakve nepokrenute upućuje u tu slučajno.
I također, jer je, u ovom trenutku, samo sam se zapravo povezivanje čvorova međusobno -
za one koji su zapravo povezani - Nemam proći i napraviti
sigurni da su svi ugašenih su tamo na odgovarajućim mjestima.
>> Počevši u korijenu, znam da je u korijenu je lijevo dijete je tri.
Znam da je korijen pravo dijete je devet.
Nakon toga, jedino drugo dijete koje sam ostavila brinuti
je 3 pravo dijete, koji je 6.
U ovom trenutku, to sve izgleda prilično dobro.
Mi ćemo izbrisati neke od tih linija.
Sada sve izgleda prilično dobro.
Vratimo se našoj specifikaciji i vidjeti što moramo učiniti sljedeći.
>> U ovom trenutku, moramo napisati funkcija zove 'sadrži'
sa prototip "bool sadrži (int vrijednost) '.
A to sadrži funkciju koja će povratak istina
ako je stablo ukazao na naše globalne korijena varijabla
sadrži vrijednost prošao u funkciji i lažno drugi način.
Idemo naprijed i učiniti.
To će biti točno kao lookup da smo napravili rukom na ipad samo malo prije.
Idemo povećavanje natrag u malo i pomaknite se gore.
Mi idemo staviti tu funkciju točno iznad naše glavne funkcije
tako da ne moramo raditi bilo kakve prototipa.
Dakle, bool sadrži (int vrijednost).
Tu ćemo ići. Tu je naš predloženi deklaracija.
Samo kako bi bili sigurni da će to sastaviti,
Ja ću ići naprijed i samo ga postaviti jednaka povratak false.
Upravo sada je ova funkcija jednostavno neće učiniti ništa i uvijek navode da
vrijednost da smo u potrazi za nije u stablu.
>> U ovom trenutku, to je vjerojatno dobra ideja -
otkako smo napisali hrpu koda i nismo ni pokušali to testiranje još -
kako bi bili sigurni da je sve to sastavlja.
Postoji nekoliko stvari koje moramo učiniti kako bi bili sigurni da će se to sastaviti.
Prvo, vidjeti ako smo koristili sve funkcije u bilo knjižnicama koje još nismo uključeni.
Funkcije koje smo koristili do sada su malloc,
i onda smo također bio koristeći ovu vrstu - ovo nije standardna tip zove 'bool' -
koja je uključena u standardnu ​​bool datoteku zaglavlja.
Mi svakako želimo uključiti standardni bool.h za bool tipa,
i mi također želimo # uključuju standardni lib.h za standardne knjižnicama
da su malloc i free, i sve to.
Dakle, zoom out, idemo prestati.
Pokušajmo i pobrinite se da je to zapravo učinio sastaviti.
Mi vidimo da to radi, tako da smo na pravom putu.
>> Ajmo otvoriti binary_tree.c opet.
To sastavlja. Idemo dolje i uvjerite se da smo ubaciti neke pozive na našoj sadrži funkcije -
samo da bi bili sigurni da je to sve dobro i dobro.
Na primjer, kada smo radili neke dohvate u našem stablu ranije,
pokušali smo potražiti vrijednosti 6, 10 i 1, a znali smo da je šest u stablu,
10 nije bio u stablo, a jedan nije bio u stablo bilo.
Ajmo koristiti one primjere pozive kao način shvatiti da li ili ne
Sadrži naša funkcija radi.
Da bi to učinili, ja ću koristiti printf funkciju,
i da ćemo ispisati rezultat poziva da sadrži.
Ja ću staviti u nizu "sadrži (% d) = jer
idemo na plug u vrijednosti koje ćemo tražiti,
i =% s \ n ", i koristiti kao naše format string.
Mi smo samo ćemo vidjeti - doslovno ispisati na zaslonu -
ono što izgleda kao funkcija poziva.
To nije zapravo funkcija poziva.
Ovo je samo niz dizajniran da izgledaju kao funkcija poziva.
>> Sada, idemo priključiti u vrijednosti.
Mi ćemo pokušati sadrži na šest,
i onda što ćemo učiniti ovdje je koristiti taj ternarni operator.
Hajdemo vidjeti - sadrži 6 - pa, sada sam sadržavao 6, a ako sadrži šest je istina,
string da ćemo poslati na% s formatu karaktera
će biti niz "pravi".
Ajmo pomicanje preko malo.
Inače, želimo poslati string "lažni" ako sadrži 6 false.
Ovo je malo glup izgleda, ali pretpostavljam da sam možda kao dobro ilustriraju
što je ternarni operator izgleda jer nismo ga vidjeli za neko vrijeme.
To će biti lijepo, zgodan način da se shvatiti ako naša Sadrži funkcija radi.
Idem za pomicanje natrag preko lijeve strane,
i ja ću kopirati i zalijepiti ovaj redak nekoliko puta.
To je promijenilo neke od tih vrijednosti oko,
tako da će to biti jedan, a to će biti 10.
>> U ovom trenutku imamo lijepu sadrži funkciju.
Imamo neke testove, pa ćemo vidjeti ako se to sve funkcionira.
U ovom trenutku smo napisana još malo koda.
Vrijeme je za otkaz van i pobrinite se da je sve još uvijek sastavlja.
Prestanite se, a sada idemo pokušati što binarnog stabla opet.
Pa, to izgleda kao da smo dobili pogrešku,
a mi smo dobili to izričito izjavljuje knjižnice funkciju printf.
To izgleda kao moramo otići i # include standardio.h.
A uz to, sve bi trebalo sastaviti. Mi smo svi dobro.
Sada ćemo pokušati trčanje binarnog stabla i vidjeti što se događa.
Ovdje smo,. / Binary_tree,
i vidimo da je, kao što smo i očekivali -
jer nismo proveli sadrži još,
odnosno, upravo smo stavili u zamjenu lažne -
vidimo da je to samo vraća false za sve njih,
tako da je sve radio za najveći dio prilično dobro.
>> Idemo natrag u, a zapravo provesti sadrži u ovom trenutku.
Idem za pomicanje prema dolje, zumiranje, i -
zapamtite, algoritam koji smo koristili bio je da smo krenuli na korijen čvor
i onda na svakom čvoru koji susrećemo, radimo usporedbu,
i na temelju te usporedbe mi ili premjestiti na lijevu dijete ili na pravo dijete.
To će izgledati vrlo slično kod binarnog pretraživanja koja smo pisali ranije u pojam.
Kada smo krenuti, znamo da želimo držati na trenutnom čvoru
da smo gleda, a trenutni čvor će biti inicijalizirane na korijenski čvor.
A sada, idemo da ide kroz stabla,
i zapamtite da je naš uvjet zaustavljanja -
kad smo zapravo radili kroz primjer rukom -
bio je kada smo naišli null čvor,
Ne kad smo gledali null djeteta,
nego kad smo zapravo preselili na čvoru u stablo
i pronašao da smo na null čvor.
Mi ćemo ponoviti do sad nije jednaka null.
I što ćemo učiniti?
Mi ćemo testirati ako (sad -> vrijednost == vrijednost),
onda znamo da smo zapravo našli čvor koji smo tražili.
Dakle, ovdje, možemo se vratiti istina.
Inače, želimo vidjeti hoće li ili ne je vrijednost manja od vrijednosti.
Ako je trenutni čvora vrijednost manja od vrijednosti tražimo,
idemo da se presele na desnoj strani.
Dakle, sad = sad -> right_child, i inače, idemo da se presele na lijevoj strani.
sad = sad -> left_child;. Prilično jednostavan.
>> Vi vjerojatno prepoznati petlju koja izgleda vrlo slično tome od
binarno pretraživanje ranije u roku, osim onda smo se bave niski, srednji i visoki.
Evo, samo moramo gledati na trenutnu vrijednost,
pa to je lijepo i jednostavno.
Ajmo pobrinite se to kod radi.
Prvo, pobrinite se da sastavlja. Izgleda kao da radi.
Pokušajmo ga izvodi.
I doista, to ispisuje sve što smo očekivali.
On pronalazi 6 u stablo, ne može pronaći 10 jer 10 nije u stablu,
i ne može pronaći jedan ili zbog jednog je također nije u stablu.
Cool stvari.
>> Dobro,. Vratimo se našoj specifikaciji i vidjeti što je sljedeće.
Sada, ona želi dodati neke više čvorova na našem stablu.
Ona želi dodati 5, 2 i 8, i pobrinite se da su naši sadrži kod
još uvijek radi kao što se očekuje.
Hajdemo to učiniti.
U ovom trenutku, umjesto da radi dosadne kopirati i zalijepiti opet,
ajmo napisati funkciju da zapravo stvoriti čvor.
Ako mi se pomaknite prema dolje sve do glavne, vidimo da smo radili ovaj
vrlo slična kod iznova i iznova svaki put da želimo stvoriti čvor.
>> Ajmo napisati funkciju koja će zapravo izgraditi čvor za nas i vratiti ga.
Ja ću ga nazvati build_node.
Ja ću izgraditi čvor s određenom vrijednosti.
Povećavanje ovdje.
Prva stvar ću učiniti zapravo stvoriti prostor za čvor na hrpi.
Dakle, čvor * n = malloc (sizeof (čvor)), n -> vrijednost = vrijednost;
i onda ovdje, ja samo idem za vraćanje svih polja biti odgovarajuće vrijednosti.
I na samom kraju, vratit ćemo našu čvor.
Dobro,. Jedna stvar je imati na umu da se ove funkcije ovdje
će se vratiti pokazivač na memoriju koja je bila gomila-izdvojila.
Što je lijepo o tome da je ovaj čvor sada -
moramo ga proglasiti na hrpi, jer ako smo ga proglasio na stog
ne bismo bili u mogućnosti to učiniti u ovoj funkciji kao što je ovaj.
To sjećanje bi otići iz djelokruga
i da će biti nevažeći ako smo pokušali pristupiti kasnije.
Budući da smo progla gomila-dodijeljenog memorije,
ćemo morati brinuti ga oslobađajući kasnije
za naš program ne propuštati bilo sjećanje.
Mi smo bili na punting da za sve ostalo u kodu
Upravo zbog jednostavnosti miloga na vrijeme,
ali ako ste ikada napisati funkciju koja izgleda ovako
gdje imaš - neki ga zovu malloc ili realloc iznutra -
Želite li biti sigurni da ste stavili nekakvu komentaru ovdje da kaže,
hej, znate, vraća gomila-dodijeljeno čvor pokrenutog s položen-u vrijednosti.
I onda želite da biste bili sigurni da ste stavili u nekakvu napomenu da kaže
pozivatelj mora osloboditi vratio pamćenje.
Na taj način, ako netko ikad ide i koristi tu funkciju,
oni znaju da ono što su dobili natrag iz tog funkcije
u nekom trenutku će morati biti oslobođen.
>> Uz pretpostavku da je sve dobro i dobro ovdje,
možemo ići dolje u našem kodu i zamijeniti sve te linije ovdje
s pozivima na naš graditi čvor funkciji.
Ajmo to jako brzo.
Onaj dio koji ne idemo zamijeniti je ovaj dio ovdje dolje
na dnu gdje smo zapravo žice do čvorova ukazati da jedni druge,
jer to ne možemo učiniti u našoj funkciji.
Ali, hajdemo to korijen = build_node (7); čvor * tri = build_node (3);
čvor * šest = build_node (6); čvor * devet = build_node (9);.
I sada, mi smo također željeli dodati čvorova za -
čvor * Pet = build_node (5); čvor * osam = build_node (8);
a što je bio drugi čvor? Hajdemo vidjeti ovdje. Željeli smo također dodati 2 -
čvor * DVIJE = build_node (2);.
Dobro,. U ovom trenutku, mi znamo da smo dobili 7, 3, 9, i 6
sve ožičen na odgovarajući način, ali ono što o 5, 8, te dva?
Da bi sve u odgovarajućem redoslijedu,
znamo da tri pravo dijete je šest.
Dakle, ako ćemo dodati 5,
je 5 također spada u desnoj strani stabla od kojih tri je korijen,
tako pet pripada kao lijevi dijete od 6 godina.
Možemo to učiniti govoreći, šest -> left_child = pet;
a zatim 8 pripada kao lijevi dijete od 9., tako devet -> left_child = osam;
i onda 2 je lijevo dijete od tri, tako da možemo učiniti da se ovdje - ti -> left_child = dva;.
Ako niste sasvim pratiti uz to, ja predlažem da ga izvući iz sebe.
>> Dobro,. Ajmo spasiti ovu. Idemo van i pobrinite se izrađuje,
i onda možemo dodati u našim sadrži pozive.
Izgleda kao da je sve još uvijek sastavlja.
Idemo u i dodati u nekim sadrži pozive.
Opet, ja ću učiniti malo kopirati i zalijepiti.
Sada ćemo potražiti 5, 8, i dva. Dobro,.
Ajmo pobrinite se da sve ovo izgleda dobro i dalje. Sjajno! Spremite i zatvorite.
Sada ćemo napraviti, sastaviti, a sada idemo pokrenuti.
Iz rezultata, to izgleda kao sve radi samo lijepo i dobro.
Sjajno! Tako sada imamo naše Sadrži funkcije napisano.
Idemo dalje i početi raditi na tome da ubacite čvorova u stablu
jer, kao što smo to radili upravo sada, stvari nisu jako lijepa.
>> Ako se vratimo na specifikaciji,
to od nas traži da napisati funkciju zove umetanje - opet, vraća bool
za li ili ne bismo mogli umetnuti čvor u stablu -
i onda je vrijednost za umetanje u stablo je naveden kao
jedini argument za našu insert funkciji.
Mi ćemo se vratiti true ako smo doista mogao umetnuti čvor koji sadrži vrijednost u stablu,
što znači da smo, jednom, imao dovoljno memorije,
i onda dva, da čvor nije već postoji u stablu od -
zapamtite, nećemo imati dvostruke vrijednosti u stablo, samo da bi se stvari jednostavno.
Dobro,. Povratak u kodu.
Otvorite ga prema gore. Zoom malo, zatim se pomaknite prema dolje.
Ajmo staviti umetak funkciju desno iznad sadrži.
Opet, to će biti pozvani bool umetak (int vrijednost).
Daj mu malo više prostora, a zatim, kao defaultu,
ajmo staviti u zamjenu lažnom na samom kraju.
Sada dolje na dnu, idemo naprijed i umjesto ručno izgradnju čvorova
u glavni sebe te ih ožičenje do točke da jedni druge kao što smo radili,
ćemo se osloniti na naše insert funkciju za to.
Nećemo se osloniti na naše insert funkciji izgraditi cijeli stablo od nule samo još,
nego ćemo dobiti osloboditi od tih linija - hrapavi komentirati iz ovih redaka -
da izgrade čvorove 5, 8, i dva.
A umjesto toga, mi ćemo ubaciti pozive na naše umetanje funkcije
kako bi bili sigurni da je to zapravo radi.
Ovdje ćemo ići.
>> Sada smo komentirali iz ove linije.
Mi imamo samo 7, 3, 9 i 6 u našem stablu u ovom trenutku.
Da biste bili sigurni da je to sve radi,
možemo smanjivanje, čine naš binarno stablo,
ga pokrenuti, a možemo vidjeti da sadrži sada nam govori da smo potpuno u pravu -
5, 8, te dva više nisu u stablo.
Idi natrag u kodu,
i kako ćemo umetnuti?
Sjetite se što smo učinili kada smo zapravo umetanjem 5, 8, i dva ranije.
Igrali smo tu Plinko igru ​​gdje smo počeli u korijenu,
siđe stabla jedan po jedan po jedan
dok smo pronašli odgovarajuću prazninu,
i onda smo poslali u čvor na odgovarajuće mjesto.
Mi ćemo učiniti istu stvar.
To je u osnovi kao pisanje koda koji smo koristili u sadrži funkciju
pronaći mjesto gdje je čvor bi trebao biti,
i onda smo tek idući umetnuti čvor tamo.
Počnimo da radi.
>> Dakle, imamo čvor * cur = korijen, a mi samo ćeš slijediti sadrži kod
dok smo da se to ne sasvim rade za nas.
Mi ćemo ići kroz stabla, dok je trenutni element nije nula,
i ako utvrdimo da cur je vrijednost jednaka vrijednosti koje smo pokušava ubaciti -
dobro, ovo je jedan od slučajeva u kojima smo zapravo ne može umetnuti čvor
u stablo, jer to znači da imamo duple vrijednosti.
Ovdje mi zapravo idemo vratiti false.
Sada, drugo, ako sad je vrijednost manja od vrijednosti,
Sada znamo da se presele u desno
jer je vrijednost pripada u desnoj polovici sadašnje stanje stabla.
Inače, mi smo idući u premjestiti na lijevoj strani.
To je u osnovi naše Sadrži funkcionirati tamo.
>> U ovom trenutku, nakon što smo završili ovaj while petlja,
naša sad pokazivač će se ukazuje na nulu
ako je funkcija još nije vratio.
Stoga nailazite cur na mjestu gdje želimo umetnuti novi čvor.
Što još treba učiniti je da zapravo izgraditi novi čvor,
što možemo učiniti prilično lako.
Možemo koristiti naše super-zgodan graditi funkciju čvora,
i nešto što nismo ranije -
samo mi nekako uzeo zdravo za gotovo, ali sada ćemo učiniti samo da bi bili sigurni -
ćemo testirati kako bi bili sigurni da je vrijednost koju vraća novi čvor je zapravo
nije null, jer ne želimo početi pristup da memoriju ako je null.
Možemo testirati kako bi bili sigurni da novi čvor nije jednaka null.
Ili umjesto toga, mi samo možemo vidjeti ako to je zapravo null,
i ako je nula, onda možemo samo povratak false rano.
>> U ovom trenutku, moramo spojiti novi čvor u svojoj odgovarajuće mjesto u stablo.
Ako se osvrnemo na glavna i gdje smo bili zapravo ožičenje u vrijednosti prije,
vidimo da je način na koji smo to čine kad smo htjeli staviti tri u stablo
bio mi pogledana lijevu dijete korijena.
Kad smo stavili 9 u stablo, morali smo pristupili pravo djeteta korijena.
Morali smo imati pokazivač na roditelja kako bi se stavili novu vrijednost u stablo.
Pomicanje natrag do umetnuti, da ne ide na prilično raditi ovdje
jer mi nemamo pokazivač roditelj.
Ono što mi želimo biti u mogućnosti to učiniti je, u ovom trenutku,
provjerite roditelja vrijednost i vidjeti - dobro, bože,
Ako roditelj je vrijednost manja od trenutne vrijednosti,
Tada je roditeljsko pravo dijete treba biti novi čvor;
inače, roditelj je lijevo dijete treba biti novi čvor.
Ali, mi nemamo taj pokazivač roditelj još.
>> Da bi ga dobili, mi zapravo idemo da su ga pratili kao što smo proći kroz stablo
i pronaći odgovarajući mjesto u našoj petlji iznad.
Mi možemo učiniti da do pomicanja natrag na vrh našeg umetanje funkcije
i praćenje drugog pokazivača varijablu naziva roditelja.
Mi ćemo ga postaviti jednaka null početku,
i onda svaki put kad smo proći kroz stabla,
idemo postaviti roditelj pokazivač odgovara trenutni pokazivač.
Postavite roditelj jednak valutama.
Na taj način, svaki put kad smo proći,
idemo kako bi se osiguralo da kao trenutni pokazivač gets incremented
roditelj pokazivač ga slijedi - samo jedan stupanj viša od trenutne pokazivačem u stablo.
To sve izgleda prilično dobro.
>> Mislim da je jedna stvar koju ćemo željeti prilagoditi je to izgraditi čvor vraća null.
Da bi dobili izgraditi čvor zapravo uspješno vratiti null,
ćemo morati mijenjati taj kod,
jer ovdje, mi nikada ne testira kako bi bili sigurni da malloc vratio valjanu pokazivač.
Dakle, ako je (n = NULL!), A zatim -
ako malloc vratio valjanu pokazivač, onda ćemo ga inicijalizirati;
inače, samo ćemo se vratiti i da će završiti vraća null za nas.
Sada sve izgleda prilično dobro. Ajmo pazite ovo zapravo sastavlja.
Napravite binarnog stabla, i oh, imamo neke stvari se ovdje događa.
>> Imamo implicitna deklaracija funkcije izgraditi čvor.
Opet, s tim prevodiocima, idemo početi na vrhu.
Što da mora značiti da sam pozivom izgraditi čvor prije nego što sam zapravo sam ga proglasio.
Vratimo se kod jako brzo.
Pomaknite se prema dolje, i siguran dosta, moj umetak funkcija je proglašen
iznad funkciju graditi čvor,
ali ja sam pokušava koristiti graditi čvor unutar umetka.
Ja idem u i primjerak - a zatim zalijepiti funkcije graditi čvor put ovdje na vrhu.
Na taj način, nadamo se da će raditi. Dajmo ovaj drugi ići.
Sada sve to sastavlja. Sve je dobro.
>> No, u ovom trenutku, nismo zapravo zove naš umetnuti funkciju.
Mi samo znamo da je to sastavlja, pa ajmo i staviti neke pozive u.
Učinimo da u našem glavnom funkciji.
Ovdje smo komentirali od 5, 8 i 2,
i onda smo ih nije spojiti se ovdje dolje.
Ajmo napraviti neki pozivi za umetanje,
i ajmo također koristiti istu vrstu stvari koje smo koristili
kad smo napravili ove printf pozive kako bi bili sigurni da je sve nije se pravilno umetnuta.
Ja ću kopirati i zalijepiti,
i umjesto sadrži ćemo učiniti umetak.
I umjesto 6, 10, i jedan, idemo koristiti 5, 8 i 2.
Ovaj nadamo trebao ubaciti 5, 8 i 2 u stablo.
Sastaviti. Sve je dobro. Sada smo zapravo ćete pokrenuti naš program.
>> Sve se vratio lažna.
Dakle, pet, osam, a dva ne ide, a izgleda da ne sadrži ni pronaći ih bilo.
Što se događa? Ajmo smanjivanje.
Prvi problem je da umetnite činilo da se vrati false,
i to izgleda kao da je to zato što smo otišli u našem povratku lažnog poziva,
a mi nikada zapravo vratio istina.
Možemo postaviti da gore.
Drugi problem je, sada čak i ako to učinimo - spasiti to, prestati to,
pokrenuti učiniti opet, to su sastaviti, a zatim ga pokrenuti -
vidimo da se nešto drugo dogodilo ovdje.
The 5, 8 i dvoje još nikada nisu pronađena u stablo.
Dakle, ono što se događa?
>> Ajmo pogledati ovo u kodu.
Hajdemo vidjeti možemo li to shvatiti.
Mi smo započeli s roditelj ne bude nula.
Postavili smo trenutni pokazivač jednak korijena pokazivač,
i idemo raditi svoj put prema dolje kroz stabla.
Ako je trenutni čvor nije null, onda znamo da možemo kretati prema dolje malo.
Postavili smo našu roditelj pokazivač biti jednaka trenutnoj pokazivač,
Provjerio vrijednost - ako su iste vrijednosti i vratili smo se lažna.
Ako su vrijednosti manje preselili smo se u pravo;
inače, preselili smo se na lijevoj strani.
Onda smo izgraditi čvor. Ja ću povećavanje malo.
I ovdje, mi ćemo pokušati spojiti do vrijednosti biti isti.
Što se događa? Idemo vidjeti ako eventualno Valgrind nam može dati savjet.
>> Volim koristiti Valgrind samo zato Valgrind stvarno brzo pokreće
i kaže vam, ako postoje bilo kakve memorije pogreške.
Kada smo pokrenuli Valgrind na kodu,
kao što možete vidjeti upravo hit here--Valgrind./binary_tree--and ući.
Možete vidjeti da nismo imali nikakve memorijsku pogrešku, tako da izgleda kao da je sve u redu do sada.
Imamo neke memory leaks, koje znamo, jer nismo
događa se osloboditi bilo koji od naših čvorova.
Pokušajmo trčanje gdb vidjeti što se zapravo događa.
Učinit ćemo gdb. / Binary_tree. To dignut gore sasvim u redu.
Ajmo postaviti break na umetkom.
Ajmo pokrenuti.
Izgleda mi nikada zapravo zove umetak.
Izgleda da je problem bio samo da kad sam promijenio ovdje dolje u glavni -
sve ove printf pozive iz sadrži -
Nikad nisam zapravo promijenio to nazvati umetak.
Sada ćemo dati ga probati. Ajmo sastaviti.
Sve izgleda dobro tamo. Sada ćemo pokušati trčanje, vidjeti što se događa.
Redu! Sve izgleda prilično dobro tamo.
>> Konačna stvar razmišljati o je, postoje li rub slučajeva na ovim umetkom?
I ispada da, dobro, jedan rub slučaj da je uvijek zanimljivo razmišljati o
je, što se događa ako vaš stablo je prazno i ​​to nazivamo umetnuti funkciju?
Hoće li raditi? Pa, neka je dati ga probati.
- Binary_tree c. -
Način da ćemo ovaj test je, idemo ići dolje na naš glavni funkciji,
i umjesto elektroinstalacija ove čvorova ovako,
samo mi ćemo komentirati van cijelu stvar,
i umjesto žica do čvorova i nas samih,
zapravo možemo samo ići naprijed i izbrisati sve ovo.
Mi ćemo učiniti sve što je poziv za umetanje.
Dakle, ajmo napraviti - umjesto 5, 8 i 2, idemo umetnuti 7, 3 i 9.
A onda ćemo također želite umetnuti 6 kao dobro.
Spremi. Prestani. Napravite binarnog stabla.
To sve sastavlja.
Mi samo možemo pokrenuti ga kao što je i vidjeti što se događa,
ali to je također će biti jako važno kako bi bili sigurni da
mi nemamo nikakve pogreške memorije,
jer je to jedan od naših rubnih slučajeva za koje znamo o tome.
>> Ajmo pobrinite se da dobro radi pod Valgrind,
što ćemo učiniti samo trčanje Valgrind. / binary_tree.
Čini se kao da smo doista imaju jednu pogrešku iz jednog konteksta -
imamo ovu segmentacije grešku.
Što se dogodilo?
Valgrind zapravo govori nam gdje je.
Udalji malo.
To izgleda kao da se događa u našem insert funkciji,
gdje smo nevažeći pročitati veličine 4 na umetkom, linija 60.
Ajmo se vratiti i vidjeti što se ovdje događa.
Udalji stvarno brzo.
Želim da biste bili sigurni da se ne ide do ruba zaslona tako da možemo vidjeti sve.
Povucite da u malo. Dobro,.
Pomaknite se prema dolje, a problem je upravo ovdje.
Što će se dogoditi ako smo dobili dolje i naš trenutni čvor je već null,
naš roditelj čvor null, pa ako ćemo gledati gore na samom vrhu, upravo ovdje -
ako je to while petlja nikad zapravo izvršava
jer je naša trenutna vrijednost je null - naš korijen null pa sad je null -
onda naš roditelj nikada ne dobiva postavljen na valutama ili s važećom vrijednosti,
tako, roditelj će također biti nula.
Trebamo se sjetiti da provjerite da
u vrijeme kada smo dobili ovdje dolje, i možemo početi pristup roditelja na vrijednosti.
Dakle, što se događa? Pa, ako roditelj null -
if (roditelj == NULL) - onda znamo da je
ne smije biti ništa u stablo.
Moramo biti težak da ga umetnuti u korijenu.
Mi možemo učiniti da samo postavljanje korijen jednak novog čvora.
Zatim u ovom trenutku, mi zapravo ne želite proći kroz tih drugih stvari.
Umjesto toga, ovdje, možemo napraviti bilo drugo-ako-drugo,
ili smo mogli kombinirati sve do ovdje u drugi,
ali ovdje ćemo samo koristiti drugi i učiniti ga na taj način.
Sada, idemo testirati kako bi bili sigurni da je naš roditelj nije null
prije toga zapravo pokušava pristupiti polja.
To će nam pomoći da se izbjegne segmentacije grešku.
Dakle, mi otkaz, smanjivanje, sastaviti, pokrenuti.
>> Nema pogreške, ali još uvijek imamo hrpu memorijskih curenja
jer mi nije bilo osloboditi od naših čvorova.
Ali, ako idemo do ovdje i gledamo naše ispisa,
vidimo da, dobro, izgleda kao i svi naši umetcima su se vraćali istina, što je dobro.
Pločice su sve istina,
, a zatim odgovarajući sadrži pozivi su također istina.
>> Dobar posao! Čini se kao da smo uspješno sam napisao umetak.
To je sve što imamo za ovotjednom specifikacija problema Set.
Jedan zabavan izazov da razmišljaju o tome kako bi zapravo ići u
i bez svih čvorova u ovom stablu.
Mi možemo učiniti tako veliki broj različitih načina,
ali ja ću ostaviti da do vas pokusa,
i kao zabava izazov, probajte i uvjerite se da možete biti sigurni
da je ovo izvješće Valgrind vraća bez greške i nema curenja.
>> Sretno na ovotjednom Huffman ovo kodiranje problema setu,
pa ćemo vidjeti sljedeći tjedan!
[CS50.TV]