[Powered by Google Translate] [Pjesa 7: më të rehatshme] [Rob Bowden] [Universiteti i Harvardit] [Kjo është CS50] [CS50.TV] Dakord. Pra, si unë, tha në email tim kjo do të jetë një binar-pemë-intensive seksion. Por nuk ka shumë pyetje që. Pra, ne jemi duke shkuar për të përpiqen dhe të tërheqë nga çdo pyetjeje dhe të shkojnë në detaje të dhimbshme të gjitha mënyrat më të mira për të bërë gjërat. Në mënyrë të drejtë në fillim, ne do të shkojmë përmes vizatimeve mostër e pemëve dhe sende binar. Kështu që këtu, "Mos harroni se një pemë binare ka nyje të ngjashme me ato të një liste të lidhura, përveç në vend të një akrep nuk janë dy: një për 'fëmijë' së majtës dhe një për "fëmijën" e djathtë ". Kështu që një pemë binare është vetëm si një listë e lidhur, përveç struct do të ketë dy pointers. Ka pemë trinary, të cilat do të ketë tre pointers, ka N-ARY pemë, të cilat vetëm kanë një tregues gjenerike që atëherë ju duhet të malloc të jetë mjaft e madhe që të ketë pointers të mjaftueshme për të gjithë fëmijët e mundshme. Pra, pemë binare vetëm ndodh që të ketë një numër të vazhdueshëm të dy. Në qoftë se ju dëshironi, ju mund të jepni një listë të lidhur si një pemë unary, por unë nuk mendoj se dikush e quan atë se. "Vizatoni një diagram kuti-dhe-shigjeta e një nyje pemë binare përmbajnë numrin e preferuar Nate-së, 7, ku çdo fëmijë është tregues null. " Mënyra kështu iPad. 

Ajo do të jetë shumë i thjeshtë. Ne jemi vetëm do të ketë një nyje, unë do të tërheqë atë si një shesh. Dhe unë do të të nxjerrë vlerat në këtu. Pra, vlera do të shkojnë në këtu, dhe pastaj këtu poshtë ne do të kemi në treguesin e majtë në të majtë dhe të djathtë kursorin në të djathtë. Dhe kjo është shumë e shumë në mënyrë konventë për të thirrur atë majtas dhe djathtas, emrat tregues. Të dyja këto do të jenë null. Kjo do të jetë vetëm null, dhe se do të jetë vetëm null. Rregull. Pra, përsëri në këtu. "Me një listë e lidhur, ne vetëm kishte për të ruajtur një akrep në nyjen e parë në listën në mënyrë që të mos harroni krejt Listen lidhur, ose listë e tërë. Gjithashtu, me pemë, ne kemi vetëm për të ruajtur një akrep në një nyje të vetme, në mënyrë për të kujtuar pemë të tërë. Kjo nyjë është calle 'root' nga pema. Të ndërtuar mbi diagramin tuaj para ose vizatoni një të re të tilla që ju keni një përshkrim kuti-dhe-shigjeta e një pemë binare me vlerën 7, pastaj 3 në të majtë, atëherë 9 në të drejtë, dhe pastaj 6 në të djathtë të 3. " Le të shohim nëse unë mund të kujtoj të gjithë se në kokën time. Pra, kjo do të jetë root tonë deri këtu. Ne do të kemi disa tregues diku, diçka që ne do të quajmë rrënjë, dhe kjo është treguar këtë djalë. Tani për të bërë një nyje të re, çfarë kemi, 3 në të majtë? Pra, një nyje e re me 3, dhe kjo fillimisht vë null. Unë vetëm do të vënë N. Tani ne duam të bëjë që të shkojnë në të majtë të 7. Pra, ne ndryshojmë këtë tregues më tani tregojnë për këtë djalë. Dhe ne bëjmë të njëjtën gjë. Ne duam një 9 mbi këtu e cila fillimisht vetëm thotë null. Ne jemi duke shkuar për të ndryshuar këtë pikë, akrep në 9, dhe tani ne duam të vënë 6 të drejtën e 3. Kështu ajo do të - të bëjë një 6. Dhe kjo do të tregojë djalë atje. Rregull. Pra, kjo është e gjitha që na kërkon të bëjmë. 

Tani le të shkojë mbi disa terminologji. Ne tashmë folur rreth asaj se si rrënja e pemës është top-më Nyja në pemë. Ai përmban 7. Nyjet në fund të pemës quhen gjethet. Çdo nyje e cila sapo ka null si fëmijët e tij është një fletë. Kështu që është e mundur, nëse pemë binare ynë është vetëm një nyjë të vetme, se një pemë është një fletë, dhe që është ajo. "The 'Lartësia' e pemës është numri i HOPS ju duhet të bëni të marrë nga lart në një fletë. " Ne do të merrni në, në një të dytë, dallimin mes pemëve të ekuilibruar dhe të paekuilibruar binare, por tani për tani, lartësia e përgjithshme e kësaj peme Unë do të thoja është 3, edhe pse në qoftë se ju të numëruar numrin e HOPS ju duhet të bëni në mënyrë që të merrni në 9, atëherë kjo është me të vërtetë vetëm një lartësi prej 2. Tani për tani kjo është një pemë binare paekuilibruar, por ne do të biseduar rreth ekuilibruar, kur ajo merr të jetë relevant. Deri tani ne mund të flasim për nyje në një pemë në aspektin në lidhje me nyjet e tjera në pemë. Deri tani ne kemi prindërit, fëmijët, vëllezërit e motrat, paraardhësit dhe pasardhësit. Ata janë goxha sens të përbashkët, atë që thotë. Nëse pyesim - prindërit është. Pra, çfarë është prind i 3? [Studentët] 7. Po >>. Prindi është vetëm do të jetë ajo që tregon ju. Atëherë çfarë janë bijtë e 7? [Studentët] 3 dhe 9. Po >>. Vini re se "fëmijët" fjalë për fjalë do të thotë fëmijë, kështu që nuk do të zbatohet 6, sepse ajo është si një mbesë. Por pastaj, nëse ne do të shkojmë pasardhës, kështu që çfarë janë pasardhësit e 7? [Studentët] 3, 6 dhe 9. Po >>. Pasardhësit e nyjeve rrënjë do të jetë gjithçka në pemë, me përjashtim të ndoshta nyja rrënjë në vetvete, në qoftë se ju nuk doni të marrin në konsideratë se një pasardhës. Dhe së fundi, paraardhësit, kështu që është drejtimi i kundërt. Pra, çfarë janë paraardhësit e 6? [Studentët] 3 dhe 7. Po >>. 9 A nuk është përfshirë. Kjo është vetëm pjesa e prapme e drejtpërdrejtë prejardhjen në rrënjë do të jetë etërit tuaj. 

"Ne themi se një pemë binare është" urdhëruar "në qoftë se për çdo nyje në pemë, të gjithë pasardhësit e saj në të majtë kanë vlera më të vogël dhe të gjitha ato në të djathtë kanë vlera të mëdha. Për shembull, pema më sipër është urdhëruar, por kjo nuk është e mundur vetëm marrëveshja urdhëruar. " Para se të marrim për këtë, një pemë e urdhëroi binar është i njohur edhe si një pemë binare e kërkimit. Këtu ne të ndodhë të jetë duke e quajtur atë një pemë binare urdhëruar, por unë kurrë nuk kam dëgjuar që ai e quajti një pemë binare urdhëruar më parë, dhe në një quiz ne jemi shumë më shumë gjasa për të vënë drurin binar të kërkimit. Ata janë një dhe të njëjtë, dhe kjo është e rëndësishme që ju njohin dallimin në mes të pemë binare dhe kërko binar pemë. Një pemë binare është vetëm një pemë që tregon dy gjëra. Çdo nyje tregon për dy gjëra. Nuk ka asnjë arsyetim për vlerat që ajo pikë për të. Pra, si gjatë këtu, pasi ajo është një pemë binare e kërkimit, ne e dimë se në qoftë se ne do të shkojmë majtë të 7, pastaj të gjitha vlerat që ne ndoshta mund të arrijnë duke shkuar la i 7 duhet të jetë më pak se 7. Vini re se të gjitha vlerat janë më pak se 7 3 dhe 6. Ata janë të gjithë të majtë të 7. Nëse ne do të shkojmë për të drejtën e 7, çdo gjë duhet të jetë më i madh se 7, kështu 9 është në të djathtë të 7, kështu që ne jemi të mirë. Ky nuk është rasti për një pemë binare, për një pemë binare të rregullt mund të ketë vetëm 3 në krye, 7 të majtë, 9 të majtë e 7, nuk ka urdhëruar të vlerave whatsoever. Tani, ne fakt nuk do ta bëjë këtë, sepse kjo është e lodhshme dhe të panevojshme, por "përpiqet të tërheqë sa më shumë pemë urdhëruar si ju mund të mendoni duke përdorur numrat 7, 3, 9, dhe 6. Sa shumë rregullime të dallueshme janë atje? Çfarë është lartësia e secilit? " 

