[Powered by Google Translate] [Pjesa 7] [Less komode] [Nate Hardison] [Universiteti i Harvardit] [Kjo është CS50.] [CS50.TV] 

Mirë se vini në nenin 7. Faleminderit për stuhi me rërë, në vend të ketë një seksion normal të kësaj jave, ne jemi duke e bërë këtë shëtitje-nëpërmjet, përmes seksionit të pyetjeve. Unë jam duke shkuar për të ndjekur së bashku me problemin Set 6 Specifikimi, dhe duke kaluar nëpër të gjitha pyetjet në Një Seksioni pyetjesh seksion. Nëse ka ndonjë pyetje, ju lutem postoni ato në CS50 diskutuar. 

Mirë. Le të ketë filluar. Tani për tani unë jam duke kërkuar në faqen 3 të Specifikimi Set Problem. Ne jemi duke shkuar për të parë të fillojmë të flasim në lidhje me pemë binare pasi ata kanë shumë rëndësi për të vendosur këtë javë problemit - encoding Tree Huffman. Një nga strukturat e të dhënave e parë kemi biseduar për në CS50 ishte array. Mos harroni se një grup është një sekuencë e elementeve - të gjitha të të njëjtit lloj - ruhen të drejtë tjetër për njëri-tjetrin në kujtesë. Nëse unë kam një koleksion numër i plotë që unë mund të tërheqë përdorur këtë stil kuti-numrat-integers - Le të thonë se unë kam 5 në kutinë e parë, kam 7 në të dytë, atëherë unë kam 8, 10, dhe 20 në kutinë e fundit. Mos harroni gjërat, të dy me të vërtetë e mirë për këtë grup janë që ne kemi këtë qasje të vazhdueshme në kohë për çdo element të veçantë  në rrjet, nëse ne e dimë indeksin e saj. Për shembull, në qoftë se unë dua të kap elementin e tretë në grup - në indeksin e 2 duke përdorur zero-bazuar sistemit tonë indeksimit - Unë fjalë për fjalë vetëm duhet të bëjë një llogaritje të thjeshtë matematikore, hop në atë pozicion në grup, largohen nga 8 që është ruajtur, ka dhe unë jam i mirë për të shkuar. 

Një nga gjërat më të këqija në lidhje me këtë grup - se kemi biseduar rreth kur kemi diskutuar listat lidhura - është se në qoftë se unë dua të futur një element në këtë grup, Unë do të duhet të bëjë disa zhvendosur rreth. Për shembull, kjo array drejtë këtu është në mënyrë renditura - renditura në ngjitje urdhër - 5, pastaj 7, pastaj 8, pastaj 10, dhe më pas 20 - por në qoftë se unë dua të futur numrin 9 në këtë grup, Unë do të duhet të zhvendoset disa nga elementet në mënyrë që të bëjë hapësirë. Ne mund të tërheqë këtë këtu. Unë do të duhet të lëvizin 5, 7, dhe pastaj 8; të krijojë një boshllëk ku unë mund të vënë në 9, dhe pastaj 10 dhe 20 mund të shkojnë për të drejtën e 9. Kjo është lloj i një dhimbje, sepse në rastin më të keq - kur ne jemi të paturit e për të futur qoftë në fillim ose në fund e array, në varësi se si ne jemi zhvendosur - ne mund të përfundojnë që të zhvendoset të gjitha elementet se ne jemi aktualisht ruajtjen në grup. 

Pra, çfarë ishte mënyra rreth kësaj? Mënyra rreth kësaj ishte për të shkuar në linked list-metodën tonë, ku - në vend të ruajtjen e elementeve 5, 7, 8, 10, dhe 20 të gjithë pranë njëri-tjetrit në kujtesën - çfarë ne vend nuk u ruajtur ato lloj e kudo që kemi dashur për të ruajtur ato në këto linked listë nyjet që unë jam tërhequr nga këtu, lloj ad hoc. Dhe pastaj ne lidhur ato së bashku duke përdorur këto pointers ardhshëm. Unë mund të ketë një tregues nga 5 në 7, një akrep nga 7 në 8, një akrep nga 8 në 10, dhe në fund, një akrep nga 10 në 20, dhe pastaj një tregues null në 20 duke treguar se nuk ka asgjë të majtë. Të tregtisë-off që ne kemi këtu është se tani në qoftë se ne duam të futur numrin 9 në listën tonë të renditura, të gjithë ne duhet të bëni është të krijojë një nyje të re me 9, wire atë deri për pikë në vendin e duhur, dhe pastaj ri-tel 8 për pikë deri në 9. Kjo është shumë shpejt, duke supozuar ne e dimë saktësisht se ku ne duam të futur 9. Por tregtisë-off në këmbim për këtë është se ne kemi humbur tani qasje të vazhdueshme në kohë për çdo element të veçantë në strukturën e të dhënave tona. Për shembull, në qoftë se unë dua të gjeni elementin e katërt në këtë listë e lidhur, Unë do të duhet të fillojë në fillim të listës dhe të punojnë rrugën time përmes numërimit nyje nyje-nga-deri sa të gjeni një të katërt. 

Në mënyrë që të marrë performancë më të mirë se sa një qasje listë lidhur - por edhe të ruajë disa nga përfitimet që kemi pasur në drejtim të hyrjes kohë nga një listë e lidhur - një pemë binare do të ketë nevojë të përdorë memorie pak më shumë. Në veçanti, në vend të vetëm duke pasur një akrep në një nyje pemë binare - si listë e lidhur nyje-ka - ne jemi duke shkuar për të shtuar një treguesin e dytë në nyje binar pemë. Në vend se vetëm duke pasur një tregues për elementin tjetër, ne do të kemi një tregues për një fëmijë të majtë dhe një fëmijë drejtë. 

Le të nxjerrë një foto për të parë atë që në fakt duket si. Përsëri, unë jam duke shkuar për të përdorur këto kuti dhe shigjeta. Një nyjë binar pemë do të nisem me vetëm një kuti të thjeshtë. Ajo do të ketë një hapësirë ​​për vlerën, dhe pastaj ajo gjithashtu do të ketë një hapësirë ​​për fëmijën e majtë dhe e djathtë të fëmijës. Unë jam duke shkuar për emërtim ata këtu. Ne do të kemi fëmijën e majtë, dhe pastaj ne do të kemi fëmijën e duhur. Ka shumë mënyra të ndryshme për ta bërë këtë. Ndonjëherë për hapësirë ​​dhe komoditet, Unë do të të vërtetë të tërheqë atë si unë jam duke bërë këtu në fund ku unë jam duke shkuar të ketë vlerë në krye, dhe pastaj fëmija të drejtë në pjesën e poshtme të djathtë, dhe fëmija majtë në pjesën e poshtme të majtë. Going back to ky diagram të lartë, ne kemi vlera në krye, atëherë ne kemi treguesin e majtë-fëmijë, dhe pastaj ne kemi të drejtë treguesin-fëmijë. 

Në Specifikimi Set Problem, ne flasim për hartimin e një nyje që ka një vlerë 7, dhe pastaj një të majtë fëmijë akrep që është i pavlefshëm, dhe një e drejtë-fëmijë që është akrep null. Ne ose mund të shkruani null kapitalit në hapësirë ​​për dy fëmijë të majtë dhe fëmija të drejtë, ose ne mund të tërheqë këtë plagë diagonale nëpër secilën nga kutitë për të treguar se është i pavlefshëm. Unë jam duke shkuar për të bërë këtë vetëm për shkak se është më e thjeshtë. Çfarë ju shihni këtu janë dy mënyra për të diagramimin një shumë të thjeshtë pemë nyje binar ku ne kemi vlerën 7 dhe pointers null fëmijës. 

Pjesa e dytë e bisedimeve tona specifikimit rreth asaj se si të lidhura me lista - Mos harroni, kemi pasur vetëm për të mbajtur në elementin e parë në një listë për të kujtuar të gjithë listën - dhe gjithashtu, me një pemë binare, ne vetëm duhet të mbajë në të një akrep në pemë në mënyrë që për të ruajtur kontrollin mbi strukturën e të dhënave të tërë. Ky element i veçantë i pemës quhet nyje rrënja e pemës. Për shembull, nëse kjo nyje - kjo nyje përmban vlerën e 7 me pointers null majtë dhe të djathtë-fëmijë - ishin vlera vetëm në pemë tonë, atëherë kjo do të jetë nyja tonë rrënjë. Kjo është shumë e fillimi i pemës tonë. Ne mund të shohim këtë pak më qartë sapo kemi filluar duke shtuar më shumë nyje të pemës tonë. Më lejoni të tërheqë një faqe të re. 

