1 00:00:00,000 --> 00:00:02,500 [Powered by Google Translate] [Pjesa 7] [Less komode] 2 00:00:02,500 --> 00:00:04,890 [Nate Hardison] [Universiteti i Harvardit] 3 00:00:04,890 --> 00:00:07,000 [Kjo është CS50.] [CS50.TV] 4 00:00:07,000 --> 00:00:09,080 >> Mirë se vini në nenin 7. 5 00:00:09,080 --> 00:00:11,330 Faleminderit për stuhi me rërë, 6 00:00:11,330 --> 00:00:13,440 në vend të ketë një seksion normal të kësaj jave, 7 00:00:13,440 --> 00:00:17,650 ne jemi duke e bërë këtë shëtitje-nëpërmjet, përmes seksionit të pyetjeve. 8 00:00:17,650 --> 00:00:22,830 Unë jam duke shkuar për të ndjekur së bashku me problemin Set 6 Specifikimi, 9 00:00:22,830 --> 00:00:25,650 dhe duke kaluar nëpër të gjitha pyetjet në 10 00:00:25,650 --> 00:00:27,770 Një Seksioni pyetjesh seksion. 11 00:00:27,770 --> 00:00:30,940 Nëse ka ndonjë pyetje, 12 00:00:30,940 --> 00:00:32,960 ju lutem postoni ato në CS50 diskutuar. 13 00:00:32,960 --> 00:00:35,480 >> Mirë. Le të ketë filluar. 14 00:00:35,480 --> 00:00:40,780 Tani për tani unë jam duke kërkuar në faqen 3 të Specifikimi Set Problem. 15 00:00:40,780 --> 00:00:44,110 Ne jemi duke shkuar për të parë të fillojmë të flasim në lidhje me pemë binare 16 00:00:44,110 --> 00:00:47,850 pasi ata kanë shumë rëndësi për të vendosur këtë javë problemit - 17 00:00:47,850 --> 00:00:49,950 encoding Tree Huffman. 18 00:00:49,950 --> 00:00:55,000 Një nga strukturat e të dhënave e parë kemi biseduar për në CS50 ishte array. 19 00:00:55,000 --> 00:01:00,170 Mos harroni se një grup është një sekuencë e elementeve - 20 00:01:00,170 --> 00:01:04,019 të gjitha të të njëjtit lloj - ruhen të drejtë tjetër për njëri-tjetrin në kujtesë. 21 00:01:04,019 --> 00:01:14,420 Nëse unë kam një koleksion numër i plotë që unë mund të tërheqë përdorur këtë stil kuti-numrat-integers - 22 00:01:14,420 --> 00:01:20,290 Le të thonë se unë kam 5 në kutinë e parë, kam 7 në të dytë, 23 00:01:20,290 --> 00:01:27,760 atëherë unë kam 8, 10, dhe 20 në kutinë e fundit. 24 00:01:27,760 --> 00:01:33,000 Mos harroni gjërat, të dy me të vërtetë e mirë për këtë grup 25 00:01:33,000 --> 00:01:38,800 janë që ne kemi këtë qasje të vazhdueshme në kohë për çdo element të veçantë 26 00:01:38,800 --> 00:01:40,500  në rrjet, nëse ne e dimë indeksin e saj. 27 00:01:40,500 --> 00:01:44,670 Për shembull, në qoftë se unë dua të kap elementin e tretë në grup - 28 00:01:44,670 --> 00:01:47,870 në indeksin e 2 duke përdorur zero-bazuar sistemit tonë indeksimit - 29 00:01:47,870 --> 00:01:52,220 Unë fjalë për fjalë vetëm duhet të bëjë një llogaritje të thjeshtë matematikore, 30 00:01:52,220 --> 00:01:56,170 hop në atë pozicion në grup, 31 00:01:56,170 --> 00:01:57,840 largohen nga 8 që është ruajtur, ka 32 00:01:57,840 --> 00:01:59,260 dhe unë jam i mirë për të shkuar. 33 00:01:59,260 --> 00:02:03,350 >> Një nga gjërat më të këqija në lidhje me këtë grup - se kemi biseduar rreth 34 00:02:03,350 --> 00:02:05,010 kur kemi diskutuar listat lidhura - 35 00:02:05,010 --> 00:02:09,120 është se në qoftë se unë dua të futur një element në këtë grup, 36 00:02:09,120 --> 00:02:11,090 Unë do të duhet të bëjë disa zhvendosur rreth. 37 00:02:11,090 --> 00:02:12,940 Për shembull, kjo array drejtë këtu 38 00:02:12,940 --> 00:02:16,850 është në mënyrë renditura - renditura në ngjitje urdhër - 39 00:02:16,850 --> 00:02:19,440 5, pastaj 7, pastaj 8, pastaj 10, dhe më pas 20 - 40 00:02:19,440 --> 00:02:23,100 por në qoftë se unë dua të futur numrin 9 në këtë grup, 41 00:02:23,100 --> 00:02:27,460 Unë do të duhet të zhvendoset disa nga elementet në mënyrë që të bëjë hapësirë. 42 00:02:27,460 --> 00:02:30,440 Ne mund të tërheqë këtë këtu. 43 00:02:30,440 --> 00:02:35,650 Unë do të duhet të lëvizin 5, 7, dhe pastaj 8; 44 00:02:35,650 --> 00:02:38,720 të krijojë një boshllëk ku unë mund të vënë në 9, 45 00:02:38,720 --> 00:02:45,910 dhe pastaj 10 dhe 20 mund të shkojnë për të drejtën e 9. 46 00:02:45,910 --> 00:02:49,450 Kjo është lloj i një dhimbje, sepse në rastin më të keq - 47 00:02:49,450 --> 00:02:54,350 kur ne jemi të paturit e për të futur qoftë në fillim ose në fund 48 00:02:54,350 --> 00:02:56,040 e array, në varësi se si ne jemi zhvendosur - 49 00:02:56,040 --> 00:02:58,850 ne mund të përfundojnë që të zhvendoset të gjitha elementet 50 00:02:58,850 --> 00:03:00,750 se ne jemi aktualisht ruajtjen në grup. 51 00:03:00,750 --> 00:03:03,810 >> Pra, çfarë ishte mënyra rreth kësaj? 52 00:03:03,810 --> 00:03:09,260 Mënyra rreth kësaj ishte për të shkuar në linked list-metodën tonë, ku - 53 00:03:09,260 --> 00:03:19,820 në vend të ruajtjen e elementeve 5, 7, 8, 10, dhe 20 të gjithë pranë njëri-tjetrit në kujtesën - 54 00:03:19,820 --> 00:03:25,630 çfarë ne vend nuk u ruajtur ato lloj e kudo që kemi dashur për të ruajtur ato 55 00:03:25,630 --> 00:03:32,470 në këto linked listë nyjet që unë jam tërhequr nga këtu, lloj ad hoc. 56 00:03:32,470 --> 00:03:42,060 Dhe pastaj ne lidhur ato së bashku duke përdorur këto pointers ardhshëm. 57 00:03:42,060 --> 00:03:44,370 Unë mund të ketë një tregues nga 5 në 7, 58 00:03:44,370 --> 00:03:46,420 një akrep nga 7 në 8, 59 00:03:46,420 --> 00:03:47,770 një akrep nga 8 në 10, 60 00:03:47,770 --> 00:03:51,220 dhe në fund, një akrep nga 10 në 20, 61 00:03:51,220 --> 00:03:54,880 dhe pastaj një tregues null në 20 duke treguar se nuk ka asgjë të majtë. 62 00:03:54,880 --> 00:03:59,690 Të tregtisë-off që ne kemi këtu 63 00:03:59,690 --> 00:04:05,360 është se tani në qoftë se ne duam të futur numrin 9 në listën tonë të renditura, 64 00:04:05,360 --> 00:04:08,270 të gjithë ne duhet të bëni është të krijojë një nyje të re me 9, 65 00:04:08,270 --> 00:04:12,290 wire atë deri për pikë në vendin e duhur, 66 00:04:12,290 --> 00:04:20,630 dhe pastaj ri-tel 8 për pikë deri në 9. 67 00:04:20,630 --> 00:04:25,660 Kjo është shumë shpejt, duke supozuar ne e dimë saktësisht se ku ne duam të futur 9. 68 00:04:25,660 --> 00:04:32,610 Por tregtisë-off në këmbim për këtë është se ne kemi humbur tani qasje të vazhdueshme në kohë 69 00:04:32,610 --> 00:04:36,230 për çdo element të veçantë në strukturën e të dhënave tona. 70 00:04:36,230 --> 00:04:40,950 Për shembull, në qoftë se unë dua të gjeni elementin e katërt në këtë listë e lidhur, 71 00:04:40,950 --> 00:04:43,510 Unë do të duhet të fillojë në fillim të listës 72 00:04:43,510 --> 00:04:48,930 dhe të punojnë rrugën time përmes numërimit nyje nyje-nga-deri sa të gjeni një të katërt. 73 00:04:48,930 --> 00:04:55,870 >> Në mënyrë që të marrë performancë më të mirë se sa një qasje listë lidhur - 74 00:04:55,870 --> 00:04:59,360 por edhe të ruajë disa nga përfitimet që kemi pasur 75 00:04:59,360 --> 00:05:01,800 në drejtim të hyrjes kohë nga një listë e lidhur - 76 00:05:01,800 --> 00:05:05,750 një pemë binare do të ketë nevojë të përdorë memorie pak më shumë. 77 00:05:05,750 --> 00:05:11,460 Në veçanti, në vend të vetëm duke pasur një akrep në një nyje pemë binare - 78 00:05:11,460 --> 00:05:13,350 si listë e lidhur nyje-ka - 79 00:05:13,350 --> 00:05:16,950 ne jemi duke shkuar për të shtuar një treguesin e dytë në nyje binar pemë. 80 00:05:16,950 --> 00:05:19,950 Në vend se vetëm duke pasur një tregues për elementin tjetër, 81 00:05:19,950 --> 00:05:24,420 ne do të kemi një tregues për një fëmijë të majtë dhe një fëmijë drejtë. 82 00:05:24,420 --> 00:05:26,560 >> Le të nxjerrë një foto për të parë atë që në fakt duket si. 83 00:05:26,560 --> 00:05:31,350 Përsëri, unë jam duke shkuar për të përdorur këto kuti dhe shigjeta. 84 00:05:31,350 --> 00:05:37,150 Një nyjë binar pemë do të nisem me vetëm një kuti të thjeshtë. 85 00:05:37,150 --> 00:05:40,940 Ajo do të ketë një hapësirë ​​për vlerën, 86 00:05:40,940 --> 00:05:47,280 dhe pastaj ajo gjithashtu do të ketë një hapësirë ​​për fëmijën e majtë dhe e djathtë të fëmijës. 87 00:05:47,280 --> 00:05:49,280 Unë jam duke shkuar për emërtim ata këtu. 88 00:05:49,280 --> 00:05:57,560 Ne do të kemi fëmijën e majtë, dhe pastaj ne do të kemi fëmijën e duhur. 89 00:05:57,560 --> 00:05:59,920 Ka shumë mënyra të ndryshme për ta bërë këtë. 90 00:05:59,920 --> 00:06:02,050 Ndonjëherë për hapësirë ​​dhe komoditet, 91 00:06:02,050 --> 00:06:06,460 Unë do të të vërtetë të tërheqë atë si unë jam duke bërë këtu në fund 92 00:06:06,460 --> 00:06:10,910 ku unë jam duke shkuar të ketë vlerë në krye, 93 00:06:10,910 --> 00:06:14,060 dhe pastaj fëmija të drejtë në pjesën e poshtme të djathtë, 94 00:06:14,060 --> 00:06:16,060 dhe fëmija majtë në pjesën e poshtme të majtë. 95 00:06:16,060 --> 00:06:20,250 Going back to ky diagram të lartë, 96 00:06:20,250 --> 00:06:22,560 ne kemi vlera në krye, 97 00:06:22,560 --> 00:06:25,560 atëherë ne kemi treguesin e majtë-fëmijë, dhe pastaj ne kemi të drejtë treguesin-fëmijë. 98 00:06:25,560 --> 00:06:30,110 >> Në Specifikimi Set Problem, 99 00:06:30,110 --> 00:06:33,110 ne flasim për hartimin e një nyje që ka një vlerë 7, 100 00:06:33,110 --> 00:06:39,750 dhe pastaj një të majtë fëmijë akrep që është i pavlefshëm, dhe një e drejtë-fëmijë që është akrep null. 101 00:06:39,750 --> 00:06:46,040 Ne ose mund të shkruani null kapitalit në hapësirë ​​për 102 00:06:46,040 --> 00:06:51,610 dy fëmijë të majtë dhe fëmija të drejtë, ose ne mund të tërheqë këtë plagë diagonale 103 00:06:51,610 --> 00:06:53,750 nëpër secilën nga kutitë për të treguar se është i pavlefshëm. 104 00:06:53,750 --> 00:06:57,560 Unë jam duke shkuar për të bërë këtë vetëm për shkak se është më e thjeshtë. 105 00:06:57,560 --> 00:07:03,700 Çfarë ju shihni këtu janë dy mënyra për të diagramimin një shumë të thjeshtë pemë nyje binar 106 00:07:03,700 --> 00:07:07,960 ku ne kemi vlerën 7 dhe pointers null fëmijës. 107 00:07:07,960 --> 00:07:15,220 >> Pjesa e dytë e bisedimeve tona specifikimit rreth asaj se si të lidhura me lista - 108 00:07:15,220 --> 00:07:18,270 Mos harroni, kemi pasur vetëm për të mbajtur në elementin e parë në një listë 109 00:07:18,270 --> 00:07:20,270 për të kujtuar të gjithë listën - 110 00:07:20,270 --> 00:07:26,140 dhe gjithashtu, me një pemë binare, ne vetëm duhet të mbajë në të një akrep në pemë 111 00:07:26,140 --> 00:07:31,120 në mënyrë që për të ruajtur kontrollin mbi strukturën e të dhënave të tërë. 112 00:07:31,120 --> 00:07:36,150 Ky element i veçantë i pemës quhet nyje rrënja e pemës. 113 00:07:36,150 --> 00:07:43,360 Për shembull, nëse kjo nyje - kjo nyje përmban vlerën e 7 114 00:07:43,360 --> 00:07:45,500 me pointers null majtë dhe të djathtë-fëmijë - 115 00:07:45,500 --> 00:07:47,360 ishin vlera vetëm në pemë tonë, 116 00:07:47,360 --> 00:07:50,390 atëherë kjo do të jetë nyja tonë rrënjë. 117 00:07:50,390 --> 00:07:52,240 Kjo është shumë e fillimi i pemës tonë. 118 00:07:52,240 --> 00:07:58,530 Ne mund të shohim këtë pak më qartë sapo kemi filluar duke shtuar më shumë nyje të pemës tonë. 119 00:07:58,530 --> 00:08:01,510 Më lejoni të tërheqë një faqe të re. 120 00:08:01,510 --> 00:08:05,000 >> Tani ne jemi duke shkuar për të nxjerrë një pemë që ka 7 në rrënjë, 121 00:08:05,000 --> 00:08:10,920 dhe 3 brenda e fëmijës majtë, dhe 9 brendësi të fëmijës duhur. 122 00:08:10,920 --> 00:08:13,500 Përsëri, kjo është shumë e thjeshtë. 123 00:08:13,500 --> 00:08:26,510 Ne kemi marrë 7, vizatoni një nyje për 3, një nyje për 9, 124 00:08:26,510 --> 00:08:32,150 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, 125 00:08:32,150 --> 00:08:37,850 dhe të drejtën për-fëmijë treguesin e nyja përmban 7 në nyje përmban 9. 126 00:08:37,850 --> 00:08:42,419 Tani, pasi 3 dhe 9 nuk kanë ndonjë fëmijë, 127 00:08:42,419 --> 00:08:48,500 ne jemi duke shkuar për të vendosur të gjitha pointers e tyre fëmijë të jetë e pavlefshme. 128 00:08:48,500 --> 00:08:56,060 Këtu, rrënja e pemës tonë korrespondon me nyje përmban numrin 7. 129 00:08:56,060 --> 00:09:02,440 Ju mund të shihni se në qoftë se të gjithë ne kemi është një tregues për atë nyje rrënjë, 130 00:09:02,440 --> 00:09:07,330 atëherë ne mund të ecin nëpër pemë tonë dhe qasje të dy nyjet fëmijë - 131 00:09:07,330 --> 00:09:10,630 dy 3 dhe 9. 132 00:09:10,630 --> 00:09:14,820 Nuk ka nevojë për të ruajtur pointers për çdo nyje të vetme në pemë. 133 00:09:14,820 --> 00:09:22,080 Mirë. Tani ne jemi duke shkuar për të shtuar një tjetër nyje në këtë diagram. 134 00:09:22,080 --> 00:09:25,370 Ne jemi duke shkuar për të shtuar një nyje përmban 6, 135 00:09:25,370 --> 00:09:34,140 dhe ne jemi duke shkuar për të shtuar këtë si fëmijën e djathtë të nyjeve përmban 3. 136 00:09:34,140 --> 00:09:41,850 Për ta bërë këtë, unë jam duke shkuar për të fshirë atë treguesin null në 3-nyjë 137 00:09:41,850 --> 00:09:47,750 dhe tel atë deri në pikë në nyje përmban 6. Mirë. 138 00:09:47,750 --> 00:09:53,800 >> Në këtë pikë, le të shkojë më shumë se një pak e terminologjisë. 139 00:09:53,800 --> 00:09:58,230 Për të filluar, arsyen se kjo është quajtur një pemë binare në veçanti 140 00:09:58,230 --> 00:10:00,460 është se ai ka dy fëmijë pointers. 141 00:10:00,460 --> 00:10:06,020 Ka lloje të tjera të pemëve që kanë pointers më shumë fëmijë. 142 00:10:06,020 --> 00:10:10,930 Në veçanti, ju bëri një "provoni" në Set Problem 5. 143 00:10:10,930 --> 00:10:19,310 Ju do të vëreni se në atë provoni, ju kishte 27 pointers të ndryshme në fëmijët të ndryshme - 144 00:10:19,310 --> 00:10:22,410 një për secilin nga 26 letra në alfabetin Shqip, 145 00:10:22,410 --> 00:10:25,410 dhe pastaj 27 për apostrof - 146 00:10:25,410 --> 00:10:28,900 kështu, kjo është e ngjashme me një lloj të pemës. 147 00:10:28,900 --> 00:10:34,070 Por këtu, pasi binar është, ne kemi vetëm dy pointers fëmijë. 148 00:10:34,070 --> 00:10:37,880 >> Përveç kësaj nyje rrënjë që kemi biseduar rreth, 149 00:10:37,880 --> 00:10:41,470 ne kemi qenë të hedhur rreth këtij termi 'fëmijë'. 150 00:10:41,470 --> 00:10:44,470 Çfarë do të thotë kjo për një nyje të jetë një fëmijë i një nyje? 151 00:10:44,470 --> 00:10:54,060 Kjo fjalë do të thotë se një nyje fëmijë është një fëmijë i një nyje 152 00:10:54,060 --> 00:10:58,760 në qoftë se nyjen e tjera ka një pointers saj fëmijëve të vendosur për të vënë në atë nyje. 153 00:10:58,760 --> 00:11:01,230 Për të vënë këtë në terma më konkrete, 154 00:11:01,230 --> 00:11:11,170 nëse 3 është theksuar nga një prej pointers fëmijëve të 7, atëherë 3 është një fëmijë i 7. 155 00:11:11,170 --> 00:11:14,510 Nëse ne do të kuptoj se çfarë fëmijët e 7 janë - 156 00:11:14,510 --> 00:11:18,510 mirë, ne shohim se 7 ka një tregues për 3 dhe një tregues për 9, 157 00:11:18,510 --> 00:11:22,190 kështu 9 dhe 3 janë fëmijët e 7. 158 00:11:22,190 --> 00:11:26,650 Nëntë nuk ka fëmijë, sepse pointers saj fëmijë janë null, 159 00:11:26,650 --> 00:11:30,940 dhe 3 ka vetëm një fëmijë, 6. 160 00:11:30,940 --> 00:11:37,430 Gjashtë gjithashtu nuk ka fëmijë për shkak të dy pointers saj janë null, të cilat ne do të nxjerrë të drejtë tani. 161 00:11:37,430 --> 00:11:45,010 >> Përveç kësaj, ne gjithashtu flasim për prindërit e një nyje të veçantë, 162 00:11:45,010 --> 00:11:51,100 dhe kjo është, si ju do të presin, e kundërta e këtij përshkrimi fëmijëve. 163 00:11:51,100 --> 00:11:58,620 Çdo nyje ka vetëm një prind - në vend të dy si ju mund të presin me njerëzit. 164 00:11:58,620 --> 00:12:03,390 Për shembull, prind i 3 është 7. 165 00:12:03,390 --> 00:12:10,800 Prind i 9 është gjithashtu 7, dhe prind i 6 është 3. Jo shumë për të. 166 00:12:10,800 --> 00:12:15,720 Ne gjithashtu kemi kushtet për të folur në lidhje me gjyshërit dhe nipërit, 167 00:12:15,720 --> 00:12:18,210 dhe më në përgjithësi, ne flasim për paraardhësit 168 00:12:18,210 --> 00:12:20,960 dhe pasardhësit e një nyje të veçantë. 169 00:12:20,960 --> 00:12:25,710 Paraardhësi i një nyje - ose paraardhësit, në vend të një nyje - 170 00:12:25,710 --> 00:12:32,730 janë të gjitha nyjet që shtrihen në rrugën nga rrënja në atë nyje. 171 00:12:32,730 --> 00:12:36,640 Për shembull, në qoftë se unë jam duke kërkuar në nyjen 6, 172 00:12:36,640 --> 00:12:46,430 atëherë paraardhësit do të jenë të dy 3 dhe 7. 173 00:12:46,430 --> 00:12:55,310 Paraardhësit e 9, për shembull, janë - në qoftë se unë jam duke kërkuar në nyjen 9 - 174 00:12:55,310 --> 00:12:59,990 atëherë paraardhësi i 9 është vetëm 7. 175 00:12:59,990 --> 00:13:01,940 Dhe pasardhësit janë pikërisht e kundërta. 176 00:13:01,940 --> 00:13:05,430 Nëse unë dua të shikoni në të gjithë pasardhësit e 7, 177 00:13:05,430 --> 00:13:11,020 atëherë unë duhet të shikoni në të gjitha nyjet nën atë. 178 00:13:11,020 --> 00:13:16,950 Pra, unë kam 3, 9, dhe 6 të gjitha, si pasardhësit e 7. 179 00:13:16,950 --> 00:13:24,170 >> Termi e fundit që ne do të flasim rreth është ky nocion për të qenë një vëlla. 180 00:13:24,170 --> 00:13:27,980 Vëllai dhe motra - lloj pas së bashku në këto kushte familjare - 181 00:13:27,980 --> 00:13:33,150 janë nyjet që janë në të njëjtin nivel në pemë. 182 00:13:33,150 --> 00:13:42,230 Pra, 3 dhe 9 janë vëllezërit e motrat, sepse ata janë në të njëjtin nivel në pemë. 183 00:13:42,230 --> 00:13:46,190 Ata të dy kanë të njëjtën prind, 7. 184 00:13:46,190 --> 00:13:51,400 E 6 vëllezërit e motrat, sepse nuk ka 9 nuk ka asnjë fëmijë. 185 00:13:51,400 --> 00:13:55,540 Dhe 7 nuk ka ndonjë vëllezërit e motrat, sepse ajo është rrënja e pemës tonë, 186 00:13:55,540 --> 00:13:59,010 dhe ka vetëm ndonjëherë 1 rrënjë. 187 00:13:59,010 --> 00:14:02,260 Për 7 të kemi vëllezërit e motrat nuk do të duhet të jetë një nyje më lart 7. 188 00:14:02,260 --> 00:14:07,480 Nuk do të ketë të jetë një prind i 7, në të cilin rast 7 nuk do të jetë rrënja nga pema. 189 00:14:07,480 --> 00:14:10,480 Pastaj se prind i ri i 7 do të duhet të ketë një fëmijë, 190 00:14:10,480 --> 00:14:16,480 dhe se fëmija më pas do të jetë motër e 7. 191 00:14:16,480 --> 00:14:21,040 >> Mirë. Lëvizin më. 192 00:14:21,040 --> 00:14:24,930 Kur kemi filluar diskutimin tonë të pemëve binare, 193 00:14:24,930 --> 00:14:28,790 kemi biseduar rreth asaj se si ne u do të përdorin ato për të 194 00:14:28,790 --> 00:14:32,800 të fituar një avantazh mbi të dy vargjeve dhe listat e lidhura. 195 00:14:32,800 --> 00:14:37,220 Dhe mënyra që ne jemi duke shkuar për të bërë këtë është me këtë pronë urdhërimin. 196 00:14:37,220 --> 00:14:41,080 Ne themi se një pema binar është urdhëruar, sipas specifikim, 197 00:14:41,080 --> 00:14:45,740 në qoftë se për çdo nyje në pemë tonë, të gjithë pasardhësit e saj në të majtë - 198 00:14:45,740 --> 00:14:48,670 fëmija majtë dhe të gjithë pasardhësve të fëmijës së majtë - 199 00:14:48,670 --> 00:14:54,510 kanë vlera më të vogël, dhe të gjitha nyjet në të djathtë - 200 00:14:54,510 --> 00:14:57,770 fëmija e drejtë dhe të gjithë pasardhësve të drejtën e femijëve së - 201 00:14:57,770 --> 00:15:02,800 kanë nyjet më të mëdha se vlera e nyjeve aktuale që ne jemi duke kërkuar në. 202 00:15:02,800 --> 00:15:07,850 Vetëm për thjeshtësi, ne do të supozojmë se nuk ka ndonjë nyje kopjuar në pemën tonë. 203 00:15:07,850 --> 00:15:11,180 Për shembull, në këtë pemë, ne nuk do të merret me rastin 204 00:15:11,180 --> 00:15:13,680 ku ne kemi vlerën 7 në rrënjë 205 00:15:13,680 --> 00:15:16,720  dhe pastaj kemi edhe vlerën 7 gjetkë në pemë. 206 00:15:16,720 --> 00:15:24,390 Në këtë rast, ju do të vëreni se kjo pemë është urdhëruar të vërtetë. 207 00:15:24,390 --> 00:15:26,510 Ne kemi vlerën 7 në rrënjë. 208 00:15:26,510 --> 00:15:29,720 Çdo gjë tek e majta e 7 - 209 00:15:29,720 --> 00:15:35,310 në qoftë se unë zgjidh të gjitha këto shenja pak këtu - 210 00:15:35,310 --> 00:15:40,450 çdo gjë tek e majta e 7 - 3 dhe 6 - 211 00:15:40,450 --> 00:15:49,410 ato vlera janë të dy më pak se 7, dhe çdo gjë në të djathtë - e cila është vetëm ky 9 - 212 00:15:49,410 --> 00:15:53,450 është më i madh se 7. 213 00:15:53,450 --> 00:15:58,650 >> Kjo nuk është pema urdhërohet vetëm që përmban këto vlera, 214 00:15:58,650 --> 00:16:03,120 por le të nxjerrë një më pak prej tyre. 215 00:16:03,120 --> 00:16:05,030 Nuk është në fakt një bandë e tërë e mënyrat që ne mund të bëjmë këtë. 216 00:16:05,030 --> 00:16:09,380 Unë jam duke shkuar për të përdorur një stenografi vetëm për të mbajtur gjërat e thjeshta ku - 217 00:16:09,380 --> 00:16:11,520 sesa tërhequr nga të gjithë kuti-dhe-shigjeta - 218 00:16:11,520 --> 00:16:14,220 Unë jam vetëm duke shkuar për të nxjerrë numrat dhe shtoni shigjetat lidh ato. 219 00:16:14,220 --> 00:16:22,920 Për të filluar, ne do të shkruani vetëm pemën tonë origjinal, ku sërish kemi pasur 7, dhe pastaj një 3, 220 00:16:22,920 --> 00:16:25,590 dhe pastaj 3 vuri përsëri në të djathtë të 6, 221 00:16:25,590 --> 00:16:30,890 dhe 7 kishte një fëmijë të drejtë që ishte 9. 222 00:16:30,890 --> 00:16:33,860 Mirë. Çfarë është një mënyrë tjetër që ne mund të shkruaj këtë pemë? 223 00:16:33,860 --> 00:16:38,800 Në vend të që të jetë fëmija 3 nga 7 majtë, 224 00:16:38,800 --> 00:16:41,360 ne gjithashtu mund të ketë 6 jetë fëmija e majtë të 7, 225 00:16:41,360 --> 00:16:44,470 dhe pastaj 3 jetë fëmija e majtë të 6. 226 00:16:44,470 --> 00:16:48,520 Kjo do të duket si ky dru të drejtë këtu, ku unë kam marrë 7, 227 00:16:48,520 --> 00:16:57,860 atëherë 6, pastaj 3, dhe një 9 në të drejtë. 228 00:16:57,860 --> 00:17:01,490 Ne gjithashtu nuk duhet të ketë 7 si nyje tonë rrënjë. 229 00:17:01,490 --> 00:17:03,860 Ne gjithashtu mund të ketë 6 si nyje tonë rrënjë. 230 00:17:03,860 --> 00:17:06,470 Çfarë do që të duken si? 231 00:17:06,470 --> 00:17:09,230 Nëse ne jemi duke shkuar për të mbajtur këtë pronë urdhëruar, 232 00:17:09,230 --> 00:17:12,970 çdo gjë tek e majta e 6 ka të jetë më pak se saj. 233 00:17:12,970 --> 00:17:16,540 Ka vetëm një mundësi, dhe kjo është 3. 234 00:17:16,540 --> 00:17:19,869 Por pastaj si fëmijën e djathtë e 6, ne kemi dy mundësi. 235 00:17:19,869 --> 00:17:25,380 Së pari, ne mund të kemi 7 dhe pastaj 9, 236 00:17:25,380 --> 00:17:28,850 ose ne mund të tërheqë atë - si unë jam gati për të bërë këtu - 237 00:17:28,850 --> 00:17:34,790 ku ne kemi 9 si fëmijën e djathtë të 6, 238 00:17:34,790 --> 00:17:39,050 dhe pastaj 7 si fëmijën e majtë të 9. 239 00:17:39,050 --> 00:17:44,240 >> Tani, 7 dhe 6 nuk janë vlerat e mundur vetëm për rrënjë. 240 00:17:44,240 --> 00:17:50,200 Ne gjithashtu mund të ketë 3 jetë në rrënjë. 241 00:17:50,200 --> 00:17:52,240 Çfarë ndodh nëse 3 është në rrënjë? 242 00:17:52,240 --> 00:17:54,390 Ja, gjërat marrin pak interesante. 243 00:17:54,390 --> 00:17:58,440 Tre nuk ka asnjë vlera që janë më pak se ajo, 244 00:17:58,440 --> 00:18:02,070 kështu që tërë anën e majtë të pemës është vetëm do të jetë e pavlefshme. 245 00:18:02,070 --> 00:18:03,230 Nuk do të jetë çdo gjë atje. 246 00:18:03,230 --> 00:18:07,220 Në të djathtë, ne mund lista gjërat në ngjitje qëllim. 247 00:18:07,220 --> 00:18:15,530 Ne mund të ketë 3, pastaj 6, 7, pastaj pastaj 9. 248 00:18:15,530 --> 00:18:26,710 Ose, ne mund të bëjmë 3, pastaj 6, pastaj 9, pastaj 7. 249 00:18:26,710 --> 00:18:35,020 Ose, ne mund të bëjmë 3, pastaj 7, pastaj 6, pastaj 9. 250 00:18:35,020 --> 00:18:40,950 Ose, 3, 7 - të vërtetë nuk ka, ne nuk mund të bëjmë një 7 më. 251 00:18:40,950 --> 00:18:43,330 Kjo është një gjë tonë atje. 252 00:18:43,330 --> 00:18:54,710 Ne mund të bëjmë 9, dhe pastaj nga 9 ne mund të bëjmë dhe pastaj 6 7. 253 00:18:54,710 --> 00:19:06,980 Ose, mund të bëjmë 3, pastaj 9, pastaj 7, dhe pastaj 6. 254 00:19:06,980 --> 00:19:12,490 >> Një gjë të tërheq vëmendjen tuaj për këtu është 255 00:19:12,490 --> 00:19:14,510 se këto pemë janë pak çuditshëm-looking. 256 00:19:14,510 --> 00:19:17,840 Në veçanti, nëse ne shikojmë në 4 pemëve në anën e djathtë - 257 00:19:17,840 --> 00:19:20,930 Unë do rrethit të tyre, këtu - 258 00:19:20,930 --> 00:19:28,410 këto pemë duken pothuajse tamam si një listë e lidhur. 259 00:19:28,410 --> 00:19:32,670 Çdo nyje ka vetëm një fëmijë, 260 00:19:32,670 --> 00:19:38,950 dhe kështu që ne nuk kemi ndonjë të kësaj strukture pemë-si që ne shohim, për shembull, 261 00:19:38,950 --> 00:19:44,720  në këtë pemë një i vetmuar mbi këtu në të majtë e poshtme. 262 00:19:44,720 --> 00:19:52,490 Këto pemë janë quajtur fakt degjeneruar pemë binare, 263 00:19:52,490 --> 00:19:54,170 dhe ne do të flasim për këto më shumë në të ardhmen - 264 00:19:54,170 --> 00:19:56,730 veçanërisht në qoftë se ju shkoni për të marrë kurse të tjera shkenca kompjuterike. 265 00:19:56,730 --> 00:19:59,670 Këto pemë janë të degjeneruar. 266 00:19:59,670 --> 00:20:03,780 Ata nuk janë shumë të dobishme, sepse, në të vërtetë, kjo strukturë jep veten 267 00:20:03,780 --> 00:20:08,060  të lookup herë ngjashme me atë të një liste të lidhura. 268 00:20:08,060 --> 00:20:13,050 Ne nuk do të marrë të përfitojnë nga memorie ekstra - ky tregues shtesë - 269 00:20:13,050 --> 00:20:18,840 për shkak të strukturës sonë të qenit i keq në këtë mënyrë. 270 00:20:18,840 --> 00:20:24,700 Në vend se të shkoni në dhe të nxjerrë jashtë pemë binare që kanë 9 në rrënjë, 271 00:20:24,700 --> 00:20:27,220 që është rasti i fundit që ne do të kemi, 272 00:20:27,220 --> 00:20:32,380 ne jemi në vend të kësaj, në këtë pikë, do të flasim pak për këtë afat tjetër 273 00:20:32,380 --> 00:20:36,150 që ne përdorim kur flasim për pemë, e cila quhet lartësia. 274 00:20:36,150 --> 00:20:45,460 >> Lartësia e një peme është distanca nga rrënja në nyjen më të largët, 275 00:20:45,460 --> 00:20:48,370 ose më mirë numrin e HOPS që ju do të keni për të bërë në mënyrë që të 276 00:20:48,370 --> 00:20:53,750 filluar nga rrënja dhe pastaj të përfundojë deri në nyjen më të largët në pemë. 277 00:20:53,750 --> 00:20:57,330 Nëse ne shikojmë në disa prej këtyre pemëve që ne i kemi tërhequr të drejtë këtu, 278 00:20:57,330 --> 00:21:07,870 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, 279 00:21:07,870 --> 00:21:14,510 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, 280 00:21:14,510 --> 00:21:20,560 dhe një hop të tretë të marrë në 9. 281 00:21:20,560 --> 00:21:26,120 Pra, lartësia e kësaj peme është 3. 282 00:21:26,120 --> 00:21:30,640 Ne mund të bëjmë të njëjtin ushtrim për pemët e tjera të përcaktuara me këtë jeshile, 283 00:21:30,640 --> 00:21:40,100 dhe ne shohim se lartësia e të gjitha këtyre pemëve është gjithashtu me të vërtetë 3. 284 00:21:40,100 --> 00:21:45,230 Kjo është pjesë e asaj që i bën ata të degjeneruar - 285 00:21:45,230 --> 00:21:53,750 se lartësia e tyre është vetëm një më pak se numri i nyjeve në pemë të tërë. 286 00:21:53,750 --> 00:21:58,400 Nëse ne shikojmë në këtë pemë tjetër që është e rrethuar me të kuqe, në anën tjetër, 287 00:21:58,400 --> 00:22:03,920 ne shohim se më të largët nyjet fletë janë 6 dhe 9 - 288 00:22:03,920 --> 00:22:06,940 lë të qenit ato nyje që nuk kanë fëmijë. 289 00:22:06,940 --> 00:22:11,760 Pra, në mënyrë që të merrni nga nyjë rrënjë ose të e 6 apo 9, 290 00:22:11,760 --> 00:22:17,840 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, 291 00:22:17,840 --> 00:22:21,240 dhe gjithashtu, vetëm një hop të dytë nga 7 për të marrë në 6. 292 00:22:21,240 --> 00:22:29,080 Pra, lartësia e kësaj peme mbi këtu është vetëm 2. 293 00:22:29,080 --> 00:22:35,330 Ju mund të ktheheni mbrapsh dhe të bëjë që për të gjithë pemët e tjera që kemi diskutuar më parë 294 00:22:35,330 --> 00:22:37,380 duke filluar me 7 dhe 6, 295 00:22:37,480 --> 00:22:42,500 dhe ju do të gjeni se lartësia e të gjitha këtyre pemëve është gjithashtu 2. 296 00:22:42,500 --> 00:22:46,320 >> Arsyeja që ne kemi qenë duke folur në lidhje me pemë binare urdhëroi 297 00:22:46,320 --> 00:22:50,250 dhe pse ata janë të ftohtë është për shkak se ju mund të kërkoni me anë të tyre në 298 00:22:50,250 --> 00:22:53,810 një mënyrë shumë të ngjashme me kërkim për një grup të renditura. 299 00:22:53,810 --> 00:22:58,720 Kjo është ajo ku ne flasim në lidhje me marrjen në atë kohë të përmirësuar lookup 300 00:22:58,720 --> 00:23:02,730 mbi listën e thjeshtë lidhur. 301 00:23:02,730 --> 00:23:05,010 Me një listë e lidhur - në qoftë se ju doni të gjeni një element të veçantë - 302 00:23:05,010 --> 00:23:07,470 ju jeni në të mirë do të bëjë një lloj të kërkimit lineare 303 00:23:07,470 --> 00:23:10,920 ku të fillojë në fillim të një liste dhe hop një-nga-një - 304 00:23:10,920 --> 00:23:12,620 një nyje nga një nyje - 305 00:23:12,620 --> 00:23:16,060 nëpër gjithë listën derisa ju të gjeni çdo gjë që ju jeni në kërkim për të. 306 00:23:16,060 --> 00:23:19,440 Ndërsa, nëse ju keni një pemë binare që është ruajtur në këtë format bukur, 307 00:23:19,440 --> 00:23:23,300 të vërtetë ju mund të merrni më shumë një kërkim binar në vazhdim e sipër 308 00:23:23,300 --> 00:23:25,160 ku jeni përça dhe sundo 309 00:23:25,160 --> 00:23:29,490 dhe të kërkoni përmes gjysmën e duhur të pemës në çdo hap. 310 00:23:29,490 --> 00:23:32,840 Le të shohim se si punon. 311 00:23:32,840 --> 00:23:38,850 >> Nëse kemi - përsëri, duke shkuar prapa në pemë tonë origjinale - 312 00:23:38,850 --> 00:23:46,710 ne të fillojë në 7, ne kemi 3 në të majtë, 9 në të djathtë, 313 00:23:46,710 --> 00:23:51,740 dhe nën 3 ne kemi 6. 314 00:23:51,740 --> 00:24:01,880 Nëse ne duam të kërkoni për numrin 6 në këtë pemë, ne do të fillojë në rrënjë. 315 00:24:01,880 --> 00:24:08,910 Ne do të krahasojmë vlerën Ne jemi në kërkim për të, të themi 6, 316 00:24:08,910 --> 00:24:12,320 të vlerës ruajtur në nyjen që ne jemi aktualisht në kërkim në, 7, 317 00:24:12,320 --> 00:24:21,200 të gjeni se 6 është me të vërtetë më pak se 7, kështu që ne do të lëvizin në të majtë. 318 00:24:21,200 --> 00:24:25,530 Nëse vlera e 6 kishte qenë më i madh se 7, ne do të kemi lëvizur në vend të së drejtës. 319 00:24:25,530 --> 00:24:29,770 Që ne e dimë se - për shkak të strukturës së pemës urdhëruar tonë binar - 320 00:24:29,770 --> 00:24:33,910 të gjitha vlerave më pak se 7 do të ruhen në të majtë të 7, 321 00:24:33,910 --> 00:24:40,520 nuk ka nevojë të shqetësojë edhe duke kërkuar nëpër anën e djathtë të pemës. 322 00:24:40,520 --> 00:24:43,780 Pasi të kemi të lëvizin në të majtë dhe ne jemi tani në nyjen përmban 3, 323 00:24:43,780 --> 00:24:48,110 ne mund të bëjmë atë përsëri të njëjtën krahasim ku ne krahasojmë 3 dhe 6. 324 00:24:48,110 --> 00:24:52,430 Dhe ne kemi gjetur se ndërsa 6 - vlera ne jemi duke kërkuar për - është më i madh se 3, 325 00:24:52,430 --> 00:24:58,580 Ne mund të shkojnë në anën e djathtë të nyjeve përmban 3. 326 00:24:58,580 --> 00:25:02,670 Nuk ka anën e majtë këtu, kështu që ne mund të kemi injoruar atë. 327 00:25:02,670 --> 00:25:06,510 Por ne e dimë se vetëm për shkak se ne jemi duke kërkuar në pemë vetë, 328 00:25:06,510 --> 00:25:08,660 dhe ne mund të shohim se pema nuk ka fëmijë. 329 00:25:08,660 --> 00:25:13,640 >> Ë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, 330 00:25:13,640 --> 00:25:16,890 por le të ndjekim këtë proces mekanikisht si një kompjuter do të bëjë 331 00:25:16,890 --> 00:25:18,620 me të vërtetë kuptojnë algorithm. 332 00:25:18,620 --> 00:25:26,200 Në këtë pikë, ne jemi tani në kërkim në një nyje që përmban 6, 333 00:25:26,200 --> 00:25:29,180 dhe ne jemi duke kërkuar për vlerën 6, 334 00:25:29,180 --> 00:25:31,740 kështu, në të vërtetë, ne kemi gjetur nyjen e duhur. 335 00:25:31,740 --> 00:25:35,070 Ne kemi gjetur vlerën 6 në pemë tonë, dhe ne mund të ndalojë kërkimin tonë. 336 00:25:35,070 --> 00:25:37,330 Në këtë pikë, në varësi të asaj që po ndodh, 337 00:25:37,330 --> 00:25:41,870 ne mund të themi, po, ne kemi gjetur vlerën 6, ajo ekziston në pemë tonë. 338 00:25:41,870 --> 00:25:47,640 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ë. 339 00:25:47,640 --> 00:25:53,010 >> Le të bëjmë Lookups një çift shumë vetëm për të parë se si kjo funksionon. 340 00:25:53,010 --> 00:25:59,390 Le të shohim se çfarë ndodh në qoftë se ne do të përpiqemi dhe të kërkoni vlerën 10. 341 00:25:59,390 --> 00:26:02,970 Nëse ne do të shikojmë deri vlerën 10, ne do të fillojë në rrënjë. 342 00:26:02,970 --> 00:26:07,070 Ne do të shohim se 10 është më e madhe se 7, kështu që ne do të lëvizin në të djathtë. 343 00:26:07,070 --> 00:26:13,640 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. 344 00:26:13,640 --> 00:26:16,210 Pra, përsëri, ne do të përpiqemi për të lëvizur në të djathtë. 345 00:26:16,210 --> 00:26:20,350 Por në këtë pikë, ne do të vini re se ne jemi në një nyje null. 346 00:26:20,350 --> 00:26:23,080 Nuk ka asgjë atje. Nuk ka asgjë ku duhet të jetë 10. 347 00:26:23,080 --> 00:26:29,360 Kjo është ajo ku ne mund të raportojnë dështimin - se nuk është me të vërtetë nuk ka 10 në pemë. 348 00:26:29,360 --> 00:26:35,420 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ë. 349 00:26:35,420 --> 00:26:38,790 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ë, 350 00:26:38,790 --> 00:26:41,260 ne jemi duke shkuar për të shkuar në të majtë. 351 00:26:41,260 --> 00:26:46,170 Ne të fillojë në 7 dhe shihni se 1 është më pak se 7, kështu që ne të shkojë në të majtë. 352 00:26:46,170 --> 00:26:51,750 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ë. 353 00:26:51,750 --> 00:26:59,080 Në këtë pikë ne kemi një nyje null, kështu që ne mund të raportojnë përsëri dështim. 354 00:26:59,080 --> 00:27:10,260 >> Nëse ju dëshironi të mësoni më shumë rreth pemë binare, 355 00:27:10,260 --> 00:27:14,420 ka një bandë e tërë e problemeve të fun pak se ju mund të bëni me ta. 356 00:27:14,420 --> 00:27:19,450 Unë sugjeroj praktikuar vizatim nga këto diagrame një-nga-një 357 00:27:19,450 --> 00:27:21,910 dhe pas nëpër të gjitha hapat e ndryshme, 358 00:27:21,910 --> 00:27:25,060 sepse kjo do të vijë në dobishëm super- 359 00:27:25,060 --> 00:27:27,480 jo vetëm kur ju jeni duke bërë problemit encoding grup Huffman 360 00:27:27,480 --> 00:27:29,390 por edhe në kurset e ardhshme - 361 00:27:29,390 --> 00:27:32,220 vetëm të mësuarit se si për të nxjerrë jashtë këto struktura të dhënave dhe të mendojnë përmes problemeve 362 00:27:32,220 --> 00:27:38,000 me stilolaps dhe letër ose, në këtë rast, iPad dhe majë shkruese. 363 00:27:38,000 --> 00:27:41,000 >> Në këtë pikë edhe pse, ne jemi duke shkuar për të lëvizur për të bërë disa praktika kodim 364 00:27:41,000 --> 00:27:44,870 dhe në fakt të luajë me këto pemë binare dhe të shohim. 365 00:27:44,870 --> 00:27:52,150 Unë jam duke shkuar për të kaluar prapa mbi kompjuterin tim. 366 00:27:52,150 --> 00:27:58,480 Për këtë pjesë të seksionit, në vend të përdorimit të CS50 Run ose CS50 hapësira, 367 00:27:58,480 --> 00:28:01,500 Unë jam duke shkuar për të përdorur pajisjen. 368 00:28:01,500 --> 00:28:04,950 >> Pas së bashku me specifikimet Set Problem, 369 00:28:04,950 --> 00:28:07,740 Unë po të shoh se unë jam menduar për të hapur pajisjen, 370 00:28:07,740 --> 00:28:11,020 shkoni në Dropbox dosjen time, të krijojë një dosje të quajtur Seksioni 7, 371 00:28:11,020 --> 00:28:15,730 dhe pastaj të krijojë një skedar të quajtur binary_tree.c. 372 00:28:15,730 --> 00:28:22,050 Këtu ne do të shkojmë. Unë kam marrë tashmë aplikim hapur. 373 00:28:22,050 --> 00:28:25,910 Unë jam duke shkuar të tërheqë një terminal. 374 00:28:25,910 --> 00:28:38,250 Unë jam duke shkuar për të shkuar në dosje Dropbox, të bëjë një direktori të quajtur section7, 375 00:28:38,250 --> 00:28:42,230 dhe të shohim se ajo është krejtësisht bosh. 376 00:28:42,230 --> 00:28:48,860 Tani unë jam duke shkuar për të hapur deri binary_tree.c. 377 00:28:48,860 --> 00:28:51,750 Mirë. Këtu ne do të shkojmë - skedar bosh. 378 00:28:51,750 --> 00:28:54,330 >> Le të kthehemi në specifikimet. 379 00:28:54,330 --> 00:28:59,850 Specifikimi i kërkon për të krijuar një përkufizim të ri tip 380 00:28:59,850 --> 00:29:03,080 për një nyje binar pemë permban vlerat int - 381 00:29:03,080 --> 00:29:07,110 ashtu si vlerat që nxori në diagramimin tonë përpara. 382 00:29:07,110 --> 00:29:11,740 Ne jemi duke shkuar për të përdorur këtë Boilerplate typedef që ne i kemi bërë të drejtë këtu 383 00:29:11,740 --> 00:29:14,420 që ju duhet të njohin nga Set Problem 5 - 384 00:29:14,420 --> 00:29:19,190 në qoftë se ju e bëri rrugën tabelë hash të programit pushtues speller. 385 00:29:19,190 --> 00:29:22,540 Ju gjithashtu duhet të njohin atë nga neni javës së kaluar 386 00:29:22,540 --> 00:29:23,890 ku kemi biseduar për listat e lidhura. 387 00:29:23,890 --> 00:29:27,870 Ne kemi marrë këtë typedef i një nyje struct, 388 00:29:27,870 --> 00:29:34,430 dhe ne kemi dhënë këtë nyje struct këtë emër e nyjeve struct parë 389 00:29:34,430 --> 00:29:39,350 kështu që ne mund të pastaj i referohen asaj që ne do të duan të kenë pointers nyjen struct 390 00:29:39,350 --> 00:29:45,740 si pjesë e struct tonë, por ne kemi pas rrethuar këtë - 391 00:29:45,740 --> 00:29:47,700 ose më mirë, mbyllur këtë - në një typedef 392 00:29:47,700 --> 00:29:54,600 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. 393 00:29:54,600 --> 00:30:03,120 >> Kjo do të jetë shumë i ngjashëm me përkufizimin e veçmas të lidhur listës që pamë javën e kaluar. 394 00:30:03,120 --> 00:30:20,070 Për ta bërë këtë, le të fillojë vetëm me shkrim nga Boilerplate. 395 00:30:20,070 --> 00:30:23,840 Ne e dimë se ne duhet të kemi një vlerë numër të plotë, 396 00:30:23,840 --> 00:30:32,170 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 - 397 00:30:32,170 --> 00:30:33,970 si ne e bëmë me-veçmas të lidhura listat - 398 00:30:33,970 --> 00:30:38,110 ne do të kemi pointers majtë dhe të djathtë të fëmijës. 399 00:30:38,110 --> 00:30:42,880 Kjo është shumë e shumë e thjeshtë - struct fëmija nyje * majtë; 400 00:30:42,880 --> 00:30:51,190 dhe struct * nyja fëmija i drejtë;. Cool. 401 00:30:51,190 --> 00:30:54,740 Kjo duket si një fillim mjaft të mirë. 402 00:30:54,740 --> 00:30:58,530 Le të kthehemi në specifikimet. 403 00:30:58,530 --> 00:31:05,030 >> Tani ne duhet të deklarojë një ndryshore globale * nyje për rrënjët e një pemë. 404 00:31:05,030 --> 00:31:10,590 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. 405 00:31:10,590 --> 00:31:12,690 Kjo ishte mënyrë që në funksionet që kemi shkruar 406 00:31:12,690 --> 00:31:16,180 ne nuk kemi për të mbajtur kaluar rreth kësaj rrënjë - 407 00:31:16,180 --> 00:31:19,620 edhe pse ne do të shohim se në qoftë se ju nuk doni të shkruani këto funksione Recursively, 408 00:31:19,620 --> 00:31:22,830 ajo mund të jetë më mirë që të mos kalojë edhe atë rreth si një globale në vendin e parë 409 00:31:22,830 --> 00:31:28,090 dhe në vend nisja atë në nivel lokal në funksion tuaj kryesor. 410 00:31:28,090 --> 00:31:31,960 Por, ne do të bëjmë atë në nivel global për të filluar. 411 00:31:31,960 --> 00:31:39,920 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 *. 412 00:31:39,920 --> 00:31:46,770 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. 413 00:31:46,770 --> 00:31:52,210 Tani, në funksion kryesor - të cilat ne do të shkruaj vërtetë shpejt drejtë këtu - 414 00:31:52,210 --> 00:32:00,450 int kryesore (int argc, const char * argv []) - 415 00:32:00,450 --> 00:32:10,640 dhe unë jam duke shkuar për të filluar deklaruar array tim argv si const vetëm kështu që unë e di 416 00:32:10,640 --> 00:32:14,550 se këto argumente janë argumente që unë ndoshta nuk dëshironi të modifikoni. 417 00:32:14,550 --> 00:32:18,390 Në qoftë se unë dua të modifikojë ato që unë ndoshta duhet të jetë bërë kopje të tyre. 418 00:32:18,390 --> 00:32:21,740 Ju do të shihni këtë shumë në kodin. 419 00:32:21,740 --> 00:32:25,440 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. 420 00:32:25,440 --> 00:32:28,630 Unë zakonisht e vënë atë në vetëm kështu që unë kujtoj veten 421 00:32:28,630 --> 00:32:33,650  që unë ndoshta nuk dëshironi të modifikoni ato argumente. 422 00:32:33,650 --> 00:32:39,240 >> Si gjithmonë, unë jam duke shkuar për të përfshirë këtë linjë 0 kthimit në fund të kryesore. 423 00:32:39,240 --> 00:32:45,730 Ja, unë do të nisja nyjen time rrënjë. 424 00:32:45,730 --> 00:32:48,900 Siç qëndron tani, unë kam marrë një tregues që është vendosur për të pavlefshëm, 425 00:32:48,900 --> 00:32:52,970 kështu që është vënë në asgjë. 426 00:32:52,970 --> 00:32:57,480 Në mënyrë që në fakt të fillojë ndërtimin e nyje, 427 00:32:57,480 --> 00:32:59,250 Unë së pari duhet të siguroj kujtesë për të. 428 00:32:59,250 --> 00:33:05,910 Unë jam duke shkuar për të bërë këtë duke bërë memorie në tog përdorur malloc. 429 00:33:05,910 --> 00:33:10,660 Unë jam duke shkuar për të vendosur rrënjë të barabartë me rezultat malloc, 430 00:33:10,660 --> 00:33:19,550 dhe unë jam duke shkuar për të përdorur operatorin sizeof për të llogaritur madhësinë e një nyje. 431 00:33:19,550 --> 00:33:24,990 Arsyeja që unë e përdor nyjen sizeof në krahasim me, të themi, 432 00:33:24,990 --> 00:33:37,020 bërë diçka si kjo - malloc (4 + 4 + 4) ose malloc 12 - 433 00:33:37,020 --> 00:33:40,820 është sepse unë dua kodi im të jetë si në përputhje të jetë e mundur. 434 00:33:40,820 --> 00:33:44,540 Unë dua të jem në gjendje për të marrë këtë skedar. C, përpiloni atë në aplikim, 435 00:33:44,540 --> 00:33:48,820 dhe pastaj përpilojnë atë në Mac 64-bit time - 436 00:33:48,820 --> 00:33:52,040 ose në një arkitekturë krejtësisht të ndryshme - 437 00:33:52,040 --> 00:33:54,640 dhe unë dua që kjo të gjithë të punojnë të njëjtën gjë. 438 00:33:54,640 --> 00:33:59,510 >> Nëse unë jam duke e bërë supozime në lidhje me madhësinë e variablave - 439 00:33:59,510 --> 00:34:02,070 madhësia e një int apo madhësinë e një akrep - 440 00:34:02,070 --> 00:34:06,070 atëherë unë jam bërë edhe supozime në lidhje me llojet e arkitekturave 441 00:34:06,070 --> 00:34:10,440 në të cilën kodi im mund me sukses të përpilojë kur ekzekutohet. 442 00:34:10,440 --> 00:34:15,030 Gjithmonë përdorni sizeof në krahasim me dorë mbledhur fushat struct. 443 00:34:15,030 --> 00:34:20,500 Arsyeja tjetër është se nuk mund të jetë gjithashtu mbushje që përpiluesi i vë në struct. 444 00:34:20,500 --> 00:34:26,570 Edhe vetëm mbledhur fushat individuale nuk është diçka që ju zakonisht dëshironi të bëni, 445 00:34:26,570 --> 00:34:30,340 kështu, fshini atë linjë. 446 00:34:30,340 --> 00:34:33,090 Tani, me të vërtetë nisja këtë nyjë rrënjë, 447 00:34:33,090 --> 00:34:36,489 Unë do të duhet të vihet në prizë vlera për secilin nga fusha të ndryshme të saj. 448 00:34:36,489 --> 00:34:41,400 Për shembull, për vlerën që unë e di unë dua të nisja në 7, 449 00:34:41,400 --> 00:34:46,920 dhe tani për tani unë jam duke shkuar për të vendosur fëmijën e majtë të jetë e pavlefshme 450 00:34:46,920 --> 00:34:55,820 dhe fëmijës të drejtën të jetë gjithashtu null. E madhe! 451 00:34:55,820 --> 00:35:02,670 Ne kemi bërë atë pjesë të spec. 452 00:35:02,670 --> 00:35:07,390 >> Specifikimi poshtë në fund të faqes 3 pyet mua për të krijuar tre nyjet më të - 453 00:35:07,390 --> 00:35:10,600 një që përmban 3, një përmban 6, dhe një me 9 - 454 00:35:10,600 --> 00:35:14,210 dhe pastaj ato tela kështu që duket tamam si diagramin tonë pemë 455 00:35:14,210 --> 00:35:17,120 se ne ishim duke folur në lidhje me parë. 456 00:35:17,120 --> 00:35:20,450 Le të bëjmë që shumë shpejt këtu. 457 00:35:20,450 --> 00:35:26,270 Ju do të shihni të vërtetë shpejt që unë jam duke shkuar për të filloni të shkruani një bandë të kodit kopjuar. 458 00:35:26,270 --> 00:35:32,100 Unë jam duke shkuar për të krijuar një * nyje dhe unë jam duke shkuar për të thirrur atë tre. 459 00:35:32,100 --> 00:35:36,000 Unë jam duke shkuar për të vendosur atë barabartë me malloc (sizeof (nyje)). 460 00:35:36,000 --> 00:35:41,070 Unë jam duke shkuar për të vendosur tri-> vlera = 3. 461 00:35:41,070 --> 00:35:54,780 Tre -> left_child = NULL; tre -> drejta _child = NULL; si. 462 00:35:54,780 --> 00:36:01,150 Kjo duket goxha i ngjashëm me fillimin e rrënjë, dhe kjo është pikërisht ajo që 463 00:36:01,150 --> 00:36:05,760 Unë do të duhet të bëni në qoftë se unë të fillojë Initializing 6 dhe 9 si. 464 00:36:05,760 --> 00:36:20,720 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, 465 00:36:20,720 --> 00:36:46,140 dhe sigurohuni se unë - mirë. 466 00:36:46,470 --> 00:37:09,900  Tani, unë kam marrë atë kopjohen dhe unë mund të shkoni përpara dhe të vendosur këtë barabartë me 6. 467 00:37:09,900 --> 00:37:14,670 Ju mund të shihni se kjo merr kohë dhe nuk është super-efikas. 468 00:37:14,670 --> 00:37:22,610 Në vetëm pak, ne do të shkruajnë një funksion që do të bëjë këtë për ne. 469 00:37:22,610 --> 00:37:32,890 Unë dua të zëvendësuar këtë me një 9, të zëvendësojë atë me një 6. 470 00:37:32,890 --> 00:37:37,360 >> Tani ne kemi marrë të gjitha nyjet tona krijuar dhe initialized. 471 00:37:37,360 --> 00:37:41,200 Ne kemi marrë rrënja jonë vendosur barabartë me 7, apo që përmbajnë vlerën 7, 472 00:37:41,200 --> 00:37:46,510 nyja jonë përmban 3, nyja jonë përmban 6, dhe nyja jonë përmban 9. 473 00:37:46,510 --> 00:37:50,390 Në këtë pikë, të gjithë ne duhet të bëni është gjithçka tela lart. 474 00:37:50,390 --> 00:37:53,020 Arsyeja që unë initialized gjitha pointers null është vetëm mënyrë që unë bëni të sigurtë që 475 00:37:53,020 --> 00:37:56,260 Unë nuk kam ndonjë pointers uninitialized në atje nga aksident. 476 00:37:56,260 --> 00:38:02,290 Dhe gjithashtu që, në këtë pikë, unë vetëm duhet të vërtetë lidhë nyjet me njëri-tjetrin - 477 00:38:02,290 --> 00:38:04,750 për ato që ata janë të lidhur në fakt për - unë nuk kam për të shkuar deri dhe të bëjë 478 00:38:04,750 --> 00:38:08,240 Sigurohuni që të gjitha nulls janë në atje në vendet e duhura. 479 00:38:08,240 --> 00:38:15,630 >> Duke filluar në rrënjë, unë e di që fëmija majtë rrënja është 3. 480 00:38:15,630 --> 00:38:21,250 Unë e di që fëmija të drejtë rrënja është 9. 481 00:38:21,250 --> 00:38:24,880 Pas kësaj, i vetmi fëmijë tjetër që unë kam lënë për t'u shqetësuar rreth 482 00:38:24,880 --> 00:38:39,080 është fëmijë drejtë 3-së, e cila është 6. 483 00:38:39,080 --> 00:38:44,670 Në këtë pikë, të gjithë duket goxha e mirë. 484 00:38:44,670 --> 00:38:54,210 Ne do të fshini disa nga këto linja. 485 00:38:54,210 --> 00:38:59,540 Tani gjithçka duket goxha e mirë. 486 00:38:59,540 --> 00:39:04,240 Le të kthehemi në specifikim tonë dhe të shohim se çfarë ne duhet të bëjmë tjetër. 487 00:39:04,240 --> 00:39:07,610 >> Në këtë pikë, ne kemi për të shkruar një funksion të quajtur "përmban ' 488 00:39:07,610 --> 00:39:14,150 me një prototip të 'përmban bool (int vlera) ". 489 00:39:14,150 --> 00:39:17,060 Dhe kjo përmban funksion do të kthehen e vërtetë 490 00:39:17,060 --> 00:39:21,200  në qoftë se pema theksuar me ndryshore globale tonë rrënjë 491 00:39:21,200 --> 00:39:26,950  përmban vlerën kaluar në funksion dhe të rreme ndryshe. 492 00:39:26,950 --> 00:39:29,000 Le të shkojnë përpara dhe të bëjë atë. 493 00:39:29,000 --> 00:39:35,380 Kjo do të jetë pikërisht si lookup që kemi bërë me dorë në iPad vetëm pak më parë. 494 00:39:35,380 --> 00:39:40,130 Le të zoom prapa në pak dhe lëvizni lart. 495 00:39:40,130 --> 00:39:43,130 Ne jemi duke shkuar për të vënë këtë funksion drejtë mbi funksioni ynë kryesor 496 00:39:43,130 --> 00:39:48,990 kështu që ne nuk duhet të bëjmë çdo lloj prototyping. 497 00:39:48,990 --> 00:39:55,960 Pra, bool përmban (int vlera). 498 00:39:55,960 --> 00:40:00,330 Nuk shkojmë. Ka deklarata tonë Boilerplate. 499 00:40:00,330 --> 00:40:02,900 Vetëm për të bërë të sigurtë që kjo do të hartojë, 500 00:40:02,900 --> 00:40:06,820 Unë jam duke shkuar për të shkuar përpara dhe të vendosur vetëm atë të barabartë për t'u kthyer rreme. 501 00:40:06,820 --> 00:40:09,980 Tani për tani ky funksion thjesht nuk do të bëjë asgjë dhe gjithmonë raportojnë se 502 00:40:09,980 --> 00:40:14,010 vlera që ne jemi duke kërkuar për nuk është në pemë. 503 00:40:14,010 --> 00:40:16,280 >> Në këtë pikë, ajo është ndoshta një ide e mirë - 504 00:40:16,280 --> 00:40:19,600 që ne kemi shkruar një bandë e tërë të kodit dhe ne nuk kemi provuar edhe testimin e tij ende - 505 00:40:19,600 --> 00:40:22,590 për të siguruar që të gjitha harton. 506 00:40:22,590 --> 00:40:27,460 Ka disa gjëra që ne duhet të bëni për të siguruar që kjo vërtetë do të përpilojnë. 507 00:40:27,460 --> 00:40:33,530 Së pari, të shohim nëse ne kemi qenë duke përdorur ndonjë funksion në çdo bibliotekave që ne nuk kemi përfshirë ende. 508 00:40:33,530 --> 00:40:37,940 Funksionet ne kemi përdorur deri tani janë malloc, 509 00:40:37,940 --> 00:40:43,310 dhe pastaj ne kemi qenë gjithashtu duke përdorur këtë lloj - këtë lloj nonstandard quajtur 'bool' - 510 00:40:43,310 --> 00:40:45,750 i cili është i përfshirë në dosjen standarde header bool. 511 00:40:45,750 --> 00:40:53,250 Ne patjetër duan të përfshijnë bool.h standarde për llojin bool, 512 00:40:53,250 --> 00:40:59,230 dhe ne gjithashtu duam të përfshijë # lib.h standarde për bibliotekat standarde 513 00:40:59,230 --> 00:41:03,530 që përfshijnë malloc, dhe të lirë, dhe të gjithë se. 514 00:41:03,530 --> 00:41:08,660 Pra, zoom out, ne jemi duke shkuar për të lënë. 515 00:41:08,660 --> 00:41:14,190 Le të përpiqen dhe të sigurohemi se ky fakt e bëri përpiloni. 516 00:41:14,190 --> 00:41:18,150 Ne e shohim se ai bën, kështu që ne jemi në rrugën e duhur. 517 00:41:18,150 --> 00:41:22,990 >> Le të hapë binary_tree.c përsëri. 518 00:41:22,990 --> 00:41:34,530 Ai përpilon. Le të shkojnë poshtë dhe të sigurohemi që kemi futur disa thirrje të funksionit përmban tonë - 519 00:41:34,530 --> 00:41:40,130 vetëm për të siguruar se kjo është e gjitha mirë dhe të mirë. 520 00:41:40,130 --> 00:41:43,170 Për shembull, kur ne e bëmë disa Lookups në pemë tonë më herët, 521 00:41:43,170 --> 00:41:48,500 Ne u përpoq të shikoni vlerat 6, 10, dhe 1, dhe ne e dinim se ishte 6 në pemë, 522 00:41:48,500 --> 00:41:52,220 10 nuk ishte në pemë, dhe 1 nuk ishte në pemë ose. 523 00:41:52,220 --> 00:41:57,230 Le të përdorim këto thirrje mostër, si një mënyrë për të kuptoj se nëse apo jo 524 00:41:57,230 --> 00:41:59,880 Funksioni përmban jonë është duke punuar. 525 00:41:59,880 --> 00:42:05,210 Në mënyrë që të bëni këtë, unë jam duke shkuar për të përdorur funksionin printf, 526 00:42:05,210 --> 00:42:10,280 dhe ne jemi duke shkuar për të shtypura nga rezultatet e thirrjes për të përmban. 527 00:42:10,280 --> 00:42:13,280 Unë jam duke shkuar për të vënë në një varg "përmban (% d) = sepse 528 00:42:13,280 --> 00:42:20,470  ne jemi duke shkuar për të plug në vlerën që ne jemi duke shkuar për të kërkuar, 529 00:42:20,470 --> 00:42:27,130 dhe =% s \ n "dhe se si të përdorin vargun tonë format. 530 00:42:27,130 --> 00:42:30,720 Ne jemi vetëm duke shkuar për të parë - fjalë për fjalë të shtypura jashtë në ekran - 531 00:42:30,720 --> 00:42:32,060 ajo që duket si një thirrje të funksionit. 532 00:42:32,060 --> 00:42:33,580 Kjo nuk është në fakt thirrjen funksion. 533 00:42:33,580 --> 00:42:36,760  Kjo është vetëm një varg i projektuar për të duken si një thirrje të funksionit. 534 00:42:36,760 --> 00:42:41,140 >> Tani, ne jemi duke shkuar për të vihet në prizë vlerat. 535 00:42:41,140 --> 00:42:43,580 Ne jemi duke shkuar për të provoni përmban më 6, 536 00:42:43,580 --> 00:42:48,340 dhe pastaj ajo që ne jemi duke shkuar për të bërë këtu është të përdorin atë operatori treshe. 537 00:42:48,340 --> 00:42:56,340 Le të shohim - përmban 6 - Pra, tani unë kam përmbante 6 dhe nëse përmban 6 është e vërtetë, 538 00:42:56,340 --> 00:43:01,850 vargu që ne jemi duke shkuar për të dërguar të karakterit të% s format 539 00:43:01,850 --> 00:43:04,850 do të jetë vargu "e vërtetë". 540 00:43:04,850 --> 00:43:07,690 Le të lëvizni mbi një pak. 541 00:43:07,690 --> 00:43:16,210 Përndryshe, ne duam të dërgoni string "false" nëse përmban 6 kthimit të rreme. 542 00:43:16,210 --> 00:43:19,730 Kjo është pak budalla-looking, por unë kuptoj unë mund edhe të ilustruar 543 00:43:19,730 --> 00:43:23,780 çfarë Operatori tresh duket pasi ne nuk kemi parë atë për pak kohë. 544 00:43:23,780 --> 00:43:27,670 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. 545 00:43:27,670 --> 00:43:30,040 Unë jam duke shkuar për të lëvizni përsëri mbi të majtë, 546 00:43:30,040 --> 00:43:39,900 dhe unë jam duke shkuar për të kopjoni dhe ngjisni këtë linjë disa herë. 547 00:43:39,900 --> 00:43:44,910 Ajo ndryshoi disa prej këtyre vlerave rreth, 548 00:43:44,910 --> 00:43:59,380 kështu që kjo do të jetë 1, dhe kjo do të jetë 10. 549 00:43:59,380 --> 00:44:02,480 >> Në këtë pikë ne kemi marrë një funksion të mirë përmban. 550 00:44:02,480 --> 00:44:06,080 Ne kemi marrë disa teste, dhe ne do të shohim nëse kjo të gjitha veprat. 551 00:44:06,080 --> 00:44:08,120 Në këtë pikë ne e kemi shkruar kodin disa më shumë. 552 00:44:08,120 --> 00:44:13,160 Koha për të lënë jashtë dhe të sigurohemi që çdo gjë ende përpilon. 553 00:44:13,160 --> 00:44:20,360 Quit jashtë, dhe tani le të përpiqemi të bërë dru binar përsëri. 554 00:44:20,360 --> 00:44:22,260 E pra, kjo duket si ne kemi marrë një gabim, 555 00:44:22,260 --> 00:44:26,930 dhe ne kemi marrë këtë në mënyrë eksplicite duke deklaruar funksionin e bibliotekës printf. 556 00:44:26,930 --> 00:44:39,350 Ajo duket si ne kemi nevojë për të shkuar në dhe # include standardio.h. 557 00:44:39,350 --> 00:44:45,350 Dhe me këtë, çdo gjë duhet të përpiloni. Ne jemi të gjithë të mirë. 558 00:44:45,350 --> 00:44:50,420 Tani le të përpiqemi drejtimin pemë binare dhe shikoni se çfarë ndodh. 559 00:44:50,420 --> 00:44:53,520 Këtu jemi,. / Binary_tree, 560 00:44:53,520 --> 00:44:55,190 dhe ne shohim se, siç kemi pritur - 561 00:44:55,190 --> 00:44:56,910 sepse ne nuk kemi zbatuar përmban ende, 562 00:44:56,910 --> 00:44:59,800 ose më mirë, ne kemi vënë vetëm në këmbim të rremë - 563 00:44:59,800 --> 00:45:03,300 ne e shohim se ajo është vetëm kthimin e rreme për të gjithë ata, 564 00:45:03,300 --> 00:45:06,180 kështu që është e gjitha që punojnë për pjesën më të madhe mjaft mirë. 565 00:45:06,180 --> 00:45:11,860 >> Le të kthehemi në dhe në fakt përmban zbatuar në këtë pikë. 566 00:45:11,860 --> 00:45:17,490 Unë jam duke shkuar për të lëvizni poshtë, zoom në, dhe - 567 00:45:17,490 --> 00:45:22,330 Mos harroni, algoritmi që kemi përdorur ka qenë se kemi filluar në nyjen rrënjë 568 00:45:22,330 --> 00:45:28,010 dhe pastaj në çdo nyje që hasim, ne bëjmë një krahasim, 569 00:45:28,010 --> 00:45:32,380 dhe bazuar në këtë krahasim, ne ose të shkojë në fëmijën e majtë ose të djathtë të fëmijës. 570 00:45:32,380 --> 00:45:39,670 Kjo do të duken shumë të ngjashme me kodin kërkim dyor që ka shkruar në fillim të mandatit. 571 00:45:39,670 --> 00:45:47,810 Kur ne nisem, ne e dimë që ne duam për të mbajtur në nyjen e tanishme 572 00:45:47,810 --> 00:45:54,050 se ne duke kërkuar në, dhe nyja aktual do të jetë initialized të nyjes root. 573 00:45:54,050 --> 00:45:56,260 Dhe tani, ne jemi duke shkuar për të mbajtur të shkojnë nëpër pemë, 574 00:45:56,260 --> 00:45:58,140 dhe mos harroni se gjendjen tonë ndalimi - 575 00:45:58,140 --> 00:46:01,870  kur ne fakt punuar përmes shembullit me dorë - 576 00:46:01,870 --> 00:46:03,960 ishte kur kemi hasur në një nyje null, 577 00:46:03,960 --> 00:46:05,480 kur nuk kemi shikuar në një fëmijë null, 578 00:46:05,480 --> 00:46:09,620 por, kur ne fakt shkoi në një nyje në pemë 579 00:46:09,620 --> 00:46:12,640 dhe gjeti se ne jemi në një nyje null. 580 00:46:12,640 --> 00:46:20,720 Ne jemi duke shkuar për të iterate deri cur nuk është e barabartë me null. 581 00:46:20,720 --> 00:46:22,920 Dhe çfarë do të bëjmë ne? 582 00:46:22,920 --> 00:46:31,610 Ne jemi duke shkuar për të provuar nëse (tani -> vlera == vlera), 583 00:46:31,610 --> 00:46:35,160 atëherë ne e dimë se e kemi gjetur në fakt nyja që ne jemi duke kërkuar për të. 584 00:46:35,160 --> 00:46:40,450 Kështu që këtu, ne mund të kthehen vërtetë. 585 00:46:40,450 --> 00:46:49,830 Përndryshe, ne duam të shohim nëse janë apo jo vlera është më e vogël se vlera. 586 00:46:49,830 --> 00:46:53,850 Nëse vlera nyjen aktual është më pak se vlera ne jemi duke kërkuar për të, 587 00:46:53,850 --> 00:46:57,280 ne jemi duke shkuar për të lëvizur në të djathtë. 588 00:46:57,280 --> 00:47:10,600 Pra, cur = cur -> right_child, dhe ndryshe, ne jemi duke shkuar për të lëvizur në të majtë. 589 00:47:10,600 --> 00:47:17,480 = cur momen -> left_child;. Shumë e thjeshtë. 590 00:47:17,480 --> 00:47:22,830 >> Ju ndoshta e njeh lak që duket shumë e ngjashme me këtë nga 591 00:47:22,830 --> 00:47:27,580 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ë. 592 00:47:27,580 --> 00:47:30,000 Këtu, ne vetëm duhet të shikoni në një vlerë aktuale, 593 00:47:30,000 --> 00:47:31,930 kështu që është e bukur dhe e thjeshtë. 594 00:47:31,930 --> 00:47:34,960 Le të sigurohemi ky kod është duke punuar. 595 00:47:34,960 --> 00:47:42,780 Së pari, sigurohuni që ajo harton. Duket si ajo bën. 596 00:47:42,780 --> 00:47:47,920 Le të provoni drejtimin e tij. 597 00:47:47,920 --> 00:47:50,160 Dhe me të vërtetë, ajo shtyp gjithçka që kemi pritur. 598 00:47:50,160 --> 00:47:54,320 Ajo gjen 6 në pemë, nuk ka gjetur 10 sepse 10 nuk është në pemë, 599 00:47:54,320 --> 00:47:57,740 dhe nuk ka gjetur as 1 1, sepse nuk është edhe në pemë. 600 00:47:57,740 --> 00:48:01,420 Cool stuff. 601 00:48:01,420 --> 00:48:04,470 >> Mirë. Le të kthehemi në specifikim tonë dhe të shohim se ç'pritet më tej. 602 00:48:04,470 --> 00:48:07,990 Tani, ajo dëshiron për të shtuar nyje disa më shumë për të pemës tonë. 603 00:48:07,990 --> 00:48:11,690 Ajo dëshiron të shtojë 5, 2 dhe 8, dhe sigurohuni që përmban kodin tonë 604 00:48:11,690 --> 00:48:13,570 ende punon ashtu siç pritet. 605 00:48:13,570 --> 00:48:14,900 Le të shkojë të bëjë këtë. 606 00:48:14,900 --> 00:48:19,430 Në këtë pikë, në vend se duke bërë atë kopje bezdisshëm dhe paste përsëri, 607 00:48:19,430 --> 00:48:23,770 le të shkruajnë një funksion të vërtetë të krijuar një nyje. 608 00:48:23,770 --> 00:48:27,740 Nëse ne lëvizni poshtë të gjitha mënyra për të kryesore, shohim se ne kemi qenë bërë këtë 609 00:48:27,740 --> 00:48:31,210 Kodi shumë të ngjashme pushim çdo herë që ne duam të krijuar një nyje. 610 00:48:31,210 --> 00:48:39,540 >> Le të shkruajnë një funksion që në të vërtetë do të ndërtojë një nyje për ne dhe ta kthejë atë. 611 00:48:39,540 --> 00:48:41,960 Unë jam duke shkuar për të thirrur atë build_node. 612 00:48:41,960 --> 00:48:45,130 Unë jam duke shkuar për të ndërtuar një nyje me një vlerë të veçantë. 613 00:48:45,130 --> 00:48:51,040 Zoom në këtu. 614 00:48:51,040 --> 00:48:56,600 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. 615 00:48:56,600 --> 00:49:05,400 Pra, nyje * n = malloc (sizeof (nyje)); n -> vlera = Vlera; 616 00:49:05,400 --> 00:49:14,960 dhe pastaj këtu, unë jam vetëm do të nisja të gjitha fushat të jenë vlerat e duhura. 617 00:49:14,960 --> 00:49:22,500 Dhe në fund, ne do të kthehen nyjen tonë. 618 00:49:22,500 --> 00:49:28,690 Mirë. Një gjë të theksohet është se ky funksion drejtë këtu 619 00:49:28,690 --> 00:49:34,320 do të kthehen një tregues për kujtesën që ka qenë tog-ndau. 620 00:49:34,320 --> 00:49:38,880 Çfarë është e mirë për këtë është se kjo nyja tani - 621 00:49:38,880 --> 00:49:42,420 ne duhet të deklarojnë atë në grumbull, sepse nëse ne shpalli atë në rafte 622 00:49:42,420 --> 00:49:45,050 ne nuk do të jetë në gjendje të bëjë atë në këtë funksion si kjo. 623 00:49:45,050 --> 00:49:47,690 Se kujtesa do të shkojnë jashtë fushës 624 00:49:47,690 --> 00:49:51,590 dhe do të jetë i pavlefshëm në qoftë se ne u përpoq për të hyrë në atë më vonë. 625 00:49:51,590 --> 00:49:53,500 Që ne jemi deklaruar tog-ndahen kujtesës, 626 00:49:53,500 --> 00:49:55,830 ne do të duhet të kujdeset për të liruar atë më vonë 627 00:49:55,830 --> 00:49:58,530 për programin tonë të mos rrjedhje ndonjë kujtesës. 628 00:49:58,530 --> 00:50:01,270 Ne kemi qenë në punting se për çdo gjë tjetër në kodin 629 00:50:01,270 --> 00:50:02,880 vetëm për hir të thjeshtësisë në atë kohë, 630 00:50:02,880 --> 00:50:05,610 por në qoftë se keni shkruar një funksion që duket si ky 631 00:50:05,610 --> 00:50:10,370 ku ju keni marrë - disa e quajnë atë një malloc ose realloc brenda - 632 00:50:10,370 --> 00:50:14,330 ju doni të bëni të sigurtë që ju të vënë disa lloj komenti deri këtu që thotë, 633 00:50:14,330 --> 00:50:29,970 hej, ju e dini, kthen një nyje tog-alokohen nisur me vlerën kaloi-në. 634 00:50:29,970 --> 00:50:33,600 Dhe pastaj ju doni të bëni të sigurtë që ju të vënë në disa lloj shënim që thotë se 635 00:50:33,600 --> 00:50:41,720 thirrësi duhet të lirojë kujtesën kthyer. 636 00:50:41,720 --> 00:50:45,450 Në këtë mënyrë, nëse dikush ndonjëherë shkon dhe e përdor atë funksion, 637 00:50:45,450 --> 00:50:48,150 ata e dinë se çfarëdo që ata marrin nga mbrapa atë funksion 638 00:50:48,150 --> 00:50:50,870 në disa pika do të duhet të lirohen. 639 00:50:50,870 --> 00:50:53,940 >> Duke supozuar se të gjitha është e mirë dhe të mirë këtu, 640 00:50:53,940 --> 00:51:02,300 ne mund të shkojnë poshtë në kodin tonë dhe të zëvendësojë të gjitha këto rreshta të drejtë këtu 641 00:51:02,300 --> 00:51:05,410 me thirrjet për të ndërtuar funksionin tonë nyjeve. 642 00:51:05,410 --> 00:51:08,170 Le të bëjmë që me të vërtetë shpejt. 643 00:51:08,170 --> 00:51:15,840 Një pjesë që ne nuk jemi duke shkuar për të zëvendësuar është kjo pjesë këtu poshtë 644 00:51:15,840 --> 00:51:18,520 në fund, ku ne fakt tela deri nyjet për pikë me njëri-tjetrin, 645 00:51:18,520 --> 00:51:21,030 për shkak se ne nuk mund të bëjmë në funksion tonë. 646 00:51:21,030 --> 00:51:37,400 Por, le bëjë rrënjë = build_node (7); nyje * tre = build_node (3); 647 00:51:37,400 --> 00:51:47,980 nyje * gjashtë = build_node (6); nyje * nëntë = build_node (9);. 648 00:51:47,980 --> 00:51:52,590 Dhe tani, ne gjithashtu donte për të shtuar nyje për - 649 00:51:52,590 --> 00:52:03,530 nyje * pesë = build_node (5); nyje * tetë = build_node (8); 650 00:52:03,530 --> 00:52:09,760 dhe çfarë ishte nyja tjetër? Le të shohim këtu. Ne kemi kërkuar të shtoni edhe një 2 - 651 00:52:09,760 --> 00:52:20,280 nyje * dy = build_node (2);. 652 00:52:20,280 --> 00:52:26,850 Mirë. Në këtë pikë, ne e dimë se ne kemi marrë 7, 3, 9, dhe 6 653 00:52:26,850 --> 00:52:30,320 gjitha Wired në mënyrë të përshtatshme, por ajo që për 5, 8, dhe 2? 654 00:52:30,320 --> 00:52:33,550 Të mbajë çdo gjë në mënyrë të duhur, 655 00:52:33,550 --> 00:52:39,230 ne e dimë se fëmija drejta Tre është 6. 656 00:52:39,230 --> 00:52:40,890 Pra, në qoftë se ne jemi duke shkuar për të shtuar 5, 657 00:52:40,890 --> 00:52:46,670 e 5 edhe i takon në anën e djathtë të pemës e cila është rrënja 3, 658 00:52:46,670 --> 00:52:50,440 aq 5 i takon si fëmijën e majtë të 6. 659 00:52:50,440 --> 00:52:58,650 Ne mund ta bëjë këtë duke thënë, gjashtë -> left_child = pesë; 660 00:52:58,650 --> 00:53:10,790 dhe pastaj 8 takon si fëmijën e majtë të 9, kështu nëntë -> left_child = tetë; 661 00:53:10,790 --> 00:53:22,190 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;. 662 00:53:22,190 --> 00:53:27,730 Nëse ju nuk e keni mjaft të ndjekin së bashku me këtë, unë sugjeroj që ju tërheq atë vetë. 663 00:53:27,730 --> 00:53:35,660 >> Mirë. Le të shpëtuar këtë. Le të shkojnë jashtë dhe sigurohuni që ajo harton, 664 00:53:35,660 --> 00:53:40,760 dhe pastaj ne mund të shtoni në thirrjet përmban tona. 665 00:53:40,760 --> 00:53:44,120 Duket si çdo gjë ende përpilon. 666 00:53:44,120 --> 00:53:51,790 Le të shkojnë në dhe të shtoni në disa përmban thirrje. 667 00:53:51,790 --> 00:53:59,640 Përsëri, unë jam duke shkuar për të bërë një pak të kopjoni dhe ngjisni. 668 00:53:59,640 --> 00:54:15,860 Tani le të kërkoni për 5, 8, dhe 2. Mirë. 669 00:54:15,860 --> 00:54:28,330 Le të sigurohemi që e gjithë kjo duket e mirë ende. E madhe! Ruaj dhe u largua. 670 00:54:28,330 --> 00:54:33,220 Tani le të bëjnë, hartojnë, dhe tani le të kandidojë. 671 00:54:33,220 --> 00:54:37,540 Nga rezultatet, duket se çdo gjë është duke punuar vetëm mirë dhe të mirë. 672 00:54:37,540 --> 00:54:41,780 E madhe! Deri tani ne kemi marrë përmban tona funksionojnë me shkrim. 673 00:54:41,780 --> 00:54:46,160 Le të lëvizin dhe të fillojë të punojë mbi atë se si për të futur nyjet në pemë 674 00:54:46,160 --> 00:54:50,000 që, si ne jemi duke bërë atë të drejtë tani, gjërat nuk janë shumë të bukur. 675 00:54:50,000 --> 00:54:52,280 >> Nëse ne do të shkojmë përsëri në specifikim, 676 00:54:52,280 --> 00:55:00,540 ajo na kërkon për të shkruar një funksion të quajtur futur - përsëri, duke u kthyer një bool 677 00:55:00,540 --> 00:55:04,400 për të nëse janë apo jo ne fakt mund të futni nyja në pemë - 678 00:55:04,400 --> 00:55:07,710 dhe pastaj vlera për të futur në pemë është specifikuar si 679 00:55:07,710 --> 00:55:11,060 Argumenti i vetëm për funksionin tonë insert. 680 00:55:11,060 --> 00:55:18,180 Ne do të kthehen vërtetë në qoftë se ne mund të vërtetë të futur vlera nyje përmban në pemë, 681 00:55:18,180 --> 00:55:20,930 që do të thotë se ne, një, kishte kujtesë të mjaftueshme, 682 00:55:20,930 --> 00:55:24,840 dhe pastaj dy, se nyja nuk ekzistojnë në pemë prej - 683 00:55:24,840 --> 00:55:32,170 Mos harroni, ne nuk do të kemi vlera të kopjuar në pemë, vetëm për të bërë gjëra të thjeshta. 684 00:55:32,170 --> 00:55:35,590 Mirë. Kthehu në kodin. 685 00:55:35,590 --> 00:55:44,240 Hapur atë. Zoom në një grimë, pastaj lëviz poshtë. 686 00:55:44,240 --> 00:55:47,220 Le të vënë funksionin insert mbi të drejtën përmban. 687 00:55:47,220 --> 00:55:56,360 Përsëri, ajo do të quhet insert bool (int vlera). 688 00:55:56,360 --> 00:56:01,840 T'i jepte një hapësirë ​​pak më shumë, dhe pastaj, si parazgjedhje, 689 00:56:01,840 --> 00:56:08,870 le të vënë në këmbim të rreme në fund. 690 00:56:08,870 --> 00:56:22,620 Tani poshtë në fund, le të shkojnë përpara dhe në vend të manualisht ndërtimin e nyjet 691 00:56:22,620 --> 00:56:27,900 në kryesore veten dhe instalime elektrike deri në ato tregojnë për njëri-tjetrin si ne jemi duke bërë, 692 00:56:27,900 --> 00:56:30,600 ne do të mbështetemi në funksion tonë të shkruaj për të bërë këtë. 693 00:56:30,600 --> 00:56:35,510 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, 694 00:56:35,510 --> 00:56:39,970 por ne do të të hequr qafe të këtyre linjave - we'll komentuar nga këto linja - 695 00:56:39,970 --> 00:56:43,430 që të ndërtojë nyjet 5, 8, dhe 2. 696 00:56:43,430 --> 00:56:55,740 Dhe në vend, ne do të futur thirrje të funksionojë tonë futur 697 00:56:55,740 --> 00:57:01,280 për të siguruar se që në fakt funksionon. 698 00:57:01,280 --> 00:57:05,840 Këtu ne do të shkojmë. 699 00:57:05,840 --> 00:57:09,300 >> Tani ne kemi komentuar këto linja. 700 00:57:09,300 --> 00:57:13,700 Ne kemi vetëm 7, 3, 9, dhe 6 në pemë tonë në këtë pikë. 701 00:57:13,700 --> 00:57:18,870 Për të bërë të sigurt se kjo është e gjitha duke punuar, 702 00:57:18,870 --> 00:57:25,050 ne mund të zoom jashtë, të bëjë pemë binare tonë, 703 00:57:25,050 --> 00:57:30,750 drejtuar atë, dhe ne mund të shohim se përmban tani është duke na thënë se ne jemi plotësisht të drejtë - 704 00:57:30,750 --> 00:57:33,110 5, 8, dhe 2 nuk janë më në pema. 705 00:57:33,110 --> 00:57:37,960 Kthehu mbrapa në kodin, 706 00:57:37,960 --> 00:57:41,070 dhe si jemi duke shkuar për të futur? 707 00:57:41,070 --> 00:57:46,290 Mbani mend se çfarë kemi bërë kur ishim futur në fakt 5, 8, 2 dhe më parë. 708 00:57:46,290 --> 00:57:50,100 Ne kemi luajtur atë lojë Plinko ku kemi filluar në rrënjë, 709 00:57:50,100 --> 00:57:52,780 zbriti në një pemë nga një nga një 710 00:57:52,780 --> 00:57:54,980 derisa kemi gjetur hendekun e duhur, 711 00:57:54,980 --> 00:57:57,570 dhe pastaj ne Wired në nyje në vendin e duhur. 712 00:57:57,570 --> 00:57:59,480 Ne jemi duke shkuar për të bërë të njëjtën gjë. 713 00:57:59,480 --> 00:58:04,070 Kjo është në thelb si shkrim kodin që kemi përdorur në funksion përmban 714 00:58:04,070 --> 00:58:05,910 për të gjetur vendin ku duhet të jetë nyje, 715 00:58:05,910 --> 00:58:10,560 dhe pastaj ne jemi vetëm duke shkuar për të futur në nyjen e drejtë atje. 716 00:58:10,560 --> 00:58:17,000 Le të fillojnë të bëjnë këtë. 717 00:58:17,000 --> 00:58:24,200 >> Pra, ne kemi një nyje * cur = root, ne jemi vetëm do të ndjekin përmban kodin 718 00:58:24,200 --> 00:58:26,850 deri sa të gjejmë se ai nuk ka mjaft të punojnë për ne. 719 00:58:26,850 --> 00:58:32,390 Ne jemi duke shkuar për të shkuar nëpër pemë, ndërsa elementi aktual nuk është i pavlefshëm, 720 00:58:32,390 --> 00:58:45,280 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 - 721 00:58:45,280 --> 00:58:49,600 mirë, kjo është një nga rastet në të cilat ne nuk mund të vërtetë të futur nyjen 722 00:58:49,600 --> 00:58:52,730 në pemë, sepse kjo do të thotë që ne kemi një vlerë të kopjuar. 723 00:58:52,730 --> 00:58:59,010 Këtu ne jemi të vërtetë do të kthehen rreme. 724 00:58:59,010 --> 00:59:08,440 Tani tjetër, në qoftë se vlera e monedhes është më pak se vlera, 725 00:59:08,440 --> 00:59:10,930 tani ne e dimë se kemi lëvizur në të djathtë 726 00:59:10,930 --> 00:59:17,190  sepse vlera e takon në gjysmën e djathtë të pemës monedhes. 727 00:59:17,190 --> 00:59:30,110 Përndryshe, ne jemi duke shkuar për të lëvizur në të majtë. 728 00:59:30,110 --> 00:59:37,980 Kjo është në thelb përmban tona funksionojë drejtë atje. 729 00:59:37,980 --> 00:59:41,820 >> Në këtë pikë, pasi ne kemi përfunduar këtë lak, ndërsa, 730 00:59:41,820 --> 00:59:47,350 akrep tonë cur do të jetë duke treguar null 731 00:59:47,350 --> 00:59:51,540 Nëse funksioni nuk është kthyer tashmë. 732 00:59:51,540 --> 00:59:58,710 Prandaj, ne jemi të paturit e situ në vendin ku ne duam të futur nyjen e re. 733 00:59:58,710 --> 01:00:05,210 Ajo që mbetet për t'u bërë është që në fakt të ndërtuar nyjen e re, 734 01:00:05,210 --> 01:00:08,480 të cilat ne mund të bëjmë shumë lehtë. 735 01:00:08,480 --> 01:00:14,930 Ne mund të përdorim super-dobishëm funksionin jonë ndërtuar nyje, 736 01:00:14,930 --> 01:00:17,210 dhe diçka që ne nuk e ka bërë më parë - 737 01:00:17,210 --> 01:00:21,400 ne vetëm lloj i mori për të dhënë, por tani ne do të bëjmë vetëm për të siguruar - 738 01:00:21,400 --> 01:00:27,130 ne do të provuar për të siguruar që vlera e kthyer nga nyja e re ishte në të vërtetë 739 01:00:27,130 --> 01:00:33,410 Nuk null, sepse ne nuk duam të fillojë qasjen atë memorie në qoftë se është i pavlefshëm. 740 01:00:33,410 --> 01:00:39,910 Ne mund të provoni të bëni të sigurtë që nyja e re nuk është e barabartë me null. 741 01:00:39,910 --> 01:00:42,910 Ose në vend, ne vetëm mund të shohim nëse ajo vërtetë është i pavlefshëm, 742 01:00:42,910 --> 01:00:52,120 dhe në qoftë se ai është i pavlefshëm, atëherë ne vetëm mund të kthehen rreme herët. 743 01:00:52,120 --> 01:00:59,090 >> Në këtë pikë, ne duhet të tela nyje të re në vend të saj të duhur në pemë. 744 01:00:59,090 --> 01:01:03,510 Nëse ne shikojmë prapa në kryesore dhe ku ne ishim të vërtetë instalime elektrike në vlerat më parë, 745 01:01:03,510 --> 01:01:08,470 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ë 746 01:01:08,470 --> 01:01:11,750 ishte ne disponim fëmijën e majtë të rrënjë. 747 01:01:11,750 --> 01:01:14,920 Kur ne kemi vënë 9 në pemë, kemi pasur për të hyrë në të drejtën e fëmijës rrënjë. 748 01:01:14,920 --> 01:01:21,030 Ne duhet të kishte një tregues të prindit në mënyrë për të vënë një vlerë të re në pemë. 749 01:01:21,030 --> 01:01:24,430 Scroll back up për të futur, se nuk do të mjaft të punojnë këtu 750 01:01:24,430 --> 01:01:27,550 sepse ne nuk kemi një tregues prind. 751 01:01:27,550 --> 01:01:31,650 Ajo që ne duam të jetë në gjendje të bëni është, në këtë pikë, 752 01:01:31,650 --> 01:01:37,080 kontrolloni vlerën e prindërve dhe të shohim - mirë, Gosh, 753 01:01:37,080 --> 01:01:41,990 në qoftë se vlera e prindërve është më pak se vlera e tanishme, 754 01:01:41,990 --> 01:01:54,440 atëherë fëmija e drejta e prindit duhet të jetë nyja e re; 755 01:01:54,440 --> 01:02:07,280 ndryshe, fëmija e majtë e prindërve duhet të jetë nyja e re. 756 01:02:07,280 --> 01:02:10,290 Por, ne nuk kemi këtë treguesin prind mjaft ende. 757 01:02:10,290 --> 01:02:15,010 >> 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ë 758 01:02:15,010 --> 01:02:18,440 dhe për të gjetur vendin e duhur në lak tonë më sipër. 759 01:02:18,440 --> 01:02:26,840 Ne mund të bëjmë që nga Scroll mbrapa deri në krye të funksionit tonë futur 760 01:02:26,840 --> 01:02:32,350 dhe ndjekja e një ndryshore tregues quhet prind. 761 01:02:32,350 --> 01:02:39,340 Ne jemi duke shkuar për të vendosur atë të barabartë me null fillimisht, 762 01:02:39,340 --> 01:02:43,640 dhe pastaj çdo herë ne do të shkojmë nëpër pemë, 763 01:02:43,640 --> 01:02:51,540 ne jemi duke shkuar për të vendosur treguesin prind për ndeshjen treguesin aktual. 764 01:02:51,540 --> 01:02:59,140 Set prind të barabartë me monedhes. 765 01:02:59,140 --> 01:03:02,260 Në këtë mënyrë, çdo herë që ne të shkojnë nëpër, 766 01:03:02,260 --> 01:03:05,550 ne jemi duke shkuar për të siguruar që, si tregues i tanishëm merr incremented 767 01:03:05,550 --> 01:03:12,640 tregues prind ndjek atë - vetëm një nivel më të lartë se sa treguesin e tanishme në pemë. 768 01:03:12,640 --> 01:03:17,370 Që të gjithë duket goxha e mirë. 769 01:03:17,370 --> 01:03:22,380 >> Unë mendoj se një gjë që ne do të duan për të rregulluar këtë është ndërtuar null nyje kthyer. 770 01:03:22,380 --> 01:03:25,380 Në mënyrë që të marrë të ndërtuar nyje të vërtetë sukses kthehen null, 771 01:03:25,380 --> 01:03:31,060 ne do të duhet të modifikojë atë kod, 772 01:03:31,060 --> 01:03:37,270 sepse këtu, nuk kemi testuar për të siguruar që malloc kthyer një tregues të vlefshëm. 773 01:03:37,270 --> 01:03:53,390 Pra, në qoftë se (n = NULL!), Atëherë - 774 01:03:53,390 --> 01:03:55,250 nëse malloc kthyer një tregues të vlefshëm, atëherë ne do të nisja atë; 775 01:03:55,250 --> 01:04:02,540 Përndryshe, ne vetëm do të kthehen dhe që do të përfundojë deri në kthimin null për ne. 776 01:04:02,540 --> 01:04:13,050 Tani të gjitha duket goxha e mirë. Le t'u siguruar që kjo në fakt përpilon. 777 01:04:13,050 --> 01:04:22,240 Të bëjë pemë binare, dhe oh, ne kemi marrë disa sende po ndodh këtu. 778 01:04:22,240 --> 01:04:29,230 >> Ne kemi marrë një deklaratë të nënkuptuar e funksionit të ndërtuar nyje. 779 01:04:29,230 --> 01:04:31,950 Përsëri, me këto hartuesit, ne jemi duke shkuar për të filluar në krye. 780 01:04:31,950 --> 01:04:36,380 Se çka duhet të them është se unë jam duke e quajtur nyje të ndërtuar para se unë kam deklaruar në fakt atë. 781 01:04:36,380 --> 01:04:37,730 Le të kthehemi në kodin vërtetë shpejt. 782 01:04:37,730 --> 01:04:43,510 Shkoni poshtë, dhe pa dyshim, funksioni im insert është shpallur 783 01:04:43,510 --> 01:04:47,400 mbi nyjen funksionit të ndërtuar, 784 01:04:47,400 --> 01:04:50,070 por unë jam duke u përpjekur për të përdorur të ndërtuar në brendësi të futur nyje. 785 01:04:50,070 --> 01:05:06,610 Unë jam duke shkuar për të shkuar në dhe kopje - dhe pastaj paste funksion nyje të ndërtuar rrugë këtu në krye. 786 01:05:06,610 --> 01:05:11,750 Në këtë mënyrë, shpresojmë që do të punojnë. Le të japim këtë një tjetër të shkojnë. 787 01:05:11,750 --> 01:05:18,920 Tani të gjitha harton. Të gjitha është e mirë. 788 01:05:18,920 --> 01:05:21,640 >> Por në këtë pikë, nuk kemi të vërtetë quhet funksionin tonë insert. 789 01:05:21,640 --> 01:05:26,510 Ne vetëm e di se ai përpilon, kështu që le të shkojnë në dhe të vënë disa telefonata in 790 01:05:26,510 --> 01:05:28,240 Le të bëjmë që në funksion tonë kryesore. 791 01:05:28,240 --> 01:05:32,390 Këtu, ne komentoi nga 5, 8, dhe 2, 792 01:05:32,390 --> 01:05:36,680 dhe pastaj ne nuk teli tyre deri këtu poshtë. 793 01:05:36,680 --> 01:05:41,640 Le të bëjë disa thirrje për të futur, 794 01:05:41,640 --> 01:05:46,440 dhe le të përdorë gjithashtu edhe të njëjtin lloj gjëra që ne e përdorur 795 01:05:46,440 --> 01:05:52,810 kur kemi bërë këto thirrje printf për t'u siguruar se çdo gjë e kam marrë futur siç duhet. 796 01:05:52,810 --> 01:06:00,550 Unë jam duke shkuar për të kopjoni dhe ngjisni, 797 01:06:00,550 --> 01:06:12,450 dhe në vend të përmban, ne do të bëjmë futur. 798 01:06:12,450 --> 01:06:30,140 Dhe në vend të 6, 10, dhe 1, ne jemi duke shkuar për të përdorur 5, 8, dhe 2. 799 01:06:30,140 --> 01:06:37,320 Kjo duhet të shpresojmë insert 5, 8, 2 dhe në pemë. 800 01:06:37,320 --> 01:06:44,050 Përpiloni. Të gjitha është e mirë. Tani ne do të vërtetë të drejtuar programin tonë. 801 01:06:44,050 --> 01:06:47,330 >> Gjithçka u kthye rreme. 802 01:06:47,330 --> 01:06:53,830 Pra, 5, 8, dhe 2 nuk shkojnë, dhe kjo duket si Përmban nuk i gjente ato ose. 803 01:06:53,830 --> 01:06:58,890 Çfarë po ndodh? Le të zoom jashtë. 804 01:06:58,890 --> 01:07:02,160 Problemi i parë ishte se insert dukej të kthehen rreme, 805 01:07:02,160 --> 01:07:08,750 dhe kjo duket si kjo është për shkak se ne e kemi lënë në thirrjen tonë kthimit të rreme, 806 01:07:08,750 --> 01:07:14,590 dhe nuk jemi kthyer në fakt e vërtetë. 807 01:07:14,590 --> 01:07:17,880 Ne mund të përcaktuar se deri. 808 01:07:17,880 --> 01:07:25,290 Problemi i dytë është, tani edhe në qoftë se ne bëjmë - të shpëtuar këtë, lë këtë, 809 01:07:25,290 --> 01:07:34,530 drejtuar të bëjë përsëri, e kanë atë të hartojnë, pastaj të drejtuar atë - 810 01:07:34,530 --> 01:07:37,670 ne shohim se diçka tjetër ka ndodhur këtu. 811 01:07:37,670 --> 01:07:42,980 E 5, 8, dhe 2 u gjetën kurrë nuk ende në pemë. 812 01:07:42,980 --> 01:07:44,350 Pra, çfarë po ndodh? 813 01:07:44,350 --> 01:07:45,700 >> Le të marrin një vështrim në këtë në kodin. 814 01:07:45,700 --> 01:07:49,790 Le të shohim nëse ne mund të kuptoj këtë. 815 01:07:49,790 --> 01:07:57,940 Ne fillim me prind mos qenë null. 816 01:07:57,940 --> 01:07:59,510 Ne kemi vendosur treguesin aktuale të barabartë me treguesin rrënjë, 817 01:07:59,510 --> 01:08:04,280 dhe ne jemi duke shkuar për të punuar rrugën tonë poshtë nëpër pemë. 818 01:08:04,280 --> 01:08:08,650 Nëse nyjen e tanishme nuk është i pavlefshëm, atëherë ne e dimë se ne mund të lëvizin poshtë pak. 819 01:08:08,650 --> 01:08:12,330 Ne kemi vendosur treguesin tonë mëmë të jetë e barabartë me treguesin e tanishme, 820 01:08:12,330 --> 01:08:15,420 kontrolluar vlerën - nëse vlerat janë të njëjta kthyem rreme. 821 01:08:15,420 --> 01:08:17,540 Nëse vlerat janë më pak kemi lëvizur në të djathtë; 822 01:08:17,540 --> 01:08:20,399 ndryshe, kemi lëvizur në të majtë. 823 01:08:20,399 --> 01:08:24,220 Pastaj ne kemi ndërtuar një nyje. Unë do të zoom në një pak. 824 01:08:24,220 --> 01:08:31,410 Dhe këtu, ne do të përpiqemi për të wire deri vlerat të jenë të njëjta. 825 01:08:31,410 --> 01:08:37,250 Çfarë po ndodh? Le të shohim nëse ndoshta Shprehje mund të na jepni një aluzion. 826 01:08:37,250 --> 01:08:43,910 >> Më pëlqen të përdorin Shprehje vetëm për shkak Shprehje vërtetë shpejt shkon 827 01:08:43,910 --> 01:08:46,729 dhe ju tregon se në qoftë se ka ndonjë gabim kujtesës. 828 01:08:46,729 --> 01:08:48,300 Kur kemi drejtuar Shprehje në kodin, 829 01:08:48,300 --> 01:08:55,859 si ju mund të shihni të drejtë here--Valgrind./binary_tree--and hit enter. 830 01:08:55,859 --> 01:09:03,640 Ju shihni se ne nuk kemi asnjë gabim kujtesës, kështu që ajo duket si çdo gjë është në rregull deri tani. 831 01:09:03,640 --> 01:09:07,529 Ne kemi disa rrjedhjet e kujtesës, të cilat ne e dimë, sepse ne nuk jemi 832 01:09:07,529 --> 01:09:08,910 ndodh për të liruar ndonjë nga nyjet tona. 833 01:09:08,910 --> 01:09:13,050 Le të përpiqemi drejtimin gdb për të parë se çfarë është në të vërtetë ndodh. 834 01:09:13,050 --> 01:09:20,010 Ne do të bëjmë gdb. / Binary_tree. Ajo booted deri just fine. 835 01:09:20,010 --> 01:09:23,670 Le të vendosur një pikë pushim në insert. 836 01:09:23,670 --> 01:09:28,600 Le të drejtuar. 837 01:09:28,600 --> 01:09:31,200 Ajo duket si ne nuk të vërtetë quhet insert. 838 01:09:31,200 --> 01:09:39,410 Ajo duket si problemi ishte vetëm se kur kam ndryshuar këtu poshtë në kryesore - 839 01:09:39,410 --> 01:09:44,279 të gjitha këto thirrje printf nga përmban - 840 01:09:44,279 --> 01:09:56,430 Unë kurrë nuk e ndryshoi në fakt këto të thirrur futur. 841 01:09:56,430 --> 01:10:01,660 Tani le t'i jepte një provoni. Le të përpilojnë. 842 01:10:01,660 --> 01:10:09,130 Të gjitha duket e mirë atje. Tani le të përpiqemi drejtimin e tij, shikoni se çfarë ndodh. 843 01:10:09,130 --> 01:10:13,320 Mirë! Çdo gjë duket goxha e mirë atje. 844 01:10:13,320 --> 01:10:18,130 >> Gjëja e fundit për të menduar rreth është, a ka ndonjë raste buzë në këtë insert? 845 01:10:18,130 --> 01:10:23,170 Dhe kjo rezulton se, mirë, një rast avantazh që është gjithmonë interesante për të menduar për 846 01:10:23,170 --> 01:10:26,250 është, çfarë ndodh në qoftë se pema juaj është bosh dhe ju e quani këtë funksion futur? 847 01:10:26,250 --> 01:10:30,330 Do të punojë? E pra, le t'i jepte një provoni. 848 01:10:30,330 --> 01:10:32,110 - Binary_tree c. - 849 01:10:32,110 --> 01:10:35,810 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, 850 01:10:35,810 --> 01:10:41,690 dhe në vend se instalime elektrike këto nyje deri si kjo, 851 01:10:41,690 --> 01:10:56,730 ne jemi vetëm duke shkuar për të komentuar nga të gjithë gjë, 852 01:10:56,730 --> 01:11:02,620 dhe në vend të instalime elektrike deri nyjet veten, 853 01:11:02,620 --> 01:11:09,400 ne fakt mund të thjesht shkoni përpara dhe fshini të gjithë këtë. 854 01:11:09,400 --> 01:11:17,560 Ne jemi duke shkuar për të bërë gjithçka për të futur një telefonatë. 855 01:11:17,560 --> 01:11:49,020 Pra, le ta bëjmë - në vend të 5, 8, dhe 2, ne jemi duke shkuar për të futur 7, 3, dhe 9. 856 01:11:49,020 --> 01:11:58,440 Dhe pastaj ne do të duan të futur 6 si. 857 01:11:58,440 --> 01:12:05,190 Ruaj. Quit. Të bëjë pemë binare. 858 01:12:05,190 --> 01:12:08,540 Të gjitha harton. 859 01:12:08,540 --> 01:12:10,320 Ne vetëm mund të kandidojë atë si është dhe shikoni se çfarë ndodh, 860 01:12:10,320 --> 01:12:12,770 por ajo gjithashtu do të jetë me të vërtetë e rëndësishme për të siguruar që 861 01:12:12,770 --> 01:12:14,740 ne nuk kemi ndonjë gabim kujtesës, 862 01:12:14,740 --> 01:12:16,840 pasi kjo është një nga rastet tona buzë që ne e dimë rreth. 863 01:12:16,840 --> 01:12:20,150 >> Le të bëjnë të sigurt se ajo punon edhe nën Shprehje, 864 01:12:20,150 --> 01:12:28,310 të cilat ne do të bëjmë vetëm me drejtimin Shprehje. / binary_tree. 865 01:12:28,310 --> 01:12:31,110 Ajo duket si ne me të vërtetë kemi një gabim nga një kontekst - 866 01:12:31,110 --> 01:12:33,790 ne e kemi këtë defekt segmentimit. 867 01:12:33,790 --> 01:12:36,690 Çfarë ka ndodhur? 868 01:12:36,690 --> 01:12:41,650 Shprehje fakt na tregon se ku është. 869 01:12:41,650 --> 01:12:43,050 Zoom out pak. 870 01:12:43,050 --> 01:12:46,040 Ajo duket si ajo që po ndodh në funksion tonë insert, 871 01:12:46,040 --> 01:12:53,420 ku ne kemi një lexuar pavlefshme të madhësisë 4 në insert, line 60. 872 01:12:53,420 --> 01:13:03,590 Le të shkojnë prapa dhe të shohim se çfarë po ndodh këtu. 873 01:13:03,590 --> 01:13:05,350 Zoom me të vërtetë të shpejtë. 874 01:13:05,350 --> 01:13:14,230 Unë dua të bëni të sigurtë që nuk shkojnë në buzë të ekranit kështu që ne mund të shohim gjithçka. 875 01:13:14,230 --> 01:13:18,760 Tërhiqe se në një pak. Mirë. 876 01:13:18,760 --> 01:13:35,030 Shkoni poshtë, dhe problemi është e drejtë këtu. 877 01:13:35,030 --> 01:13:40,120 Çfarë ndodh në qoftë se ne të merrni poshtë dhe nyja ynë aktual është tashmë null, 878 01:13:40,120 --> 01:13:44,010 nyja jonë mëmë është null, kështu që nëse ne shikojmë deri në shumë të lartë, të drejtë këtu - 879 01:13:44,010 --> 01:13:47,340 në qoftë se nuk ky lak, ndërsa në fakt ekzekuton 880 01:13:47,340 --> 01:13:52,330 sepse vlera null ynë aktual është - rrënja jonë është aq null cur është i pavlefshëm - 881 01:13:52,330 --> 01:13:57,810 pastaj nuk prindi ynë merr vendosur për monedhes apo në një vlerë të vlefshme, 882 01:13:57,810 --> 01:14:00,580 kështu, prindi do të jetë i pavlefshëm. 883 01:14:00,580 --> 01:14:03,700 Ne duhet të mos harroni të kontrolloni për këtë 884 01:14:03,700 --> 01:14:08,750 me kohë kemi marrë këtu poshtë, dhe ne të fillojnë të hyrë vlerën e prindërve. 885 01:14:08,750 --> 01:14:13,190 Pra, çfarë ndodh? E pra, nëse prindi është i pavlefshëm - 886 01:14:13,190 --> 01:14:17,990 në qoftë se (== NULL prind) - atëherë ne e dimë se 887 01:14:17,990 --> 01:14:19,530 nuk duhet të jetë çdo gjë në pemë. 888 01:14:19,530 --> 01:14:22,030 Ne duhet të jetë duke u përpjekur për të futur atë në rrënjë. 889 01:14:22,030 --> 01:14:32,570 Ne mund ta bëjë këtë vetëm me vendosjen e rrënjë të barabartë me nyje të ri. 890 01:14:32,570 --> 01:14:40,010 Pastaj në këtë pikë, ne nuk të vërtetë duan të shkojnë nëpër këto gjëra të tjera. 891 01:14:40,010 --> 01:14:44,780 Në vend të kësaj, të drejtë këtu, ne mund të bëjmë as një tjetër-nëse-tjetër, 892 01:14:44,780 --> 01:14:47,610 ose ne mund të kombinojnë gjithçka deri këtu në një tjetër, 893 01:14:47,610 --> 01:14:56,300 por këtu ne do të përdorin vetëm tjetër dhe të bëjë atë në këtë mënyrë. 894 01:14:56,300 --> 01:14:59,030 Tani, ne jemi duke shkuar për të provuar për të siguruar që prindi ynë nuk është i pavlefshëm 895 01:14:59,030 --> 01:15:02,160 para se atëherë vërtetë duke u përpjekur për të hyrë në fushat e saj. 896 01:15:02,160 --> 01:15:05,330 Kjo do të na ndihmojë të shmangur fajin segmentimit. 897 01:15:05,330 --> 01:15:14,740 Pra, ne të lë, zoom out, hartojnë, të drejtuar. 898 01:15:14,740 --> 01:15:18,130 >> Nuk ka gabime, por ne ende kemi një bandë e rrjedhjeve të kujtesës 899 01:15:18,130 --> 01:15:20,650 sepse nuk kemi liruar ndonjë nga nyjet tona. 900 01:15:20,650 --> 01:15:24,350 Por, nëse ne do të shkojmë deri këtu dhe ne shikojmë printuar tonë, 901 01:15:24,350 --> 01:15:30,880 ne shohim se, mirë, duket si të gjithë fut tona u kthyer e vërtetë, e cila është e mirë. 902 01:15:30,880 --> 01:15:33,050 Të fut janë të gjitha të vërteta, 903 01:15:33,050 --> 01:15:36,670 dhe pastaj përmban përshtatshme thirrjet janë gjithashtu e vërtetë. 904 01:15:36,670 --> 01:15:41,510 >> Mirë punë! Ajo duket si ne kemi shkruar sukses futur. 905 01:15:41,510 --> 01:15:47,430 Kjo është e gjitha që kemi për Specifikimin Set kësaj jave Problem. 906 01:15:47,430 --> 01:15:51,720 Një sfidë fun për të menduar është se si ju do të vërtetë të shkoni në 907 01:15:51,720 --> 01:15:55,340 dhe pa të gjitha nyjet në këtë pemë. 908 01:15:55,340 --> 01:15:58,830 Ne mund ta bëjë këtë një numër të mënyra të ndryshme, 909 01:15:58,830 --> 01:16:01,930 por unë do të iki se deri tek ju për të eksperimentuar, 910 01:16:01,930 --> 01:16:06,080 dhe si një sfidë fun, të përpiqet dhe të sigurohemi që ju mund të sigurt 911 01:16:06,080 --> 01:16:09,490 se ky raport nuk kthehet Shprehje gabime dhe nuk rrjedhjet. 912 01:16:09,490 --> 01:16:12,880 >> Good luck në Huffman grup kësaj jave coding problemit, 913 01:16:12,880 --> 01:16:14,380 dhe ne do të shohim se javën e ardhshme! 914 01:16:14,380 --> 01:16:17,290 [CS50.TV]