Ne do të bëjmë një çift, por ideja kryesore është, kjo është në asnjë mënyrë një përfaqësim unik i një pemë binare që përmbajnë këto vlera. Gjithë ne kemi nevojë është një pemë binare që përmban 7, 3, 6, dhe 9. Një tjetër është e mundur të vlefshme do të jetë rrënja është 3, shkoni në të majtë dhe kjo është 6, shkoni në të majtë dhe kjo është 7, shkoni në të majtë dhe kjo është 9. Kjo është një mënyrë të përkryer e vlefshme kërkimit binar pemë. Kjo nuk është shumë e dobishme, sepse ajo është vetëm si një listë e lidhur dhe të gjitha këto pointers janë vetëm null. Por kjo është një pemë të vlefshme. Po? [Student] A nuk e vlerave duhet të jetë më e madhe në të djathtë? Apo është kjo -? Këto >> Unë do të thotë për të shkuar në mënyrë tjetër. Ka gjithashtu - po, le të kaloni këtë. 9, 7, 6, 3. Kapur mirë. Ajo ende duhet të binden se çfarë është një pemë binare kërkimi është menduar për të bërë. Pra, gjithçka në të majtë duhet të jetë më pak se çdo nyje të caktuar. Ne vetëm mund të lëvizin, të themi, këtë 6 dhe e vënë atë këtu. Jo, ne nuk mundemi. Pse unë mbaj duke bërë se? Le të bëjmë - këtu është 6, këtu është 7, 6 pikë në 3. Kjo është ende e vlefshme kërkimit binar pemë. Çfarë është e gabuar në qoftë se unë - le të shohim nëse unë mund të dalë me një marrëveshje. Po, në rregull. Pra, çfarë është e gabuar me këtë pemë? I guess Unë kam dhënë tashmë ju një aluzion se nuk është diçka e gabuar me të. Pse unë mbaj duke bërë se? Rregull. Kjo duket e arsyeshme. Nëse ne shikojmë në çdo nyje, si 7, pastaj në të majtë të 7 është një 3. Pra, ne kemi 3, gjë për të drejtën e 3 është një 6. Dhe në qoftë se ju shikoni në 6, gjë për të drejtën e 6 është një 9. Pra, pse nuk është kjo një kërkim të vlefshme binar pemë? [Studentët] 9 është ende në të majtë të 7. Po >>. Ajo duhet të jetë e vërtetë që të gjitha vlerat që ju ndoshta mund të arrijnë duke shkuar në të majtë të 7 janë më pak se 7. Nëse ne do të shkojmë majtë të 7, ne kemi marrë për 3 dhe ne ende mund të merrni në 6, ne ende mund të merrni në 9, por duke shkuar më pak se 7, ne nuk duhet të jetë në gjendje për të marrë një numër që është më i madh se 7. Pra, kjo nuk është e vlefshme kërkimit binar pemë. 

Vëllai im kishte në fakt një pyetje intervistë që ishte në thelb kjo, vetëm kodi deri diçka për të vërtetuar nëse një pemë është një pemë binare e kërkimit, dhe kështu gjëja e parë që ai bëri ishte vetëm kontrolloni për të parë qoftë të majtë dhe të djathtë janë të sakta, dhe pastaj iterate atje. Por ju nuk mund ta bëni vetëm se, ju duhet të mbajnë gjurmët për faktin se tani që unë kam shkuar lënë nga 7, gjithçka në këtë subtree duhet të jetë më pak se 7. Algorithm correct ka nevojë për të mbajtur nën prej caqeve që vlerat ndoshta mund të bien in Ne nuk do të kalojnë nëpër të gjitha prej tyre. Ekziston një lidhje e bukur përsëritje, edhe pse ne nuk kemi marrë për ata, ose ne nuk do të marrë për ata, përcaktimin se sa ka në të vërtetë janë. Kështu që nuk janë 14 prej tyre. Ideja se si ju do të bëni atë matematikisht është si, ju mund të vini çdo një të vetme që të jetë nyja rrënjë, dhe pastaj në qoftë se unë marr 7 të jetë nyja rrënjë, atëherë ka, të themi, disa numra që mund të shkojnë të jetë nyje ime e majtë, dhe ka disa numra që mund të jetë nyje ime e djathtë, por në qoftë se unë kam n numra gjithsej, atëherë shuma që mund të shkojnë në të majtë plus shuma që mund të shkojnë në të djathtë është n - 1. Pra, nga numrat e mbetura, ata duhet të jenë në gjendje të shkojnë as në të majtë apo të djathtë. Duket e vështirë që, në qoftë se kam vënë 3 pari atëherë gjithçka ka për të shkuar në të majtë, por në qoftë se kam vënë 7, atëherë disa gjëra mund të shkoni majtas dhe disa gjëra mund të shkojnë në të djathtë. Dhe nga '3 'e parë që unë do të thotë çdo gjë mund të shkoni në të djathtë. Është me të vërtetë, ju vetëm duhet të mendojnë për atë si, sa gjërat mund të shkojnë në nivelin e ardhshëm të pemës. Dhe kjo vjen nga që të jetë 14 ose ju mund të tërheqë të gjithë ata, dhe pastaj ju do të merrni 14. 

Going back këtu, "Urdhërohet pemë binare janë të ftohtë, sepse ne mund të kërkoni nëpër to në një mënyrë shumë të ngjashme me kërkim për një grup të renditura. Për ta bërë këtë, ne të fillojë në rrënjë dhe të punojnë rrugën tonë poshtë pemës drejt gjetheve, duke kontrolluar çdo nyje vlerat e kundër vlerave ne jemi në kërkim për të. Nëse vlera nyjen aktual është më pak se vlera ne jemi duke kërkuar për të, ju shkoni pranë fëmijës së djathtë nyjen së. Përndryshe, ju shkoni me fëmijën e majtë nyjen së. Në disa pika, ju do të gjeni vlerën ose ju jeni duke kërkuar për të, ose ju do të kandidojë në një null, treguar vlerën nuk është në pemë. " Unë kam për rishikimin pemë që kishim para, që do të marrë një të dytë. Por ne duam të shohim nëse deri 6, 10, dhe 1 janë në pemë. Pra, çfarë ishte, 7, 9, 3, 6. Rregull. Numrat që ju doni të kërkoni, ne duam të shohim deri 6. Si e bën këtë punë algorithm? E pra, ne gjithashtu kemi disa tregues rrënjë në pemë tonë. Dhe ne do të shkojë në rrënjë dhe të thonë, është kjo vlerë e barabartë me vlerën e ne jemi në kërkim për? Pra, ne jemi duke kërkuar për 6, kështu që nuk është e barabartë. Pra, ne do të mbajë, dhe tani të themi, në rregull, kështu që është më pak se 6 7. A do të thotë që ne duam të shkojnë në të majtë, ose nuk duam për të shkuar në të djathtë? [Student] Left. Po >>. Kjo është në mënyrë të konsiderueshme më e lehtë, të gjithë ju duhet të bëni është të nxjerrë një nyje e mundshme të pemës dhe pastaj ju don 't - në vend që të përpiqen për të menduar në kokën tuaj, rregull, në qoftë se është pak, nuk kam vajtur majtas ose shkoni të drejtë, vetëm duke kërkuar në këtë foto, ajo është shumë e qartë që unë kam për të shkuar në të majtë nëse kjo nyje është më e madhe se vlera që unë jam duke kërkuar për të. Pra, ju shkoni në të majtë, tani unë jam në 3. Unë dua të - 3 është më pak se vlera që unë jam duke kërkuar për të, e cila është 6. Pra, ne do të shkojmë në të djathtë, dhe tani unë përfundojë deri në 6, cila është vlera që unë jam duke kërkuar për të, kështu që unë të kthehen vërtetë. Vlera tjetër unë jam duke shkuar për të kërkuar është 10. Rregull. Pra 10, tani, do të - të prerë që - do të ndjekë rrënjë. Tani, 10 do të jetë më i madh se 7, kështu që unë dua të shikojnë në të djathtë. Unë jam duke shkuar për të ardhur këtu, 10 do të jetë më i madh se 9, kështu që unë jam duke shkuar për të dëshironi të shikoni në të djathtë. Kam ardhur gjatë këtu, por mbi këtu tani unë jam në null. Çfarë të bëj në qoftë se unë goditi null? [Student] Kthehu rreme? Po >>. Unë nuk e kam gjetur 10. 1 do të jetë një rast pothuajse identike, përveç se është vetëm do të jetë kthyer, në vend që të kërkoni poshtë në anën e djathtë, unë jam duke shkuar për të kërkuar poshtë në anën e majtë. 

Tani unë mendoj se ne në të vërtetë të merrni për kodin. Ja ku - hapur pajisjen CS50 dhe të lundruar në rrugën tuaj atje, por ju mund vetëm të bëjë atë në hapësirë. Kjo është ndoshta ideal për të bërë atë në hapësirë, sepse ne mund të punojnë në hapësirë. "Së pari ne do të duhet një përkufizim të ri për një lloj nyje pemë binare që përmbajnë vlera Int. Përdorimi i Boilerplate typedef më poshtë, të krijojë një përkufizim të ri për një lloj nyje në një pemë binare. Në qoftë se ju merrni mbërthyer. . . "Blah, blah, blah. Mirë. Pra, le të vënë Boilerplate këtu, nyje typedef struct, dhe nyja. Po, në rregull. Pra, cilat janë fushat që ne jemi duke shkuar për të duan në nyje tonë? [Student] Int dhe pastaj dy pointers? Int >> vlerë, dy pointers? Si mund të shkruaj pointers? [Student] struct. Unë duhet të zoom >> in Yeah, kështu që struct nyje * la, dhe struct * nyja e drejtë. Dhe mbani mend diskutimin nga koha e kaluar, se kjo nuk ka kuptim, kjo nuk ka kuptim, kjo nuk ka kuptim. Ju duhet çdo gjë atje në mënyrë që të përcaktojë këtë struct rekursive. Mirë, kështu që kjo është ajo që pema jonë do të duken si. Nëse ne e bëmë një pemë trinary, atëherë një nyje mund të duket si, B2 B1, struct * nyja B3, ku b është një degë - në fakt, unë kam dëgjuar shumë majtas, mesme, të drejtë, çfarëdo, por. Ne vetëm kujdesen për binar, në mënyrë të drejtë, të majtë. "Tani deklarojë një ndryshore globale * nyje për rrënjët e pemës." Pra, ne nuk jemi duke shkuar për të bërë këtë. Në mënyrë për t'i bërë gjërat pak më e vështirë dhe më të përgjithësuar, ne nuk do të kemi një ndryshore globale nyje. Në vend të kësaj, në kryesore ne do të deklarojë të gjitha gjërat tona nyjen, dhe kjo do të thotë se më poshtë, kur ne të fillojnë running Funksioni përmban tonë dhe funksioni ynë insert, vend i përmban tona funksionojnë vetëm duke përdorur këtë ndryshore globale nyje, ne do të duhet të marrë si argument pemë që ne duam që ajo të procesit. Duke ndryshore globale ishte menduar për të bërë gjërat më të lehtë. Ne jemi duke shkuar për të bërë gjëra të vështirë. Tani të marrë një minutë apo më shumë vetëm për të bërë këtë gjë e tillë, ku brenda kryesore që ju doni të krijuar këtë pemë, dhe kjo është e gjitha që ju doni të bëni. Provo dhe të ndërtuar këtë pemë në funksion tuaj kryesor. 