Tani ne jemi duke shkuar për të nxjerrë një pemë që ka 7 në rrënjë, dhe 3 brenda e fëmijës majtë, dhe 9 brendësi të fëmijës duhur. Përsëri, kjo është shumë e thjeshtë. Ne kemi marrë 7, vizatoni një nyje për 3, një nyje për 9, dhe unë jam duke shkuar për të vendosur treguesin e majtë fëmijëve prej 7 për pikë në nyjen përmban 3, dhe të drejtën për-fëmijë treguesin e nyja përmban 7 në nyje përmban 9. Tani, pasi 3 dhe 9 nuk kanë ndonjë fëmijë, ne jemi duke shkuar për të vendosur të gjitha pointers e tyre fëmijë të jetë e pavlefshme. Këtu, rrënja e pemës tonë korrespondon me nyje përmban numrin 7. Ju mund të shihni se në qoftë se të gjithë ne kemi është një tregues për atë nyje rrënjë, atëherë ne mund të ecin nëpër pemë tonë dhe qasje të dy nyjet fëmijë - dy 3 dhe 9. Nuk ka nevojë për të ruajtur pointers për çdo nyje të vetme në pemë. Mirë. Tani ne jemi duke shkuar për të shtuar një tjetër nyje në këtë diagram. Ne jemi duke shkuar për të shtuar një nyje përmban 6, dhe ne jemi duke shkuar për të shtuar këtë si fëmijën e djathtë të nyjeve përmban 3. Për ta bërë këtë, unë jam duke shkuar për të fshirë atë treguesin null në 3-nyjë dhe tel atë deri në pikë në nyje përmban 6. Mirë. 

Në këtë pikë, le të shkojë më shumë se një pak e terminologjisë. Për të filluar, arsyen se kjo është quajtur një pemë binare në veçanti është se ai ka dy fëmijë pointers. Ka lloje të tjera të pemëve që kanë pointers më shumë fëmijë. Në veçanti, ju bëri një "provoni" në Set Problem 5. Ju do të vëreni se në atë provoni, ju kishte 27 pointers të ndryshme në fëmijët të ndryshme - një për secilin nga 26 letra në alfabetin Shqip, dhe pastaj 27 për apostrof - kështu, kjo është e ngjashme me një lloj të pemës. Por këtu, pasi binar është, ne kemi vetëm dy pointers fëmijë. 

Përveç kësaj nyje rrënjë që kemi biseduar rreth, ne kemi qenë të hedhur rreth këtij termi 'fëmijë'. Çfarë do të thotë kjo për një nyje të jetë një fëmijë i një nyje? Kjo fjalë do të thotë se një nyje fëmijë është një fëmijë i një nyje në qoftë se nyjen e tjera ka një pointers saj fëmijëve të vendosur për të vënë në atë nyje. Për të vënë këtë në terma më konkrete, nëse 3 është theksuar nga një prej pointers fëmijëve të 7, atëherë 3 është një fëmijë i 7. Nëse ne do të kuptoj se çfarë fëmijët e 7 janë - mirë, ne shohim se 7 ka një tregues për 3 dhe një tregues për 9, kështu 9 dhe 3 janë fëmijët e 7. Nëntë nuk ka fëmijë, sepse pointers saj fëmijë janë null, dhe 3 ka vetëm një fëmijë, 6. Gjashtë gjithashtu nuk ka fëmijë për shkak të dy pointers saj janë null, të cilat ne do të nxjerrë të drejtë tani. 

Përveç kësaj, ne gjithashtu flasim për prindërit e një nyje të veçantë, dhe kjo është, si ju do të presin, e kundërta e këtij përshkrimi fëmijëve. Çdo nyje ka vetëm një prind - në vend të dy si ju mund të presin me njerëzit. Për shembull, prind i 3 është 7. Prind i 9 është gjithashtu 7, dhe prind i 6 është 3. Jo shumë për të. Ne gjithashtu kemi kushtet për të folur në lidhje me gjyshërit dhe nipërit, dhe më në përgjithësi, ne flasim për paraardhësit dhe pasardhësit e një nyje të veçantë. Paraardhësi i një nyje - ose paraardhësit, në vend të një nyje - janë të gjitha nyjet që shtrihen në rrugën nga rrënja në atë nyje. Për shembull, në qoftë se unë jam duke kërkuar në nyjen 6, atëherë paraardhësit do të jenë të dy 3 dhe 7. Paraardhësit e 9, për shembull, janë - në qoftë se unë jam duke kërkuar në nyjen 9 - atëherë paraardhësi i 9 është vetëm 7. Dhe pasardhësit janë pikërisht e kundërta. Nëse unë dua të shikoni në të gjithë pasardhësit e 7, atëherë unë duhet të shikoni në të gjitha nyjet nën atë. Pra, unë kam 3, 9, dhe 6 të gjitha, si pasardhësit e 7. 

Termi e fundit që ne do të flasim rreth është ky nocion për të qenë një vëlla. Vëllai dhe motra - lloj pas së bashku në këto kushte familjare - janë nyjet që janë në të njëjtin nivel në pemë. Pra, 3 dhe 9 janë vëllezërit e motrat, sepse ata janë në të njëjtin nivel në pemë. Ata të dy kanë të njëjtën prind, 7. E 6 vëllezërit e motrat, sepse nuk ka 9 nuk ka asnjë fëmijë. Dhe 7 nuk ka ndonjë vëllezërit e motrat, sepse ajo është rrënja e pemës tonë, dhe ka vetëm ndonjëherë 1 rrënjë. Për 7 të kemi vëllezërit e motrat nuk do të duhet të jetë një nyje më lart 7. Nuk do të ketë të jetë një prind i 7, në të cilin rast 7 nuk do të jetë rrënja nga pema. Pastaj se prind i ri i 7 do të duhet të ketë një fëmijë, dhe se fëmija më pas do të jetë motër e 7. 

Mirë. Lëvizin më. Kur kemi filluar diskutimin tonë të pemëve binare, kemi biseduar rreth asaj se si ne u do të përdorin ato për të të fituar një avantazh mbi të dy vargjeve dhe listat e lidhura. Dhe mënyra që ne jemi duke shkuar për të bërë këtë është me këtë pronë urdhërimin. Ne themi se një pema binar është urdhëruar, sipas specifikim, në qoftë se për çdo nyje në pemë tonë, të gjithë pasardhësit e saj në të majtë - fëmija majtë dhe të gjithë pasardhësve të fëmijës së majtë - kanë vlera më të vogël, dhe të gjitha nyjet në të djathtë - fëmija e drejtë dhe të gjithë pasardhësve të drejtën e femijëve së - kanë nyjet më të mëdha se vlera e nyjeve aktuale që ne jemi duke kërkuar në. Vetëm për thjeshtësi, ne do të supozojmë se nuk ka ndonjë nyje kopjuar në pemën tonë. Për shembull, në këtë pemë, ne nuk do të merret me rastin ku ne kemi vlerën 7 në rrënjë  dhe pastaj kemi edhe vlerën 7 gjetkë në pemë. Në këtë rast, ju do të vëreni se kjo pemë është urdhëruar të vërtetë. Ne kemi vlerën 7 në rrënjë. Çdo gjë tek e majta e 7 - në qoftë se unë zgjidh të gjitha këto shenja pak këtu - çdo gjë tek e majta e 7 - 3 dhe 6 - ato vlera janë të dy më pak se 7, dhe çdo gjë në të djathtë - e cila është vetëm ky 9 - është më i madh se 7. 

Kjo nuk është pema urdhërohet vetëm që përmban këto vlera, por le të nxjerrë një më pak prej tyre. Nuk është në fakt një bandë e tërë e mënyrat që ne mund të bëjmë këtë. Unë jam duke shkuar për të përdorur një stenografi vetëm për të mbajtur gjërat e thjeshta ku - sesa tërhequr nga të gjithë kuti-dhe-shigjeta - Unë jam vetëm duke shkuar për të nxjerrë numrat dhe shtoni shigjetat lidh ato. Për të filluar, ne do të shkruani vetëm pemën tonë origjinal, ku sërish kemi pasur 7, dhe pastaj një 3, dhe pastaj 3 vuri përsëri në të djathtë të 6, dhe 7 kishte një fëmijë të drejtë që ishte 9. Mirë. Çfarë është një mënyrë tjetër që ne mund të shkruaj këtë pemë? Në vend të që të jetë fëmija 3 nga 7 majtë, ne gjithashtu mund të ketë 6 jetë fëmija e majtë të 7, dhe pastaj 3 jetë fëmija e majtë të 6. Kjo do të duket si ky dru të drejtë këtu, ku unë kam marrë 7, atëherë 6, pastaj 3, dhe një 9 në të drejtë. Ne gjithashtu nuk duhet të ketë 7 si nyje tonë rrënjë. Ne gjithashtu mund të ketë 6 si nyje tonë rrënjë. Çfarë do që të duken si? Nëse ne jemi duke shkuar për të mbajtur këtë pronë urdhëruar, çdo gjë tek e majta e 6 ka të jetë më pak se saj. Ka vetëm një mundësi, dhe kjo është 3. Por pastaj si fëmijën e djathtë e 6, ne kemi dy mundësi. Së pari, ne mund të kemi 7 dhe pastaj 9, ose ne mund të tërheqë atë - si unë jam gati për të bërë këtu - ku ne kemi 9 si fëmijën e djathtë të 6, dhe pastaj 7 si fëmijën e majtë të 9. 

