1 00:00:00,000 --> 00:00:02,500 [Powered by Google Translate] [7. §] [Kevesebb Comfortable] 2 00:00:02,500 --> 00:00:04,890 [Nate Hardison] [Harvard Egyetem] 3 00:00:04,890 --> 00:00:07,000 [Ez a CS50.] [CS50.TV] 4 00:00:07,000 --> 00:00:09,080 >> Üdvözöljük a 7. szakasz. 5 00:00:09,080 --> 00:00:11,330 Hála a hurrikán Sandy, 6 00:00:11,330 --> 00:00:13,440 ahelyett, hogy egy normális szakasz ezen a héten, 7 00:00:13,440 --> 00:00:17,650 csináljuk ezt walk-through keresztül részén kérdésekre. 8 00:00:17,650 --> 00:00:22,830 Fogok követni együtt Problem Set 6 előírásnak 9 00:00:22,830 --> 00:00:25,650 és megy keresztül minden kérdésre a 10 00:00:25,650 --> 00:00:27,770 A szakasz Kérdések részben. 11 00:00:27,770 --> 00:00:30,940 Ha vannak olyan kérdések, 12 00:00:30,940 --> 00:00:32,960 kérjük, tegye ezeket CS50 megvitatni. 13 00:00:32,960 --> 00:00:35,480 >> Rendben. Menjünk az induláshoz. 14 00:00:35,480 --> 00:00:40,780 Most nézem a 3. oldalon A probléma Set specifikáció. 15 00:00:40,780 --> 00:00:44,110 Megyünk először kezdi beszélni bináris fák 16 00:00:44,110 --> 00:00:47,850 mivel ezek sok releváns e heti problémája set - 17 00:00:47,850 --> 00:00:49,950 A Huffman fa kódolást. 18 00:00:49,950 --> 00:00:55,000 Az egyik legelső adatszerkezetek beszélgettünk a CS50 volt a tömbben. 19 00:00:55,000 --> 00:01:00,170 Ne feledje, hogy a tömb egy sorozata elemek - 20 00:01:00,170 --> 00:01:04,019 az összes azonos típusú - a tárolt jog egymás mellett a memóriában. 21 00:01:04,019 --> 00:01:14,420 Ha van egy egész sor, hogy tudok felhívni ezzel a doboz-szám-egész stílus - 22 00:01:14,420 --> 00:01:20,290 Tegyük fel, hogy van 5 az első mezőbe, már 7 a második, 23 00:01:20,290 --> 00:01:27,760 akkor már 8, 10, és 20-ben a végső mezőben. 24 00:01:27,760 --> 00:01:33,000 Ne feledje, hogy a kettő igazán jó dolog ez a tömb 25 00:01:33,000 --> 00:01:38,800 az, hogy itt van ez a konstans idejű hozzáférést adott elem 26 00:01:38,800 --> 00:01:40,500  a tömbben, ha tudjuk, az index. 27 00:01:40,500 --> 00:01:44,670 Például, ha azt akarom, hogy megragad a harmadik elem a tömbben - 28 00:01:44,670 --> 00:01:47,870 az index 2 a mi nulla alapú indexelő rendszer - 29 00:01:47,870 --> 00:01:52,220 Én szó szerint csak meg kell csinálni egy egyszerű matematikai számítás 30 00:01:52,220 --> 00:01:56,170 hop e pozícióját a tömb, 31 00:01:56,170 --> 00:01:57,840 húzza ki a 8 tárolt ott, 32 00:01:57,840 --> 00:01:59,260 és én vagyok jó menni. 33 00:01:59,260 --> 00:02:03,350 >> Az egyik rossz dolog ez a tömb -, hogy beszéltünk 34 00:02:03,350 --> 00:02:05,010 amikor beszéltünk kapcsolódó listák - 35 00:02:05,010 --> 00:02:09,120 hogy ha szeretnék beszúrni egy elemet ebbe a tömb, 36 00:02:09,120 --> 00:02:11,090 Megyek, hogy meg kell csinálni néhány változó körül. 37 00:02:11,090 --> 00:02:12,940 Például ez a tömb itt 38 00:02:12,940 --> 00:02:16,850 a rendezett sorrendben - rendezve növekvő sorrendben - 39 00:02:16,850 --> 00:02:19,440 5, majd a 7, majd 8, akkor a 10, majd 20 és - 40 00:02:19,440 --> 00:02:23,100 de ha szeretné szúrni a 9-es számú ebbe a tömb, 41 00:02:23,100 --> 00:02:27,460 Megyek is váltani néhány tényező annak érdekében, hogy helyet. 42 00:02:27,460 --> 00:02:30,440 Tudjuk felhívni ezt itt. 43 00:02:30,440 --> 00:02:35,650 Megyek kell mozgatni az 5, a 7, majd a 8; 44 00:02:35,650 --> 00:02:38,720 hozzon létre egy rés, ahol lehet, hogy a 9, 45 00:02:38,720 --> 00:02:45,910 majd a 10 és a 20 is megy jobbra a 9. 46 00:02:45,910 --> 00:02:49,450 Ez a fajta a fájdalom, mert a legrosszabb esetben - 47 00:02:49,450 --> 00:02:54,350 amikor mi kellene beilleszteni vagy az elején vagy a végén 48 00:02:54,350 --> 00:02:56,040 a tömb, attól függően, hogy mi változik - 49 00:02:56,040 --> 00:02:58,850 talán a végén kelljen váltani az összes elemet 50 00:02:58,850 --> 00:03:00,750 azt, hogy jelenleg tárolja a tömbben. 51 00:03:00,750 --> 00:03:03,810 >> Szóval, mi volt az út körül ez? 52 00:03:03,810 --> 00:03:09,260 Az út körül ez az volt, hogy menjen a linkelt lista módszer, ahol - 53 00:03:09,260 --> 00:03:19,820 tárolása helyett az elemek 5, 7, 8, 10, és 20 mind egymás mellett a memóriában - 54 00:03:19,820 --> 00:03:25,630 mi inkább nem is tárolja a fajta, ahol szerettünk volna tárolni őket 55 00:03:25,630 --> 00:03:32,470 ezekben a linkelt listát csomópontokon vagyok rajz itt, egyfajta ad hoc. 56 00:03:32,470 --> 00:03:42,060 És akkor kapcsolódik össze őket ezekkel a következő mutatók. 57 00:03:42,060 --> 00:03:44,370 Én lehet egy mutató 5 és a 7, 58 00:03:44,370 --> 00:03:46,420 egy mutatót a 7 és a 8, 59 00:03:46,420 --> 00:03:47,770 egy mutatót a 8 és a 10, 60 00:03:47,770 --> 00:03:51,220 és végül, a mutató a 10 a 20, 61 00:03:51,220 --> 00:03:54,880 majd egy null mutató a 20 azt jelzi, hogy nincs semmi a bal. 62 00:03:54,880 --> 00:03:59,690 A trade-off, hogy mi van itt 63 00:03:59,690 --> 00:04:05,360 az, hogy most, ha azt akarjuk, hogy helyezze be a 9-es szám a mi rendezett lista 64 00:04:05,360 --> 00:04:08,270 minden, amit meg kell tennie, hogy hozzon létre egy új csomópontot, 9, 65 00:04:08,270 --> 00:04:12,290 kösse fel, hogy pont a megfelelő helyre, 66 00:04:12,290 --> 00:04:20,630 és azután újra vezeték a 8 és mutasson le a 9. 67 00:04:20,630 --> 00:04:25,660 Ez elég gyors, feltételezve, hogy pontosan tudjuk, hová akarunk szúrni a 9. 68 00:04:25,660 --> 00:04:32,610 De a trade-off cserébe ez, hogy már most elvesztettük a konstans idejű hozzáférést 69 00:04:32,610 --> 00:04:36,230 hogy valamely elemet a mi adatszerkezet. 70 00:04:36,230 --> 00:04:40,950 Például, ha azt akarom, hogy megtalálják a negyedik elem ebben a linkelt listán, 71 00:04:40,950 --> 00:04:43,510 Megyek, hogy meg kell kezdeni a legelején a lista 72 00:04:43,510 --> 00:04:48,930 és a munka az én utam a számláló node-by-node amíg meg nem találom a negyedik. 73 00:04:48,930 --> 00:04:55,870 >> Annak érdekében, hogy jobb hozzáférés teljesítményt nyújt, mint a láncolt lista - 74 00:04:55,870 --> 00:04:59,360 hanem megtartja néhány az előnyök, hogy mi volt 75 00:04:59,360 --> 00:05:01,800 szempontjából beiktatási idő a láncolt lista - 76 00:05:01,800 --> 00:05:05,750 egy bináris fa lesz szüksége, hogy egy kicsit több memóriát igényel. 77 00:05:05,750 --> 00:05:11,460 Különösen, ahelyett, hogy csak, amelyek egy mutatót egy bináris fa csomópont - 78 00:05:11,460 --> 00:05:13,350 mint a linkelt lista node nem - 79 00:05:13,350 --> 00:05:16,950 fogunk egy második mutatót a bináris fa csomópontot. 80 00:05:16,950 --> 00:05:19,950 Ahelyett, hogy csak, amely egy mutató a következő elemre, 81 00:05:19,950 --> 00:05:24,420 megyünk, hogy egy mutató egy balra gyermek és a jobb gyermek. 82 00:05:24,420 --> 00:05:26,560 >> Hadd dolgozzon egy képet, hogy milyen, hogy néznek ki. 83 00:05:26,560 --> 00:05:31,350 Ismét fogom használni ezeket a dobozokat és nyilakat. 84 00:05:31,350 --> 00:05:37,150 A bináris fa csomópont kezdetben csak egy egyszerű doboz. 85 00:05:37,150 --> 00:05:40,940 Ez lesz egy hely az érték, 86 00:05:40,940 --> 00:05:47,280 , majd ez is megy, hogy egy helyet a bal és a jobb gyermek gyermek. 87 00:05:47,280 --> 00:05:49,280 Megyek felcímkézni őket. 88 00:05:49,280 --> 00:05:57,560 Fogjuk, hogy a bal oldali gyermek, aztán megyünk joga gyermeket. 89 00:05:57,560 --> 00:05:59,920 Sok különböző módon ezt. 90 00:05:59,920 --> 00:06:02,050 Néha a tér és kényelem, 91 00:06:02,050 --> 00:06:06,460 Én tényleg döntetlen érzés csinálok itt az alsó 92 00:06:06,460 --> 00:06:10,910 hová megyek, hogy az érték a tetején, 93 00:06:10,910 --> 00:06:14,060 majd a jobb gyermeket a jobb alsó, 94 00:06:14,060 --> 00:06:16,060 és a bal gyerek a bal alsó. 95 00:06:16,060 --> 00:06:20,250 Visszatérve a top diagram, 96 00:06:20,250 --> 00:06:22,560 van az érték, a legtetején, 97 00:06:22,560 --> 00:06:25,560 akkor mi van a bal-gyermek mutatót, és akkor megvan a joga-gyermek mutatót. 98 00:06:25,560 --> 00:06:30,110 >> A probléma Set előírásnak 99 00:06:30,110 --> 00:06:33,110 beszélünk rajz egy csomópont, amelynek értéke 7, 100 00:06:33,110 --> 00:06:39,750 majd egy bal-utód pointer azaz null, és a jobb-gyermek pointer, ami null. 101 00:06:39,750 --> 00:06:46,040 Mi sem levelet tőkét NULL a teret 102 00:06:46,040 --> 00:06:51,610 a bal és a jobb gyermek gyermek, vagy tudjuk felhívni a diagonális perjel 103 00:06:51,610 --> 00:06:53,750 révén az egyes dobozok, jelezve, hogy ez null. 104 00:06:53,750 --> 00:06:57,560 Fogom csinálni, hogy csak azért, mert ez az egyszerűbb. 105 00:06:57,560 --> 00:07:03,700 Amit itt látsz két módon diagramkészítő egy nagyon egyszerű bináris fa csomópont 106 00:07:03,700 --> 00:07:07,960 ahol van az érték 7 és null gyermek mutatók. 107 00:07:07,960 --> 00:07:15,220 >> A második rész a leírás arról beszél, hogy a kapcsolt listák - 108 00:07:15,220 --> 00:07:18,270 emlékszem, már csak megtartani a legelső elem a listán 109 00:07:18,270 --> 00:07:20,270 meg kell emlékezni a teljes lista - 110 00:07:20,270 --> 00:07:26,140 és hasonlóképpen, egy bináris fa, csak meg kell tartani az egyik mutató a fa 111 00:07:26,140 --> 00:07:31,120 fenntartása érdekében ellenőrzés a teljes adatszerkezet. 112 00:07:31,120 --> 00:07:36,150 Ez a speciális eleme a fa, az úgynevezett gyökér csomópont a fa. 113 00:07:36,150 --> 00:07:43,360 Például, ha ez csomópont - ez csomópont tartalmazza az érték 7 114 00:07:43,360 --> 00:07:45,500 null bal-és jobb-gyermek mutatók - 115 00:07:45,500 --> 00:07:47,360 volt az egyetlen érték a fa, 116 00:07:47,360 --> 00:07:50,390 akkor ez lenne a mi gyökér csomópont. 117 00:07:50,390 --> 00:07:52,240 Ez a kezdetektől fogva a mi fa. 118 00:07:52,240 --> 00:07:58,530 Láthatjuk ezt egy kicsit pontosabban, ha elkezdjük hozzá több csomópont a mi fa. 119 00:07:58,530 --> 00:08:01,510 Hadd húzza fel egy új oldalt. 120 00:08:01,510 --> 00:08:05,000 >> Most megyünk, hogy készítsen egy fa, amely 7-én a gyökér, 121 00:08:05,000 --> 00:08:10,920 és 3 belső a bal gyermek, és 9 belső a jobb gyermek. 122 00:08:10,920 --> 00:08:13,500 Ismét, ez elég egyszerű. 123 00:08:13,500 --> 00:08:26,510 Van 7, rajzoljon egy csomópont a 3, a csomópont 9, 124 00:08:26,510 --> 00:08:32,150 és én fogom be a bal-gyermek 7-pointer mutasson a csomópont, amely 3, 125 00:08:32,150 --> 00:08:37,850 és a jobb-gyermek mutató a csomópont, amely 7, hogy a csomópont, amely 9. 126 00:08:37,850 --> 00:08:42,419 Most, mivel 3 és 9 nincs gyermekek, 127 00:08:42,419 --> 00:08:48,500 fogunk állítani az összes gyermekük mutatókat is null. 128 00:08:48,500 --> 00:08:56,060 Itt a gyökere a fa megfelel a csomópont, amely a 7-es szám. 129 00:08:56,060 --> 00:09:02,440 Láthatjuk, hogy ha minden van egy mutató, hogy a gyökér csomópont, 130 00:09:02,440 --> 00:09:07,330 tudjuk majd séta a fák és a hozzáférést mind a gyermek csomópontok - 131 00:09:07,330 --> 00:09:10,630 mindegyike 3 és 9. 132 00:09:10,630 --> 00:09:14,820 Nem kell fenntartani mutatókat minden egyes csomópontnak a fán. 133 00:09:14,820 --> 00:09:22,080 Rendben. Most megyünk újabb csomópontot ezt diagram. 134 00:09:22,080 --> 00:09:25,370 Megyünk, hogy adjunk egy csomópont, amely 6, 135 00:09:25,370 --> 00:09:34,140 és mi megyünk hozzá ezt a jogot gyermek csomópont, amely 3. 136 00:09:34,140 --> 00:09:41,850 Ehhez fogom kitörölni, hogy null pointer a 3-as csomópont 137 00:09:41,850 --> 00:09:47,750 és bekötésének fel, hogy pont a csomópont, amely 6. Rendben. 138 00:09:47,750 --> 00:09:53,800 >> Ezen a ponton, menjünk át egy kicsit a terminológiát. 139 00:09:53,800 --> 00:09:58,230 Elindításához, az oka, hogy ez az úgynevezett bináris fa, különösen 140 00:09:58,230 --> 00:10:00,460 az, hogy két gyermeke mutatók. 141 00:10:00,460 --> 00:10:06,020 Vannak más típusú fák több gyermek mutatók. 142 00:10:06,020 --> 00:10:10,930 Különösen, ha nem egy "próbálja" a Problem Set 5. 143 00:10:10,930 --> 00:10:19,310 Észre fogod venni, hogy ebben az próbálkozás, hogy volt 27 különböző mutatókat a különböző gyermekek - 144 00:10:19,310 --> 00:10:22,410 egy-egy a 26 betű az angol ábécé, 145 00:10:22,410 --> 00:10:25,410 majd a 27. az aposztróf - 146 00:10:25,410 --> 00:10:28,900 igen, ez hasonló a típusú fa. 147 00:10:28,900 --> 00:10:34,070 De itt, mivel a bináris, akkor csak két gyermeke mutatók. 148 00:10:34,070 --> 00:10:37,880 >> Ezen kívül a gyökér csomópont, hogy mi beszéltünk, 149 00:10:37,880 --> 00:10:41,470 általunk is dobott körül ezt a kifejezést "gyermek". 150 00:10:41,470 --> 00:10:44,470 Mit jelent ez egy csomópont, hogy a gyermek egy másik csomópont? 151 00:10:44,470 --> 00:10:54,060 Ez szó szerint azt jelenti, hogy a gyermek csomópont egy gyermek egy másik csomópont 152 00:10:54,060 --> 00:10:58,760 ha a másik csomópont egyik gyermek mutatók állítva, hogy pont, hogy a csomópont. 153 00:10:58,760 --> 00:11:01,230 Ahhoz, hogy ezt figyelembe konkrétabban, 154 00:11:01,230 --> 00:11:11,170 ha 3 Hangsúlyozzuk, hogy az egyik a gyermek mutatók 7, akkor a 3. gyerek 7. 155 00:11:11,170 --> 00:11:14,510 Ha volt, hogy kitaláljuk, mi a gyerekek közül 7 - 156 00:11:14,510 --> 00:11:18,510 nos, azt látjuk, hogy van egy 7 mutató 3 és a mutató 9, 157 00:11:18,510 --> 00:11:22,190 így 9 és 3 gyermekei 7. 158 00:11:22,190 --> 00:11:26,650 Kilenc nincs gyerek, mert a gyerek pointers null, 159 00:11:26,650 --> 00:11:30,940 és 3 csak egy gyerek, 6. 160 00:11:30,940 --> 00:11:37,430 Hat szintén nem gyermekek, mert mind a mutatók olyan null, amelyet akkor döntetlen most. 161 00:11:37,430 --> 00:11:45,010 >> Továbbá, mi is beszélünk a szülők egy adott csomópont, 162 00:11:45,010 --> 00:11:51,100 és ez, ahogy az elvárható, a fordítottja a gyermek leírás. 163 00:11:51,100 --> 00:11:58,620 Minden csomópont csak az egyik szülő - kettő helyett, mint az várható az emberekkel. 164 00:11:58,620 --> 00:12:03,390 Így például, a szülő a 3 7. 165 00:12:03,390 --> 00:12:10,800 A szülő a 9 is, 7, és a szülő 6-3 lehet. Nem sok hozzá. 166 00:12:10,800 --> 00:12:15,720 Mi is kifejezések beszélni nagyszülők és az unokák, 167 00:12:15,720 --> 00:12:18,210 és általánosságban beszélünk az ősök 168 00:12:18,210 --> 00:12:20,960 és leszármazottai egy adott csomópont. 169 00:12:20,960 --> 00:12:25,710 Az őse egy csomópont - vagy ősök inkább egy csomópont - 170 00:12:25,710 --> 00:12:32,730 mind a csomópontok fekszenek az út a gyökértől az adott csomópont. 171 00:12:32,730 --> 00:12:36,640 Például, ha nézem a 6 csomópont, 172 00:12:36,640 --> 00:12:46,430 akkor az ősök lesznek mind a 3 és 7. 173 00:12:46,430 --> 00:12:55,310 Az ősei 9, például - már ha nézem a csomópont 9 - 174 00:12:55,310 --> 00:12:59,990 akkor az őse a 9 csupán 7. 175 00:12:59,990 --> 00:13:01,940 És leszármazottaik pontosan az ellenkezője történt. 176 00:13:01,940 --> 00:13:05,430 Ha azt akarom, hogy nézd meg az összes leszármazottai 7, 177 00:13:05,430 --> 00:13:11,020 akkor meg kell nézni az összes csomópont alatta. 178 00:13:11,020 --> 00:13:16,950 Szóval, van 3, 9 és 6 Összes leszármazottai 7. 179 00:13:16,950 --> 00:13:24,170 >> Az utolsó kifejezés, hogy fogunk beszélni, ez az elképzelés, hogy egy testvér. 180 00:13:24,170 --> 00:13:27,980 Testvérek - fajta követő mentén e családi feltételek - 181 00:13:27,980 --> 00:13:33,150 olyan csomópontok, amelyek ugyanazon a szinten a fán. 182 00:13:33,150 --> 00:13:42,230 Így, a 3. és a 9. testvérek mert ugyanazon a szinten a fán. 183 00:13:42,230 --> 00:13:46,190 Mindkettő ugyanolyan szülő, 7. 184 00:13:46,190 --> 00:13:51,400 A 6 nincs testvére, mert 9 nincsenek gyerekek. 185 00:13:51,400 --> 00:13:55,540 És 7 nem rendelkezik testvérei, mert ez a gyökér a fa, 186 00:13:55,540 --> 00:13:59,010 és van mindig csak 1 root. 187 00:13:59,010 --> 00:14:02,260 A 7, hogy testvérei oda kellene egy csomópont 7 feletti. 188 00:14:02,260 --> 00:14:07,480 Ehhez az kellene, hogy egy szülő 7, amely esetben 7 nem lenne a gyökér a fa. 189 00:14:07,480 --> 00:14:10,480 Aztán, hogy az új 7-szülő is van, hogy egy gyerek, 190 00:14:10,480 --> 00:14:16,480 és hogy a gyermek akkor lenne a testvére 7. 191 00:14:16,480 --> 00:14:21,040 >> Rendben. Lépjünk tovább. 192 00:14:21,040 --> 00:14:24,930 Amikor elkezdtük vitánk bináris fák, 193 00:14:24,930 --> 00:14:28,790 beszélgettünk arról, hogy hogyan fogunk használni őket, hogy 194 00:14:28,790 --> 00:14:32,800 szert előnyt mind tömbök és láncolt listákat. 195 00:14:32,800 --> 00:14:37,220 És ahogy fogjuk csinálni, hogy van ezzel a rendelési tulajdonság. 196 00:14:37,220 --> 00:14:41,080 Azt mondjuk, hogy a bináris fa elrendelte, a specifikáció szerint, 197 00:14:41,080 --> 00:14:45,740 ha minden csomópont a mi fa, annak minden leszármazottja a bal oldalon - 198 00:14:45,740 --> 00:14:48,670 a bal gyermek, és az összes a baloldal gyermek utódai - 199 00:14:48,670 --> 00:14:54,510 tekintette kisebb értékeket, és az összes a csomópontok a jobb - 200 00:14:54,510 --> 00:14:57,770 a megfelelő gyermek, és az összes a jog gyermek utódai - 201 00:14:57,770 --> 00:15:02,800 tekintette csomópontok nagyobb az értéke a jelenlegi csomópont keresünk. 202 00:15:02,800 --> 00:15:07,850 Csak az egyszerűség kedvéért, fogjuk feltételezni, hogy nincsenek ismétlődő csomópont a mi fa. 203 00:15:07,850 --> 00:15:11,180 Például ez a fa nem fogunk foglalkozni az üggyel 204 00:15:11,180 --> 00:15:13,680 ahol van az érték 7-gyökér 205 00:15:13,680 --> 00:15:16,720  és akkor is az érték 7-mailt a fán. 206 00:15:16,720 --> 00:15:24,390 Ebben az esetben, észre fogod venni, hogy ez a fa valóban rendelhető. 207 00:15:24,390 --> 00:15:26,510 Megvan az érték 7-nél a gyökér. 208 00:15:26,510 --> 00:15:29,720 Minden, ami a bal oldalon 7 - 209 00:15:29,720 --> 00:15:35,310 ha undo az összes ilyen apró jelek itt - 210 00:15:35,310 --> 00:15:40,450 minden balra a 7 - a 3 és a 6 - 211 00:15:40,450 --> 00:15:49,410 ezek az értékek egyaránt kevesebb, mint 7, és minden jobbra -, amely csak ezt a 9 - 212 00:15:49,410 --> 00:15:53,450 több mint 7,. 213 00:15:53,450 --> 00:15:58,650 >> Ez nem az egyetlen rendelt fa tartalmazó ezeket az értékeket, 214 00:15:58,650 --> 00:16:03,120 de hadd dolgozzon még egy pár közülük. 215 00:16:03,120 --> 00:16:05,030 Van egy csomó módon, hogy meg tudjuk csinálni. 216 00:16:05,030 --> 00:16:09,380 Megyek, hogy egy rövidített, csak hogy a dolgok egyszerű, ha - 217 00:16:09,380 --> 00:16:11,520 ahelyett rajz ki az egész doboz-és-nyilak - 218 00:16:11,520 --> 00:16:14,220 Én csak lesz, hogy felhívja a számot és add nyilak azokat összekötő. 219 00:16:14,220 --> 00:16:22,920 Megkezdéséhez, akkor csak írj az eredeti fa újra, ahol volt 7, majd a 3, 220 00:16:22,920 --> 00:16:25,590 majd 3 mutatott vissza a jogot, hogy a 6, 221 00:16:25,590 --> 00:16:30,890 és 7 volt joga gyerek volt 9. 222 00:16:30,890 --> 00:16:33,860 Rendben. Mi más módon, hogy mi lehetett írni ezt a fát? 223 00:16:33,860 --> 00:16:38,800 Ahelyett, hogy 3 legyen a bal gyermek 7, 224 00:16:38,800 --> 00:16:41,360 mi is van a 6 BE a bal gyermek 7, 225 00:16:41,360 --> 00:16:44,470 , majd 3 az a bal gyermeke a 6. 226 00:16:44,470 --> 00:16:48,520 Hogy fog kinézni ez a fa itt, ahol megvan 7, 227 00:16:48,520 --> 00:16:57,860 majd a 6, majd 3, és egy 9 a jobb oldalon. 228 00:16:57,860 --> 00:17:01,490 Azt sem kell, hogy legyen a 7 a gyökér csomópontot. 229 00:17:01,490 --> 00:17:03,860 Azt is, hogy 6-a gyökér csomópontot. 230 00:17:03,860 --> 00:17:06,470 Mi lenne, hogy néz ki? 231 00:17:06,470 --> 00:17:09,230 Ha megyünk, hogy fenntartsák ezt a megrendelt ingatlanok, 232 00:17:09,230 --> 00:17:12,970 minden balra a 6-nak, hogy kevesebb, mint az. 233 00:17:12,970 --> 00:17:16,540 Csak egy lehetőség, és ez 3. 234 00:17:16,540 --> 00:17:19,869 De aztán, mint a jobb gyermek 6, van két lehetőség. 235 00:17:19,869 --> 00:17:25,380 Először is, mi volna a 7, majd a 9, 236 00:17:25,380 --> 00:17:28,850 vagy mi lehet rajzolni - mint fogok itt csinálni - 237 00:17:28,850 --> 00:17:34,790 ahol van a 9, mint a jobb gyermeke 6, 238 00:17:34,790 --> 00:17:39,050 és azután az a 7. a bal gyermek a 9. 239 00:17:39,050 --> 00:17:44,240 >> Most, 7 és 6 nem az egyetlen lehetséges értékeit a gyökér. 240 00:17:44,240 --> 00:17:50,200 Mi is már 3 lennie a gyökér. 241 00:17:50,200 --> 00:17:52,240 Mi történik, ha 3 a gyökere? 242 00:17:52,240 --> 00:17:54,390 Itt, a dolgok egy kicsit érdekes. 243 00:17:54,390 --> 00:17:58,440 Három nem rendelkezik, amelyek értéke kisebb, mint azt, 244 00:17:58,440 --> 00:18:02,070 annak érdekében, hogy teljes bal oldala a fa csak lesz null. 245 00:18:02,070 --> 00:18:03,230 Ott nem lesz semmi. 246 00:18:03,230 --> 00:18:07,220 Jobbra, tudtuk sorolni a dolgokat növekvő sorrendben. 247 00:18:07,220 --> 00:18:15,530 Mi is van 3, majd 6, majd 7, majd 9. 248 00:18:15,530 --> 00:18:26,710 Vagy mi tehetnénk 3, majd 6, majd 9, majd 7. 249 00:18:26,710 --> 00:18:35,020 Vagy mi tehetnénk 3, majd 7, majd 6, majd 9. 250 00:18:35,020 --> 00:18:40,950 Vagy, 3, 7 - valójában nem, nem tehetünk a 7 többé. 251 00:18:40,950 --> 00:18:43,330 Ez a mi egy dolog van. 252 00:18:43,330 --> 00:18:54,710 Tehetünk 9, majd a 9 tehetünk, 6, majd 7. 253 00:18:54,710 --> 00:19:06,980 Vagy, amit tehetünk, 3, majd 9, majd 7, majd 6. 254 00:19:06,980 --> 00:19:12,490 >> Egy dolog, hogy felhívja a figyelmet, hogy itt 255 00:19:12,490 --> 00:19:14,510 hogy ezek a fák egy kicsit fura kinézetű. 256 00:19:14,510 --> 00:19:17,840 Különösen, ha megnézzük a 4 fákat a jobb oldalon - 257 00:19:17,840 --> 00:19:20,930 Majd én karikázza őket, itt - 258 00:19:20,930 --> 00:19:28,410 ezek a fák meg majdnem pontosan olyan, mint a láncolt lista. 259 00:19:28,410 --> 00:19:32,670 Minden csomópont csak egy gyerek, 260 00:19:32,670 --> 00:19:38,950 és így nem rendelkezik az ezen fa-szerű szerkezet azt látjuk, például, 261 00:19:38,950 --> 00:19:44,720  ebben az egy magányos fa alatt itt a bal alsó. 262 00:19:44,720 --> 00:19:52,490 Ezek a fák valóban nevezzük degenerált bináris fák, 263 00:19:52,490 --> 00:19:54,170 és beszélünk ezekről látna a jövőben - 264 00:19:54,170 --> 00:19:56,730 különösen akkor, ha megy, hogy más számítástechnika tanfolyamok. 265 00:19:56,730 --> 00:19:59,670 Ezek a fák degenerált. 266 00:19:59,670 --> 00:20:03,780 Ők nem nagyon hasznos, mert valóban, ez a szerkezet alkalmas arra, 267 00:20:03,780 --> 00:20:08,060  A lookup-szer hasonló egy csatolt lista. 268 00:20:08,060 --> 00:20:13,050 Azt nem értem, hogy kihasználják az extra memória - ezt az extra mutató - 269 00:20:13,050 --> 00:20:18,840 mert a mi szerkezet, hogy rossz az ilyen módon. 270 00:20:18,840 --> 00:20:24,700 Ahelyett, hogy megy és rajzolja ki a bináris fák, amelyek 9 a gyökér, 271 00:20:24,700 --> 00:20:27,220 , mely a végleges helyzet, hogy mi volna, 272 00:20:27,220 --> 00:20:32,380 vagyunk ehelyett ezen a ponton fog beszélni egy kicsit erről a másik kifejezés 273 00:20:32,380 --> 00:20:36,150 hogy használjuk, ha beszélünk a fák, melynek neve a magasságot. 274 00:20:36,150 --> 00:20:45,460 >> A magassága a fa a távolság a gyökér a leginkább távoli csomópont, 275 00:20:45,460 --> 00:20:48,370 vagy inkább az ugrások számát, hogy meg kellett volna tenni annak érdekében, hogy 276 00:20:48,370 --> 00:20:53,750 indul a gyökér, majd végül a leginkább távoli csomópont a fában. 277 00:20:53,750 --> 00:20:57,330 Ha megnézzük néhány ilyen fát, hogy már készített itt, 278 00:20:57,330 --> 00:21:07,870 láthatjuk, hogy ha ezt a fát a bal felső sarokban, és kezdjük a 3, 279 00:21:07,870 --> 00:21:14,510 akkor meg kell, hogy 1 hop, hogy a 6, a második hop, hogy a 7, 280 00:21:14,510 --> 00:21:20,560 és egy harmadik hop eljutni a 9. 281 00:21:20,560 --> 00:21:26,120 Szóval, a magassága a fa 3 lehet. 282 00:21:26,120 --> 00:21:30,640 Meg tudjuk csinálni ugyanezt a gyakorlatot a többi fák felvázolt ezzel a zöld, 283 00:21:30,640 --> 00:21:40,100 Úgy látjuk, hogy a magassága Mindezen fák is valóban 3. 284 00:21:40,100 --> 00:21:45,230 Ez része a mi teszi őket degenerált - 285 00:21:45,230 --> 00:21:53,750 hogy a magasságuk kisebb, mint csak egy a csomópontok száma az egész fa. 286 00:21:53,750 --> 00:21:58,400 Ha megnézzük a másik fát, ami bekerített piros, a másik viszont, 287 00:21:58,400 --> 00:22:03,920 azt látjuk, hogy a legtöbb, távoli levélcsomópontjaiban vannak a 6 és a 9 - 288 00:22:03,920 --> 00:22:06,940 a levelek, hogy azokat a csomópontokat, hogy nem gyerekek. 289 00:22:06,940 --> 00:22:11,760 Tehát annak érdekében, hogy a gyökér csomópont, hogy vagy a 6 vagy a 9, 290 00:22:11,760 --> 00:22:17,840 van, hogy egy ugrás, hogy a 7, majd egy második, hop, hogy a 9, 291 00:22:17,840 --> 00:22:21,240 és a fentiekhez hasonlóan csak a második kitérő a 7, hogy a 6. 292 00:22:21,240 --> 00:22:29,080 Szóval, a magassága ennek a fának ide csak 2. 293 00:22:29,080 --> 00:22:35,330 Mehetsz vissza, és nem, hogy az összes többi fák, hogy korábban tárgyalt 294 00:22:35,330 --> 00:22:37,380 kezdve a 7 és a 6, 295 00:22:37,480 --> 00:22:42,500 , és rájössz, hogy a magassága mindezen fák is 2. 296 00:22:42,500 --> 00:22:46,320 >> Az ok, mi már beszélünk sorrendben bináris fák 297 00:22:46,320 --> 00:22:50,250 és miért ők hűvös van, mert akkor keresni őket 298 00:22:50,250 --> 00:22:53,810 nagyon hasonló módon keres egy rendezett tömbben. 299 00:22:53,810 --> 00:22:58,720 Ez az, ahol beszélni kezd, hogy a jobb keresési idő 300 00:22:58,720 --> 00:23:02,730 az egyszerű láncolt lista. 301 00:23:02,730 --> 00:23:05,010 A láncolt lista - ha meg akarja találni egy adott elem - 302 00:23:05,010 --> 00:23:07,470 te vagy a legjobb csinálni valamilyen lineáris keresés 303 00:23:07,470 --> 00:23:10,920 hol kezdődik az elején egy listát, és hop egy-by-one - 304 00:23:10,920 --> 00:23:12,620 egy csomópont egy csomópont - 305 00:23:12,620 --> 00:23:16,060 keresztül, a teljes listát, amíg meg nem találja, amit keresett. 306 00:23:16,060 --> 00:23:19,440 Mivel, ha van egy bináris fa, ami alatt az szép formátumban, 307 00:23:19,440 --> 00:23:23,300 akkor tényleg kap inkább egy bináris keresés folyik 308 00:23:23,300 --> 00:23:25,160 ahol oszd meg és uralkodj 309 00:23:25,160 --> 00:23:29,490 és keressük a megfelelő felét a fa minden egyes lépést. 310 00:23:29,490 --> 00:23:32,840 Nézzük meg, hogy hogyan működik. 311 00:23:32,840 --> 00:23:38,850 >> Ha van - megint megy vissza az eredeti fa - 312 00:23:38,850 --> 00:23:46,710 kezdjük a 7, már 3, a bal oldalon, 9 a jobb oldalon, 313 00:23:46,710 --> 00:23:51,740 és alatt a 3 van a 6. 314 00:23:51,740 --> 00:24:01,880 Ha azt akarjuk, hogy keressük meg a 6-os szám a fán, mi lenne kezdeni a gyökér. 315 00:24:01,880 --> 00:24:08,910 Mi lenne összehasonlítani az értéket keresünk, mondjuk 6, 316 00:24:08,910 --> 00:24:12,320 A tárolt érték a csomópont, hogy mi jelenleg vizsgálja, 7, 317 00:24:12,320 --> 00:24:21,200 találják, hogy a 6 valóban kisebb, mint 7, ezért mi lenne mozgatni balra. 318 00:24:21,200 --> 00:24:25,530 Ha az érték a 6 volt nagyobb, mint 7, akkor volna inkább jobbra mozdul el. 319 00:24:25,530 --> 00:24:29,770 Mivel tudjuk, hogy - mivel a szerkezetét sorrendben bináris fa - 320 00:24:29,770 --> 00:24:33,910 minden érték kevesebb, mint 7 fognak tárolni a bal 7, 321 00:24:33,910 --> 00:24:40,520 nincs szükség még zavarta nézegette a jobb oldalon a fa. 322 00:24:40,520 --> 00:24:43,780 Amint mozgatni a bal és mi vagyunk most a csomópont, amely 3, 323 00:24:43,780 --> 00:24:48,110 amit tehetünk, hogy ugyanezt az összehasonlítást megint, ahol összehasonlítjuk a 3 és a 6. 324 00:24:48,110 --> 00:24:52,430 És azt látjuk, hogy míg 6 - értéke keresünk - nagyobb, mint 3, 325 00:24:52,430 --> 00:24:58,580 mehetünk a jobb oldalán a csomópont, amely 3. 326 00:24:58,580 --> 00:25:02,670 Nincs bal oldalán van, így tudtuk figyelmen kívül hagyta ezt. 327 00:25:02,670 --> 00:25:06,510 De csak azért, mert tudjuk, hogy keresünk a fa is, 328 00:25:06,510 --> 00:25:08,660 és láthatjuk, hogy a fa nem gyerekek. 329 00:25:08,660 --> 00:25:13,640 >> Ez is elég könnyű, hogy felnézzen 6-ezt a fát, ha csinálunk magunk, mint az emberek, 330 00:25:13,640 --> 00:25:16,890 de hadd kövesse ezt a folyamatot mechanikusan, mint egy számítógép tenne 331 00:25:16,890 --> 00:25:18,620 hogy valóban megértsék az algoritmus. 332 00:25:18,620 --> 00:25:26,200 Ezen a ponton vagyunk most néztem egy csomópont, amely 6, 333 00:25:26,200 --> 00:25:29,180 és keresünk az érték 6, 334 00:25:29,180 --> 00:25:31,740 így van, sőt, most már megtalálta a megfelelő csomópontot. 335 00:25:31,740 --> 00:25:35,070 Megtaláltuk az érték 6 a mi fa, és tudjuk megállítani a keresést. 336 00:25:35,070 --> 00:25:37,330 Ennél a pontnál, attól függően, hogy mi folyik itt, 337 00:25:37,330 --> 00:25:41,870 azt mondhatjuk, igen, megtaláltuk az érték 6, létezik a mi fa. 338 00:25:41,870 --> 00:25:47,640 Vagy, ha azt tervezed, hogy helyezzen be egy csomópont, vagy csinálsz valamit, amit tehetünk, hogy ezen a ponton. 339 00:25:47,640 --> 00:25:53,010 >> Csináljuk egy pár kikeresések csak hogy lássa, hogyan is működik ez. 340 00:25:53,010 --> 00:25:59,390 Nézzük meg, mi történik, ha volt, hogy megpróbálja, és keresse fel a 10 értéket. 341 00:25:59,390 --> 00:26:02,970 Ha volt, hogy néz ki a 10 értéket, mi lenne kezdeni a gyökér. 342 00:26:02,970 --> 00:26:07,070 Mi lenne látni, hogy 10 nagyobb, mint 7, ezért mi lenne mozgatni jobbra. 343 00:26:07,070 --> 00:26:13,640 Mi lenne eljutni a 9 és hasonlítsa össze 9 a 10 és látom, hogy a 9. valóban kisebb, mint 10. 344 00:26:13,640 --> 00:26:16,210 Tehát újra, mi lenne próbálja mozgatni a jobb. 345 00:26:16,210 --> 00:26:20,350 De ezen a ponton, akkor azt észre, hogy vagyunk egy null csomópont. 346 00:26:20,350 --> 00:26:23,080 Nincs ott semmi. Nincs semmi, ahol a 10 kell. 347 00:26:23,080 --> 00:26:29,360 Ez az, ahol lehet jelenteni hiba -, hogy valóban nem 10 a fán. 348 00:26:29,360 --> 00:26:35,420 És végül, menjünk át az esetben, ha próbálunk keresni 1 a fán. 349 00:26:35,420 --> 00:26:38,790 Ez hasonló ahhoz, mi történik, ha megnézzük akár 10, kivéve, ahelyett, hogy a jobb oldalon, 350 00:26:38,790 --> 00:26:41,260 fogunk menni balra. 351 00:26:41,260 --> 00:26:46,170 Kezdjük a 7 és látom, hogy az 1-kevesebb mint 7, így haladunk balra. 352 00:26:46,170 --> 00:26:51,750 Kapunk a 3 és látom, hogy az 1-3-nál kisebb, így megint megpróbálja mozgatni a bal oldalon. 353 00:26:51,750 --> 00:26:59,080 Ezen a ponton van egy null csomópontot, így ismét tudunk jelenteni hiba. 354 00:26:59,080 --> 00:27:10,260 >> Ha szeretne többet megtudni a bináris fák, 355 00:27:10,260 --> 00:27:14,420 van egy csomó jó kis problémákat, hogy meg tudod csinálni velük. 356 00:27:14,420 --> 00:27:19,450 Azt javaslom, gyakorló a rajz ki ezeket a diagramok egy-az-egy 357 00:27:19,450 --> 00:27:21,910 és az azt követő végig a különböző lépések, 358 00:27:21,910 --> 00:27:25,060 mert ez fog jönni szuper-praktikus 359 00:27:25,060 --> 00:27:27,480 Nem csak akkor, ha csinálsz a Huffman kódolás probléma set 360 00:27:27,480 --> 00:27:29,390 hanem a jövőben tanfolyamok - 361 00:27:29,390 --> 00:27:32,220 csak a tanulás, hogyan kell felhívni ezeket adatstruktúrák és gondolja át a problémákat 362 00:27:32,220 --> 00:27:38,000 A toll és papír, vagy ebben az esetben, iPad és a ceruzát. 363 00:27:38,000 --> 00:27:41,000 >> Ezen a ponton azonban fogunk lépni, hogy néhány kódolási gyakorlat 364 00:27:41,000 --> 00:27:44,870 és valóban játszani ezekkel a bináris fák és lásd. 365 00:27:44,870 --> 00:27:52,150 Megyek váltson vissza a számítógéphez. 366 00:27:52,150 --> 00:27:58,480 Ennek része a szakasz használata helyett CS50 Run vagy CS50 Spaces, 367 00:27:58,480 --> 00:28:01,500 Fogom használni a készüléket. 368 00:28:01,500 --> 00:28:04,950 >> Miután együtt Problem Set specifikáció, 369 00:28:04,950 --> 00:28:07,740 Látom, hogy kéne, hogy nyissa ki a készüléket, 370 00:28:07,740 --> 00:28:11,020 megy a Dropbox mappában hozzon létre egy mappát nevű 7. szakasz, 371 00:28:11,020 --> 00:28:15,730 majd hozzon létre egy nevű fájlt binary_tree.c. 372 00:28:15,730 --> 00:28:22,050 Itt vagyunk. Megvan a készülék már nyitva van. 373 00:28:22,050 --> 00:28:25,910 Megyek húzza fel a terminál. 374 00:28:25,910 --> 00:28:38,250 Fogok menni a Dropbox mappába, készíts egy könyvtárat nevű section7, 375 00:28:38,250 --> 00:28:42,230 és nézd meg, hogy ez teljesen üres. 376 00:28:42,230 --> 00:28:48,860 Most fogom nyitni binary_tree.c. 377 00:28:48,860 --> 00:28:51,750 Rendben. Itt vagyunk - üres fájlt. 378 00:28:51,750 --> 00:28:54,330 >> Menjünk vissza a specifikáció. 379 00:28:54,330 --> 00:28:59,850 A specifikáció kéri, hogy hozzon létre egy új típusú definíció 380 00:28:59,850 --> 00:29:03,080 Egy bináris fa csomópontot tartalmazó int értékek - 381 00:29:03,080 --> 00:29:07,110 mint az értékeket, hogy mi hívta ki a diagramm előtt. 382 00:29:07,110 --> 00:29:11,740 Fogjuk használni ezt a boilerplate typedef hogy tettünk itt 383 00:29:11,740 --> 00:29:14,420 hogy el kell ismernie honnan Problem Set 5 - 384 00:29:14,420 --> 00:29:19,190 ha nem a hash tábla módja hódító a helyesírás program. 385 00:29:19,190 --> 00:29:22,540 Azt is elismerik, hogy a múlt heti részben 386 00:29:22,540 --> 00:29:23,890 ahol beszélgettünk kapcsolódó listákat. 387 00:29:23,890 --> 00:29:27,870 Van ez a typedef struct csomópont, 388 00:29:27,870 --> 00:29:34,430 és az általunk megadott e struct csomópont ez a név a struct csomópont előzetes 389 00:29:34,430 --> 00:29:39,350 azért, hogy aztán hivatkozni rá, mivel mi szeretnénk, hogy struct csomópontra mutató 390 00:29:39,350 --> 00:29:45,740 mint a mi struct, de még akkor körülvéve ezt - 391 00:29:45,740 --> 00:29:47,700 vagy inkább zárva ez - egy typedef 392 00:29:47,700 --> 00:29:54,600 úgy, hogy később a kódot, akkor olvassa el ezt a struktúra, mint csak egy csomópont helyett struct csomópont. 393 00:29:54,600 --> 00:30:03,120 >> Ez lesz nagyon hasonló az egyszeres láncolt lista definíció, hogy azt a múlt héten. 394 00:30:03,120 --> 00:30:20,070 Ehhez nézzük csak elkezd írásban ki boilerplate. 395 00:30:20,070 --> 00:30:23,840 Tudjuk, hogy van, hogy van egy egész értéket, 396 00:30:23,840 --> 00:30:32,170 úgyhogy életbe int értéket, majd ahelyett, hogy csak egy mutató a következő elem - 397 00:30:32,170 --> 00:30:33,970 ahogy azt tette egyszeresen kötött listák - 398 00:30:33,970 --> 00:30:38,110 megyünk, hogy a bal és a jobb gyermek mutatók. 399 00:30:38,110 --> 00:30:42,880 Ez elég egyszerű is - struct node * balra gyermek; 400 00:30:42,880 --> 00:30:51,190 és struct node * jobb gyermek;. Cool. 401 00:30:51,190 --> 00:30:54,740 Úgy néz ki, mint egy nagyon jó kezdet. 402 00:30:54,740 --> 00:30:58,530 Menjünk vissza a specifikáció. 403 00:30:58,530 --> 00:31:05,030 >> Most arra van szükség, hogy állapítsa meg a globális node * változót a gyökér egy fa. 404 00:31:05,030 --> 00:31:10,590 Fogjuk, hogy ez a globális, mint tettünk 1. mutató a mi láncolt lista is globális. 405 00:31:10,590 --> 00:31:12,690 Ez volt annak érdekében, hogy a funkciók írunk 406 00:31:12,690 --> 00:31:16,180 nem kell tartanunk tompított körül ez gyökér - 407 00:31:16,180 --> 00:31:19,620 azonban látni fogjuk, hogy ha nem akarsz írni ezeket a funkciókat rekurzív 408 00:31:19,620 --> 00:31:22,830 lehet, hogy jobb, ha nem is adja át a körbe, mint globális az első helyen 409 00:31:22,830 --> 00:31:28,090 és helyette inicializálni azt helyileg a fő funkciója. 410 00:31:28,090 --> 00:31:31,960 De megcsináljuk globálisan kezdeni. 411 00:31:31,960 --> 00:31:39,920 Ismét adok pár terek, és megyek nyilvánítja egy csomópontot * gyökér. 412 00:31:39,920 --> 00:31:46,770 Csak, hogy győződjön meg arról, hogy nem hagyja a inicializált, megyek beállítani egyenlő null. 413 00:31:46,770 --> 00:31:52,210 Most, a fő funkciója - amit írok nagyon gyorsan itt - 414 00:31:52,210 --> 00:32:00,450 int main (int argc, const char * argv []) - 415 00:32:00,450 --> 00:32:10,640 és én fogom kezdeni nyilvánító én argv tömb const csak azért, hogy tudom 416 00:32:10,640 --> 00:32:14,550 hogy ezek az érvek szólnak érvek, hogy én valószínűleg nem szeretné módosítani. 417 00:32:14,550 --> 00:32:18,390 Ha azt szeretnénk, hogy módosítsa azokat kéne valószínűleg másolás őket. 418 00:32:18,390 --> 00:32:21,740 Majd meglátod, ez sokat kódot. 419 00:32:21,740 --> 00:32:25,440 Ez rendben mindkét irányban. Ez rendben van, hogy hagyja azt - kihagyja a const, ha szeretné. 420 00:32:25,440 --> 00:32:28,630 Én általában tedd csak azért, hogy emlékeztessem magam 421 00:32:28,630 --> 00:32:33,650  hogy én valószínűleg nem szeretné módosítani ezeket az érveket. 422 00:32:33,650 --> 00:32:39,240 >> Mint mindig, fogom fel ezt a return 0 sort a végén fő. 423 00:32:39,240 --> 00:32:45,730 Itt fogom inicializálja a gyökér csomópontot. 424 00:32:45,730 --> 00:32:48,900 A jelenlegi helyzet most, van egy mutató, ami null, 425 00:32:48,900 --> 00:32:52,970 így ez mutatott semmit. 426 00:32:52,970 --> 00:32:57,480 Annak érdekében, hogy valóban kezdjék építeni a csomópont, 427 00:32:57,480 --> 00:32:59,250 Először meg kell memóriát kiosztani rá. 428 00:32:59,250 --> 00:33:05,910 Fogom csinálni, hogy azáltal, hogy memóriát a heap malloc használatával. 429 00:33:05,910 --> 00:33:10,660 Megyek be gyökér azonos eredménye malloc, 430 00:33:10,660 --> 00:33:19,550 és én fogom használni a sizeof operátor kiszámításához méretű csomópont. 431 00:33:19,550 --> 00:33:24,990 Ennek az az oka, hogy tudom használni sizeof node szemben, mondjuk, 432 00:33:24,990 --> 00:33:37,020 csinál valamit, mint ez - malloc (4 + 4 +4), vagy malloc 12 - 433 00:33:37,020 --> 00:33:40,820 azért van, mert azt akarom, hogy kódot is összeegyeztethető legyen. 434 00:33:40,820 --> 00:33:44,540 Azt akarom, hogy képes legyen ezt. C fájlt, fordítsd le a készülékre, 435 00:33:44,540 --> 00:33:48,820 majd fordítsd le az én 64-bites Mac - 436 00:33:48,820 --> 00:33:52,040 vagy egy teljesen más architektúra - 437 00:33:52,040 --> 00:33:54,640 és azt akarom, hogy ez mind a munka ugyanaz. 438 00:33:54,640 --> 00:33:59,510 >> Ha csinálok feltételezéseket mérete változó - 439 00:33:59,510 --> 00:34:02,070 méretének int vagy mérete alapján a mutató - 440 00:34:02,070 --> 00:34:06,070 akkor én is, hogy feltételezéseket a fajta architektúrák 441 00:34:06,070 --> 00:34:10,440 , amely a kód sikeresen fordítani, ha fut. 442 00:34:10,440 --> 00:34:15,030 Mindig használjon sizeof szemben kézzel összeadásával struct mezőket. 443 00:34:15,030 --> 00:34:20,500 A másik ok az, hogy nem is lehet padding, hogy a fordító hozza a struct. 444 00:34:20,500 --> 00:34:26,570 Még csak összeadásával egyes mezők nem olyan dolog, amit általában szeretne tenni, 445 00:34:26,570 --> 00:34:30,340 igen, törölje azt a vonalat. 446 00:34:30,340 --> 00:34:33,090 Most, hogy igazán inicializálni ezt a gyökér csomópont, 447 00:34:33,090 --> 00:34:36,489 Megyek is, hogy csatlakoztassa az értékeket minden egyes különböző területeken. 448 00:34:36,489 --> 00:34:41,400 Például érték tudom akarok inicializálni 7, 449 00:34:41,400 --> 00:34:46,920 és most megyek be a bal gyermeket, hogy null 450 00:34:46,920 --> 00:34:55,820 és a megfelelő gyermek is null. Nagyszerű! 451 00:34:55,820 --> 00:35:02,670 Azt csináltam, hogy része a spec. 452 00:35:02,670 --> 00:35:07,390 >> A specifikáció le alján 3 oldalon megkérdezi, hogy hozzon létre három csomópont - 453 00:35:07,390 --> 00:35:10,600 1, 3, 1, amely 6, és egy 9 - 454 00:35:10,600 --> 00:35:14,210 majd bekötni őket, így úgy néz ki, pontosan olyan, mint a fa diagram 455 00:35:14,210 --> 00:35:17,120 hogy beszéltünk korábban. 456 00:35:17,120 --> 00:35:20,450 Csináljuk, hogy elég gyorsan ide. 457 00:35:20,450 --> 00:35:26,270 Látni fogod, nagyon gyorsan, hogy én fogok kezdeni írni egy csomó kettős kódot. 458 00:35:26,270 --> 00:35:32,100 Megyek, hogy hozzon létre egy csomópont * és fogom hívni három. 459 00:35:32,100 --> 00:35:36,000 Fogom állítani egyenlő malloc (sizeof (node)). 460 00:35:36,000 --> 00:35:41,070 Megyek be három-> value = 3. 461 00:35:41,070 --> 00:35:54,780 Három -> left_child = NULL; 3 -> jobb _child = NULL; is. 462 00:35:54,780 --> 00:36:01,150 Úgy néz ki, nagyon hasonlít inicializálása a gyökér, és pontosan ez az, amit 463 00:36:01,150 --> 00:36:05,760 Megyek, hogy meg kell csinálni, ha elkezdek inicializálása 6 és 9 is. 464 00:36:05,760 --> 00:36:20,720 Én megteszem, hogy nagyon gyorsan itt - valójában fogok csinálni egy kis másolás és beillesztés, 465 00:36:20,720 --> 00:36:46,140 és győződjön meg arról, hogy az I - rendben van. 466 00:36:46,470 --> 00:37:09,900  Nos, megvan másolt és tudok menni előre, és állítsa legfeljebb 6. 467 00:37:09,900 --> 00:37:14,670 Láthatjuk, hogy ez eltart egy ideig, és nem szuper-hatékony. 468 00:37:14,670 --> 00:37:22,610 A csak egy kicsit, akkor írjon egy függvényt, amely ezt nekünk. 469 00:37:22,610 --> 00:37:32,890 Azt akarom, hogy váltsa fel e egy 9, cserélje ki, hogy a 6. 470 00:37:32,890 --> 00:37:37,360 >> Most már megvan minden kedves csomópont létrehozása és inicializálni. 471 00:37:37,360 --> 00:37:41,200 Megvan a gyökér egyezni a 7, vagy amely az érték 7, 472 00:37:41,200 --> 00:37:46,510 mi csomópont tartalma 3, a mi csomópont, amely 6, és a mi csomópont, amely 9. 473 00:37:46,510 --> 00:37:50,390 Ezen a ponton minden, amit meg kell tennie, hogy vezetékes mindent. 474 00:37:50,390 --> 00:37:53,020 Azért inicializálja az összes mutató null is csak azért, hogy én arról, hogy 475 00:37:53,020 --> 00:37:56,260 Nekem nincs semmilyen inicializálatlan pointerek ott véletlenül. 476 00:37:56,260 --> 00:38:02,290 És azt is, mivel ezen a ponton, azt csak a ténylegesen csatlakoztassa a csomópontok egymáshoz - 477 00:38:02,290 --> 00:38:04,750 az is, hogy ők valóban kapcsolódik - Nem tudom, hogy menjen át, és 478 00:38:04,750 --> 00:38:08,240 arról, hogy az összes null ott vannak a megfelelő helyeken. 479 00:38:08,240 --> 00:38:15,630 >> Kezdve a gyökér, tudom, hogy a gyökér bal gyermek 3. 480 00:38:15,630 --> 00:38:21,250 Tudom, hogy a root jogot gyermek 9. 481 00:38:21,250 --> 00:38:24,880 Ezt követően, az egyetlen gyerek, hogy hagytam aggódni 482 00:38:24,880 --> 00:38:39,080 a 3-as helyes gyermeke, amely 6. 483 00:38:39,080 --> 00:38:44,670 Ezen a ponton, minden jól néz ki. 484 00:38:44,670 --> 00:38:54,210 Majd törölje néhány ilyen sorokat. 485 00:38:54,210 --> 00:38:59,540 Most minden jól néz ki. 486 00:38:59,540 --> 00:39:04,240 Menjünk vissza a specifikáció, és mi van a következő teendő. 487 00:39:04,240 --> 00:39:07,610 >> Ezen a ponton meg kell írni egy függvényt úgynevezett "tartalmaz" 488 00:39:07,610 --> 00:39:14,150 egy prototípusa "bool tartalmaz (int érték)." 489 00:39:14,150 --> 00:39:17,060 És ez tartalmaz funkciót fog visszatérni true 490 00:39:17,060 --> 00:39:21,200  ha a fa által mutatott globális gyökér változót 491 00:39:21,200 --> 00:39:26,950  értéket tartalmazó átment a funkciót és hamis egyébként. 492 00:39:26,950 --> 00:39:29,000 Menjünk előre, és csinálni. 493 00:39:29,000 --> 00:39:35,380 Ez lesz pontosan olyan, mint a kereső, hogy mi volt kézzel az iPad csak egy kicsit ezelőtt. 494 00:39:35,380 --> 00:39:40,130 Nézzük zoom vissza egy kicsit, és felfelé. 495 00:39:40,130 --> 00:39:43,130 Megyünk, hogy ezt a funkciót jobbra fent a fő funkciója 496 00:39:43,130 --> 00:39:48,990 azért, hogy ne kelljen tennie bármilyen prototípus. 497 00:39:48,990 --> 00:39:55,960 Szóval, bool tartalmaz (int érték). 498 00:39:55,960 --> 00:40:00,330 Ott vagyunk. Itt a mi boilerplate nyilatkozatot. 499 00:40:00,330 --> 00:40:02,900 Csak, hogy győződjön meg arról, hogy ez fog készíteni, 500 00:40:02,900 --> 00:40:06,820 Én megyek előre, és csak állítsa egyenlő return false. 501 00:40:06,820 --> 00:40:09,980 Most ez a funkció csak nem fog tenni semmit, és mindig számolnak be, hogy 502 00:40:09,980 --> 00:40:14,010 az értéket, amelyet keresünk, nem a fán. 503 00:40:14,010 --> 00:40:16,280 >> Ezen a ponton, akkor valószínűleg egy jó ötlet - 504 00:40:16,280 --> 00:40:19,600 hiszen írtam egy csomó kódot, és még nem is próbáltam tesztelés még - 505 00:40:19,600 --> 00:40:22,590 , hogy győződjön meg arról, hogy minden össze. 506 00:40:22,590 --> 00:40:27,460 Van egy pár dolog, amit meg kell tennie, hogy győződjön meg arról, hogy ez valóban fordítani. 507 00:40:27,460 --> 00:40:33,530 Először is, hátha mi már bármilyen funkciót olyan könyvtárakat, amelyek még nem tartalmazza. 508 00:40:33,530 --> 00:40:37,940 A funkciók általunk használt eddig malloc, 509 00:40:37,940 --> 00:40:43,310 és akkor már is használja ezt a típust - ez a szabványos típusú úgynevezett "bool' - 510 00:40:43,310 --> 00:40:45,750 amely szerepel a szabványos bool header file. 511 00:40:45,750 --> 00:40:53,250 Azt mindenképpen szeretnénk tartalmazzák a standard bool.h a bool típusú, 512 00:40:53,250 --> 00:40:59,230 és mi is szeretnénk, hogy # include szabvány lib.h a szabványos könyvtárak 513 00:40:59,230 --> 00:41:03,530 amelyek magukban foglalják malloc és ingyenes, és minden adott. 514 00:41:03,530 --> 00:41:08,660 Szóval, kicsinyítés, fogunk lépni. 515 00:41:08,660 --> 00:41:14,190 Próbáljuk meg és győződjön meg arról, hogy ez valóban tette fordítás. 516 00:41:14,190 --> 00:41:18,150 Látjuk, hogy ez így van, így vagyunk a helyes úton. 517 00:41:18,150 --> 00:41:22,990 >> Nyissuk ki binary_tree.c újra. 518 00:41:22,990 --> 00:41:34,530 Azt állítja össze. Menjünk le, és győződjön meg arról, hogy mi be néhány hívást a mi Tartalom funkció - 519 00:41:34,530 --> 00:41:40,130 csak azért, hogy győződjön meg arról, hogy ez mind szép és jó. 520 00:41:40,130 --> 00:41:43,170 Például, amikor csináltunk néhány lekérdezések a mi korábbi fa, 521 00:41:43,170 --> 00:41:48,500 megpróbáltuk felnéz az értékek 6, 10, és 1, és tudtuk, hogy 6 volt a fa, 522 00:41:48,500 --> 00:41:52,220 10 nem volt a fa, és 1 nem volt a fa sem. 523 00:41:52,220 --> 00:41:57,230 Nézzünk a mintát kéri, mert így, hogy kitaláljuk-e vagy sem 524 00:41:57,230 --> 00:41:59,880 mi Tartalom funkció működik. 525 00:41:59,880 --> 00:42:05,210 Annak érdekében, hogy ezt, hogy fogom használni a printf függvény, 526 00:42:05,210 --> 00:42:10,280 és megyünk, hogy nyomtassa ki az eredményt a hívás tartalmaz. 527 00:42:10,280 --> 00:42:13,280 Megyek, hogy hozzanak egy string "tartalmaz (% d) = mert 528 00:42:13,280 --> 00:42:20,470  fogunk csatlakoztassa az értéket fogunk keresni, 529 00:42:20,470 --> 00:42:27,130 és =% s \ n ", és használni, hogy a mi format string. 530 00:42:27,130 --> 00:42:30,720 Mi csak fog látni - szó szerint nyomtassa ki a képernyőn - 531 00:42:30,720 --> 00:42:32,060 ami úgy néz ki, mint egy függvényhívás. 532 00:42:32,060 --> 00:42:33,580 Ez valójában nem a függvényhívást. 533 00:42:33,580 --> 00:42:36,760  Ez csak egy string tervezték, hogy néz ki, mint egy függvényhívás. 534 00:42:36,760 --> 00:42:41,140 >> Nos, megyünk, hogy csatlakoztassa az értékeket. 535 00:42:41,140 --> 00:42:43,580 Fogunk próbálni tartalmaz 6-án, 536 00:42:43,580 --> 00:42:48,340 és akkor mit fogunk csinálni itt használni, hogy háromkomponensű üzemeltető. 537 00:42:48,340 --> 00:42:56,340 Lássuk - tartalmazza a 6 - igen, most már tartalmazott 6 és ha tartalmaz 6 igaz, 538 00:42:56,340 --> 00:43:01,850 a húr, hogy fogunk küldeni a% s formátum karakter 539 00:43:01,850 --> 00:43:04,850 lesz a húr "igazi". 540 00:43:04,850 --> 00:43:07,690 Nézzük lépjünk át egy kicsit. 541 00:43:07,690 --> 00:43:16,210 Egyébként, szeretnénk küldeni a string "hamis", ha tartalmaz 6 visszatér hamis. 542 00:43:16,210 --> 00:43:19,730 Ez egy kicsit ostoba kinézetű, de rájöttem én is, valamint bemutatják 543 00:43:19,730 --> 00:43:23,780 mi a háromkomponensű üzemeltető néz ki, mivel nem láttuk, hogy egy darabig. 544 00:43:23,780 --> 00:43:27,670 Ez lesz egy szép, praktikus módja annak, hogy kitaláljuk, ha a Tartalom funkció működik. 545 00:43:27,670 --> 00:43:30,040 Megyek lépjen vissza a baloldalt, 546 00:43:30,040 --> 00:43:39,900 és én fogom másolni és beilleszteni ezt a sort egy párszor. 547 00:43:39,900 --> 00:43:44,910 Ez megváltoztatott néhány ezen értékek körül, 548 00:43:44,910 --> 00:43:59,380 így ez lesz 1, és ez lesz a 10-ig. 549 00:43:59,380 --> 00:44:02,480 >> Ezen a ponton van egy szép Tartalom funkciót. 550 00:44:02,480 --> 00:44:06,080 Van néhány vizsgálatot, és majd meglátjuk, ha ez az egész működik. 551 00:44:06,080 --> 00:44:08,120 Ezen a ponton már írt néhány kódot. 552 00:44:08,120 --> 00:44:13,160 Ideje, hogy kilép, és győződjön meg arról, hogy minden még össze. 553 00:44:13,160 --> 00:44:20,360 Lépjen ki, és most próbáljuk, hogy bináris fa újra. 554 00:44:20,360 --> 00:44:22,260 Nos, úgy néz ki, megvan egy hiba, 555 00:44:22,260 --> 00:44:26,930 és megvan ez kifejezetten kimondja a printf könyvtári függvény. 556 00:44:26,930 --> 00:44:39,350 Úgy néz ki, meg kell menni, és # include standardio.h. 557 00:44:39,350 --> 00:44:45,350 És arra, hogy mindent meg kell fordítani. Mindannyian jó. 558 00:44:45,350 --> 00:44:50,420 Most próbáljuk futó bináris fa, és meglátjuk, mi történik. 559 00:44:50,420 --> 00:44:53,520 Itt vagyunk,. / Binary_tree, 560 00:44:53,520 --> 00:44:55,190 és látjuk, hogy amint vártuk - 561 00:44:55,190 --> 00:44:56,910 mert nem hajtották végre tartalmaz még, 562 00:44:56,910 --> 00:44:59,800 vagy inkább, már most bevezetett return false - 563 00:44:59,800 --> 00:45:03,300 azt látjuk, hogy ez csak visszatér hamis mindet, 564 00:45:03,300 --> 00:45:06,180 annak érdekében, hogy ez minden dolgozó a legtöbb elég jól. 565 00:45:06,180 --> 00:45:11,860 >> Menjünk vissza, és ténylegesen végrehajtja tartalmaz, ezen a ponton. 566 00:45:11,860 --> 00:45:17,490 Megyek lapozzunk lefelé, nagyítás, és - 567 00:45:17,490 --> 00:45:22,330 ne feledd, az algoritmus, hogy mi használt volt, hogy indult a gyökér csomópont 568 00:45:22,330 --> 00:45:28,010 majd minden csomópont találkozunk, mi az összehasonlítás, 569 00:45:28,010 --> 00:45:32,380 és ennek alapján összehasonlítva mi vagy mozgassa balra gyermek vagy jobbra gyermek. 570 00:45:32,380 --> 00:45:39,670 Ez fog nézni nagyon hasonló a bináris keresés kódot írtuk korábban a távon. 571 00:45:39,670 --> 00:45:47,810 Amikor elindul, tudjuk, hogy szeretnénk megtartani a jelenlegi csomópont 572 00:45:47,810 --> 00:45:54,050 hogy keresünk, és a jelenlegi csomópont lesz inicializálni a gyökér csomópontot. 573 00:45:54,050 --> 00:45:56,260 És most, mi lesz, hogy megy át a fa, 574 00:45:56,260 --> 00:45:58,140 és ne feledje, hogy a megállási feltétel - 575 00:45:58,140 --> 00:46:01,870  amikor ténylegesen ledolgozott példáján keresztül kézzel - 576 00:46:01,870 --> 00:46:03,960 volt, amikor találkoztunk a null csomópont, 577 00:46:03,960 --> 00:46:05,480 nem akkor, amikor megnéztük a null gyermek, 578 00:46:05,480 --> 00:46:09,620 hanem amikor ténylegesen költözött csomópont a fában 579 00:46:09,620 --> 00:46:12,640 és megállapította, hogy vagyunk egy null csomópont. 580 00:46:12,640 --> 00:46:20,720 Elmegyünk navigálhat amíg akt nem egyenlő null. 581 00:46:20,720 --> 00:46:22,920 És mit fogunk csinálni? 582 00:46:22,920 --> 00:46:31,610 Fogunk tesztelni if ​​(akt -> érték == érték), 583 00:46:31,610 --> 00:46:35,160 akkor tudjuk, hogy már valóban találtak a csomópont, amit keresünk. 584 00:46:35,160 --> 00:46:40,450 Tehát itt, mi is vissza igaz. 585 00:46:40,450 --> 00:46:49,830 Egyébként, szeretnénk-e, vagy sem az érték kisebb, mint az érték. 586 00:46:49,830 --> 00:46:53,850 Ha az aktuális csomópont értéke kisebb, mint az érték keresünk, 587 00:46:53,850 --> 00:46:57,280 fogunk mozgatni jobbra. 588 00:46:57,280 --> 00:47:10,600 Szóval, akt = akt -> right_child, és különben fogunk mozgatni balra. 589 00:47:10,600 --> 00:47:17,480 akt = akt -> left_child,. Elég egyszerű. 590 00:47:17,480 --> 00:47:22,830 >> Akkor valószínűleg ismeri a hurok, hogy nagyon hasonlít az e-től 591 00:47:22,830 --> 00:47:27,580 bináris keresés korábban ezt a kifejezést, csak akkor van dolgunk, alacsony, közepes és magas. 592 00:47:27,580 --> 00:47:30,000 Itt már csak egy pillantást vetni a folyó értéken, 593 00:47:30,000 --> 00:47:31,930 így szép és egyszerű. 594 00:47:31,930 --> 00:47:34,960 Hadd győződjön meg róla, ez a kód működik. 595 00:47:34,960 --> 00:47:42,780 Először is, győződjön meg róla, hogy lefordul. Úgy néz ki, igen. 596 00:47:42,780 --> 00:47:47,920 Próbáljuk fut. 597 00:47:47,920 --> 00:47:50,160 És valóban, ez kiírja mindent, hogy mi várható. 598 00:47:50,160 --> 00:47:54,320 Megállapítja, 6 a fa, nem talál 10 mert 10 nem a fán, 599 00:47:54,320 --> 00:47:57,740 és nem talál 1 vagy azért, mert 1-es szintén nem a fán. 600 00:47:57,740 --> 00:48:01,420 Cool stuff. 601 00:48:01,420 --> 00:48:04,470 >> Rendben. Menjünk vissza a specifikáció, és mi a következő lépés. 602 00:48:04,470 --> 00:48:07,990 Most azt akarja, hogy adjunk néhány csomópont a mi fa. 603 00:48:07,990 --> 00:48:11,690 Azt akarja, hogy adjunk 5, 2 és 8, és győződjön meg róla, hogy a kódot tartalmaz 604 00:48:11,690 --> 00:48:13,570 még mindig működik, mint várták. 605 00:48:13,570 --> 00:48:14,900 Menjünk erre. 606 00:48:14,900 --> 00:48:19,430 Ezen a ponton, és nem csinál, hogy zavaró másolás és beillesztés újra, 607 00:48:19,430 --> 00:48:23,770 írjunk egy függvényt, hogy ténylegesen létre egy csomópont. 608 00:48:23,770 --> 00:48:27,740 Ha lapozzunk lefelé egészen a legfontosabb, azt látjuk, hogy mi már ezt 609 00:48:27,740 --> 00:48:31,210 nagyon hasonló kód újra és újra, minden alkalommal, hogy szeretnénk létrehozni egy csomópont. 610 00:48:31,210 --> 00:48:39,540 >> Nézzünk levelet, hogy a funkció valóban épít egy csomópont a számunkra, és küldje vissza. 611 00:48:39,540 --> 00:48:41,960 Fogom hívni build_node. 612 00:48:41,960 --> 00:48:45,130 Megyek, hogy építsenek egy csomópont egy adott értéket. 613 00:48:45,130 --> 00:48:51,040 Nagyítás itt. 614 00:48:51,040 --> 00:48:56,600 Az első dolog, fogok csinálni valójában teret a csomópont a kupac. 615 00:48:56,600 --> 00:49:05,400 Szóval, node * n = malloc (sizeof (node)), n -> value = érték; 616 00:49:05,400 --> 00:49:14,960 és akkor itt, én csak úgy inicializálja az összes mezőt, hogy megfelelő értékeket. 617 00:49:14,960 --> 00:49:22,500 És a legvégén, akkor vissza a csomópontot. 618 00:49:22,500 --> 00:49:28,690 Rendben. Egy dolog megjegyezni, hogy ezt a funkciót itt 619 00:49:28,690 --> 00:49:34,320 megy vissza a mutató a memóriában, hogy már halom különítettek el. 620 00:49:34,320 --> 00:49:38,880 Mi a szép ebben, hogy ez a csomópont most - 621 00:49:38,880 --> 00:49:42,420 van, hogy állapítsa meg azt a halom, mert ha nyilvánította a verem 622 00:49:42,420 --> 00:49:45,050 nem lennénk képesek csinálni ezt a funkciót, mint ez. 623 00:49:45,050 --> 00:49:47,690 Ez a memória menne ki a hatálya alól 624 00:49:47,690 --> 00:49:51,590 , és érvénytelen, ha megpróbáltuk elérni, hogy később. 625 00:49:51,590 --> 00:49:53,500 Mivel mi nyilvánításáról halom memóriát, 626 00:49:53,500 --> 00:49:55,830 fogjuk, hogy vigyázzon a felszabadítása később 627 00:49:55,830 --> 00:49:58,530 a mi program nem szivároghat semmilyen memóriát. 628 00:49:58,530 --> 00:50:01,270 Már ladikozás, hogy minden mást a kódot 629 00:50:01,270 --> 00:50:02,880 Csak az egyszerűség kedvéért abban az időben, 630 00:50:02,880 --> 00:50:05,610 de ha valaha is írni egy függvényt, amely a következőképpen néz ki 631 00:50:05,610 --> 00:50:10,370 hol van - néhányan a malloc vagy realloc belül - 632 00:50:10,370 --> 00:50:14,330 azt szeretnénk, hogy győződjön meg arról, hogy teszel valami megjegyzést ide, hogy azt mondja, 633 00:50:14,330 --> 00:50:29,970 hé, tudod, vissza halom kiosztott csomópont inicializálja a recirkulált-értéke. 634 00:50:29,970 --> 00:50:33,600 És akkor azt szeretnénk, hogy győződjön meg arról, hogy teszel valami megjegyzést, hogy azt mondja 635 00:50:33,600 --> 00:50:41,720 a hívó kell szabadítanunk a visszaadott memóriát. 636 00:50:41,720 --> 00:50:45,450 Így, ha valaki valaha is megy, és használja ezt a funkciót, 637 00:50:45,450 --> 00:50:48,150 tudják, hogy bármit is kap vissza ezt a funkciót 638 00:50:48,150 --> 00:50:50,870 egy bizonyos ponton meg kell szabadítani. 639 00:50:50,870 --> 00:50:53,940 >> Feltételezve, hogy minden rendben van, és jó itt, 640 00:50:53,940 --> 00:51:02,300 mehetünk le a kódot, és cserélje ki az összes ezeket a sorokat itt 641 00:51:02,300 --> 00:51:05,410 A hívásokat a mi épít node funkciót. 642 00:51:05,410 --> 00:51:08,170 Csináljuk azt nagyon gyorsan. 643 00:51:08,170 --> 00:51:15,840 Az egyik része, hogy nem fogunk cserélni ez a rész itt lent 644 00:51:15,840 --> 00:51:18,520 alján, ahol tulajdonképpen bekötésének fel a csomópontokat, hogy mutasson az egyes más, 645 00:51:18,520 --> 00:51:21,030 mert nem tehetünk a mi funkciót. 646 00:51:21,030 --> 00:51:37,400 De csináljuk root = build_node (7); node * 3 = build_node (3); 647 00:51:37,400 --> 00:51:47,980 node * 6 = build_node (6); node * 9 = build_node (9),. 648 00:51:47,980 --> 00:51:52,590 És most, mi is volna hozzá csomópontok - 649 00:51:52,590 --> 00:52:03,530 node * 5 = build_node (5); node * 8 = build_node (8); 650 00:52:03,530 --> 00:52:09,760 és mi volt a másik csomópont? Lássuk csak. Azt akartuk, hogy még hozzá egy 2 - 651 00:52:09,760 --> 00:52:20,280 node * 2 = build_node (2);. 652 00:52:20,280 --> 00:52:26,850 Rendben. Ezen a ponton, tudjuk, hogy megvan a 7, a 3, a 9 és a 6 653 00:52:26,850 --> 00:52:30,320 Az összes vezetékes up megfelelően, de mi a helyzet az 5, a 8 és a 2? 654 00:52:30,320 --> 00:52:33,550 Annak érdekében, hogy minden a megfelelő sorrendben, 655 00:52:33,550 --> 00:52:39,230 tudjuk, hogy három joga gyermek 6. 656 00:52:39,230 --> 00:52:40,890 Tehát, ha megyünk hozzá az 5, 657 00:52:40,890 --> 00:52:46,670 az 5 is tartozik a jobb oldalon a fa, amelyből 3 a gyökér, 658 00:52:46,670 --> 00:52:50,440 így 5 közé tartozik, mint a baloldali gyermek a 6. 659 00:52:50,440 --> 00:52:58,650 Ezt úgy tehetjük meg, mondván, hat -> left_child = 5; 660 00:52:58,650 --> 00:53:10,790 és azután a 8 tartozik mint a bal gyermek a 9, így 9 -> left_child = 8; 661 00:53:10,790 --> 00:53:22,190 majd 2 a bal gyerek 3, így nem tehetünk, hogy az ide - téged -> left_child = 2,. 662 00:53:22,190 --> 00:53:27,730 Ha nem egészen kövesse végig, hogy azt javaslom, hogy dolgozzon ki magad. 663 00:53:27,730 --> 00:53:35,660 >> Rendben. Nézzük mentéséhez. Menjünk ki, és győződjön meg róla, hogy lefordul, 664 00:53:35,660 --> 00:53:40,760 és akkor adhat a mi Tartalom hívásokat. 665 00:53:40,760 --> 00:53:44,120 Úgy tűnik, még mindig minden össze. 666 00:53:44,120 --> 00:53:51,790 Menjünk, és adjunk hozzá néhány tartalmaz hívásokat. 667 00:53:51,790 --> 00:53:59,640 Ismét fogok csinálni egy kis másolás és beillesztés. 668 00:53:59,640 --> 00:54:15,860 Most kereséséhez az 5., 8., és 2. Rendben. 669 00:54:15,860 --> 00:54:28,330 Hadd győződjön meg arról, hogy ez az egész jól néz ki még mindig. Nagyszerű! Mentés és kilépés. 670 00:54:28,330 --> 00:54:33,220 Most tegyük, lefordítja, és most menjünk futni. 671 00:54:33,220 --> 00:54:37,540 Az eredmény, úgy néz ki minden rendben működik, csak szép és jó. 672 00:54:37,540 --> 00:54:41,780 Nagyszerű! Tehát most megvan a Tartalom funkciót írva. 673 00:54:41,780 --> 00:54:46,160 Menjünk, és elkezd dolgozni, hogyan lehet beilleszteni csomópontok a fa 674 00:54:46,160 --> 00:54:50,000 hiszen, ahogy mi csináljuk, hogy most, a dolgok nem nagyon csinos. 675 00:54:50,000 --> 00:54:52,280 >> Ha visszamegyünk a specifikáció, 676 00:54:52,280 --> 00:55:00,540 azt kéri tőlünk, hogy levelet nevezett funkció be - ismét visszatér a bool 677 00:55:00,540 --> 00:55:04,400 az-e vagy sem tudnánk ténylegesen be a csomópont a fa - 678 00:55:04,400 --> 00:55:07,710 majd az értéket beilleszteni a fa van megadva 679 00:55:07,710 --> 00:55:11,060 az egyetlen érv, hogy a betét funkciót. 680 00:55:11,060 --> 00:55:18,180 Vissza fogunk térni igaz, ha valóban be a csomópont, amely érték a fa, 681 00:55:18,180 --> 00:55:20,930 ami azt jelenti, hogy az egyik volt elég memória, 682 00:55:20,930 --> 00:55:24,840 , majd két, a csomópont nem létezik a fán, mivel - 683 00:55:24,840 --> 00:55:32,170 emlékszem, mi nem megy, hogy ismétlődő értékeket a fa, csak hogy a dolgok egyszerű. 684 00:55:32,170 --> 00:55:35,590 Rendben. Vissza a kódot. 685 00:55:35,590 --> 00:55:44,240 Nyisd ki. Nagyítás egy kicsit, majd görgessen lefelé. 686 00:55:44,240 --> 00:55:47,220 Tegyük a Függvény beszúrása jobbra felett tartalmaz. 687 00:55:47,220 --> 00:55:56,360 Ismét, ez lesz az úgynevezett bool betét (int érték). 688 00:55:56,360 --> 00:56:01,840 Adj neki egy kicsit több helyet, majd az alapértelmezett, 689 00:56:01,840 --> 00:56:08,870 tegyük a return false a legvégén. 690 00:56:08,870 --> 00:56:22,620 Most meg az alján, menjünk előre, és ahelyett, hogy manuálisan épület a csomópontok 691 00:56:22,620 --> 00:56:27,900 a fő magunkat és vezetékek őket mutatni egymásnak, mint mi csinálunk, 692 00:56:27,900 --> 00:56:30,600 mi támaszkodunk betét funkciót csinálni. 693 00:56:30,600 --> 00:56:35,510 Nem fogunk támaszkodni a Függvény beszúrása építeni az egész fát a semmiből csak még, 694 00:56:35,510 --> 00:56:39,970 hanem fogunk megszabadulni ezeket a sorokat - we'll megjegyzésbe az ezeken a vonalakon - 695 00:56:39,970 --> 00:56:43,430 hogy épít a csomópontok az 5., 8., és 2. 696 00:56:43,430 --> 00:56:55,740 És ahelyett, hogy fogjuk be a hívásokat a Függvény beszúrása 697 00:56:55,740 --> 00:57:01,280 hogy győződjön meg arról, hogy tényleg működik. 698 00:57:01,280 --> 00:57:05,840 Itt vagyunk. 699 00:57:05,840 --> 00:57:09,300 >> Most már kommentálta ezeket a sorokat. 700 00:57:09,300 --> 00:57:13,700 Már csak 7, 3, 9, és 6 a mi fa ezen a ponton. 701 00:57:13,700 --> 00:57:18,870 Annak érdekében, hogy ez az egész működik, 702 00:57:18,870 --> 00:57:25,050 tudjuk kicsinyíteni, hogy a bináris fa, 703 00:57:25,050 --> 00:57:30,750 fut, és azt látjuk, hogy tartalmazza a most azt mondja, hogy mi vagyunk teljesen jobbra - 704 00:57:30,750 --> 00:57:33,110 5., 8., és 2 már nem a fa. 705 00:57:33,110 --> 00:57:37,960 Menj vissza a kódot, 706 00:57:37,960 --> 00:57:41,070 és hogyan fogunk be? 707 00:57:41,070 --> 00:57:46,290 Emlékszel, mit tettünk, amikor ténylegesen behelyezése 5, 8, 2 korábban. 708 00:57:46,290 --> 00:57:50,100 Azt játszottam, hogy Plinko játék, ahol elkezdtük a gyökér, 709 00:57:50,100 --> 00:57:52,780 lement a fát egyenként egy 710 00:57:52,780 --> 00:57:54,980 amíg megtaláltuk a megfelelő rést, 711 00:57:54,980 --> 00:57:57,570 aztán vezetékes a csomópont a megfelelő helyen. 712 00:57:57,570 --> 00:57:59,480 Megyünk nem ugyanaz a dolog. 713 00:57:59,480 --> 00:58:04,070 Ez alapvetően, mint az írás a kódot, hogy mi használt funkciót tartalmaz 714 00:58:04,070 --> 00:58:05,910 hogy megtalálja a helyet, ahol a csomópont legyen, 715 00:58:05,910 --> 00:58:10,560 és akkor még csak megy be a csomópont ott. 716 00:58:10,560 --> 00:58:17,000 Kezdjük csinálja. 717 00:58:17,000 --> 00:58:24,200 >> Tehát van egy node * cur = root, mi csak fogja követni a kódot tartalmaz 718 00:58:24,200 --> 00:58:26,850 amíg meg nem találják, hogy nem igazán működik a számunkra. 719 00:58:26,850 --> 00:58:32,390 Megyünk, hogy menjen át a fa, míg az aktuális elem nem nulla, 720 00:58:32,390 --> 00:58:45,280 és ha úgy találjuk, hogy akt értéke egyenlő értéket próbálunk beszúrni - 721 00:58:45,280 --> 00:58:49,600 Nos, ez az egyik olyan esetekben, amikor nem tudtuk valójában be a csomópont 722 00:58:49,600 --> 00:58:52,730 a fa, mert ez azt jelenti, hogy van egy ismétlődő értéket. 723 00:58:52,730 --> 00:58:59,010 Itt most tényleg megy vissza hamis. 724 00:58:59,010 --> 00:59:08,440 Most, else if akt értéke kisebb, mint érték, 725 00:59:08,440 --> 00:59:10,930 Most tudjuk, hogy mozog a jobb 726 00:59:10,930 --> 00:59:17,190  mert az érték tartozik a jobb felén a cur fa. 727 00:59:17,190 --> 00:59:30,110 Máskülönben fogunk mozgatni balra. 728 00:59:30,110 --> 00:59:37,980 Ez alapvetően a mi Tartalom működik ott. 729 00:59:37,980 --> 00:59:41,820 >> Ezen a ponton, ha egyszer már végrehajtotta ezt a while ciklus, 730 00:59:41,820 --> 00:59:47,350 mi cur mutató lesz mutatva null 731 00:59:47,350 --> 00:59:51,540 ha a funkció még nem tért vissza. 732 00:59:51,540 --> 00:59:58,710 Mi tehát, amelynek akt azon a helyen, ahol szeretné szúrni az új csomópontot. 733 00:59:58,710 --> 01:00:05,210 Mit kell még tenni, hogy ténylegesen építeni az új csomópont, 734 01:00:05,210 --> 01:00:08,480 amit tehetünk nagyon könnyen. 735 01:00:08,480 --> 01:00:14,930 Tudjuk használni a szuper-praktikus épít csomópont funkció, 736 01:00:14,930 --> 01:00:17,210 és valami, amit nem tett meg korábban - 737 01:00:17,210 --> 01:00:21,400 már csak ilyen volt a nyújtott, de most megteszem, csak hogy megbizonyosodjon arról - 738 01:00:21,400 --> 01:00:27,130 fogunk tesztelni, hogy győződjön meg arról, hogy a visszaadott érték az új csomópont ténylegesen 739 01:00:27,130 --> 01:00:33,410 nem nulla, mert nem akarjuk kezdeni elérése, hogy az emlékezet, ha null. 740 01:00:33,410 --> 01:00:39,910 Meg lehet próbálni, hogy győződjön meg arról, hogy az új csomópont nem egyenlő null. 741 01:00:39,910 --> 01:00:42,910 Vagy inkább, mi is csak látni, ha valójában null, 742 01:00:42,910 --> 01:00:52,120 és ha null, akkor is csak vissza false elején. 743 01:00:52,120 --> 01:00:59,090 >> Ezen a ponton meg kell bekötni az új csomópontot a megfelelő helyen a fán. 744 01:00:59,090 --> 01:01:03,510 Ha visszatekintünk a főbb és hol voltunk valójában kábelezés értékek előtt, 745 01:01:03,510 --> 01:01:08,470 azt látjuk, hogy az utat csinálunk, amikor akartunk tenni 3 a fán 746 01:01:08,470 --> 01:01:11,750 volt, mi érhető el a bal oldali gyermek root. 747 01:01:11,750 --> 01:01:14,920 Amikor put 9 a fa, mi volt elérni a jobb gyermek a gyökér. 748 01:01:14,920 --> 01:01:21,030 Volt, hogy egy mutató a szülő annak érdekében, hogy egy új értéket a fa. 749 01:01:21,030 --> 01:01:24,430 Görgetés vissza beszúrni, hogy ez nem fog teljesen itt dolgozni 750 01:01:24,430 --> 01:01:27,550 mert nincs szülő mutató. 751 01:01:27,550 --> 01:01:31,650 Mi azt akarjuk, hogy képes megtenni az, ezen a ponton, 752 01:01:31,650 --> 01:01:37,080 ellenőrizze a szülő érték és látni - nos, istenem, 753 01:01:37,080 --> 01:01:41,990 ha a szülő értéke kisebb, mint az aktuális érték, 754 01:01:41,990 --> 01:01:54,440 akkor a szülő joga gyermeknek kell lennie az új csomópont; 755 01:01:54,440 --> 01:02:07,280 ellenkező esetben a szülő bal gyermeke legyen az új csomópontot. 756 01:02:07,280 --> 01:02:10,290 De nincs ez a szülő mutató elég még. 757 01:02:10,290 --> 01:02:15,010 >> Annak érdekében, hogy azt, mi tényleg kell majd követni, hogy ahogy haladunk át a fát 758 01:02:15,010 --> 01:02:18,440 és megtalálni a megfelelő helyet a mi hurok felett. 759 01:02:18,440 --> 01:02:26,840 Meg tudjuk csinálni, hogy a görgetés vissza a csúcsra a Függvény beszúrása 760 01:02:26,840 --> 01:02:32,350 és nyomon követése egy pointer változót nevezzük a szülő. 761 01:02:32,350 --> 01:02:39,340 Fogjuk beállítani egyenlő null kezdetben, 762 01:02:39,340 --> 01:02:43,640 majd minden alkalommal megyünk át a fa, 763 01:02:43,640 --> 01:02:51,540 fogunk beállítani a szülő mutatót, hogy megfeleljen a jelenlegi mutatót. 764 01:02:51,540 --> 01:02:59,140 Állítsa szülő egyenlő cur. 765 01:02:59,140 --> 01:03:02,260 Így minden alkalommal, amikor megyünk keresztül, 766 01:03:02,260 --> 01:03:05,550 fogunk annak biztosítására, hogy a jelenlegi mutató lesz eggyel 767 01:03:05,550 --> 01:03:12,640 az anyavállalat mutató következik, hogy - csak egy szinttel magasabb, mint a jelenlegi mutatót a fán. 768 01:03:12,640 --> 01:03:17,370 Ez mind jól néz ki. 769 01:03:17,370 --> 01:03:22,380 >> Azt hiszem, az egy dolog, hogy mi szeretnénk beállítani ez a csomópont kiépítése visszatérnek null. 770 01:03:22,380 --> 01:03:25,380 Annak érdekében, hogy építeni csomópontot ténylegesen sikeresen vissza null, 771 01:03:25,380 --> 01:03:31,060 akkor kell módosítani, hogy a kódot, 772 01:03:31,060 --> 01:03:37,270 mert itt, soha nem tesztelték, hogy győződjön meg arról, hogy a malloc visszaadott érvényes mutató. 773 01:03:37,270 --> 01:03:53,390 Tehát, ha (n! = NULL), majd - 774 01:03:53,390 --> 01:03:55,250 ha malloc vissza érvényes mutató, aztán inicializálja azt; 775 01:03:55,250 --> 01:04:02,540 másként, akkor csak vissza, és hogy a végén visszatérnek null nekünk. 776 01:04:02,540 --> 01:04:13,050 Most minden jól néz ki. Hadd győződjön meg róla, ez valójában össze. 777 01:04:13,050 --> 01:04:22,240 Győződjön bináris fa, és jaj, mi van néhány dolog folyik itt. 778 01:04:22,240 --> 01:04:29,230 >> Van egy implicit nyilatkozatot funkciót épít csomópont. 779 01:04:29,230 --> 01:04:31,950 Ismét ezekkel fordítóprogramok, fogunk kezdeni a tetején. 780 01:04:31,950 --> 01:04:36,380 Mi az, hogy az azt jelenti, hogy én hívom építeni csomópont előtt, amit ténylegesen bevallott azt. 781 01:04:36,380 --> 01:04:37,730 Menjünk vissza a kód nagyon gyorsan. 782 01:04:37,730 --> 01:04:43,510 Lapozzunk lefelé, és persze elég, a betét funkció bejelentett 783 01:04:43,510 --> 01:04:47,400 felett a build csomópont funkció 784 01:04:47,400 --> 01:04:50,070 de én próbálom használni építeni node belül betét. 785 01:04:50,070 --> 01:05:06,610 Én megyek és másolás -, és illessze be a build függvény csomópont egészen ide a tetején. 786 01:05:06,610 --> 01:05:11,750 Így remélem, hogy működni fog. Adjunk a másik megy. 787 01:05:11,750 --> 01:05:18,920 Most már minden össze. Minden jó. 788 01:05:18,920 --> 01:05:21,640 >> De ezen a ponton, már nem is felhívta a betét funkciót. 789 01:05:21,640 --> 01:05:26,510 Mi csak tudjuk, hogy lefordul, úgyhogy menjünk, és némi kéri be 790 01:05:26,510 --> 01:05:28,240 Csináljuk, hogy a fő funkciója. 791 01:05:28,240 --> 01:05:32,390 Itt, megjegyzésben 5, 8, és 2, 792 01:05:32,390 --> 01:05:36,680 és akkor nem kösse őket ide. 793 01:05:36,680 --> 01:05:41,640 Nézzünk néhány hívást beszúrni, 794 01:05:41,640 --> 01:05:46,440 és menjünk is használja ugyanazt a fajta dolog, hogy mi használt 795 01:05:46,440 --> 01:05:52,810 mikor tette ezeket printf kéri, hogy győződjön meg arról, hogy minden nem kap behelyezve. 796 01:05:52,810 --> 01:06:00,550 Fogom másolni és beilleszteni, 797 01:06:00,550 --> 01:06:12,450 és ahelyett, hogy tartalmaz fogunk csinálni betéttel. 798 01:06:12,450 --> 01:06:30,140 És a 6 helyett, 10, és 1, fogunk az 5, 8, és 2. 799 01:06:30,140 --> 01:06:37,320 Ez remélhetőleg 5 betét, a 8., és 2 a fára. 800 01:06:37,320 --> 01:06:44,050 Fordítsd le. Minden jó. Most akkor tulajdonképpen fut a program. 801 01:06:44,050 --> 01:06:47,330 >> Mindent vissza hamis. 802 01:06:47,330 --> 01:06:53,830 Szóval, 5, 8, és 2 nem ment, és úgy néz ki, mint a Tartalom nem találta őket sem. 803 01:06:53,830 --> 01:06:58,890 Mi folyik itt? Menjünk kicsinyítéshez. 804 01:06:58,890 --> 01:07:02,160 Az első probléma az volt, hogy úgy tűnt, lapka vissza hamis, 805 01:07:02,160 --> 01:07:08,750 és úgy néz ki, hogy azért van, mert mi maradt a return false hívás 806 01:07:08,750 --> 01:07:14,590 és mi soha nem tért vissza igaz. 807 01:07:14,590 --> 01:07:17,880 Azt lehet állítani, hogy akár. 808 01:07:17,880 --> 01:07:25,290 A második probléma, most még ha nem teszünk - mentéséhez lépjen ki ezt, 809 01:07:25,290 --> 01:07:34,530 vagy futtasd a make megint, azt azonnal le, majd futtassa - 810 01:07:34,530 --> 01:07:37,670 azt látjuk, hogy valami más történt itt. 811 01:07:37,670 --> 01:07:42,980 Az 5, 8, és 2 még nem találták a fában. 812 01:07:42,980 --> 01:07:44,350 Szóval, mi folyik itt? 813 01:07:44,350 --> 01:07:45,700 >> Vessünk egy pillantást erre a kódot. 814 01:07:45,700 --> 01:07:49,790 Lássuk, mi is kitaláljuk. 815 01:07:49,790 --> 01:07:57,940 Kezdjük a szülő, hogy nem null. 816 01:07:57,940 --> 01:07:59,510 Mi meg a jelenlegi mutató megegyezik a gyökér mutató, 817 01:07:59,510 --> 01:08:04,280 és fogunk dolgozni az utat lefelé a fáról. 818 01:08:04,280 --> 01:08:08,650 Ha a jelenlegi csomópont nem nulla, akkor tudjuk, hogy tudunk mozogni le egy kicsit. 819 01:08:08,650 --> 01:08:12,330 Mi meg a szülő mutató megegyezik a jelenlegi mutató, 820 01:08:12,330 --> 01:08:15,420 ellenőrizni az értéket - ha az értékek megegyeznek visszatértünk hamis. 821 01:08:15,420 --> 01:08:17,540 Ha az értékek kevésbé költöztünk jobbra; 822 01:08:17,540 --> 01:08:20,399 egyébként költöztünk a bal oldalon. 823 01:08:20,399 --> 01:08:24,220 Majd építünk egy csomópont. Majd nagyítani egy kicsit. 824 01:08:24,220 --> 01:08:31,410 És itt fogunk próbálni bekötésének fel az értékeket meg kell egyeznie. 825 01:08:31,410 --> 01:08:37,250 Mi folyik itt? Lássuk esetleg Valgrind tud adni nekünk egy tippet. 826 01:08:37,250 --> 01:08:43,910 >> Szeretem használni Valgrind csak azért, mert Valgrind nagyon gyorsan fut 827 01:08:43,910 --> 01:08:46,729 és azt mondja, ha van olyan memória hiba. 828 01:08:46,729 --> 01:08:48,300 Amikor fut Valgrind a kódot, 829 01:08:48,300 --> 01:08:55,859 amint látod van here--Valgrind./binary_tree--and hit adja. 830 01:08:55,859 --> 01:09:03,640 Látod, hogy mi nem volt memória hiba, ezért úgy néz ki, minden rendben eddig. 831 01:09:03,640 --> 01:09:07,529 Van némi memóriavesztés, amiről tudjuk, mert nem vagyunk 832 01:09:07,529 --> 01:09:08,910 történik, hogy szabad bármelyik csomópont. 833 01:09:08,910 --> 01:09:13,050 Próbáljuk futó GDB, hogy mi folyik itt valójában. 834 01:09:13,050 --> 01:09:20,010 Megteszünk gdb. / Binary_tree. Ez az indítás megtörtént csak finom. 835 01:09:20,010 --> 01:09:23,670 Nézzünk be egy töréspontot a betét. 836 01:09:23,670 --> 01:09:28,600 Fussunk. 837 01:09:28,600 --> 01:09:31,200 Úgy néz ki, hogy valójában soha nem hívott betéttel. 838 01:09:31,200 --> 01:09:39,410 Úgy néz ki, a probléma az volt csak, hogy mikor változott itt lent a fő - 839 01:09:39,410 --> 01:09:44,279 Mindezen printf hívások tartalmaz - 840 01:09:44,279 --> 01:09:56,430 Én soha nem változott e hívni betéttel. 841 01:09:56,430 --> 01:10:01,660 Most, hogy ez a próbálkozás. Menjünk összeállításához. 842 01:10:01,660 --> 01:10:09,130 Minden jól néz ki ott. Most próbáljuk fut, meglátjuk, mi történik. 843 01:10:09,130 --> 01:10:13,320 Rendben! Minden, ami jól néz ki ott. 844 01:10:13,320 --> 01:10:18,130 >> Az utolsó dolog, amit gondolni, vannak-e olyan esetek él ezen betét? 845 01:10:18,130 --> 01:10:23,170 És kiderül, hogy, nos, az egyik szélén helyzet, hogy mindig érdekes gondolni 846 01:10:23,170 --> 01:10:26,250 az, hogy mi történik, ha a fa üres és hívja ezt betét funkció? 847 01:10:26,250 --> 01:10:30,330 Működni fog? Nos, adjunk neki egy esélyt. 848 01:10:30,330 --> 01:10:32,110 - Binary_tree. C - 849 01:10:32,110 --> 01:10:35,810 Ahogy megyünk tesztelni ezt, fogunk lemenni a fő funkciója, 850 01:10:35,810 --> 01:10:41,690 és ahelyett, hogy ezek a csomópontok vezetékek ki, mint ez, 851 01:10:41,690 --> 01:10:56,730 mi csak megy megjegyzésbe az egész dolog, 852 01:10:56,730 --> 01:11:02,620 és ahelyett, vezetékek ki a csomópontot magunkat, 853 01:11:02,620 --> 01:11:09,400 mi is valójában csak megy előre, és törölje ezt az egészet. 854 01:11:09,400 --> 01:11:17,560 Megyünk, hogy minden hívást beilleszteni. 855 01:11:17,560 --> 01:11:49,020 Szóval, csináljuk - ahelyett, 5, 8, 2, megyünk be 7, 3 és 9. 856 01:11:49,020 --> 01:11:58,440 És akkor mi is szeretnénk beszúrni 6 is. 857 01:11:58,440 --> 01:12:05,190 Mentés. Kilépés. Győződjön bináris fa. 858 01:12:05,190 --> 01:12:08,540 Minden össze. 859 01:12:08,540 --> 01:12:10,320 Mi is csak futni úgy, ahogy van, és meglátjuk, mi történik, 860 01:12:10,320 --> 01:12:12,770 de ez is lesz nagyon fontos, hogy győződjön meg arról, hogy 861 01:12:12,770 --> 01:12:14,740 nem rendelkezik memória hiba, 862 01:12:14,740 --> 01:12:16,840 mivel ez az egyik él esetek tudunk. 863 01:12:16,840 --> 01:12:20,150 >> Legyen biztos abban, hogy jól működik Valgrind alatt, 864 01:12:20,150 --> 01:12:28,310 amit megteszek mellett csak futás Valgrind. / binary_tree. 865 01:12:28,310 --> 01:12:31,110 Úgy néz ki, hogy tényleg van egy hiba az egyik kontextus - 866 01:12:31,110 --> 01:12:33,790 itt van ez szegmentációs hibát. 867 01:12:33,790 --> 01:12:36,690 Mi történt? 868 01:12:36,690 --> 01:12:41,650 Valgrind valójában azt mondja nekünk, hogy hol van. 869 01:12:41,650 --> 01:12:43,050 Kicsinyítés egy kicsit. 870 01:12:43,050 --> 01:12:46,040 Úgy néz ki, ez történik a mi betét funkció, 871 01:12:46,040 --> 01:12:53,420 ha van egy érvénytelen olvasási méret 4-es lapka, line 60. 872 01:12:53,420 --> 01:13:03,590 Menjünk vissza, és nézd meg, hogy mi folyik itt. 873 01:13:03,590 --> 01:13:05,350 Kicsinyítés nagyon gyors. 874 01:13:05,350 --> 01:13:14,230 Azt szeretnénk, hogy győződjön meg arról, hogy nem megy a szélén a képernyőn, így látunk mindent. 875 01:13:14,230 --> 01:13:18,760 Húzza ki, hogy egy kicsit. Rendben. 876 01:13:18,760 --> 01:13:35,030 Lapozzunk lefelé, és a probléma itt. 877 01:13:35,030 --> 01:13:40,120 Mi történik, ha kap le, és a jelenlegi csomópont már null, 878 01:13:40,120 --> 01:13:44,010 a szülő csomópont null, tehát ha felnéz legtetején, itt - 879 01:13:44,010 --> 01:13:47,340 ha ez a while ciklus ténylegesen soha nem hajt végre 880 01:13:47,340 --> 01:13:52,330 mert a jelenlegi értéke null - a gyökér null annyira akt null - 881 01:13:52,330 --> 01:13:57,810 akkor a szülő soha nem lesz beállítva, hogy akt vagy egy érvényes értéket, 882 01:13:57,810 --> 01:14:00,580 így, szülő lesz null. 883 01:14:00,580 --> 01:14:03,700 Emlékeznünk kell arra, hogy ellenőrizze, hogy a 884 01:14:03,700 --> 01:14:08,750 mire jutunk ide, és kezdjük elérni a szülő értékét. 885 01:14:08,750 --> 01:14:13,190 Szóval, mi történik? Nos, ha a szülő null - 886 01:14:13,190 --> 01:14:17,990 if (szülő == NULL) -, akkor tudjuk, hogy 887 01:14:17,990 --> 01:14:19,530 ott nem lehet semmit a fán. 888 01:14:19,530 --> 01:14:22,030 Meg kell próbál helyezze azt a gyökér. 889 01:14:22,030 --> 01:14:32,570 Meg tudjuk csinálni, hogy a csak a root beállítás megegyezik az új csomópont. 890 01:14:32,570 --> 01:14:40,010 Aztán ezen a ponton, akkor valójában nem akar menni ezeken más dolog. 891 01:14:40,010 --> 01:14:44,780 Ehelyett, itt van, amit tehetünk, vagy egy else-if-else, 892 01:14:44,780 --> 01:14:47,610 vagy mi lehet kombinálni mindent itt egy más, 893 01:14:47,610 --> 01:14:56,300 de itt akkor csak használ mást, és nem így. 894 01:14:56,300 --> 01:14:59,030 Most fogunk tesztelni, hogy győződjön meg arról, hogy a szülő nem null 895 01:14:59,030 --> 01:15:02,160 addig próbálunk hozzáférni a mezőket. 896 01:15:02,160 --> 01:15:05,330 Ez segít nekünk elkerülni a szegmentációs hibát. 897 01:15:05,330 --> 01:15:14,740 Szóval, kilép, kicsinyítés, fordításához, futtatásához. 898 01:15:14,740 --> 01:15:18,130 >> Nem hiba, de még mindig van egy csomó memória szivárgás 899 01:15:18,130 --> 01:15:20,650 mert nem szabad sem a csomópontok. 900 01:15:20,650 --> 01:15:24,350 De, ha megyünk ide, és nézd meg a nyomtatás, 901 01:15:24,350 --> 01:15:30,880 azt látjuk, hogy, nos, úgy tűnik, minden kedves lapkák visszatértek igaz, ami jó. 902 01:15:30,880 --> 01:15:33,050 A betétek mind igaz, 903 01:15:33,050 --> 01:15:36,670 majd a megfelelő Tartalom hívás is igaz. 904 01:15:36,670 --> 01:15:41,510 >> Szép munka! Úgy néz ki, most már sikeresen írt betét. 905 01:15:41,510 --> 01:15:47,430 Ennyi van az e heti Problem Set specifikációja. 906 01:15:47,430 --> 01:15:51,720 Egy szórakoztató kihívás gondolni, hogyan ténylegesen megy 907 01:15:51,720 --> 01:15:55,340 és szabad az összes csomópont ezt a fát. 908 01:15:55,340 --> 01:15:58,830 Meg tudjuk csinálni, így számos különböző módon, 909 01:15:58,830 --> 01:16:01,930 de elmegyek, hogy rajtad múlik, hogy kísérlet, 910 01:16:01,930 --> 01:16:06,080 és mint egy szórakoztató kihívás, próbálja meg és győződjön meg róla, hogy biztos lehet benne, 911 01:16:06,080 --> 01:16:09,490 hogy ez a Valgrind jelentés nem ad vissza hibát, és nem szivárog. 912 01:16:09,490 --> 01:16:12,880 >> Sok szerencsét az e heti Huffman kódolás problémája készlet, 913 01:16:12,880 --> 01:16:14,380 és találkozunk jövő héten! 914 01:16:14,380 --> 01:16:17,290 [CS50.TV]