Rregull. Pra, ju nuk keni për të kanë ndërtuar rrugën e pemës gjithë ende. Por dikush ka diçka që unë mund të tërheqë deri për të treguar se si dikush mund të fillojë ndërtimin e një pemë të tillë? [Student] banging dikujt, duke u përpjekur për të marrë jashtë. [Bowden] Çdokush rehat me ndërtimin e tyre pemë? [Student] Sure. Kjo nuk është bërë. Kjo >> është në rregull. Ne vetëm mund të përfundojë - oh, ju mund ta ruani atë? Hooray. Pra, këtu kemi - oh, unë jam pak të prerë. Jam unë zoomed në? Zoom në, shkoni jashtë. >> Unë kam një pyetje. Po >>? [Student] Kur ju të përcaktojë strukturën, janë gjëra të tilla si initialized për asgjë? [Bowden] nr >> Okay. Pra, ju do të duhet të nisja - [Bowden] nr Kur ju të përcaktuar, ose kur ju të deklarojë një struct, ajo nuk është initialized nga default, ajo është vetëm si në qoftë se ju të deklarojë një int. Kjo është saktësisht e njëjta gjë. Është si çdo fushat e saj individuale mund të ketë një vlerë plehrash në të. Dhe >> është e mundur për të përcaktuar - ose të shpallë një struct në një mënyrë që ajo bën nisja e tyre? [Bowden] Po. Pra, initialization shkurtore sintaksa do të duken si - Ka dy mënyra që ne mund të bëjmë këtë. Unë mendoj se ne duhet të hartojnë atë të bëjë tingëllimë siguruar gjithashtu e bën këtë. Urdhri i argumenteve që vjen në struct, ju vënë si qëllim të argumenteve brenda këtyre formatimin e teksteve kaçurrel. Pra, nëse ju doni të nisja atë të 9 dhe e la të pavlefshme dhe pastaj të drejtë të jetë i pavlefshëm, ajo do të jetë 9, null, null. Alternativë është, dhe redaktor nuk ka si këtë sintaksë, dhe ajo mendon se unë dua një bllok të ri, por tjetër është diçka si - këtu, unë do të vënë atë në një linjë të re. Ju mund të thoni në mënyrë eksplicite, unë harroj sintaksë të saktë. Kështu që ju mund të në mënyrë eksplicite adresuar ato me emër, dhe thonë, . C, ose. Vlera = 9,. Majtas NULL =. Unë jam guessing këto duhet të presje. . Drejtë = NULL, kështu që në këtë mënyrë ju nuk e bëni në të vërtetë duhet të dini rendin e struct, dhe kur ju jeni duke e lexuar këtë, kjo është shumë më e qartë se çfarë vlera duke u nisur për të. 

Kjo ndodh të jetë një nga gjërat që - kështu, për pjesën më të madhe, C + + është një superset e C. Ju mund të merrni kodin C, lëvizin atë mbi të C + +, dhe ajo duhet të hartojnë. Kjo është një nga gjërat që C + + nuk e mbështesin, kështu që njerëzit nuk kanë tendencë për të bërë atë. Unë nuk e di nëse kjo është e vetmja arsye pse njerëzit nuk priren për të bërë atë, por rasti kur unë e nevojshme për të përdorur atë nevojshme për të punuar me C + + dhe kështu që unë nuk mund të përdorë këtë. Një tjetër shembull i diçkaje që nuk punojnë me C + + është si malloc kthen "* void," teknikisht, por ju mund vetëm të them char * = x çfarëdo malloc, dhe kjo automatikisht do të hidhet në një char *. Kjo cast automatike nuk ndodh në C + +. Kjo nuk do të përpilojnë, dhe ju do të duhet të them në mënyrë eksplicite * char, malloc, çfarëdo, për të hedhur atë në një char *. Nuk ka shumë gjëra që C dhe C + + nuk bien dakord mbi, por ato janë dy. Pra, ne do të shkojmë me këtë sintaksë. Por edhe në qoftë se ne nuk shkoni me atë sintaksës, çfarë është - mund të jetë i gabuar me këtë? [Student] Unë nuk duhet të dereference atë? Po >>. Mos harroni se ka një shigjetë dereference nënkuptuar, dhe kështu kur ne jemi vetëm që kanë të bëjnë me një struct, ne duam t'u përdorur. për të marrë në një fushë brenda të struct. Dhe e vetmja kohë që ne përdorim shigjetë është kur ne duam të bëjmë - mirë, është e barabartë me shigjetë - kjo është ajo që do të thotë në qoftë se kam përdorur arrow. Të gjitha mjetet shigjetë është, dereference këtë, tani unë jam në një struct, dhe unë mund të merrni këtë fushë. Ose të merrni në fushën e drejtpërdrejtë ose dereference dhe për të marrë fushë - Unë mendoj se kjo duhet të jetë vlerë. Por këtu unë jam që kanë të bëjnë me vetëm një struct jo, një tregues për një struct, dhe kështu që unë nuk mund të përdorin arrow. Por ky lloj i gjë që mund të bëjmë për të gjitha nyjet. Oh Perëndia im. Kjo është 6, 7, dhe 3. Atëherë ne mund të ngritur degë në pemë tonë, ne mund të kemi 7 - ne mund të kemi, majtas e tij duhet të theksojnë 3. Pra, si mund ta bëjmë këtë? [Studentët, pakuptueshëm] >> yeah. Adresa e node3, dhe në qoftë se ju nuk keni adresë, atëherë ai thjesht nuk do të përpilojnë. Por mos harroni se këto janë pointers në nyjet e ardhshme. E drejta duhet pikë në 9, dhe 3 duhet pikë për të drejtën e 6. Unë mendoj se kjo është e gjitha vendosur. Çdo komente ose pyetje? [Student, pakuptueshëm] Rrënja do të jetë 7. Ne mund të them vetëm nyjen * ptr = ose, rrënjë = & node7. 

Për qëllimet tona, ne jemi duke shkuar për të merret me insert, kështu që ne jemi duke shkuar për të duan të shkruajnë një funksion për të futur në këtë pemë binare dhe është futur në mënyrë të pashmangshme do të thërrasë malloc për të krijuar një nyje të re për këtë pemë. Pra, gjërat janë duke shkuar për të marrë çrregullt me ​​faktin se disa nyje janë aktualisht në rafte dhe nyjet e tjera do të përfundojnë deri në tog kur ne futur ato. Kjo është krejtësisht e vlefshme, por arsyeja e vetme ne jemi në gjendje për ta bërë këtë në rafte është për shkak se ajo është e tillë një shembull i ndërtuar që ne e dimë pema është menduar për të ndërtuar si 7, 3, 6, 9. Nëse ne nuk e kemi këtë, atëherë ne nuk do të duhet të malloc në vendin e parë. Siç do të shohim pak më vonë, ne duhet të malloc'ing. Tani për tani kjo është krejtësisht e arsyeshme për të vënë në rafte, por le të ndryshojë këtë në një zbatim malloc. Pra, secili prej tyre është tani do të jetë diçka si nyja * node9 = malloc (sizeof (nyje)). Dhe tani ne do të duhet të bëjë kontroll tonë. në qoftë se (== NULL node9) - Unë nuk dua se - 1 kthehen, dhe pastaj ne mund të bëjmë node9-> sepse tani kjo është një akrep, vlera = 6, node9-> la = NULL, node9-> djathtë = NULL, dhe ne do të duhet të bëjë se për secilin nga këto nyje. Pra, në vend, le të vënë atë në brendësi të një funksion të veçantë. Le të thërrasë atë nyje * build_node, dhe kjo është disi e ngjashme me TV ne ofrojmë për Huffman coding. Ne ju japim funksionet initializer për një pemë dhe deconstructor "funksione" për ato pemë dhe të njëjtat për pyjet. 