Tani, 7 dhe 6 nuk janë vlerat e mundur vetëm për rrënjë. Ne gjithashtu mund të ketë 3 jetë në rrënjë. Çfarë ndodh nëse 3 është në rrënjë? Ja, gjërat marrin pak interesante. Tre nuk ka asnjë vlera që janë më pak se ajo, kështu që tërë anën e majtë të pemës është vetëm do të jetë e pavlefshme. Nuk do të jetë çdo gjë atje. Në të djathtë, ne mund lista gjërat në ngjitje qëllim. Ne mund të ketë 3, pastaj 6, 7, pastaj pastaj 9. Ose, ne mund të bëjmë 3, pastaj 6, pastaj 9, pastaj 7. Ose, ne mund të bëjmë 3, pastaj 7, pastaj 6, pastaj 9. Ose, 3, 7 - të vërtetë nuk ka, ne nuk mund të bëjmë një 7 më. Kjo është një gjë tonë atje. Ne mund të bëjmë 9, dhe pastaj nga 9 ne mund të bëjmë dhe pastaj 6 7. Ose, mund të bëjmë 3, pastaj 9, pastaj 7, dhe pastaj 6. 

Një gjë të tërheq vëmendjen tuaj për këtu është se këto pemë janë pak çuditshëm-looking. Në veçanti, nëse ne shikojmë në 4 pemëve në anën e djathtë - Unë do rrethit të tyre, këtu - këto pemë duken pothuajse tamam si një listë e lidhur. Çdo nyje ka vetëm një fëmijë, dhe kështu që ne nuk kemi ndonjë të kësaj strukture pemë-si që ne shohim, për shembull,  në këtë pemë një i vetmuar mbi këtu në të majtë e poshtme. Këto pemë janë quajtur fakt degjeneruar pemë binare, dhe ne do të flasim për këto më shumë në të ardhmen - veçanërisht në qoftë se ju shkoni për të marrë kurse të tjera shkenca kompjuterike. Këto pemë janë të degjeneruar. Ata nuk janë shumë të dobishme, sepse, në të vërtetë, kjo strukturë jep veten  të lookup herë ngjashme me atë të një liste të lidhura. Ne nuk do të marrë të përfitojnë nga memorie ekstra - ky tregues shtesë - për shkak të strukturës sonë të qenit i keq në këtë mënyrë. Në vend se të shkoni në dhe të nxjerrë jashtë pemë binare që kanë 9 në rrënjë, që është rasti i fundit që ne do të kemi, ne jemi në vend të kësaj, në këtë pikë, do të flasim pak për këtë afat tjetër që ne përdorim kur flasim për pemë, e cila quhet lartësia. 

Lartësia e një peme është distanca nga rrënja në nyjen më të largët, ose më mirë numrin e HOPS që ju do të keni për të bërë në mënyrë që të filluar nga rrënja dhe pastaj të përfundojë deri në nyjen më të largët në pemë. Nëse ne shikojmë në disa prej këtyre pemëve që ne i kemi tërhequr të drejtë këtu, ne mund të shohim se në qoftë se ne kemi marrë këtë pemë në këndin e sipërm të majtë dhe të fillojnë në 3, atëherë ne duhet të bëjmë hop 1 për të shkuar në 6, një hop të dytë për të marrë në 7, dhe një hop të tretë të marrë në 9. Pra, lartësia e kësaj peme është 3. Ne mund të bëjmë të njëjtin ushtrim për pemët e tjera të përcaktuara me këtë jeshile, dhe ne shohim se lartësia e të gjitha këtyre pemëve është gjithashtu me të vërtetë 3. Kjo është pjesë e asaj që i bën ata të degjeneruar - se lartësia e tyre është vetëm një më pak se numri i nyjeve në pemë të tërë. Nëse ne shikojmë në këtë pemë tjetër që është e rrethuar me të kuqe, në anën tjetër, ne shohim se më të largët nyjet fletë janë 6 dhe 9 - lë të qenit ato nyje që nuk kanë fëmijë. Pra, në mënyrë që të merrni nga nyjë rrënjë ose të e 6 apo 9, ne kemi për të bërë një hop të marrë në 7 dhe pastaj një hop të dytë për të marrë në 9, dhe gjithashtu, vetëm një hop të dytë nga 7 për të marrë në 6. Pra, lartësia e kësaj peme mbi këtu është vetëm 2. Ju mund të ktheheni mbrapsh dhe të bëjë që për të gjithë pemët e tjera që kemi diskutuar më parë duke filluar me 7 dhe 6, dhe ju do të gjeni se lartësia e të gjitha këtyre pemëve është gjithashtu 2. 

Arsyeja që ne kemi qenë duke folur në lidhje me pemë binare urdhëroi dhe pse ata janë të ftohtë është për shkak se ju mund të kërkoni me anë të tyre në një mënyrë shumë të ngjashme me kërkim për një grup të renditura. Kjo është ajo ku ne flasim në lidhje me marrjen në atë kohë të përmirësuar lookup mbi listën e thjeshtë lidhur. Me një listë e lidhur - në qoftë se ju doni të gjeni një element të veçantë - ju jeni në të mirë do të bëjë një lloj të kërkimit lineare ku të fillojë në fillim të një liste dhe hop një-nga-një - një nyje nga një nyje - nëpër gjithë listën derisa ju të gjeni çdo gjë që ju jeni në kërkim për të. Ndërsa, nëse ju keni një pemë binare që është ruajtur në këtë format bukur, të vërtetë ju mund të merrni më shumë një kërkim binar në vazhdim e sipër ku jeni përça dhe sundo dhe të kërkoni përmes gjysmën e duhur të pemës në çdo hap. Le të shohim se si punon. 

Nëse kemi - përsëri, duke shkuar prapa në pemë tonë origjinale - ne të fillojë në 7, ne kemi 3 në të majtë, 9 në të djathtë, dhe nën 3 ne kemi 6. Nëse ne duam të kërkoni për numrin 6 në këtë pemë, ne do të fillojë në rrënjë. Ne do të krahasojmë vlerën Ne jemi në kërkim për të, të themi 6, të vlerës ruajtur në nyjen që ne jemi aktualisht në kërkim në, 7, të gjeni se 6 është me të vërtetë më pak se 7, kështu që ne do të lëvizin në të majtë. Nëse vlera e 6 kishte qenë më i madh se 7, ne do të kemi lëvizur në vend të së drejtës. Që ne e dimë se - për shkak të strukturës së pemës urdhëruar tonë binar - të gjitha vlerave më pak se 7 do të ruhen në të majtë të 7, nuk ka nevojë të shqetësojë edhe duke kërkuar nëpër anën e djathtë të pemës. Pasi të kemi të lëvizin në të majtë dhe ne jemi tani në nyjen përmban 3, ne mund të bëjmë atë përsëri të njëjtën krahasim ku ne krahasojmë 3 dhe 6. Dhe ne kemi gjetur se ndërsa 6 - vlera ne jemi duke kërkuar për - është më i madh se 3, Ne mund të shkojnë në anën e djathtë të nyjeve përmban 3. Nuk ka anën e majtë këtu, kështu që ne mund të kemi injoruar atë. Por ne e dimë se vetëm për shkak se ne jemi duke kërkuar në pemë vetë, dhe ne mund të shohim se pema nuk ka fëmijë. 

Është gjithashtu shumë e lehtë për të parë deri 6 në këtë pemë, nëse ne jemi duke bërë atë veten si njerëzit, por le të ndjekim këtë proces mekanikisht si një kompjuter do të bëjë me të vërtetë kuptojnë algorithm. Në këtë pikë, ne jemi tani në kërkim në një nyje që përmban 6, dhe ne jemi duke kërkuar për vlerën 6, kështu, në të vërtetë, ne kemi gjetur nyjen e duhur. Ne kemi gjetur vlerën 6 në pemë tonë, dhe ne mund të ndalojë kërkimin tonë. Në këtë pikë, në varësi të asaj që po ndodh, ne mund të themi, po, ne kemi gjetur vlerën 6, ajo ekziston në pemë tonë. Ose, në qoftë se ne jeni duke planifikuar për të futur një nyje ose të bëjë diçka, ne mund të bëjmë që në këtë pikë. 

Le të bëjmë Lookups një çift shumë vetëm për të parë se si kjo funksionon. Le të shohim se çfarë ndodh në qoftë se ne do të përpiqemi dhe të kërkoni vlerën 10. Nëse ne do të shikojmë deri vlerën 10, ne do të fillojë në rrënjë. Ne do të shohim se 10 është më e madhe se 7, kështu që ne do të lëvizin në të djathtë. Ne do të marrë në 9 dhe 9 krahasuar me 10 dhe 9 të shihni se është me të vërtetë më pak se 10. Pra, përsëri, ne do të përpiqemi për të lëvizur në të djathtë. Por në këtë pikë, ne do të vini re se ne jemi në një nyje null. Nuk ka asgjë atje. Nuk ka asgjë ku duhet të jetë 10. Kjo është ajo ku ne mund të raportojnë dështimin - se nuk është me të vërtetë nuk ka 10 në pemë. Dhe së fundi, le të shkojnë nëpër rastin kur ne jemi duke u përpjekur për të parë deri 1 në pemë. Kjo është e ngjashme me atë që ndodh në qoftë se ne e shohim deri 10, përveç në vend për të shkuar në të djathtë, ne jemi duke shkuar për të shkuar në të majtë. Ne të fillojë në 7 dhe shihni se 1 është më pak se 7, kështu që ne të shkojë në të majtë. Ne kemi marrë në 3 dhe të shohim se 1 është më pak se 3, kështu që përsëri ne të përpiqemi për të lëvizur në të majtë. Në këtë pikë ne kemi një nyje null, kështu që ne mund të raportojnë përsëri dështim. 

Nëse ju dëshironi të mësoni më shumë rreth pemë binare, ka një bandë e tërë e problemeve të fun pak se ju mund të bëni me ta. Unë sugjeroj praktikuar vizatim nga këto diagrame një-nga-një dhe pas nëpër të gjitha hapat e ndryshme, sepse kjo do të vijë në dobishëm super- jo vetëm kur ju jeni duke bërë problemit encoding grup Huffman por edhe në kurset e ardhshme - vetëm të mësuarit se si për të nxjerrë jashtë këto struktura të dhënave dhe të mendojnë përmes problemeve me stilolaps dhe letër ose, në këtë rast, iPad dhe majë shkruese. 

Në këtë pikë edhe pse, ne jemi duke shkuar për të lëvizur për të bërë disa praktika kodim dhe në fakt të luajë me këto pemë binare dhe të shohim. Unë jam duke shkuar për të kaluar prapa mbi kompjuterin tim. Për këtë pjesë të seksionit, në vend të përdorimit të CS50 Run ose CS50 hapësira, Unë jam duke shkuar për të përdorur pajisjen. 

Pas së bashku me specifikimet Set Problem, Unë po të shoh se unë jam menduar për të hapur pajisjen, shkoni në Dropbox dosjen time, të krijojë një dosje të quajtur Seksioni 7, dhe pastaj të krijojë një skedar të quajtur binary_tree.c. Këtu ne do të shkojmë. Unë kam marrë tashmë aplikim hapur. Unë jam duke shkuar të tërheqë një terminal. Unë jam duke shkuar për të shkuar në dosje Dropbox, të bëjë një direktori të quajtur section7, dhe të shohim se ajo është krejtësisht bosh. Tani unë jam duke shkuar për të hapur deri binary_tree.c. Mirë. Këtu ne do të shkojmë - skedar bosh. 

Le të kthehemi në specifikimet. Specifikimi i kërkon për të krijuar një përkufizim të ri tip për një nyje binar pemë permban vlerat int - ashtu si vlerat që nxori në diagramimin tonë përpara. Ne jemi duke shkuar për të përdorur këtë Boilerplate typedef që ne i kemi bërë të drejtë këtu që ju duhet të njohin nga Set Problem 5 - në qoftë se ju e bëri rrugën tabelë hash të programit pushtues speller. Ju gjithashtu duhet të njohin atë nga neni javës së kaluar ku kemi biseduar për listat e lidhura. Ne kemi marrë këtë typedef i një nyje struct, dhe ne kemi dhënë këtë nyje struct këtë emër e nyjeve struct parë kështu që ne mund të pastaj i referohen asaj që ne do të duan të kenë pointers nyjen struct si pjesë e struct tonë, por ne kemi pas rrethuar këtë - ose më mirë, mbyllur këtë - në një typedef në mënyrë që, më vonë në kod ne mund t'i referohemi në këtë struct si vetëm një nyje në vend të një nyje struct. 

Kjo do të jetë shumë i ngjashëm me përkufizimin e veçmas të lidhur listës që pamë javën e kaluar. Për ta bërë këtë, le të fillojë vetëm me shkrim nga Boilerplate. Ne e dimë se ne duhet të kemi një vlerë numër të plotë, kështu që ne do të vënë në vlerën e int, dhe pastaj në vend të vetëm një tregues për elementin e ardhshëm - si ne e bëmë me-veçmas të lidhura listat - ne do të kemi pointers majtë dhe të djathtë të fëmijës. Kjo është shumë e shumë e thjeshtë - struct fëmija nyje * majtë; dhe struct * nyja fëmija i drejtë;. Cool. Kjo duket si një fillim mjaft të mirë. Le të kthehemi në specifikimet. 

Tani ne duhet të deklarojë një ndryshore globale * nyje për rrënjët e një pemë. Ne jemi duke shkuar për të bërë këtë globale ashtu si kemi bërë treguesin e parë në listën tonë lidhet edhe globale. Kjo ishte mënyrë që në funksionet që kemi shkruar ne nuk kemi për të mbajtur kaluar rreth kësaj rrënjë - edhe pse ne do të shohim se në qoftë se ju nuk doni të shkruani këto funksione Recursively, ajo mund të jetë më mirë që të mos kalojë edhe atë rreth si një globale në vendin e parë dhe në vend nisja atë në nivel lokal në funksion tuaj kryesor. Por, ne do të bëjmë atë në nivel global për të filluar. Përsëri, ne do të japim një çift të hapësirave, dhe unë jam duke shkuar për të deklaruar një rrënjë nyje *. Vetëm për t'u siguruar që unë nuk e lënë këtë uninitialized, unë jam duke shkuar për të vendosur atë të barabartë null. Tani, në funksion kryesor - të cilat ne do të shkruaj vërtetë shpejt drejtë këtu - int kryesore (int argc, const char * argv []) - dhe unë jam duke shkuar për të filluar deklaruar array tim argv si const vetëm kështu që unë e di se këto argumente janë argumente që unë ndoshta nuk dëshironi të modifikoni. Në qoftë se unë dua të modifikojë ato që unë ndoshta duhet të jetë bërë kopje të tyre. Ju do të shihni këtë shumë në kodin. Kjo është në rregull ose mënyrë. Kjo është në rregull për të lënë atë si - heq const në qoftë se ju dëshironi. Unë zakonisht e vënë atë në vetëm kështu që unë kujtoj veten  që unë ndoshta nuk dëshironi të modifikoni ato argumente. 

Si gjithmonë, unë jam duke shkuar për të përfshirë këtë linjë 0 kthimit në fund të kryesore. Ja, unë do të nisja nyjen time rrënjë. Siç qëndron tani, unë kam marrë një tregues që është vendosur për të pavlefshëm, kështu që është vënë në asgjë. Në mënyrë që në fakt të fillojë ndërtimin e nyje, Unë së pari duhet të siguroj kujtesë për të. Unë jam duke shkuar për të bërë këtë duke bërë memorie në tog përdorur malloc. Unë jam duke shkuar për të vendosur rrënjë të barabartë me rezultat malloc, dhe unë jam duke shkuar për të përdorur operatorin sizeof për të llogaritur madhësinë e një nyje. Arsyeja që unë e përdor nyjen sizeof në krahasim me, të themi, bërë diçka si kjo - malloc (4 + 4 + 4) ose malloc 12 - është sepse unë dua kodi im të jetë si në përputhje të jetë e mundur. Unë dua të jem në gjendje për të marrë këtë skedar. C, përpiloni atë në aplikim, dhe pastaj përpilojnë atë në Mac 64-bit time - ose në një arkitekturë krejtësisht të ndryshme - dhe unë dua që kjo të gjithë të punojnë të njëjtën gjë. 

Nëse unë jam duke e bërë supozime në lidhje me madhësinë e variablave - madhësia e një int apo madhësinë e një akrep - atëherë unë jam bërë edhe supozime në lidhje me llojet e arkitekturave në të cilën kodi im mund me sukses të përpilojë kur ekzekutohet. Gjithmonë përdorni sizeof në krahasim me dorë mbledhur fushat struct. Arsyeja tjetër është se nuk mund të jetë gjithashtu mbushje që përpiluesi i vë në struct. Edhe vetëm mbledhur fushat individuale nuk është diçka që ju zakonisht dëshironi të bëni, kështu, fshini atë linjë. Tani, me të vërtetë nisja këtë nyjë rrënjë, Unë do të duhet të vihet në prizë vlera për secilin nga fusha të ndryshme të saj. Për shembull, për vlerën që unë e di unë dua të nisja në 7, dhe tani për tani unë jam duke shkuar për të vendosur fëmijën e majtë të jetë e pavlefshme dhe fëmijës të drejtën të jetë gjithashtu null. E madhe! Ne kemi bërë atë pjesë të spec. 