Pra, këtu ne do të ketë një funksion initializer të vetëm të ndërtuar një nyje për ne. Dhe kjo do të duket shumë e shumë tamam si kjo. Dhe unë jam edhe do të jetë dembel dhe jo të ndryshojë emrin e ndryshueshme, edhe pse node9 nuk ka kuptim më. Oh, unë mendoj se vlera node9 duhet të nuk kanë qenë 6. Tani ne mund të kthehen node9. Dhe këtu ne duhet të kthehen null. Gjithkush bien dakord mbi atë funksion ndërtuar-a-nyjeve? Deri tani ne vetëm mund të telefononi që të ndërtojë çdo nyje me një vlerë të caktuar dhe pointers null. Tani ne mund të quajmë këtë, ne mund të bëjmë nyje * node9 = build_node (9). Dhe le ta bëjmë. . . 6, 3, 7, 6, 3, 7. Dhe tani ne duam të ngritur pointers të njëjta, përveç tani gjithçka është tashmë në drejtim të pointers kështu që nuk ka më nevojë për adresën e. Rregull. Pra, çfarë është gjëja e fundit që unë dua të bëj? Ka një gabim-checking se unë nuk jam duke bërë. Çfarë ka të ndërtuar kthimin nyje? [Student, pakuptueshëm] >> Yeah. Nëse malloc dështuar, ajo do të kthehet null. Kështu që unë jam duke shkuar për ta vënë atë poshtë lazily këtu në vend për të bërë një kusht për secilin. Në qoftë se (== NULL node9, ose - edhe më të thjeshta, kjo është e barabartë me vetëm nëse nuk node9. Pra, nëse nuk node9, apo jo node6, apo jo node3, apo jo node7, kthehen 1. Ndoshta ne duhet të shtypura malloc dështuar, apo diçka. [Student] A është i barabartë me të rreme null si? [Bowden] Çdo vlerë zero është e rreme. Pra, null është një vlerë zero. Zero është një vlerë zero. False është një vlerë zero. Çdo - pretty much të vetmet 2 Vlerat janë zero dhe zero null, rreme hash është vetëm definohet si zero. Kjo vlen edhe në qoftë se ne nuk deklarojnë ndryshore globale. Nëse ne nuk kemi rrënjë * nyje deri këtu, pastaj - Gjë e bukur për variabla globale është se ata gjithmonë kanë një vlerë fillestare. Kjo nuk është e vërtetë e funksioneve, si brenda këtu, nëse kemi, si, * nyja ose x nyjë. Ne nuk kemi asnjë ide se çfarë x.value, x.whatever, ose ne mund të shtypura dhe ato mund të jetë arbitrare. Kjo nuk është e vërtetë e variablave globale. Pra, rrënja nyje apo x nyjë. By default, çdo gjë që është globale, nëse nuk initialized në mënyrë eksplicite për disa vlera, ka një vlerë zero si vlerën e tij. Kështu që këtu, rrënjë nyje *, ne nuk eksplicite nisja atë për asgjë, kështu që vlera e saj do të jetë i paracaktuar null, që është vlera zero e pointers. Vlera e paracaktuar e x do të thotë se x.value është zero, x.left është i pavlefshëm, dhe x.right është i pavlefshëm. Kështu që kjo është një struct, të gjitha fushat e struct do të jetë zero vlera. Ne nuk duhet të përdorin atë këtu, pse. [Student] Të structs janë të ndryshme se sa variablave të tjerë, dhe variablave të tjera janë Vlerat e plehrave, këto janë zero? [Bowden] vlerat tjera. Pra, në x, x do të jetë zero. Nëse kjo është në qëllimin global, ajo ka një vlerë fillestare. Mirë >>. [Bowden] Ose vlera fillestare që ju dha atë ose zero. Unë mendoj se kujdeset për të gjithë këtë. 

Rregull. Kështu pjesa tjetër e pyetjes pyet, "Tani ne duam të shkruani një funksion të quajtur përmban me një prototip të bool përmban vlerën int. " Ne nuk do të bëjë bool përmban vlerën int. Prototip ynë do të duken si bool përmban (vlera int. Dhe pastaj ne jemi gjithashtu do të kalojë atë pemë se duhet të kontrolluar për të parë nëse ajo ka atë vlerë. Pra nyje * pemë). Rregull. Dhe atëherë ne mund ta quajmë atë me diçka si, ndoshta ne do të duan të printf apo diçka. Përmban 6, rrënjë tonë. Kjo duhet të kthehet, ose një e vërtetë, ndërsa përmban 5 rrënja duhet të kthehen rreme. Pra, të marrë një të dytë për të zbatuar këtë. Ju mund ta bëni atë ose iteratively ose Recursively. Gjë e bukur për mënyrën se si ne kemi vendosur gjërat është se ajo jep veten për zgjidhjen tonë shumë më të lehtë rekursive se globale ndryshueshme rruga e bëri. Sepse në qoftë se ne vetëm kemi përmban vlera int, atëherë ne kemi asnjë mënyrë për të recursing poshtë tregoje. Ne do të duhet të ketë një funksion të veçantë ndihmëtar që recurses poshtë tregoje për ne. Por, pasi që ne kemi ndryshuar atë për të marrë pemë si argument, të cilat ajo duhet të ketë qenë gjithmonë në vendin e parë, tani ne mund të recurse më lehtë. Pra, përsëritës apo gjithkund rekursive, ne do të shkojnë mbi të dyja, por ne do të shohim që përfundon gjithkund rekursive duke qenë mjaft e lehtë. Rregull. Ka njeri të ketë diçka që ne mund të punojnë me të? 

[Student] Unë kam marrë një përsëritës zgjidhje. >> All right, përsëritës. Mirë, kjo duket e mirë. Pra, duan të ecin nëpër atë na? [Student] Sure. Kështu që unë vendosur një ndryshore temp të marrë nyja e parë e pemës. Dhe pastaj unë vetëm looped nëpërmjet temp, ndërsa nuk ka null barabartë, kështu ndërsa ishte ende në pemë, I guess. Dhe në qoftë se vlera është e barabartë me vlerën që temp është treguar, atëherë ajo kthehet atë vlerë. Përndryshe, ai kontrollon nëse është në anën e djathtë apo të majtë. Nëse ndonjëherë ju merrni një situatë ku nuk ka pemë më shumë, atëherë ajo kthehet - ajo daljet lak dhe kthen rreme. [Bowden] Okay. Kështu që duket e mirë. Çdokush keni ndonjë koment për asgjë? Unë nuk kam asnjë komentet e saktësisë në të gjitha. Një gjë që mund të bëjmë është ky djalë. Oh, ajo do të shkojë një longish pak. Unë do të rregullojmë se deri. Rregull. 

Gjithkush duhet të mbani mend se si punon tresh. Ka qenë definitivisht kuize në të kaluarën që të ju jap një funksion me një operator tresh, dhe thonë, kjo përkthehet, të bëjë diçka që nuk e përdor tresh. Pra, ky është një rast shumë të zakonshme të kur unë do të mendoj për të përdorur tresh, ku nëse disa kusht të vendosur një ndryshore për diçka, përcaktuar tjetër që ndryshore të njëjtë për diçka tjetër. Kjo është diçka që shumë shpesh mund të shndërrohet në këtë lloj gjë ku të vendosur se ndryshore për këtë - ose, edhe, është kjo e vërtetë? Atëherë kjo, tjetër këtë. [Student] E para është nëse vërtetë, apo jo? [Bowden] Yeah. Mënyrën se si unë gjithmonë lexuar atë është, temp e barabartë me vlerë më të madhe se vlera e temp, atëherë kjo, tjetër këtë. Është pyetur një pyetje. Është ajo e madhe? Pastaj të bëjë gjënë e parë. Tjetër të bërë gjënë e dytë. Unë pothuajse gjithmonë - dy pika, unë vetëm - në kokën time, kam lexuar si tjetër. 

A ka dikush të ketë një zgjidhje rekursive? Rregull. Ky i fundit ne jemi duke shkuar për të - ajo tashmë mund të jetë i madh, por ne jemi duke shkuar për ta bërë atë edhe më të mirë. Kjo është shumë e shumë të njëjtën ide e saktë. Është vetëm, mirë, nuk ju duan të shpjegojë? [Student] Sure. Pra, ne jemi duke e bërë të sigurtë që pema nuk është i pavlefshëm parë, sepse nëse pema është i pavlefshëm, atëherë ajo do të kthehet të rreme, sepse ne nuk kemi gjetur atë. Dhe në qoftë se nuk ka ende një pemë, ne do të shkojmë në - së pari kontrolloni nëse vlera është nyja aktuale. Kthehu në qoftë se është e vërtetë, dhe në qoftë se ne nuk recurse në të majtë apo të djathtë. Bën që të shëndosha të përshtatshme? >> Mm-hmm. (Marrëveshja) Pra, vini re se kjo është gati - strukturalisht shumë të ngjashme me zgjidhjen përsëritës. Është vetëm se në vend të recursing, kemi pasur një lak kohë. Dhe rasti baza këtu, ku pema nuk null barabartë ishte kushti nën të cilin u ndamë nga lak, ndërsa. Ata janë shumë të ngjashme. Por ne jemi duke shkuar për të marrë këtë hap më tej. Tani, ne bëjmë të njëjtën gjë këtu. Njoftim ne jemi kthyer të njëjtën gjë në të dyja këto linja, me përjashtim të një argumenti është i ndryshëm. Pra, ne jemi duke shkuar për të bërë që në një tresh. I goditi diçka opsion, dhe ajo bëri një simbol. Rregull. Pra, ne jemi duke shkuar për t'u kthyer që përmban. Kjo po bëhet që të jetë linja të shumta, mirë, kjo është zoomed në. Zakonisht, si një gjë e stilistike, unë nuk mendoj se shumë njerëz vënë një hapësirë ​​pas shigjetë, por unë mendoj nëse jeni të qëndrueshëm, kjo është në rregull. Nëse vlera është më e vogël se vlera e pemës, ne duam të recurse pemë në të majtë, tjetër ne duam të recurse në të drejtën e pemë. Kështu që ishte një hap për të bërë këtë vështrim të vogla. Hapi dy për të bërë këtë vështrim të vogla - Ne mund t'i ndajmë këtë për linja të shumta. Rregull. Hapi dy për të bërë atë të duket e vogël është këtu, Pra, vlera e kthimit barabartë vlerën pemë, ose përmban çfarëdo. 

Kjo është një gjë e rëndësishme. Unë nuk jam i sigurt nëse ai tha se në mënyrë eksplicite në klasë, por ai që quhet qark i shkurtër vlerësimit. Ideja këtu është vlera == vlera pemë. Nëse kjo është e vërtetë, atëherë kjo është e vërtetë, dhe ne duam të 'ose' se me çdo gjë që është e gjatë këtu. Pra edhe pa menduar për çdo gjë që është e gjatë këtu, çfarë është shprehja gjithë do të ktheheni? [Student] Vërtetë? Po >>, sepse vërtetë e çdo gjë, or'd - or'd apo e vërtetë me çdo gjë është domosdoshmërisht e vërtetë. Pra, sa më shpejt që ne e shohim vlerën e kthimit = vlerës pemë, ne jemi vetëm do të kthehen vërtetë. Jo edhe më tej do të recurse përmban poshtë vijës. Ne mund të marrë këtë hap më tej. Pema kthimi nuk pavlefshëm të barabartë dhe të gjithë këtë. Kjo e bëri atë një funksion-line. Kjo është gjithashtu një shembull i shkurtër qark vlerësimit. Por tani kjo është ide e njëjtë - në vend të - kështu që nëse pema nuk null barabartë - ose, edhe, në qoftë se pema e bën null barabartë, që është rasti e keqe, nëse pema është e barabartë null, atëherë kushti i parë do të jetë e rreme. Pra rreme anded me ndonjë gjë do të jetë ajo? [Student] False. Po >>. Kjo është gjysma tjetër e qark i shkurtër vlerësimit, ku në qoftë se pema nuk null jo të barabartë, atëherë ne nuk do të shkojnë edhe - ose në qoftë se pema e bën null barabartë, atëherë ne nuk do të bëjmë vlerën == vlerë pemë. Ne jemi vetëm do të kthehen menjëherë rreme. E cila është e rëndësishme, pasi në qoftë se ajo nuk shkurtër qark të vlerësuar, atëherë në qoftë se pema e bën null barabartë, ky kusht i dytë do të defektit Seg, sepse pema-> vlera null dereferencing. Pra, kjo është se. Mund të bëjë këtë - zhvendoset herë gjatë. Kjo është një gjë shumë e zakonshme gjithashtu, nuk e bërë këtë një linjë me këtë, por kjo është një gjë e zakonshme në kushtet e, ndoshta jo të drejtë këtu, por në qoftë se (! pemë = NULL, dhe pemë-> vlera == vlera), të bëjë çdo gjë. Ky është një kusht shumë i zakonshëm, ku në vend të për të thyer këtë në dy VJ, ku si, është null pema? Mirë, nuk është i pavlefshëm, kështu që tani është vlera pema e barabartë me vlerën e? Bëni këtë. Në vend të kësaj, ky kusht, kjo kurrë nuk do të seg faj sepse ajo do të shpërthejë nëse kjo ndodh të jetë null. Well, I guess nëse pema juaj është një tregues tërësisht i pavlefshëm, ajo ende mund të seg faj, por ajo nuk mund seg faj nëse pema është i pavlefshëm. Nëse do të ishte null, ajo do të shpërthejë para se dereferenced ndonjëherë treguesin në vendin e parë. [Student] A është ky vlerësim i quajtur dembel? 

[Bowden] vlerësimi Lazy është një gjë e veçantë. Vlerësimi Lazy është më shumë si ju kërkoni për një vlerë, ju kërkoni për të llogaritur një vlerë, lloj, por ju nuk keni nevojë atë menjëherë. Pra, deri sa ju të vërtetë nevojë për të, ajo nuk është vlerësuar. Kjo nuk është saktësisht e njëjta gjë, por në pset Huffman, ai thotë se ne "lazily" shkruajnë. Arsyeja që ne të bërë këtë është për shkak se ne jemi në fakt buffering e shkrimit - ne nuk duam të shkruani bit individuale në një kohë, ose bytes individuale në një kohë, ne vend të dëshironi të merrni një copë e bytes. Pastaj një herë ne kemi një copë të bytes, atëherë ne do të shkruajnë atë. Edhe pse ju kërkoni atë për të shkruar - dhe fwrite dhe fread të bëjë të njëjtin lloj gjë. Ata tampon lexon dhe shkruan tuaj. Edhe pse ju kërkoni atë për të shkruar menjëherë, ajo ndoshta nuk do të. Dhe ju nuk mund të jetë i sigurt se gjërat do të jetë e shkruar derisa ju telefononi hfclose apo çfarëdo qoftë ajo është, e cila më pas thotë, në rregull, unë jam i mbyllur dosjen time, që do të thotë unë do të shkruaj më mirë gjithçka që unë nuk kam shkruar ende. Ajo nuk ka nevojë për të shkruar çdo gjë jashtë derisa ju jeni mbyllur dosjen, dhe pastaj ajo ka nevojë për të. Pra, kjo është vetëm ajo dembel - ajo pret derisa ajo ka për të ndodhë. Kjo - të marrë 51 dhe ju do të shkoni në atë më në detaje, sepse OCaml dhe gjithçka në 51, çdo gjë është recursion. Nuk ka zgjidhje përsëritës, në thelb. Çdo gjë është recursion, dembel dhe vlerësimi do të jetë e rëndësishme për një shumë të rrethanave ku, në qoftë se ju nuk e keni vlerësuar lazily, që do të thotë - Shembulli është streams, të cilat janë pafundësisht të gjatë. Në teori, ju mund të mendoni e numrave natyrore si një lumë i 1-2-3-4-5-6-7, Pra, gjërat lazily vlerësuara janë të mirë. Nëse unë them unë dua numrin dhjetë, atëherë unë mund të vlerësojnë deri në numrin dhjetë. Nëse unë dua numrin njëqindtë, atëherë unë mund të vlerësojnë deri në numrin e qindta. Pa vlerësimit dembel, atëherë ajo do të përpiqet për të vlerësuar të gjithë numrat menjëherë. Ju jeni vlerësimin numrat pafundësisht shumë, dhe kjo është jo vetëm e mundur. Pra, ka shumë rrethana ku vlerësimi dembel është vetëm e domosdoshme për marrjen e gjëra për të punuar. 

Tani ne duam të shkruani insert ku insert do të jetë në mënyrë të ngjashme duke ndryshuar në përcaktimin e saj. Deri tani ajo është futur bool (vlera int). Ne jemi duke shkuar për të ndryshuar që të insert bool (int, vlera nyjen * pemë). Ne jemi të vërtetë do të ndryshojë se përsëri në një grimë, ne do të shohim se pse. Dhe le të shkojë build_node, vetëm për dreq e tij, sipër të futur kështu që ne nuk kemi për të shkruar një prototip funksion. E cila është një aluzion se ju jeni do të jetë duke përdorur build_node në insert. Rregull. Merrni një minutë për këtë. Unë mendoj se kam ruajtur rishikimin në qoftë se ju doni të tërheqë nga ajo, ose, të paktën, kam bërë tani. Doja një pushim të vogël për të menduar për logjikën e futur, në qoftë se ju nuk mund të mendoj për atë. Në thelb, ju vetëm do të jetë ndonjëherë futur në gjethe. Si, në qoftë se unë insert 1, atëherë unë jam në mënyrë të pashmangshme do të jetë futur 1 - Unë do të ndryshojë në të zezë - I'll të futur 1 mbi këtu. Ose në qoftë se unë insert 4, unë dua të futur 4 mbi këtu. Pra, pa marrë parasysh atë që ju bëni, ju do të jeni të futur në një fletë. Të gjithë ju duhet të bëni është të iterate drurin derisa ju të merrni në nyje që duhet të jetë prindi nyjen së, prindi nyja të ri, dhe pastaj të ndryshojë treguesin e majtë apo të djathtë, në varësi të faktit nëse kjo është më e madhe se ose më pak se nyjen e tanishme. Ndryshimi që treguesin për pikë në nyje tuaj të re. Pra iterate drurin, të bëjë pikë fletë në nyje të ri. Gjithashtu mendoj se pse që ndalon llojin e situatës para, ku kam ndërtuar pemë binare ku ajo ishte e saktë në qoftë se ju vetëm dukej në një nyje të vetme, 9 por ishte në të majtë të përsëritur 7 në qoftë se ju të gjithë rrugën poshtë. Pra, kjo është e pamundur në këtë skenar, pasi - mendoni rreth 9 futur apo diçka; në nyjen e parë, Unë jam duke shkuar për të parë 7 dhe unë jam vetëm duke shkuar për të shkuar në të djathtë. Kështu që nuk ka rëndësi se çfarë të bëj, në qoftë se unë jam duke shkuar për të futur një fletë, dhe në një fletë duke përdorur algoritmin e duhur, ajo do të jetë e pamundur për mua për të futur 9 të majtë e 7 sepse sa më shpejt që unë goditi 7 Unë jam duke shkuar për të shkuar në të djathtë. Ka njeri të ketë diçka për të filluar me? [Student] bëj unë. Sigurisht >>. [Student, pakuptueshëm] [Student tjera, pakuptueshëm] [Bowden] Është vlerësuar. Rregull. Dëshironi të shpjegoni? 

[Student] Që ne e dimë se ne ishim futur nyjet e reja në fund të pemës, Unë looped nëpër pemë iteratively derisa unë kam një nyje që vinte në dukje null. Dhe pastaj kam vendosur për të vënë atë ose në anën e djathtë ose e majtë duke përdorur këtë variabël të drejtë, ai më tha se ku për të vënë atë. Dhe pastaj, në thelb, unë vetëm e bëri që zgjasin - se nyja temp pikë në nyje të ri që është krijuar, ose në anën e majtë ose në të djathtë, në varësi të asaj vlera e drejtë ishte. Së fundi, kam vendosur vlera të reja nyje me vlerën e testimit saj. [Bowden] Mirë, kështu që unë shoh një çështje këtu. Kjo është si 95% të rrugës atje. Një çështje që unë shoh, mirë, dikush tjetër do të shihni një çështje? Çfarë është rrethanë, sipas të cilës ata thyejnë nga lak? [Student] Nëse temp është i pavlefshëm? Po >>. Pra, si ju thyer nga lak është nëse temp është i pavlefshëm. Por çfarë të bëj këtu? Unë temp dereference, e cila është në mënyrë të pashmangshme null. Pra, gjëja tjetër që ju duhet të bëni nuk është vetëm të mbajnë gjurmët deri në temp është i pavlefshëm, ju doni të mbani gjurmët e prindit në të gjitha kohët. Ne gjithashtu duam * prind nyje, unë mendoj ne mund të vazhdojmë që në në fillim null. Kjo do të ketë sjellje të pazakontë për rrënjët e pemës, por ne do të merrni për këtë. Nëse vlera është më e madhe se çfarëdo, atëherë temp temp = drejtë. Por, para se të bëjmë këtë, prindi = temp. Ose janë prindërit gjithmonë do të temp të barabartë? Është se çështja? Nëse temp nuk është i pavlefshëm, atëherë unë jam duke shkuar për të lëvizur poshtë, pa marrë parasysh se çfarë, te nje nyje për të cilën temp është prind. Pra, prindi do të jetë temp, dhe pastaj kam lëvizur temp poshtë. Tani temp është null, por thekson prind të prindit të gjë që është null. Pra këtu poshtë, unë nuk dua për të vendosur të drejtën e barabartë me 1. Kështu që unë u zhvendos në të djathtë, kështu që nëse e drejta = 1, dhe unë mendoj se edhe ju doni të bëni - nëse ju hyni në të majtë, ju doni për të vendosur të drejtën e barabartë me 0. Ose tjetër, nëse ndonjëherë ju të lëvizin në të djathtë. Në mënyrë të drejtë = 0. Nëse = 1 djathtë, tani ne duam të bërë të drejtën prind newnode akrep, tjetër ne duam të bërë majtë prind newnode akrep. Pyetjet për këtë? Rregull. Pra, kjo është mënyra se si ne - mirë, në të vërtetë, në vend të bërë këtë, Ne gjysma pritet që të përdorni build_node. Dhe pastaj, nëse është e barabartë newnode null, kthehen rreme. Kjo është se. Tani, kjo është ajo që kemi pritur që ju të bëni. 

Kjo është ajo që zgjidhjet e stafit të bëjë. Unë nuk pajtohem me këtë si mënyrën e "drejtë" për të shkuar në lidhje me të por kjo është krejtësisht e mirë dhe ajo do të punojë. Një gjë që është një e drejtë pak i çuditshëm tani është në qoftë se pema fillon si null, ne të kalojë në një pemë null. Unë mendoj se varet se si ju define sjelljen e kalimit në një pemë null. Unë do të mendoj se në qoftë se ju të kalojë në një pemë null, pastaj futur vlera në një pemë null duhet vetëm të kthehet në një pemë, ku vlera e vetme është se nyja e vetme. Njerëzit dakord me këtë? Ju mund të, nëse do të donit, në qoftë se ju të kalojë në një pemë null dhe ju doni të futur një vlerë në të, kthimit të rreme. Është e deri tek ju për të përcaktuar se. Për të bërë gjënë e parë dhe pastaj thashë - mirë, ju jeni do të ketë probleme duke bërë këtë, sepse ajo do të jetë më e lehtë në qoftë se kemi pasur një tregues globale për gjë, por ne nuk e bëjnë, kështu që nëse pema është i pavlefshëm, nuk ka asgjë që mund të bëjmë për këtë. Ne vetëm mund të kthehen rreme. Kështu që unë jam duke shkuar për të ndryshuar futur. Ne teknikisht mund vetëm të ndryshojë këtë të drejtë këtu, se si është iterating mbi gjërat, por unë jam duke shkuar për të ndryshuar futur për të marrë një nyje ** pemë. Pointers dyfishtë. Çfarë do të thotë kjo? Në vend që të merret me pointers në nyje, gjë që unë jam duke shkuar për të manipuluar është ky pointer. Unë jam duke shkuar për të manipuluar këtë tregues. Unë jam duke shkuar për të manipuluar pointers direkt. Kjo ka kuptim që, mendoj për poshtë - mirë, tani kjo pikë për null. Ajo që unë dua të bëj është të manipuluar këtë tregues për pikë për të mos null. Unë dua që ajo të tregojë nyje tim të ri. Në qoftë se unë vetëm i mbajnë gjurmët e pointers për pointers mia, atëherë unë nuk kam nevojë për të mbajtur gjurmët e një tregues mëmë. Unë vetëm mund të mbajnë gjurmët për të parë nëse kursori është duke treguar null, dhe nëse treguesi është duke treguar null, ndryshojë atë për pikë në nyje dua. Dhe unë mund të ndryshojë atë që unë kam një tregues për treguesin. Le të shohim këtë të drejtë tani. Ju në fakt mund të bëjë atë Recursively mjaft lehtë. A duam të bëjmë këtë? Po, ne bëjmë. 

Le të shohim atë Recursively. Së pari, çfarë është rasti ynë bazë do të jetë? Pothuajse gjithmonë rasti ynë bazë, por në fakt, kjo është lloj i ndërlikuar. Gjërat e parë e parë, në qoftë se (== NULL pemë) I guess ne jemi vetëm do të kthehen rreme. Kjo është e ndryshme nga pemë null tuaj tani. Ky është tregues për treguesin tuaj rrënjë qenë null që do të thotë se treguesin tuaj rrënjë nuk ekziston. Pra këtu poshtë, në qoftë se unë bëj * nyje - le të vetëm të ripërdorimin këtë. Nyja * root = NULL, dhe atëherë unë jam duke shkuar për të thirrur futur duke bërë diçka të tillë, futur në 4 & rrënjë. Pra dhe rrënjë, nëse rrënja është një nyje * atëherë dhe rrënjë është do të jetë një nyjë **. Kjo është e vlefshme. Në këtë rast, pemë, deri këtu, pema nuk është null - ose insert. Këtu. Pema nuk është i pavlefshëm; * pema është i pavlefshëm, e cila është e mirë sepse në qoftë se pema * është null, atëherë unë mund të manipulojnë atë tani tregojnë për atë që unë dua që ajo të tregojë. Por në qoftë se pema është i pavlefshëm, që do të thotë unë vetëm erdhi këtu dhe tha null. Kjo nuk ka kuptim. Unë nuk mund të bëjë asgjë me këtë. Nëse pema është null, kthimit të rreme. Kështu që unë në thelb thënë tashmë se çfarë ndodh vërtetë ynë bazë është. Dhe ajo që është se do të jetë? [Student, pakuptueshëm] [Bowden] Po. Pra, në qoftë se (== NULL * pemë). Kjo ka të bëjë me rastin gjatë këtu ku nëse akrep ime e kuqe është tregues që unë jam përqëndruar në, kështu si unë jam i fokusuar në këtë tregues, tani unë jam i fokusuar në këtë tregues. Tani unë jam i fokusuar në këtë tregues. Pra, nëse pointer ime e kuqe, e cila është ** mi nyjë, është gjithnjë - nëse *, akrep ime e kuqe, është gjithnjë null, që do të thotë se unë jam në rastin kur unë jam përqëndruar në një tregues se pikat - ky është një tregues që i përket një gjethe. Unë dua të ndryshojë këtë tregues për pikë në nyje tim të ri. Vijnë përsëri mbi këtu. Newnode im do të jetë vetëm nyje * n = build_node (vlera) pastaj n, nëse n = null, kthehen rreme. Tjetër ne duam të ndryshojmë atë që kursori është duke treguar tani tregojnë për nyje tonë të ndërtuar rishtazi. Ne mund të bëjë në fakt që këtu. Në vend të thënë n, ne themi pema * = * nëse pemë. Gjithkush kuptojnë se? Që duke u marrë me pointers për pointers, ne mund të ndryshojmë pointers null që të tregojnë për gjërat që ne duam që ata të tregojnë për të. Kjo është rasti ynë bazë. 

Tani përsëritje tonë, ose recursion tonë, do të jetë shumë e ngjashme me të gjitha recursions tjera, ne kemi qenë duke bërë. Ne do të duan për të futur vlera, dhe tani unë jam duke shkuar për të përdorur tresh përsëri, por ajo që është gjendja jonë do të jetë? Çfarë është ajo që ne jemi duke kërkuar për të vendosur nëse duam të shkojmë majtas apo djathtas? Le të bëjmë atë në hapa të veçantë. Në qoftë se (vlera <) çfarë? [Student] vlerën e pemës së? [Bowden] Pra, mos harroni se unë jam aktualisht - [Studentët, pakuptueshëm] [Bowden] Yeah, në mënyrë të drejtë këtu, le të themi se kjo shigjetë e gjelbër është një shembull i asaj që pema është aktualisht, është një tregues për këtë tregues. Kështu që do të thotë që unë jam një tregues për një tregues për 3. The dereference dy herë dukej mirë. Çfarë - si mund ta bëni këtë? [Student] Dereference herë, dhe pastaj të bëjë shigjeta në këtë mënyrë? [Bowden] Pra, (* pemë) është dereference herë, -> vlera do të më jepni vlerën e nyjeve që unë jam në mënyrë të tërthortë duke treguar për të. Kështu që unë mund të shkruaj atë ** tree.value nëse ju preferoni atë. Ose punon. Në qoftë se është rasti, atëherë unë dua të thërrasë futur me vlerë. Dhe çfarë është nyja e mia ** përditësuar do të jetë? Unë dua të shkoj në të majtë, kështu ** tree.left do të jetë majtë im. Dhe unë dua tregues për atë gjë kështu që nëse e majta përfundon duke qenë tregues null, Unë mund të modifikojë atë për pikë në nyje tim të ri. 

Dhe rasti tjetër mund të jetë shumë e ngjashme. Le të bëjë në fakt që tresh time tani. Vendos vlerën në qoftë se vlera <(** pemë). Vlera. Atëherë ne duam të rinovuar ** tona në të majtë, tjetër ne duam të rinovuar ** tona në të djathtë. [Student] A do të merrni treguesin në treguesin? [Bowden] Mos harroni se - ** tree.right është një yll nyje. [Student, pakuptueshëm] >> Yeah. ** Tree.right është si ky shkop ose diçka. Pra, duke marrë një tregues për atë, që i jep mua atë që unë dua i treguesin në atë djalë. [Student] A mund të shkojmë përsëri arsyeja pse ne jemi duke përdorur dy pointers? [Bowden] Yeah. Pra, - jo, ju mund të, dhe se zgjidhja më parë ishte një mënyrë për të bërë atë pa bërë dy pointers. Ju duhet të jetë në gjendje për të kuptuar përdorimin e dy pointers, dhe kjo është një zgjidhje e pastër. Gjithashtu, vini re se, çfarë ndodh në qoftë se pema ime - çfarë ndodh nëse rrënja ime ishte null? Çfarë ndodh në qoftë se unë bëj këtë rast të drejtë këtu? Pra nyje * root = NULL, futur 4 në & rrënjë. Çfarë është rrënja do të jetë pas kësaj? [Student, pakuptueshëm] >> Yeah. Vlera rrënjë do të jetë 4. Root majtë do të jetë null, rrënja e drejtë do të jetë i pavlefshëm. Në rastet kur nuk kemi rrënjë të kalojë nga adresa, ne nuk mund të modifikoni rrënjë. Në rastin kur pema - ku rrënja ishte null, ne vetëm kishte për të kthyer rreme. Nuk ka asgjë që mund të bëni. Ne nuk mund të futur një nyje në një pemë bosh. Por tani ne mund, ne vetëm të bëjë një pemë bosh në një pemë një nyje. E cila është zakonisht mënyra pritur që ajo është menduar për të punuar. 

Për më tepër, kjo është dukshëm më e shkurtër se edhe mbajtja e prindit, dhe kështu ju iterate poshtë gjithë rrugën. Tani unë kam prind tim, dhe unë vetëm kam të drejtë treguesin time prind për çdo gjë. Në vend të kësaj, në qoftë se ne e bëmë këtë iteratively, ajo do të jetë ideja njëjtë me një lak, ndërsa. Por në vend që të merren me treguesin tim mëmë, vend akrep tim aktual do të jetë gjëja më që unë jam direkt modifikuar për pikë në nyje tim të ri. Unë nuk duhet të merren me faktin nëse është e treguar në të majtë. Unë nuk duhet të merren me faktin nëse është e treguar në të djathtë. Është vetëm çdo gjë që ky tregues është, unë jam duke shkuar për të vendosur atë në pikë në nyje tim të ri. Gjithkush kuptuar se si funksionon? Nëse pse nuk duam të bëjmë atë në këtë mënyrë, por të paktën se kjo punon si një zgjidhje? [Student] Ku nuk kemi kthim i vërtetë? [Bowden] Kjo është ndoshta e drejtë këtu. Nëse ne duhet futur atë, kthim i vërtetë. Tjetër, këtu poshtë ne do të duan të kthehen në çfarëdo kthimit futur. 

Dhe ajo që është e veçantë në lidhje me këtë funksion rekursive? Është bisht rekursive, aq sa kohë që ne të hartojë me disa optimization, ajo do të njohin atë dhe ju kurrë nuk do të merrni një overflow stack nga kjo, edhe në qoftë se pema jonë ka një lartësi prej 10,000 apo 10 milion. [Student, pakuptueshëm] [Bowden] Unë mendoj se kjo e bën atë në dash - apo çfarë niveli optimization është e nevojshme për një recursion bisht të njohur. Unë mendoj se ai njeh - GCC dhe tingëllimë gjithashtu kanë kuptime të ndryshme për nivelin e tyre optimization. Unë dua të them se është Dasho 2, me siguri se do të njohë recursion bisht. Por ne - ju mund të ndërtojë si një shembull Fibonocci apo diçka. Kjo nuk është e lehtë për të provuar me këtë, sepse kjo është e vështirë për të ndërtuar një pemë binare që është aq i madh. Por, vërtet, unë mendoj se është Dasho 2, që në qoftë se ju hartojnë me Dasho 2, ajo do të shikoni për recursion bisht dhe jam optimist se nga. Le të kthehemi në - futur fjalë për fjalë gjëja e fundit që ajo ka nevojë. Le të kthehemi në insert mbi këtu ku ne jemi duke shkuar për të bërë të njëjtën ide. Ajo ende do të ketë krisje të mos qenë në gjendje për të krejtësisht të handle kur rrënja vetë është i pavlefshëm, ose nga hyrja kaluara është null, por në vend që të merret me një tregues mëmë, le të aplikojnë të njëjtën logjikë e pointers mbajtur për pointers. Nëse këtu kemi mbajtur nyje tonë ** cur, dhe ne nuk kemi nevojë për të mbajtur gjurmët e drejtë më, por nyje ** cur = & pemë. Dhe tani loop tonë, ndërsa do të jetë duke cur * nuk null barabartë. A nuk duhet të mbajnë gjurmët e prindërve më. A nuk duhet të mbajnë gjurmët e majtë dhe të djathtë. Dhe unë do të thërrasë atë temp, sepse ne jemi tashmë duke përdorur Temp. Rregull. Pra, nëse (vlera> * temp), pastaj & (* temp) -> të drejtë tjetër temp = & (* temp) -> majtë. Dhe tani, në këtë pikë, pasi këtë lak, ndërsa, Unë vetëm të bëjë këtë, sepse ndoshta është më e lehtë për të menduar për iteratively se Recursively, por pas kësaj lak, ndërsa, * Temp është tregues që ne duam të ndryshojmë. 

Para se të kemi pasur prind, dhe ne të kërkuar për të ndryshuar ose majtas prindit ose prindit të drejtë, por në qoftë se ne duam të ndryshojmë drejtën prind, * temp atëherë është e drejtë prindi, dhe ne mund të ndryshojë atë direkt. Pra këtu poshtë, ne mund të bëjmë * temp = newnode, dhe kjo është ajo. Pra njoftimit, të gjithë ne e bëmë në këtë ishte marrë nga rreshta të kodit. Në mënyrë për të mbajtur gjurmët e prindit në të gjitha që është përpjekje shtesë. Këtu, në qoftë se ne vetëm i mbajnë gjurmët e treguesin në treguesin, dhe madje edhe në qoftë se ne të kërkuar për të hequr qafe të gjitha këto formatimin e teksteve kaçurrel tani, bërë atë të duket e shkurtër. Kjo tani është zgjidhja e saktë të njëjtën, por linjat pak të kodit. Pasi ju filloni duke njohur këtë si një zgjidhje të vlefshme, kjo është edhe më e lehtë për arsye se rreth si, rregull, pse nuk kam këtë flamur në të djathtë int? Çfarë do të thotë kjo? Oh, kjo është nënkuptuar se çdo herë që unë shkoj drejtë, kam nevojë për të vendosur atë, tjetër në qoftë se unë shkoj lënë kam nevojë për të vendosur atë në zero. Këtu, unë nuk kam lidhje me atë për arsye, por vetëm më të lehtë për të menduar rreth. Pyetje? [Student, pakuptueshëm] >> Yeah. Mirë, kështu që në pak fundit - I guess një funksion të shpejtë dhe të lehtë ne mund të bëjmë është, let's - së bashku, unë mendoj, të përpiqet dhe të shkruajnë një funksion përmban që nuk i intereson nëse ajo është një pemë binare kërkim. Kjo përmban funksion duhet të kthehen vërtetë në qoftë se kudo në këtë pemë binare e përgjithshme është vlera ne jemi duke kërkuar për të. Pra, le të bëjë atë të parë Recursively dhe pastaj ne do të bëjmë atë iteratively. Ne në fakt mund të bëni vetëm atë së bashku, sepse kjo do të jetë me të vërtetë të shkurtër. 

Çfarë është rasti im bazë do të jetë? [Student, pakuptueshëm] [Bowden] Pra, në qoftë se (== NULL pemë), pastaj çfarë? [Student] Kthehu rreme. [Bowden] Else, mirë, unë nuk nevojë tjetër. Nëse ishte rast tjetër mia bazë. Vlera [Student] TREE-së? Po >>. Pra, nëse (pemë-> vlera == vlerë. Njoftim ne jemi kthyer në nyjen * jo, nyja ** s? Përmban kurrë nuk do të duhet të përdorni një ** nyjen, pasi ne nuk jemi modifikuar pointers. Ne jemi vetëm duke traversing ato. Nëse kjo ndodh, atëherë ne duam të kthehen vërtetë. Tjetër ne duam të kaloj fëmijët. Pra, ne nuk mund të arsyetojë se nëse gjithçka në të majtë është më pak dhe çdo gjë në të djathtë është më e madhe. Pra, çfarë është gjendja jonë do të jetë këtu - apo, çka do të shkojmë për të bërë? [Student, pakuptueshëm] >> Yeah. Kthimi përmban (vlera pemë-> majtas) ose përmban (vlera pemë-> djathtas). Dhe kjo është ajo. Dhe vini re ka disa qark të shkurtër të vlerësimit, ku në qoftë se ne të ndodhë për të gjetur vlerën në pemë majtë, ne kurrë nuk duhet të shikojmë në pemë e duhur. Kjo është funksioni i tërë. Tani le të bëjmë atë iteratively, e cila do të jetë më pak e bukur. Ne do të marrë fillimin e zakonshme të nyjeve monedhes * = pemë. Ndërsa (tani! = NULL). Shpejt do të shohim një problem. Nëse momen - këtu, në qoftë se ne ndonjëherë të thyer nga kjo, atëherë ne kemi të drejtuar nga gjërat për të shikoni në, kështu që rezultati false. Në qoftë se (cur-> vlera == vlera), kthehen vërtetë. Deri tani, ne jemi në një vend - ne nuk e dimë nëse ne duam të shkojnë majtas ose djathtas. Pra arbitrarisht, le të shkojnë vetëm të majtë. Unë kam drejtuar padyshim në një çështje ku unë kam braktisur plotësisht gjithçka - Unë vetëm do të ndonjëherë të shikoni në anën e majtë të një pemë. Unë kurrë nuk do të kontrollojë çdo gjë që është një fëmijë të drejtën e çdo gjë. Si mund ta fix this? [Student] Ju duhet të mbajnë gjurmët e të majtë dhe të djathtë në një pirg. [Bowden] Yeah. Pra, le të bëjë atë struct lista, nyje * n, dhe pastaj nyjen ** ardhshme? Unë mendoj se works fine. Ne duam për të shkuar mbi të majtë, ose let's - deri këtu. Struct = listë listë, ajo do të fillojë jashtë në këtë listë struct. * List = NULL. Kështu që do të jetë e lidhur me listën tonë të tregoje se kemi anashkaluar. Ne do të kaloj mbetur tani, por që ne në mënyrë të pashmangshme duhet të kthehen në të djathtë, Ne jemi duke shkuar për të mbajtur anën e djathtë brenda listës sonë struct. Atëherë ne do të kemi new_list ose struct, struct * listë, new_list = malloc (sizeof (lista)). Unë jam duke shkuar për të injoruar error checking-se, por ju duhet të kontrolloni për të parë nëse është e pavlefshme. New_list nyjen ajo do të tregojnë për - oh, kjo është arsyeja pse kam kërkuar atë deri këtu. Ajo do të tregojnë për një listë të dytë struct. Kjo është vetëm se si të lidhura listat punë. Kjo është e njëjtë si një listë int lidhur përveç ne jemi vetëm duke zëvendësuar int me * nyjeve. Kjo është saktësisht e njëjtë. Pra new_list, vlera e nyjeve tonë new_list, do të jetë cur-> drejtë. Vlera e tonë new_list-> ardhshme do të jetë lista jonë origjinale, dhe pastaj ne jemi duke shkuar për të rinovuar listën tonë për pikë në new_list. 

Tani ne kemi nevojë për disa lloj mënyrë për të tërhequr gjërave, si kemi përshkuar tërë subtree majtë. Tani ne kemi nevojë për të tërhequr gjëra nga ajo, si cur është i pavlefshëm, ne nuk duam të kthehen vetëm false. Ne duam që tani të tërhequr jashtë në listën tonë të ri. Një mënyrë e përshtatshme për ta bërë këtë - mirë, në fakt, ka mënyra të shumta për ta bërë këtë. Çdokush kanë një sugjerim? Ku unë duhet të bëjë këtë apo se si unë duhet ta bëjë këtë? Ne kemi vetëm disa minuta, por çdo sugjerime? Në vend të - një mënyrë, në vend të të qenit, ndërsa gjendjen tonë, ajo që ne jemi aktualisht në kërkim të nuk është i pavlefshëm, në vend të kësaj ne do të vazhdojë të shkojë deri në listën tonë është vetë null. Pra, nëse lista jonë e përfundon duke u null, atëherë ne kemi drejtuar nga gjërat për të kërkuar, për të kërkuar gjatë. Por kjo do të thotë se gjëja e parë në listën tonë është vetëm do të jetë nyja e parë. Gjëja e parë do të jetë - ne nuk duhet të shohin se. Kështu lista-> n do të jetë pema tonë. lista-> ardhshme do të jetë e pavlefshme. Dhe tani, ndërsa lista nuk ka null barabartë. Cur do të tërheqë diçka nga lista tonë. Pra, cur do të barabartë lista-> n. Dhe pastaj lista do të barabartë lista-> n, ose lista-> ardhshëm. Pra, nëse vlera e monedhes barabartë vlerë. Tani ne mund të shtoni edhe treguesin tonë të drejtë dhe treguesin e majtë tonë për aq kohë sa ata nuk janë null. Poshtë këtu, unë mendoj se ne duhet të kemi bërë që në vendin e parë. Në qoftë se (cur-> drejtë! = NULL) atëherë ne jemi duke shkuar për të futur atë nyje në listën tonë. Në qoftë se (cur-> majtas), kjo është pak e punë shtesë, por kjo është në rregull. Në qoftë se (cur-> majtas! = NULL), dhe ne jemi duke shkuar për të futur të majtën në listën tonë të lidhura, dhe që duhet të jetë ajo. Ne iterate - sa kohë që ne kemi diçka në listën tonë, ne kemi një tjetër nyje për të parë në. Kështu që ne shikojmë në atë nyje, Ne përpara listën tonë me një tjetër. Në qoftë se nyja është vlera ne jemi duke kërkuar për të, ne mund të kthehen vërtetë. Tjetër futur dy tregoje tona majtë dhe të djathtë, për aq kohë sa ata nuk janë null, në listën tonë kështu që ne në mënyrë të pashmangshme të shkojë mbi ta. Pra, në qoftë se ata nuk ishin null, nëse treguesin tonë root vuri në dukje dy gjëra, atëherë në fillim kemi tërhequr diçka kështu lista jonë përfundon duke u null. Dhe pastaj ne kemi vënë përsëri në dy gjëra, kështu që tani është lista jonë e madhësisë 2. Atëherë ne jemi duke shkuar për lak back up dhe ne jemi vetëm duke shkuar për të tërhequr, le të themi, në treguesin e majtë të nyjes root tonë. Dhe kjo do të ndodh vetëm i mbajnë, ne do të përfundojë deri në looping mbi çdo gjë. 

Vini re se kjo ishte dukshëm më e komplikuar në tretësirë ​​rekursive. Dhe unë kam thënë shumë herë se zgjidhja rekursive zakonisht ka shumë të përbashkëta me përsëritës zgjidhje. Ja kjo është pikërisht ajo që zgjidhja rekursive është duke bërë. Ndryshimi i vetëm është se në vend të implicite përdorur rafte, rafte programi, si mënyrën tuaj të mbajtur gjurmët e asaj që nyjet ju ende nevojë për të vizituar, tani ju duhet të përdorni në mënyrë eksplicite një listë të lidhura. Në të dy rastet ju jeni mbajtja e asaj nyje ka ende nevojë për t'u vizituar. Në rastin gjithkund rekursive është vetëm më e lehtë për shkak se një pirg zbatohet për ju si rafte programit. Vini re se kjo listë e lidhur, kjo është një pirg. Çdo gjë që ne vetëm vënë në rafte është menjëherë ajo që ne jemi duke shkuar për të tërhequr off rafte për të vizituar ardhshëm. Ne jemi jashtë kohës, por ndonjë pyetje? [Student, pakuptueshëm] [Bowden] Yeah. Pra, nëse kemi listën tonë të lidhur, aktuale do të tregojnë për këtë djalë, dhe tani ne jemi vetëm avancimin listën tonë lidhur me përqëndrohet në këtë djalë. Ne jemi duke traversing më shumë se lista e lidhur në atë linjë. Dhe atëherë unë mendoj se ne duhet të lirojë listën tonë dhe sende të lidhur herë para se të kthehej vërtetë apo e rreme, ne duhet të iterate mbi listën tonë dhe gjithmonë i lidhur këtu poshtë, unë mendoj, në qoftë se ne cur e drejtë nuk është e barabartë me, shtoni atë, kështu që tani që ne duam të çlirojmë cur, sepse, mirë, nuk e kemi plotësisht të harrojmë për listën e? Po. Pra, kjo është ajo që ne duam të bëjmë këtu. Ku është akrep? Cur ishte atëherë - duam një listë struct * 10 është e barabartë me listë tjetër. Lista e lirë, list = temp. Dhe në rastin kur kemi të kthehen vërtetë, ne nuk duhet të iterate mbi pjesën e mbetur të listës sonë i lidhur çlirimin gjëra. Gjë e bukur për zgjidhjen e gjithkund rekursive është liruar gjëra thjesht do të thotë factorings popping jashtë rafte e cila do të ndodhë për ju. Pra, ne kemi shkuar nga diçka që është si 3 linjat e vështirë të mendoj-rreth kodit për diçka që është dukshëm më shumë të vështirë të mendoj-rreth rreshta të kodit. Më pyetje? Dakord. Ne jemi të mirë. Bye! [CS50.TV]