Specifikimi poshtë në fund të faqes 3 pyet mua për të krijuar tre nyjet më të - një që përmban 3, një përmban 6, dhe një me 9 - dhe pastaj ato tela kështu që duket tamam si diagramin tonë pemë se ne ishim duke folur në lidhje me parë. Le të bëjmë që shumë shpejt këtu. Ju do të shihni të vërtetë shpejt që unë jam duke shkuar për të filloni të shkruani një bandë të kodit kopjuar. Unë jam duke shkuar për të krijuar një * nyje dhe unë jam duke shkuar për të thirrur atë tre. Unë jam duke shkuar për të vendosur atë barabartë me malloc (sizeof (nyje)). Unë jam duke shkuar për të vendosur tri-> vlera = 3. Tre -> left_child = NULL; tre -> drejta _child = NULL; si. Kjo duket goxha i ngjashëm me fillimin e rrënjë, dhe kjo është pikërisht ajo që Unë do të duhet të bëni në qoftë se unë të fillojë Initializing 6 dhe 9 si. Unë do të bëj që me të vërtetë të shpejtë këtu - në fakt, unë jam duke shkuar për të bërë një kopje pak dhe paste, dhe sigurohuni se unë - mirë.  Tani, unë kam marrë atë kopjohen dhe unë mund të shkoni përpara dhe të vendosur këtë barabartë me 6. Ju mund të shihni se kjo merr kohë dhe nuk është super-efikas. Në vetëm pak, ne do të shkruajnë një funksion që do të bëjë këtë për ne. Unë dua të zëvendësuar këtë me një 9, të zëvendësojë atë me një 6. 

Tani ne kemi marrë të gjitha nyjet tona krijuar dhe initialized. Ne kemi marrë rrënja jonë vendosur barabartë me 7, apo që përmbajnë vlerën 7, nyja jonë përmban 3, nyja jonë përmban 6, dhe nyja jonë përmban 9. Në këtë pikë, të gjithë ne duhet të bëni është gjithçka tela lart. Arsyeja që unë initialized gjitha pointers null është vetëm mënyrë që unë bëni të sigurtë që Unë nuk kam ndonjë pointers uninitialized në atje nga aksident. Dhe gjithashtu që, në këtë pikë, unë vetëm duhet të vërtetë lidhë nyjet me njëri-tjetrin - për ato që ata janë të lidhur në fakt për - unë nuk kam për të shkuar deri dhe të bëjë Sigurohuni që të gjitha nulls janë në atje në vendet e duhura. 

Duke filluar në rrënjë, unë e di që fëmija majtë rrënja është 3. Unë e di që fëmija të drejtë rrënja është 9. Pas kësaj, i vetmi fëmijë tjetër që unë kam lënë për t'u shqetësuar rreth është fëmijë drejtë 3-së, e cila është 6. Në këtë pikë, të gjithë duket goxha e mirë. Ne do të fshini disa nga këto linja. Tani gjithçka duket goxha e mirë. Le të kthehemi në specifikim tonë dhe të shohim se çfarë ne duhet të bëjmë tjetër. 

Në këtë pikë, ne kemi për të shkruar një funksion të quajtur "përmban ' me një prototip të 'përmban bool (int vlera) ". Dhe kjo përmban funksion do të kthehen e vërtetë  në qoftë se pema theksuar me ndryshore globale tonë rrënjë  përmban vlerën kaluar në funksion dhe të rreme ndryshe. Le të shkojnë përpara dhe të bëjë atë. Kjo do të jetë pikërisht si lookup që kemi bërë me dorë në iPad vetëm pak më parë. Le të zoom prapa në pak dhe lëvizni lart. Ne jemi duke shkuar për të vënë këtë funksion drejtë mbi funksioni ynë kryesor kështu që ne nuk duhet të bëjmë çdo lloj prototyping. Pra, bool përmban (int vlera). Nuk shkojmë. Ka deklarata tonë Boilerplate. Vetëm për të bërë të sigurtë që kjo do të hartojë, Unë jam duke shkuar për të shkuar përpara dhe të vendosur vetëm atë të barabartë për t'u kthyer rreme. Tani për tani ky funksion thjesht nuk do të bëjë asgjë dhe gjithmonë raportojnë se vlera që ne jemi duke kërkuar për nuk është në pemë. 

Në këtë pikë, ajo është ndoshta një ide e mirë - që ne kemi shkruar një bandë e tërë të kodit dhe ne nuk kemi provuar edhe testimin e tij ende - për të siguruar që të gjitha harton. Ka disa gjëra që ne duhet të bëni për të siguruar që kjo vërtetë do të përpilojnë. Së pari, të shohim nëse ne kemi qenë duke përdorur ndonjë funksion në çdo bibliotekave që ne nuk kemi përfshirë ende. Funksionet ne kemi përdorur deri tani janë malloc, dhe pastaj ne kemi qenë gjithashtu duke përdorur këtë lloj - këtë lloj nonstandard quajtur 'bool' - i cili është i përfshirë në dosjen standarde header bool. Ne patjetër duan të përfshijnë bool.h standarde për llojin bool, dhe ne gjithashtu duam të përfshijë # lib.h standarde për bibliotekat standarde që përfshijnë malloc, dhe të lirë, dhe të gjithë se. Pra, zoom out, ne jemi duke shkuar për të lënë. Le të përpiqen dhe të sigurohemi se ky fakt e bëri përpiloni. Ne e shohim se ai bën, kështu që ne jemi në rrugën e duhur. 

Le të hapë binary_tree.c përsëri. Ai përpilon. Le të shkojnë poshtë dhe të sigurohemi që kemi futur disa thirrje të funksionit përmban tonë - vetëm për të siguruar se kjo është e gjitha mirë dhe të mirë. Për shembull, kur ne e bëmë disa Lookups në pemë tonë më herët, Ne u përpoq të shikoni vlerat 6, 10, dhe 1, dhe ne e dinim se ishte 6 në pemë, 10 nuk ishte në pemë, dhe 1 nuk ishte në pemë ose. Le të përdorim këto thirrje mostër, si një mënyrë për të kuptoj se nëse apo jo Funksioni përmban jonë është duke punuar. Në mënyrë që të bëni këtë, unë jam duke shkuar për të përdorur funksionin printf, dhe ne jemi duke shkuar për të shtypura nga rezultatet e thirrjes për të përmban. Unë jam duke shkuar për të vënë në një varg "përmban (% d) = sepse  ne jemi duke shkuar për të plug në vlerën që ne jemi duke shkuar për të kërkuar, dhe =% s \ n "dhe se si të përdorin vargun tonë format. Ne jemi vetëm duke shkuar për të parë - fjalë për fjalë të shtypura jashtë në ekran - ajo që duket si një thirrje të funksionit. Kjo nuk është në fakt thirrjen funksion.  Kjo është vetëm një varg i projektuar për të duken si një thirrje të funksionit. 

Tani, ne jemi duke shkuar për të vihet në prizë vlerat. Ne jemi duke shkuar për të provoni përmban më 6, dhe pastaj ajo që ne jemi duke shkuar për të bërë këtu është të përdorin atë operatori treshe. Le të shohim - përmban 6 - Pra, tani unë kam përmbante 6 dhe nëse përmban 6 është e vërtetë, vargu që ne jemi duke shkuar për të dërguar të karakterit të% s format do të jetë vargu "e vërtetë". Le të lëvizni mbi një pak. Përndryshe, ne duam të dërgoni string "false" nëse përmban 6 kthimit të rreme. Kjo është pak budalla-looking, por unë kuptoj unë mund edhe të ilustruar çfarë Operatori tresh duket pasi ne nuk kemi parë atë për pak kohë. Kjo do të jetë një e mirë, dobishëm mënyrë që të kuptoj se në qoftë se funksioni përmban ynë është duke punuar. Unë jam duke shkuar për të lëvizni përsëri mbi të majtë, dhe unë jam duke shkuar për të kopjoni dhe ngjisni këtë linjë disa herë. Ajo ndryshoi disa prej këtyre vlerave rreth, kështu që kjo do të jetë 1, dhe kjo do të jetë 10. 

Në këtë pikë ne kemi marrë një funksion të mirë përmban. Ne kemi marrë disa teste, dhe ne do të shohim nëse kjo të gjitha veprat. Në këtë pikë ne e kemi shkruar kodin disa më shumë. Koha për të lënë jashtë dhe të sigurohemi që çdo gjë ende përpilon. Quit jashtë, dhe tani le të përpiqemi të bërë dru binar përsëri. E pra, kjo duket si ne kemi marrë një gabim, dhe ne kemi marrë këtë në mënyrë eksplicite duke deklaruar funksionin e bibliotekës printf. Ajo duket si ne kemi nevojë për të shkuar në dhe # include standardio.h. Dhe me këtë, çdo gjë duhet të përpiloni. Ne jemi të gjithë të mirë. Tani le të përpiqemi drejtimin pemë binare dhe shikoni se çfarë ndodh. Këtu jemi,. / Binary_tree, dhe ne shohim se, siç kemi pritur - sepse ne nuk kemi zbatuar përmban ende, ose më mirë, ne kemi vënë vetëm në këmbim të rremë - ne e shohim se ajo është vetëm kthimin e rreme për të gjithë ata, kështu që është e gjitha që punojnë për pjesën më të madhe mjaft mirë. 

Le të kthehemi në dhe në fakt përmban zbatuar në këtë pikë. Unë jam duke shkuar për të lëvizni poshtë, zoom në, dhe - Mos harroni, algoritmi që kemi përdorur ka qenë se kemi filluar në nyjen rrënjë dhe pastaj në çdo nyje që hasim, ne bëjmë një krahasim, dhe bazuar në këtë krahasim, ne ose të shkojë në fëmijën e majtë ose të djathtë të fëmijës. Kjo do të duken shumë të ngjashme me kodin kërkim dyor që ka shkruar në fillim të mandatit. Kur ne nisem, ne e dimë që ne duam për të mbajtur në nyjen e tanishme se ne duke kërkuar në, dhe nyja aktual do të jetë initialized të nyjes root. Dhe tani, ne jemi duke shkuar për të mbajtur të shkojnë nëpër pemë, dhe mos harroni se gjendjen tonë ndalimi -  kur ne fakt punuar përmes shembullit me dorë - ishte kur kemi hasur në një nyje null, kur nuk kemi shikuar në një fëmijë null, por, kur ne fakt shkoi në një nyje në pemë dhe gjeti se ne jemi në një nyje null. Ne jemi duke shkuar për të iterate deri cur nuk është e barabartë me null. Dhe çfarë do të bëjmë ne? Ne jemi duke shkuar për të provuar nëse (tani -> vlera == vlera), atëherë ne e dimë se e kemi gjetur në fakt nyja që ne jemi duke kërkuar për të. Kështu që këtu, ne mund të kthehen vërtetë. Përndryshe, ne duam të shohim nëse janë apo jo vlera është më e vogël se vlera. Nëse vlera nyjen aktual është më pak se vlera ne jemi duke kërkuar për të, ne jemi duke shkuar për të lëvizur në të djathtë. Pra, cur = cur -> right_child, dhe ndryshe, ne jemi duke shkuar për të lëvizur në të majtë. = cur momen -> left_child;. Shumë e thjeshtë. 

Ju ndoshta e njeh lak që duket shumë e ngjashme me këtë nga kërkim dyor herët në afat, përveç atëherë ne u bëjmë me të, në mes të ulët dhe të lartë. Këtu, ne vetëm duhet të shikoni në një vlerë aktuale, kështu që është e bukur dhe e thjeshtë. Le të sigurohemi ky kod është duke punuar. Së pari, sigurohuni që ajo harton. Duket si ajo bën. Le të provoni drejtimin e tij. Dhe me të vërtetë, ajo shtyp gjithçka që kemi pritur. Ajo gjen 6 në pemë, nuk ka gjetur 10 sepse 10 nuk është në pemë, dhe nuk ka gjetur as 1 1, sepse nuk është edhe në pemë. Cool stuff. 

Mirë. Le të kthehemi në specifikim tonë dhe të shohim se ç'pritet më tej. Tani, ajo dëshiron për të shtuar nyje disa më shumë për të pemës tonë. Ajo dëshiron të shtojë 5, 2 dhe 8, dhe sigurohuni që përmban kodin tonë ende punon ashtu siç pritet. Le të shkojë të bëjë këtë. Në këtë pikë, në vend se duke bërë atë kopje bezdisshëm dhe paste përsëri, le të shkruajnë një funksion të vërtetë të krijuar një nyje. Nëse ne lëvizni poshtë të gjitha mënyra për të kryesore, shohim se ne kemi qenë bërë këtë Kodi shumë të ngjashme pushim çdo herë që ne duam të krijuar një nyje. 

Le të shkruajnë një funksion që në të vërtetë do të ndërtojë një nyje për ne dhe ta kthejë atë. Unë jam duke shkuar për të thirrur atë build_node. Unë jam duke shkuar për të ndërtuar një nyje me një vlerë të veçantë. Zoom në këtu. Gjëja e parë që unë jam duke shkuar për të bërë është në fakt krijojnë hapësirë ​​për nyjen në tog. Pra, nyje * n = malloc (sizeof (nyje)); n -> vlera = Vlera; dhe pastaj këtu, unë jam vetëm do të nisja të gjitha fushat të jenë vlerat e duhura. Dhe në fund, ne do të kthehen nyjen tonë. Mirë. Një gjë të theksohet është se ky funksion drejtë këtu do të kthehen një tregues për kujtesën që ka qenë tog-ndau. Çfarë është e mirë për këtë është se kjo nyja tani - ne duhet të deklarojnë atë në grumbull, sepse nëse ne shpalli atë në rafte ne nuk do të jetë në gjendje të bëjë atë në këtë funksion si kjo. Se kujtesa do të shkojnë jashtë fushës dhe do të jetë i pavlefshëm në qoftë se ne u përpoq për të hyrë në atë më vonë. Që ne jemi deklaruar tog-ndahen kujtesës, ne do të duhet të kujdeset për të liruar atë më vonë për programin tonë të mos rrjedhje ndonjë kujtesës. Ne kemi qenë në punting se për çdo gjë tjetër në kodin vetëm për hir të thjeshtësisë në atë kohë, por në qoftë se keni shkruar një funksion që duket si ky ku ju keni marrë - disa e quajnë atë një malloc ose realloc brenda - ju doni të bëni të sigurtë që ju të vënë disa lloj komenti deri këtu që thotë, hej, ju e dini, kthen një nyje tog-alokohen nisur me vlerën kaloi-në. Dhe pastaj ju doni të bëni të sigurtë që ju të vënë në disa lloj shënim që thotë se thirrësi duhet të lirojë kujtesën kthyer. Në këtë mënyrë, nëse dikush ndonjëherë shkon dhe e përdor atë funksion, ata e dinë se çfarëdo që ata marrin nga mbrapa atë funksion në disa pika do të duhet të lirohen. 

Duke supozuar se të gjitha është e mirë dhe të mirë këtu, ne mund të shkojnë poshtë në kodin tonë dhe të zëvendësojë të gjitha këto rreshta të drejtë këtu me thirrjet për të ndërtuar funksionin tonë nyjeve. Le të bëjmë që me të vërtetë shpejt. Një pjesë që ne nuk jemi duke shkuar për të zëvendësuar është kjo pjesë këtu poshtë në fund, ku ne fakt tela deri nyjet për pikë me njëri-tjetrin, për shkak se ne nuk mund të bëjmë në funksion tonë. Por, le bëjë rrënjë = build_node (7); nyje * tre = build_node (3); nyje * gjashtë = build_node (6); nyje * nëntë = build_node (9);. Dhe tani, ne gjithashtu donte për të shtuar nyje për - nyje * pesë = build_node (5); nyje * tetë = build_node (8); dhe çfarë ishte nyja tjetër? Le të shohim këtu. Ne kemi kërkuar të shtoni edhe një 2 - nyje * dy = build_node (2);. Mirë. Në këtë pikë, ne e dimë se ne kemi marrë 7, 3, 9, dhe 6 gjitha Wired në mënyrë të përshtatshme, por ajo që për 5, 8, dhe 2? Të mbajë çdo gjë në mënyrë të duhur, ne e dimë se fëmija drejta Tre është 6. Pra, në qoftë se ne jemi duke shkuar për të shtuar 5, e 5 edhe i takon në anën e djathtë të pemës e cila është rrënja 3, aq 5 i takon si fëmijën e majtë të 6. Ne mund ta bëjë këtë duke thënë, gjashtë -> left_child = pesë; dhe pastaj 8 takon si fëmijën e majtë të 9, kështu nëntë -> left_child = tetë; dhe pastaj 2 është fëmija i majtë i 3, kështu që ne mund të bëjmë që deri këtu - ty -> left_child = dy;. Nëse ju nuk e keni mjaft të ndjekin së bashku me këtë, unë sugjeroj që ju tërheq atë vetë. 

Mirë. Le të shpëtuar këtë. Le të shkojnë jashtë dhe sigurohuni që ajo harton, dhe pastaj ne mund të shtoni në thirrjet përmban tona. Duket si çdo gjë ende përpilon. Le të shkojnë në dhe të shtoni në disa përmban thirrje. Përsëri, unë jam duke shkuar për të bërë një pak të kopjoni dhe ngjisni. Tani le të kërkoni për 5, 8, dhe 2. Mirë. Le të sigurohemi që e gjithë kjo duket e mirë ende. E madhe! Ruaj dhe u largua. Tani le të bëjnë, hartojnë, dhe tani le të kandidojë. Nga rezultatet, duket se çdo gjë është duke punuar vetëm mirë dhe të mirë. E madhe! Deri tani ne kemi marrë përmban tona funksionojnë me shkrim. Le të lëvizin dhe të fillojë të punojë mbi atë se si për të futur nyjet në pemë që, si ne jemi duke bërë atë të drejtë tani, gjërat nuk janë shumë të bukur. 

Nëse ne do të shkojmë përsëri në specifikim, ajo na kërkon për të shkruar një funksion të quajtur futur - përsëri, duke u kthyer një bool për të nëse janë apo jo ne fakt mund të futni nyja në pemë - dhe pastaj vlera për të futur në pemë është specifikuar si Argumenti i vetëm për funksionin tonë insert. Ne do të kthehen vërtetë në qoftë se ne mund të vërtetë të futur vlera nyje përmban në pemë, që do të thotë se ne, një, kishte kujtesë të mjaftueshme, dhe pastaj dy, se nyja nuk ekzistojnë në pemë prej - Mos harroni, ne nuk do të kemi vlera të kopjuar në pemë, vetëm për të bërë gjëra të thjeshta. Mirë. Kthehu në kodin. Hapur atë. Zoom në një grimë, pastaj lëviz poshtë. Le të vënë funksionin insert mbi të drejtën përmban. Përsëri, ajo do të quhet insert bool (int vlera). T'i jepte një hapësirë ​​pak më shumë, dhe pastaj, si parazgjedhje, le të vënë në këmbim të rreme në fund. Tani poshtë në fund, le të shkojnë përpara dhe në vend të manualisht ndërtimin e nyjet në kryesore veten dhe instalime elektrike deri në ato tregojnë për njëri-tjetrin si ne jemi duke bërë, ne do të mbështetemi në funksion tonë të shkruaj për të bërë këtë. Ne nuk do të mbështetet në funksion tonë të shkruaj për të ndërtuar pemën gjithë nga e para vetëm ende, por ne do të të hequr qafe të këtyre linjave - we'll komentuar nga këto linja - që të ndërtojë nyjet 5, 8, dhe 2. Dhe në vend, ne do të futur thirrje të funksionojë tonë futur për të siguruar se që në fakt funksionon. Këtu ne do të shkojmë. 

Tani ne kemi komentuar këto linja. Ne kemi vetëm 7, 3, 9, dhe 6 në pemë tonë në këtë pikë. Për të bërë të sigurt se kjo është e gjitha duke punuar, ne mund të zoom jashtë, të bëjë pemë binare tonë, drejtuar atë, dhe ne mund të shohim se përmban tani është duke na thënë se ne jemi plotësisht të drejtë - 5, 8, dhe 2 nuk janë më në pema. Kthehu mbrapa në kodin, dhe si jemi duke shkuar për të futur? Mbani mend se çfarë kemi bërë kur ishim futur në fakt 5, 8, 2 dhe më parë. Ne kemi luajtur atë lojë Plinko ku kemi filluar në rrënjë, zbriti në një pemë nga një nga një derisa kemi gjetur hendekun e duhur, dhe pastaj ne Wired në nyje në vendin e duhur. Ne jemi duke shkuar për të bërë të njëjtën gjë. Kjo është në thelb si shkrim kodin që kemi përdorur në funksion përmban për të gjetur vendin ku duhet të jetë nyje, dhe pastaj ne jemi vetëm duke shkuar për të futur në nyjen e drejtë atje. Le të fillojnë të bëjnë këtë. 

Pra, ne kemi një nyje * cur = root, ne jemi vetëm do të ndjekin përmban kodin deri sa të gjejmë se ai nuk ka mjaft të punojnë për ne. Ne jemi duke shkuar për të shkuar nëpër pemë, ndërsa elementi aktual nuk është i pavlefshëm, dhe në qoftë se ne gjejmë vlera se mar-së është e barabartë me vlerën që ne jemi duke u përpjekur për të futur - mirë, kjo është një nga rastet në të cilat ne nuk mund të vërtetë të futur nyjen në pemë, sepse kjo do të thotë që ne kemi një vlerë të kopjuar. Këtu ne jemi të vërtetë do të kthehen rreme. Tani tjetër, në qoftë se vlera e monedhes është më pak se vlera, tani ne e dimë se kemi lëvizur në të djathtë  sepse vlera e takon në gjysmën e djathtë të pemës monedhes. Përndryshe, ne jemi duke shkuar për të lëvizur në të majtë. Kjo është në thelb përmban tona funksionojë drejtë atje. 

Në këtë pikë, pasi ne kemi përfunduar këtë lak, ndërsa, akrep tonë cur do të jetë duke treguar null Nëse funksioni nuk është kthyer tashmë. Prandaj, ne jemi të paturit e situ në vendin ku ne duam të futur nyjen e re. Ajo që mbetet për t'u bërë është që në fakt të ndërtuar nyjen e re, të cilat ne mund të bëjmë shumë lehtë. Ne mund të përdorim super-dobishëm funksionin jonë ndërtuar nyje, dhe diçka që ne nuk e ka bërë më parë - ne vetëm lloj i mori për të dhënë, por tani ne do të bëjmë vetëm për të siguruar - ne do të provuar për të siguruar që vlera e kthyer nga nyja e re ishte në të vërtetë Nuk null, sepse ne nuk duam të fillojë qasjen atë memorie në qoftë se është i pavlefshëm. Ne mund të provoni të bëni të sigurtë që nyja e re nuk është e barabartë me null. Ose në vend, ne vetëm mund të shohim nëse ajo vërtetë është i pavlefshëm, dhe në qoftë se ai është i pavlefshëm, atëherë ne vetëm mund të kthehen rreme herët. 

Në këtë pikë, ne duhet të tela nyje të re në vend të saj të duhur në pemë. Nëse ne shikojmë prapa në kryesore dhe ku ne ishim të vërtetë instalime elektrike në vlerat më parë, ne shohim se mënyra se si ne po e bëjmë këtë, kur ne të kërkuar për të vënë 3 në pemë ishte ne disponim fëmijën e majtë të rrënjë. Kur ne kemi vënë 9 në pemë, kemi pasur për të hyrë në të drejtën e fëmijës rrënjë. Ne duhet të kishte një tregues të prindit në mënyrë për të vënë një vlerë të re në pemë. Scroll back up për të futur, se nuk do të mjaft të punojnë këtu sepse ne nuk kemi një tregues prind. Ajo që ne duam të jetë në gjendje të bëni është, në këtë pikë, kontrolloni vlerën e prindërve dhe të shohim - mirë, Gosh, në qoftë se vlera e prindërve është më pak se vlera e tanishme, atëherë fëmija e drejta e prindit duhet të jetë nyja e re; ndryshe, fëmija e majtë e prindërve duhet të jetë nyja e re. Por, ne nuk kemi këtë treguesin prind mjaft ende. 

Në mënyrë për të marrë atë, ne jemi në të vërtetë do të duhet për të gjetur atë si të shkojmë nëpër pemë dhe për të gjetur vendin e duhur në lak tonë më sipër. Ne mund të bëjmë që nga Scroll mbrapa deri në krye të funksionit tonë futur dhe ndjekja e një ndryshore tregues quhet prind. Ne jemi duke shkuar për të vendosur atë të barabartë me null fillimisht, dhe pastaj çdo herë ne do të shkojmë nëpër pemë, ne jemi duke shkuar për të vendosur treguesin prind për ndeshjen treguesin aktual. Set prind të barabartë me monedhes. Në këtë mënyrë, çdo herë që ne të shkojnë nëpër, ne jemi duke shkuar për të siguruar që, si tregues i tanishëm merr incremented tregues prind ndjek atë - vetëm një nivel më të lartë se sa treguesin e tanishme në pemë. Që të gjithë duket goxha e mirë. 

Unë mendoj se një gjë që ne do të duan për të rregulluar këtë është ndërtuar null nyje kthyer. Në mënyrë që të marrë të ndërtuar nyje të vërtetë sukses kthehen null, ne do të duhet të modifikojë atë kod, sepse këtu, nuk kemi testuar për të siguruar që malloc kthyer një tregues të vlefshëm. Pra, në qoftë se (n = NULL!), Atëherë - nëse malloc kthyer një tregues të vlefshëm, atëherë ne do të nisja atë; Përndryshe, ne vetëm do të kthehen dhe që do të përfundojë deri në kthimin null për ne. Tani të gjitha duket goxha e mirë. Le t'u siguruar që kjo në fakt përpilon. Të bëjë pemë binare, dhe oh, ne kemi marrë disa sende po ndodh këtu. 

Ne kemi marrë një deklaratë të nënkuptuar e funksionit të ndërtuar nyje. Përsëri, me këto hartuesit, ne jemi duke shkuar për të filluar në krye. Se çka duhet të them është se unë jam duke e quajtur nyje të ndërtuar para se unë kam deklaruar në fakt atë. Le të kthehemi në kodin vërtetë shpejt. Shkoni poshtë, dhe pa dyshim, funksioni im insert është shpallur mbi nyjen funksionit të ndërtuar, por unë jam duke u përpjekur për të përdorur të ndërtuar në brendësi të futur nyje. Unë jam duke shkuar për të shkuar në dhe kopje - dhe pastaj paste funksion nyje të ndërtuar rrugë këtu në krye. Në këtë mënyrë, shpresojmë që do të punojnë. Le të japim këtë një tjetër të shkojnë. Tani të gjitha harton. Të gjitha është e mirë. 

Por në këtë pikë, nuk kemi të vërtetë quhet funksionin tonë insert. Ne vetëm e di se ai përpilon, kështu që le të shkojnë në dhe të vënë disa telefonata in Le të bëjmë që në funksion tonë kryesore. Këtu, ne komentoi nga 5, 8, dhe 2, dhe pastaj ne nuk teli tyre deri këtu poshtë. Le të bëjë disa thirrje për të futur, dhe le të përdorë gjithashtu edhe të njëjtin lloj gjëra që ne e përdorur kur kemi bërë këto thirrje printf për t'u siguruar se çdo gjë e kam marrë futur siç duhet. Unë jam duke shkuar për të kopjoni dhe ngjisni, dhe në vend të përmban, ne do të bëjmë futur. Dhe në vend të 6, 10, dhe 1, ne jemi duke shkuar për të përdorur 5, 8, dhe 2. Kjo duhet të shpresojmë insert 5, 8, 2 dhe në pemë. Përpiloni. Të gjitha është e mirë. Tani ne do të vërtetë të drejtuar programin tonë. 

Gjithçka u kthye rreme. Pra, 5, 8, dhe 2 nuk shkojnë, dhe kjo duket si Përmban nuk i gjente ato ose. Çfarë po ndodh? Le të zoom jashtë. Problemi i parë ishte se insert dukej të kthehen rreme, dhe kjo duket si kjo është për shkak se ne e kemi lënë në thirrjen tonë kthimit të rreme, dhe nuk jemi kthyer në fakt e vërtetë. Ne mund të përcaktuar se deri. Problemi i dytë është, tani edhe në qoftë se ne bëjmë - të shpëtuar këtë, lë këtë, drejtuar të bëjë përsëri, e kanë atë të hartojnë, pastaj të drejtuar atë - ne shohim se diçka tjetër ka ndodhur këtu. E 5, 8, dhe 2 u gjetën kurrë nuk ende në pemë. Pra, çfarë po ndodh? 

Le të marrin një vështrim në këtë në kodin. Le të shohim nëse ne mund të kuptoj këtë. Ne fillim me prind mos qenë null. Ne kemi vendosur treguesin aktuale të barabartë me treguesin rrënjë, dhe ne jemi duke shkuar për të punuar rrugën tonë poshtë nëpër pemë. Nëse nyjen e tanishme nuk është i pavlefshëm, atëherë ne e dimë se ne mund të lëvizin poshtë pak. Ne kemi vendosur treguesin tonë mëmë të jetë e barabartë me treguesin e tanishme, kontrolluar vlerën - nëse vlerat janë të njëjta kthyem rreme. Nëse vlerat janë më pak kemi lëvizur në të djathtë; ndryshe, kemi lëvizur në të majtë. Pastaj ne kemi ndërtuar një nyje. Unë do të zoom në një pak. Dhe këtu, ne do të përpiqemi për të wire deri vlerat të jenë të njëjta. Çfarë po ndodh? Le të shohim nëse ndoshta Shprehje mund të na jepni një aluzion. 

Më pëlqen të përdorin Shprehje vetëm për shkak Shprehje vërtetë shpejt shkon dhe ju tregon se në qoftë se ka ndonjë gabim kujtesës. Kur kemi drejtuar Shprehje në kodin, si ju mund të shihni të drejtë here--Valgrind./binary_tree--and hit enter. Ju shihni se ne nuk kemi asnjë gabim kujtesës, kështu që ajo duket si çdo gjë është në rregull deri tani. Ne kemi disa rrjedhjet e kujtesës, të cilat ne e dimë, sepse ne nuk jemi ndodh për të liruar ndonjë nga nyjet tona. Le të përpiqemi drejtimin gdb për të parë se çfarë është në të vërtetë ndodh. Ne do të bëjmë gdb. / Binary_tree. Ajo booted deri just fine. Le të vendosur një pikë pushim në insert. Le të drejtuar. Ajo duket si ne nuk të vërtetë quhet insert. Ajo duket si problemi ishte vetëm se kur kam ndryshuar këtu poshtë në kryesore - të gjitha këto thirrje printf nga përmban - Unë kurrë nuk e ndryshoi në fakt këto të thirrur futur. Tani le t'i jepte një provoni. Le të përpilojnë. Të gjitha duket e mirë atje. Tani le të përpiqemi drejtimin e tij, shikoni se çfarë ndodh. Mirë! Çdo gjë duket goxha e mirë atje. 

Gjëja e fundit për të menduar rreth është, a ka ndonjë raste buzë në këtë insert? Dhe kjo rezulton se, mirë, një rast avantazh që është gjithmonë interesante për të menduar për është, çfarë ndodh në qoftë se pema juaj është bosh dhe ju e quani këtë funksion futur? Do të punojë? E pra, le t'i jepte një provoni. - Binary_tree c. - Mënyrën se si ne jemi duke shkuar për të provuar këtë është, ne jemi duke shkuar për të shkuar deri në funksionin tonë kryesor, dhe në vend se instalime elektrike këto nyje deri si kjo, ne jemi vetëm duke shkuar për të komentuar nga të gjithë gjë, dhe në vend të instalime elektrike deri nyjet veten, ne fakt mund të thjesht shkoni përpara dhe fshini të gjithë këtë. Ne jemi duke shkuar për të bërë gjithçka për të futur një telefonatë. Pra, le ta bëjmë - në vend të 5, 8, dhe 2, ne jemi duke shkuar për të futur 7, 3, dhe 9. Dhe pastaj ne do të duan të futur 6 si. Ruaj. Quit. Të bëjë pemë binare. Të gjitha harton. Ne vetëm mund të kandidojë atë si është dhe shikoni se çfarë ndodh, por ajo gjithashtu do të jetë me të vërtetë e rëndësishme për të siguruar që ne nuk kemi ndonjë gabim kujtesës, pasi kjo është një nga rastet tona buzë që ne e dimë rreth. 

Le të bëjnë të sigurt se ajo punon edhe nën Shprehje, të cilat ne do të bëjmë vetëm me drejtimin Shprehje. / binary_tree. Ajo duket si ne me të vërtetë kemi një gabim nga një kontekst - ne e kemi këtë defekt segmentimit. Çfarë ka ndodhur? Shprehje fakt na tregon se ku është. Zoom out pak. Ajo duket si ajo që po ndodh në funksion tonë insert, ku ne kemi një lexuar pavlefshme të madhësisë 4 në insert, line 60. Le të shkojnë prapa dhe të shohim se çfarë po ndodh këtu. Zoom me të vërtetë të shpejtë. Unë dua të bëni të sigurtë që nuk shkojnë në buzë të ekranit kështu që ne mund të shohim gjithçka. Tërhiqe se në një pak. Mirë. Shkoni poshtë, dhe problemi është e drejtë këtu. Çfarë ndodh në qoftë se ne të merrni poshtë dhe nyja ynë aktual është tashmë null, nyja jonë mëmë është null, kështu që nëse ne shikojmë deri në shumë të lartë, të drejtë këtu - në qoftë se nuk ky lak, ndërsa në fakt ekzekuton sepse vlera null ynë aktual është - rrënja jonë është aq null cur është i pavlefshëm - pastaj nuk prindi ynë merr vendosur për monedhes apo në një vlerë të vlefshme, kështu, prindi do të jetë i pavlefshëm. Ne duhet të mos harroni të kontrolloni për këtë me kohë kemi marrë këtu poshtë, dhe ne të fillojnë të hyrë vlerën e prindërve. Pra, çfarë ndodh? E pra, nëse prindi është i pavlefshëm - në qoftë se (== NULL prind) - atëherë ne e dimë se nuk duhet të jetë çdo gjë në pemë. Ne duhet të jetë duke u përpjekur për të futur atë në rrënjë. Ne mund ta bëjë këtë vetëm me vendosjen e rrënjë të barabartë me nyje të ri. Pastaj në këtë pikë, ne nuk të vërtetë duan të shkojnë nëpër këto gjëra të tjera. Në vend të kësaj, të drejtë këtu, ne mund të bëjmë as një tjetër-nëse-tjetër, ose ne mund të kombinojnë gjithçka deri këtu në një tjetër, por këtu ne do të përdorin vetëm tjetër dhe të bëjë atë në këtë mënyrë. Tani, ne jemi duke shkuar për të provuar për të siguruar që prindi ynë nuk është i pavlefshëm para se atëherë vërtetë duke u përpjekur për të hyrë në fushat e saj. Kjo do të na ndihmojë të shmangur fajin segmentimit. Pra, ne të lë, zoom out, hartojnë, të drejtuar. 

Nuk ka gabime, por ne ende kemi një bandë e rrjedhjeve të kujtesës sepse nuk kemi liruar ndonjë nga nyjet tona. Por, nëse ne do të shkojmë deri këtu dhe ne shikojmë printuar tonë, ne shohim se, mirë, duket si të gjithë fut tona u kthyer e vërtetë, e cila është e mirë. Të fut janë të gjitha të vërteta, dhe pastaj përmban përshtatshme thirrjet janë gjithashtu e vërtetë. 

Mirë punë! Ajo duket si ne kemi shkruar sukses futur. Kjo është e gjitha që kemi për Specifikimin Set kësaj jave Problem. Një sfidë fun për të menduar është se si ju do të vërtetë të shkoni në dhe pa të gjitha nyjet në këtë pemë. Ne mund ta bëjë këtë një numër të mënyra të ndryshme, por unë do të iki se deri tek ju për të eksperimentuar, dhe si një sfidë fun, të përpiqet dhe të sigurohemi që ju mund të sigurt se ky raport nuk kthehet Shprehje gabime dhe nuk rrjedhjet. 

Good luck në Huffman grup kësaj jave coding problemit, dhe ne do të shohim se javën e ardhshme! [CS50.TV]