[Powered by Google Translate] [Adran 7] [Llai cyfforddus] [Nate Hardison] [Harvard University] [Mae hyn yn CS50.] [CS50.TV] 

Croeso i Adran 7. Diolch i Sandy corwynt, yn hytrach na chael adran arferol yr wythnos hon, ydym yn ei wneud y daith hon-drwy, drwy'r adran o'r cwestiynau. Rydw i'n mynd i gael eu dilyn ynghyd â'r Problem Set 6 Manyleb, ac yn mynd drwy bob un o'r cwestiynau yn y Mae Adran o Gwestiynau adran. Os oes unrhyw gwestiynau, os gwelwch yn dda yn rhoi'r rhain ar CS50 Trafod. 

Iawn. Gadewch i ni ddechrau arni. Ar hyn o bryd rwyf i'n edrych ar dudalen 3 y Set Problem Fanyleb. Rydym yn mynd yn gyntaf i ddechrau siarad am goed deuaidd ers y cael llawer o berthnasol i set problem yr wythnos hon - amgodiad Coed Huffman. Un o'r strwythurau data cyntaf buom yn siarad am ar CS50 oedd y rhesi. Cofiwch fod amrywiaeth yn ddilyniant o elfennau - i gyd o'r un fath - storio dde nesaf at ei gilydd yn y cof. Os oes gen i amrywiaeth cyfanrif y gallaf dynnu llun gan ddefnyddio arddull hon blychau-rifau-cyfanrifau - Lets 'ddeud gennyf 5 yn y blwch cyntaf, mae gennyf 7 yn yr ail, hynny, rwyf wedi 8, 10, a 20 yn y blwch olaf. Pethau Cofiwch, y ddau yn dda iawn am y casgliad yw bod gennym y mynediad hwn yn gyson-amser i unrhyw elfen benodol  yn yr amrywiaeth os ydym yn gwybod ei mynegai. Er enghraifft, os wyf am i chrafangia 'r drydedd elfen yn yr amrywiaeth - ar fynegai 2 gan ddefnyddio ein system mynegeio ar sail sero - Yr wyf yn llythrennol yn rhaid i wneud cyfrifiad mathemategol syml, hop i'r swydd honno yn yr amrywiaeth, dynnu allan o'r 8 sydd yn cael ei storio yno, ac rwy'n da i fynd. 

Un o'r pethau drwg am y casgliad - y buom yn siarad am pan fyddwn yn trafod rhestrau cysylltiedig - yw, os wyf i am osod elfen i hyn array, Rydw i'n mynd i gael i wneud rhywfaint o symud o gwmpas. Er enghraifft, mae hyn yn amrywiaeth dde yma yw er mwyn datrys - didoli yn nhrefn esgynnol - 5, yna 7, yna 8, yna 10, ac yna 20 - ond os wyf i am osod y rhif 9 i mewn i hyn array, Rydw i'n mynd i gael i symud rhai o'r elfennau er mwyn gwneud lle. Gallwn dynnu hyn allan yma. Rydw i'n mynd i gael i symud y 5, 7, ac yna yr 8; creu bwlch lle y gallaf roi'r 9, ac yna y gall 10 a'r 20 yn mynd i'r dde o'r 9. Mae hwn yn fath o boen oherwydd yn y senario gwaethaf-achos - pan fyddwn ni'n cael i fewnosod naill ai ar ddechrau neu ar ddiwedd y rhesi, yn dibynnu ar sut rydym yn symud - efallai y byddwn yn y pen draw yn gorfod symud yr holl elfennau ein bod ar hyn o bryd storio yn y rhesi. 

Felly, beth oedd y ffordd o gwmpas hyn? Mae'r ffordd o amgylch hyn oedd i fynd i'n dull rhestr cysylltiedig-os - yn hytrach na storio elfennau 5, 7, 8, 10, ac 20 i gyd nesaf at ei gilydd er cof - hyn yr ydym yn hytrach yn cael ei storio yn eu math o lle bynnag rydym yn awyddus i storio yn y rhestr nodau cysylltiedig-yr wyf i'n tynnu allan yma, math o ad hoc. Ac yna rydym yn eu cysylltu gyda'i gilydd gan ddefnyddio awgrymiadau hyn nesaf. Gallaf gael pwyntydd o 5 i 7, pwyntydd gan y 7 i 8, pwyntydd o'r 8 i 10, ac yn olaf, pwyntydd o'r 10 i'r 20, ac yna pwyntydd nwl yn y 20 sy'n dangos nad oes dim byd chwith. Mae'r fasnach-off sydd gennym yma yw bod nawr os ydym am i fewnosod y rhif 9 yn ein rhestr didoli, i gyd mae'n rhaid i ni ei wneud yw creu nod newydd gyda 9, gwifren i fyny i bwyntio at y man priodol, ac yna ail-wifren yr 8 i bwyntio i lawr i'r 9. Dyna 'n bert gyflym, gan dybio ein bod yn gwybod yn union lle rydym am i mewnosoder y 9. Ond y fasnach-off yn gyfnewid am hyn yw ein bod wedi colli awr fynediad cyson-amser i unrhyw elfen benodol yn ein strwythur data. Er enghraifft, os ydw i am ddod o hyd i'r bedwaredd elfen yn y rhestr hon cysylltiedig, Rydw i'n mynd i gael i ddechrau ar y cychwyn cyntaf y rhestr a gweithio fy ffordd trwy gyfrif nod-by-nod hyd nes i mi dod o hyd i'r un pedwerydd. 

Er mwyn cael perfformiad gwell mynediad na rhestr cysylltiedig - ond hefyd yn cadw rhai o'r buddiannau a fu gennym o ran gosod-amser o restr cysylltiedig - coeden ddeuaidd yn mynd i angen i ddefnyddio cof ychydig yn fwy. Yn benodol, yn hytrach na dim ond cael un pwyntydd mewn nod goeden ddeuol - fel y rhestr cysylltiedig-nod yn - rydym yn mynd i ychwanegu bwyntydd ail y nod goeden ddeuaidd. Yn hytrach na dim ond cael un pwyntydd i'r elfen nesaf, rydym yn mynd i gael pwyntydd i blentyn chwith a dde phlentyn. 

Gadewch i ni dynnu llun i weld beth sydd mewn gwirionedd yn edrych fel. Unwaith eto, dw i'n mynd i ddefnyddio blychau hyn a saethau. Bydd nod goeden ddeuol dechrau gyda dim ond blwch syml. Mae'n mynd i gael lle ar gyfer y gwerth, ac yna mae hefyd yn mynd i gael lle ar gyfer y plentyn chwith ac i'r plentyn iawn. Rydw i'n mynd i labelu nhw yma. Rydym yn mynd i gael y plentyn chwith, ac yna rydym yn mynd i gael i'r plentyn iawn. Mae llawer o ffyrdd gwahanol o wneud hyn. Weithiau, am le a hwylustod, 'N annhymerus' mewn gwirionedd yn tynnu ei fel fy mod yn ei wneud yma ar y gwaelod lle dwi'n mynd i gael y gwerth ar y brig, ac yna i'r plentyn iawn ar y gwaelod ar y dde, a'r plentyn chwith ar y gwaelod ar y chwith. Mynd yn ôl at y diagram uchaf, mae gennym y gwerth ar y brig, Yna, mae gennym y pwyntydd chwith plentyn, ac yna mae gennym y pwyntydd dde plentyn. 

Yn y Set Problem Fanyleb, fyddwn yn sôn am dynnu nod sydd â gwerth 7, ac yna i'r chwith-pwyntydd plant sy'n null, ac mae pwyntydd dde-plentyn sy'n null. Gallwn naill ai ysgrifennu NULL cyfalaf yn y gofod ar gyfer Gall y plentyn chwith ac i'r plentyn iawn, neu rydym yn tynnu y slaes lletraws drwy bob un o'r blychau i ddangos ei fod yn null. Rydw i'n mynd i wneud hynny dim ond oherwydd dyna symlach. Beth welwch chi yma yn ddwy ffordd o diagramau yn nod deuaidd syml iawn goeden lle mae gennym y gwerth 7 ac awgrymiadau blant null. 

Mae ail ran ein sgyrsiau fanyleb am sut gyda rhestrau cysylltiedig - cofiwch, dim ond wedi i ddal gafael ar yr elfen gyntaf mewn rhestr i gofio am y rhestr gyfan - ac yn yr un modd, gyda choeden ddeuol, dim ond rhaid i ni ddal gafael ar i un pwyntydd i'r goeden er mwyn cadw rheolaeth dros y strwythur data cyfan. Mae'r elfen arbennig o'r goeden a elwir yn nod wraidd y goeden. Er enghraifft, os yw hyn yn nod un - nod sy'n cynnwys y gwerth 7 gyda awgrymiadau chwith a dde-phlentyn null - oedd y gwerth yn unig yn ein coed, yna byddai hyn yn ein nod gwraidd. Mae'n cychwyn cyntaf ein coeden. Gallwn weld hyn ychydig yn fwy clir ar ôl i ni ddechrau ychwanegu nodau mwy i ein coeden. Gadewch i mi dynnu i fyny tudalen newydd. 

Nawr rydym yn mynd i dynnu coeden sy'n tyfu 7 yn y gwraidd, a 3 y tu mewn y plentyn chwith, a 9 tu mewn i'r plentyn iawn. Unwaith eto, mae hyn yn eithaf syml. Mae gennym 7, lluniwch nod ar gyfer y 3, yn nod ar gyfer 9, ac rydw i'n mynd i osod y pwyntydd chwith-phlentyn o 7 i bwyntio at y nod yn cynnwys 3, ac mae'r pwyntydd dde-blentyn y nod yn cynnwys 7 i nod sy'n cynnwys 9. Nawr, nid ers 3 a 9 yn cael unrhyw blant, rydym yn mynd i osod eu holl awgrymiadau plentyn i fod yn null. Yma, wrth wraidd ein coeden yn cyfateb i nod sy'n cynnwys y rhif 7. Gallwch weld bod os bydd yr holl gennym yw pwyntydd i'r nod gwraidd, yna gallwn gerdded trwy ein coeden a chael gafael ar nodau blant ddau - yn 3 a 9. Nid oes angen i gynnal awgrymiadau i bob nod sengl ar y goeden. Iawn. Nawr rydym yn mynd i ychwanegu un arall at y nod diagram. Rydym yn mynd i ychwanegu nod sy'n cynnwys 6, ac rydym yn mynd i ychwanegu hyn fel y plentyn hawl y nod yn cynnwys 3. I wneud hynny, dw i'n mynd i ddileu y pwyntydd nwl yn y 3-nod a gwifren i fyny i dynnu sylw at y nod sy'n cynnwys 6. Iawn. 

Ar y pwynt hwn, gadewch i ni fynd dros ychydig o derminoleg. I ddechrau, y rheswm bod hyn yn cael ei alw'n goeden ddeuol yn arbennig yw ei fod ganddo ddau awgrymiadau plentyn. Mae yna fathau eraill o goed sy'n cael awgrymiadau mwy ar y plentyn. Yn benodol, gwnaethoch 'roi cynnig' mewn 5 Set Problem. Byddwch yn sylwi bod yn y cais, byddwch yn cael 27 awgrymiadau gwahanol i blant gwahanol - un ar gyfer pob un o'r 26 o lythyrau yn y wyddor Saesneg, ac yna y 27ain ar gyfer y collnod - felly, mae hynny'n debyg i fath o goeden. Ond yma, gan ei fod yn binary, dim ond dau awgrymiadau plentyn. 

Yn ogystal â hyn, nod gwraidd ein bod yn sôn amdanynt, rydym hefyd wedi bod yn taflu o gwmpas y term 'plentyn'. Beth mae'n ei olygu i un nod i fod yn blentyn arall nod? Mae'n llythrennol yn golygu bod nod plentyn yn blentyn arall nod os yw'r nod arall un o'i awgrymiadau plentyn osod i gyfeirio at y nod. I roi hyn mewn termau diriaethol mwy, os 3 yn tynnu sylw at un o'r awgrymiadau plentyn 7, yna 3 yn blentyn o 7. Pe baem yn chyfrif i maes beth y mae'r plant o 7 yw - yn dda, rydym yn gweld bod 7 Mae pwyntydd i 3 a pwyntydd i 9, hynny 9 a 3 yn blant o 7. Nid oes gan naw plant oherwydd ei awgrymiadau plant yn null, a 3 dim ond un plentyn, 6. Six oes ganddo blant oherwydd ddau o'i arwyddion yn null, y byddwn yn tynnu ar hyn o bryd. 

Yn ogystal, rydym hefyd yn sôn am y rhieni nod penodol, ac mae hyn yn, fel y byddech yn ei ddisgwyl, gefn y disgrifiad plentyn. Mae pob nod Dim ond un rhiant - yn hytrach na dau fel y gallech ddisgwyl gyda phobl. Er enghraifft, rhiant 3 yw 7. Y rhiant o 9 hefyd yn 7, a'r rhiant o 6 yw 3. Dim llawer iddo. Rydym hefyd wedi termau i siarad am neiniau a theidiau a wyrion, ac yn fwy cyffredinol rydym yn sôn am yr hynafiaid a disgynyddion yn nod penodol. Mae'r gyndad nod - neu hynafiaid, yn hytrach, o nod - hefyd pob un o'r nodau sy'n gorwedd ar y llwybr o'r gwraidd i'r nod. Er enghraifft, os ydw i'n edrych ar y 6 nod, yna mae'r hynafiaid yn mynd i fod yn 3 a 7. Mae hynafiaid o 9, er enghraifft, yw - os ydw i'n edrych ar y 9 nod - yna bydd y hynafiad o 9 yn unig 7. Ac mae disgynyddion yn union i'r gwrthwyneb. Os ydw i eisiau edrych ar yr holl ddisgynyddion 7, Yna rhaid i mi edrych ar yr holl nodau oddi tano. Felly, yr wyf wedi 3, 9, a 6 i gyd fel disgynyddion 7. 

Mae'r tymor olaf y byddwn yn siarad amdano yw y syniad o fod yn frawd neu chwaer. Brodyr a chwiorydd - math o yn dilyn ar hyd ar y telerau teulu - yn nodau sydd ar yr un lefel yn y goeden. Felly, 3 a 9 yn frodyr a chwiorydd am eu bod ar yr un lefel yn y goeden. Mae gan y ddau yr un rhiant, 7. Mae'r 6 Nid oes gan frodyr a chwiorydd oherwydd 9 Nid oes unrhyw blant. Ac 7 Nid oes gan unrhyw frodyr a chwiorydd oherwydd ei fod yn wraidd ein coeden, a dim ond erioed 1 gwraidd. Am 7 i â brodyr neu chwiorydd byddai'n rhaid i fod yn nod uchod 7. Byddai rhaid i fod yn rhiant o 7, ym mha Achos 7 mwyach wraidd y goeden. Yna byddai rhiant newydd o 7 hefyd yn rhaid i chi gael plentyn, ac y byddai plentyn wedyn yn frawd neu chwaer o 7. 

Iawn. Symud ymlaen. Pan fyddwn yn dechrau ein trafodaeth o goed deuaidd, buom yn siarad am sut yr ydym yn mynd i'w defnyddio i cael mantais dros y ddwy araeau a rhestrau cysylltiedig. A'r ffordd yr ydym yn mynd i wneud hynny yw gyda'r eiddo archebu. Rydym yn dweud bod coeden ddeuaidd yn drefnus, yn ôl y fanyleb, os ar gyfer pob nod yn ein coeden, ei holl ddisgynyddion ar y chwith - y plentyn chwith a holl ddisgynyddion y plentyn chwith - yn werthoedd llai, a phob un o'r nodau ar y dde - i'r plentyn iawn a'r holl ddisgynyddion i'r plentyn iawn - yn gael nodau fwy na gwerth y nod ar hyn o bryd ein bod yn edrych ar. Dim ond ar gyfer symlrwydd, rydym yn mynd i gymryd yn ganiataol nad oes unrhyw nodau dyblyg yn ein coeden. Er enghraifft, yn y goeden hon, nid ydym yn mynd i ddelio â'r achos lle mae gennym y gwerth 7 yn y gwraidd  ac yna rydym hefyd yn cael y gwerth 7 mewn mannau eraill yn y goeden. Yn yr achos hwn, byddwch yn sylwi bod y goeden yn cael ei archebu yn wir. Mae gennym y gwerth 7 yn y gwraidd. Mae popeth i'r chwith o 7 - os wyf yn dadwneud pob un o'r marciau bach yma - popeth i'r chwith o 7 - 3 a 6 - gwerthoedd hynny yn y ddwy llai na 7, a phopeth ar y dde - sydd ychydig y 9 - yn fwy na 7. 

Nid yw hyn yn y goeden archebu yn unig yn cynnwys y gwerthoedd hyn, ond gadewch i ni dynnu mwy ychydig ohonynt. Mae mewn gwirionedd yn criw cyfan o ffyrdd y gallwn wneud hyn. Rydw i'n mynd i ddefnyddio llaw-fer yn unig i gadw pethau'n syml lle - yn hytrach na thynnu allan y cyfan blychau-a-saethau - Im 'jyst yn mynd i dynnu rhifau ac ychwanegu saethau sy'n eu cysylltu. I ddechrau, byddwn yn unig yn ysgrifennu ein coed gwreiddiol eto lle cawsom 7, ac yna 3, ac yna 3 sylw at y ffaith yn ôl i'r dde i'r 6, a 7 wedi cael plentyn hawl a oedd 9. Iawn. Beth ffordd arall y gallem ysgrifennu goeden hon? Yn hytrach na chael 3 fod y plentyn chwith 7, gallem hefyd fod y 6 fel un y plentyn chwith 7, ac yna 3 fod y plentyn chwith y 6. Byddai hynny'n edrych fel hyn goeden dde yma lle dwi 'di cael 7, Yna, 6, yna 3, a 9 ar y dde. Nid ydym ychwaith yn rhaid i chi gael 7 fel ein nod gwraidd. Gallem hefyd 6 fel ein nod gwraidd. Beth fyddai'n sy'n edrych fel? Os ydym yn mynd i gynnal yr eiddo hwn gorchymyn, popeth i'r chwith o'r 6 wedi i fod yn llai nag ef. Dim ond un posibilrwydd, a dyna 3. Ond wedyn cyn i'r plentyn iawn o 6, mae gennym ddau bosibilrwydd. Yn gyntaf, gallem gael y 7 ac yna'r 9, neu gallem dynnu - fel fy mod ar fin gwneud yma - lle mae gennym y 9 fel y plentyn cywir o'r 6, ac yna y 7 fel y plentyn chwith y 9. 

Nawr, nid 7 a 6 yn unig y gwerthoedd posibl ar gyfer y gwraidd. Gallem hefyd wedi 3 fod wrth wraidd. Beth sy'n digwydd os 3 yw wrth wraidd? Yma, mae pethau yn cael ychydig bach diddorol. Nid oedd tri oes unrhyw werthoedd sy'n llai na hynny, fel bod ochr chwith gyfan y goeden yn unig yn mynd i fod yn null. Nid oes yn mynd i fod yn unrhyw beth yno. I'r dde, gallem restru'r pethau yn nhrefn esgynnol. Gallem gael 3, yna 6, yna 7, yna 9. Neu, gallem wneud 3, yna 6, yna 9, yna 7. Neu, gallem wneud 3, yna 7, yna 6, yna 9. Neu, 3, 7 - mewn gwirionedd dim, ni allwn wneud 7 anymore. Dyna ein un peth yno. Gallwn wneud 9, ac yna o 9 y gallwn ei wneud 6 ac yna 7. Neu, gallwn wneud 3, yna 9, yna 7, ac yna 6. 

Un peth i dynnu eich sylw at yma bod y coed ychydig yn rhyfedd yr olwg. Yn arbennig, os ydym yn edrych ar y 4 goed ar yr ochr dde - 'N annhymerus' rhoi cylch o'u cwmpas, yma - coed hyn yn edrych bron yn union fel rhestr cysylltiedig. Mae pob nod Dim ond un plentyn, ac felly nid oes gennym unrhyw ran o'r strwythur coeden tebyg a welwn, er enghraifft,  yn y goeden 1 sengl dros yma ar y chwith gwaelod. Mae'r coed hyn yn cael eu galw mewn gwirionedd yn ddirywiedig coed binary, a byddwn yn siarad am rhain yn fwy yn y dyfodol - yn enwedig os ydych yn mynd ymlaen i ddilyn cyrsiau gwyddoniaeth gyfrifiadurol arall. Mae'r coed hyn yn dirywio. Dydyn nhw ddim yn ddefnyddiol iawn oherwydd, yn wir, strwythur hwn yn cynnig ei hun  i gyrchu ei gwaith tebyg i rhestr cysylltiedig. Nid ydym yn mynd i fanteisio ar y cof ychwanegol - mae hyn yn pwyntydd ychwanegol - oherwydd ein strwythur yn ddrwg yn y ffordd hon. Yn hytrach na mynd ar ac yn tynnu allan y coed deuaidd sydd 9 ar y gwraidd, sydd yn yr achos olaf y byddai gennym, rydym yn hytrach, ar y pwynt hwn, yn mynd i siarad ychydig am y term arall ein bod yn defnyddio wrth siarad am goed, a elwir yn uchder. 

Mae uchder coeden yw'r pellter o'r gwraidd i'r nod y rhan fwyaf o-bell, neu yn hytrach y nifer o hopys y byddai'n rhaid i chi eu gwneud er mwyn ddechrau o'r gwraidd ac yna yn y pen draw ar y nod y rhan fwyaf o-bell yn y goeden. Os ydym yn edrych ar rai o'r coed hyn yr ydym wedi tynnu i'r dde yma, gallwn weld bod os ydym yn cymryd y goeden yn y gornel chwith uchaf, ac rydym yn dechrau ar y 3, yna mae'n rhaid i ni wneud 1 hop i gyrraedd y 6, hop ail gyrraedd y 7, a hop trydydd gyrraedd y 9. Felly, mae'r uchder y goeden hon yw 3. Gallwn wneud yr un ymarfer ar gyfer y coed eraill a amlinellir â'r gwyrdd, a gwelwn fod uchder y rhain i gyd coed hefyd yn wir 3. Dyna rhan o'r hyn sy'n eu gwneud yn dirywio - bod eu taldra yn unig yw un yn llai na nifer y nodau yn y goeden gyfan. Os ydym yn edrych ar y goeden eraill sy'n amgylchynu gyda choch, ar y llaw arall, rydym yn gweld bod y nodau dail mwyaf-bell yw 6 a 9 - y dail sef y rheiny nodau nad oes ganddynt unrhyw blant. Felly, er mwyn cael oddi wrth y nod gwraidd naill ai i'r 6 neu 9, mae'n rhaid i ni wneud un hop i gyrraedd y 7 ac yna hop ail gyrraedd y 9, ac yn yr un modd, dim ond hop yr ail o'r 7 i gyrraedd y 6. Felly, uchder y goeden dros yma yn unig 2. Gallwch chi fynd yn ôl a gwneud hynny ar gyfer yr holl goed eraill a fuom yn trafod gan ddechrau gyda'r 7 a 6, a byddwch yn canfod bod y uchder yr holl o'r coed hynny hefyd yn 2. 

Y rheswm rydym wedi bod yn siarad am archebu coed deuaidd a pham eu bod yn oer oherwydd gallwch chwilio drwyddynt yn ffordd debyg iawn i chwilio dros amrywiaeth datrys. Dyma lle rydym yn sôn am gael yr adeg honno am-edrych gwell dros y rhestr syml sy'n gysylltiedig. Gyda rhestr cysylltiedig - os ydych am ddod o hyd i elfen benodol - rydych ar y gorau yn mynd i wneud rhyw fath o chwiliad llinol lle rydych yn dechrau ar ddechrau'r rhestr a hop un-wrth-un - un nod gan un nod - drwy'r rhestr gyfan nes i chi ddod o hyd i beth bynnag yr ydych yn chwilio am. Tra, os oes gennych chi goeden ddeuaidd sy'n cael ei storio yn y fformat 'n glws, gallwch chi mewn gwirionedd yn cael mwy o chwiliad deuaidd yn mynd ymlaen lle rydych yn rhannu a gorchfygu a chwilio drwy'r hanner priodol o'r goeden ym mhob cam. Gadewch i ni weld sut mae hynny'n gweithio. 

Os oes gennym - eto, yn mynd yn ôl at ein coed gwreiddiol - byddwn yn dechrau am 7, mae gennym 3 ar y chwith, 9 ar y dde, ac o dan y 3 gennym y 6. Os ydym am i chwilio am y rhif 6 yn y goeden hon, byddem yn dechrau yn y gwraidd. Byddem yn cymharu gwerth rydym yn chwilio am, dyweder 6, i'r gwerth storio yn y nod ein bod ar hyn o bryd yn edrych ar, 7, dod o hyd bod 6 yn wir llai na 7, ac felly byddem yn symud i'r chwith. Os yw gwerth o 6 wedi bod yn fwy na 7, byddem wedi symud yn hytrach ar y dde. Ers i ni yn gwybod hynny - oherwydd y strwythur ein coeden ddeuaidd archebu - pob un o'r gwerth sy'n llai na 7 yn mynd i gael eu storio ar y chwith 7, does dim angen i hyd yn oed yn trafferthu edrych drwy'r ochr dde y goeden. Ar ôl inni symud i'r chwith ac rydym yn awr yn y nod yn cynnwys 3, gallwn wneud y gymhariaeth un peth eto pan rydym yn cymharu y 3 a'r 6. Ac rydym yn dod o hyd, er bod 6 - y gwerth yr ydym yn chwilio amdano - yn fwy na 3, gallwn fynd i ochr dde y nod yn cynnwys 3. Does dim ochr chwith yma, felly gallem fod wedi anwybyddu hynny. Ond dim ond yn gwybod bod oherwydd ein bod yn edrych ar y goeden ei hun, a gallwn weld bod y goeden heb blant. 

Mae hefyd yn eithaf hawdd i chwilio am 6 yn y goeden hon os ydym yn ei wneud ein hunain fel bodau dynol, ond gadewch i ni ddilyn y broses hon yn fecanyddol fel cyfrifiadur a fyddai'n gwneud i ddeall yn iawn y algorithm. Ar y pwynt hwn, rydym yn awr yn edrych ar nod sy'n cynnwys 6, ac rydym yn chwilio am y gwerth 6, felly, yn wir, rydym wedi dod o hyd y nod priodol. Gwelsom y gwerth 6 yn ein coed, a gallwn atal ein chwiliad. Ar y pwynt hwn, yn dibynnu ar yr hyn sy'n mynd ymlaen, gallwn ddweud, ie, rydym wedi dod o hyd i'r gwerth 6, mae'n bodoli yn ein coeden. Neu, os ydym yn bwriadu gosod nod neu wneud rhywbeth, gallwn wneud hynny ar hyn o bryd. 

Gadewch i ni wneud lookups ychydig mwy dim ond i weld sut mae hyn yn gweithio. Gadewch i ni edrych ar yr hyn sy'n digwydd pe baem yn ceisio edrych ar y gwerth 10. Pe baem yn edrych ar y gwerth 10, byddem yn dechrau yn y gwraidd. Byddem yn gweld bod 10 yn fwy na 7, ac felly byddem yn symud i'r dde. Byddem wrth ein cyrraedd y 9 a chymharu 9 i 10 ac yn gweld bod 9 yn wir yn llai na 10. Felly eto, byddem yn ceisio symud i'r dde. Ond ar y pwynt hwn, byddem yn sylwi ein bod yn nod null. Does dim byd yno. Does dim byd lle dylai'r 10 fydd. Dyma lle y gallwn adrodd methu - nad oes yn wir rhif 10 yn y goeden. Ac yn olaf, gadewch i ni fynd drwy achos lle'r ydym yn ceisio edrych i fyny 1 yn y goeden. Mae hyn yn debyg i'r hyn sy'n digwydd os ydym yn edrych i fyny 10, ac eithrio yn hytrach na mynd i'r dde, rydyn ni'n mynd i fynd i'r chwith. Rydym yn dechrau ar y 7 ac yn gweld bod 1 yn llai na 7, felly rydym yn symud i'r chwith. Rydym yn cael y 3 a gweld bod 1 yn llai na 3, felly unwaith eto rydym yn ceisio symud i'r chwith. Ar y pwynt hwn mae gennym nod null, felly unwaith eto gallwn adrodd methiant. 

Os ydych am ddysgu mwy am goed deuaidd, mae criw cyfan o broblemau bach llawn hwyl y gallwch eu gwneud gyda nhw. Yr wyf yn awgrymu ymarfer tynnu allan o'r diagramau un wrth un ac yn dilyn drwy bob un o'r gwahanol gamau, oherwydd bydd hyn yn dod yn super-'n hylaw nid yn unig pan ydych yn gwneud y set encoding Huffman problem ond hefyd mewn cyrsiau yn y dyfodol - ond yn dysgu sut i dynnu allan y strwythurau data ac i feddwl am y problemau gyda beiro a phapur neu, yn yr achos hwn, iPad a bwyntil. 

Ar y pwynt hwn, fodd bynnag, rydym yn mynd i symud ymlaen i wneud rhywfaint o ymarfer codio ac mewn gwirionedd yn chwarae gyda coed hyn deuaidd a gweld. Rydw i'n mynd i newid yn ôl i fy chyfrifiadur. Ar gyfer y rhan o'r adran, yn hytrach na defnyddio CS50 Run neu CS50 Mannau, Rydw i'n mynd i ddefnyddio'r offer. 

Yn dilyn ynghyd â'r Set Problem fanyleb, Rwy'n gweld fy mod i'n fod i agor i fyny 'r offer, mynd i fy Dropbox folder, creu ffolder o'r enw Adran 7, ac yna yn creu ffeil o'r enw binary_tree.c. Yma rydym yn mynd. Rydw i wedi cael y cyfarpar sydd eisoes ar agor. Rydw i'n mynd dynnu i fyny derfynell. Rydw i'n mynd i fynd i'r ffolder Dropbox, yn gwneud cyfeiriadur o'r enw adran 7, a gweld ei fod yn hollol wag. Nawr rwy'n mynd i agor binary_tree.c. Iawn. Yma rydym yn mynd - ffeil wag. 

Gadewch i ni fynd yn ôl at y fanyleb. Mae'r fanyleb yn gofyn i greu diffiniad math newydd ar gyfer nod goeden ddeuol sy'n cynnwys gwerthoedd int - yn union fel y gwerthoedd yr ydym yn tynnu allan yn ein diagramau o'r blaen. Rydym yn mynd i ddefnyddio hyn boilerplate typedef ein bod ni wedi wneud yn iawn yma y dylech gydnabod o 5 Set Problemau - os ydych yn gwneud y ffordd tabl hash o conquering y rhaglen sillafu. Dylech hefyd gydnabod o adran yr wythnos diwethaf lle buom yn siarad am restrau cysylltiedig. Rydym wedi cael y typedef o nod strwythur, ac rydym wedi cael y nod strwythur yr enw hwn o nod strwythur ymlaen llaw fel y gallwn wedyn gyfeirio ato ers byddwn yn awyddus i gael awgrymiadau nod strwythur fel rhan o'n strwythur, ond rydym wedi wedyn yn amgylchynu hyn - neu yn hytrach, amgáu hyn - mewn typedef fel eu bod, yn ddiweddarach yn y cod, gallwn gyfeirio at y strwythur fel dim ond nod yn hytrach na nod strwythur. 

Mae hyn yn mynd i fod yn debyg iawn i'r diffiniad rhestr unigol-gysylltiedig a welsom yr wythnos diwethaf. I wneud hyn, gadewch i ni dim ond dechrau drwy ysgrifennu allan y boilerplate. Rydym yn gwybod bod yn rhaid inni gael gwerth cyfanrif, felly byddwn yn rhoi gwerth int, ac yna yn hytrach na gorfod dim ond un pwyntydd i'r elfen nesaf - fel y gwnaethom gyda unigol sy'n gysylltiedig â'r rhestrau - rydym yn mynd i gael awgrymiadau blant chwith ac i'r dde. Dyna 'n bert syml hefyd - plentyn nod strwythur * chwith; a strwythur nod * plentyn cywir;. Cool. Sy'n edrych fel dechrau 'n bert da. Gadewch i ni fynd yn ôl at y fanyleb. 

Nawr mae angen i ni ddatgan newidyn nod * byd-eang ar gyfer y gwraidd coeden. Rydym yn mynd i wneud hyn yn fyd-eang yn union fel rydym yn gwneud pwyntydd cyntaf yn ein rhestr gysylltiedig hefyd fyd-eang. Roedd hyn fel bod yn y swyddogaethau yr ydym yn ysgrifennu Nid oes raid i ni gadw basio o gwmpas y gwreiddiau - er y byddwn yn gweld, os ydych chi eisiau ysgrifennu swyddogaethau hyn recursively, efallai y byddai'n well i ddim hyd yn oed basio o gwmpas fel fyd-eang yn y lle cyntaf ac yn hytrach ymgychwyn yn lleol yn eich prif swyddogaeth. Ond, byddwn yn ei wneud yn fyd-eang i gychwyn. Unwaith eto, byddwn yn rhoi cwpl o fannau, ac yr wyf i'n mynd i ddatgan gwreiddyn * nod. Dim ond i wneud yn siŵr nad wyf yn gadael y uninitialized, dw i'n mynd i osod ei gyfartal i null. Yn awr, yn brif swyddogaeth - a byddwn yn ysgrifennu yn gyflym iawn iawn yma - int brif (int argc, Etholaeth golosg * argv []) - ac rydw i'n mynd i ddechrau datgan fy amrywiaeth argv fel Etholaeth yn union fel fy mod yn gwybod bod y dadleuon yn dadleuon yr wyf debygol dont 'angen ei addasu. Os ydw i eisiau eu haddasu mae'n debyg y dylwn fod yn gwneud copïau ohonynt. Byddwch yn gweld hyn yn llawer mewn cod. Mae'n iawn naill ffordd neu'r llall. Mae'n iawn i adael fel - hepgorer y Etholaeth os hoffech chi. Rwyf fel arfer yn ei roi mewn dim ond er mwyn i mi atgoffa fy hun  fy mod yn debygol dont 'angen i addasu y dadleuon hynny. 

Fel bob amser, yr wyf i'n mynd i gynnwys 0 ffurflen hon lein ar y end of main. Yma, byddaf yn ymgychwyn fy nod gwraidd. Fel mae'n sefyll ar hyn o bryd, mae gen i pwyntydd sydd wedi gosod i null, felly mae'n pwyntio at ddim byd. Er mwyn dechrau mewn gwirionedd yn adeiladu'r nod, Tro cyntaf i mi angen i ddyrannu cof ar ei gyfer. Rydw i'n mynd i wneud hynny drwy wneud cof ar y domen gan ddefnyddio malloc. Rydw i'n mynd i osod gwreiddiau cyfartal i'r canlyniad malloc, ac rydw i'n mynd i ddefnyddio'r gweithredwr sizeof i gyfrifo faint o nod. Y rheswm yr wyf yn defnyddio sizeof nod yn hytrach na, dyweder, gwneud rhywbeth fel hyn - malloc (4 + 4 +4) neu malloc 12 - oherwydd fy mod am fy cod i fod mor gydnaws ag y bo modd. Rwyf am fod yn gallu ei gymryd. Ffeil c, llunio ar y peiriant, ac yna llunio ar fy 64-bit Mac - neu ar bensaernïaeth hollol wahanol - ac yr wyf am i hyn oll yn gweithio yr un fath. 

Os ydw i'n gwneud rhagdybiaethau ynglŷn â faint o newidynnau - faint o int neu faint yn saeth - yna rwyf hefyd yn gwneud rhagdybiaethau am y mathau o saernïaeth y gall fy cod yn llwyddiannus lunio pan rhedeg. Bob amser yn defnyddio sizeof yn hytrach na llaw grynhoi y caeau strwythur. Y rheswm arall yw y gallai hefyd fod padin bod y casglwr yn rhoi i mewn i'r strwythur. Hyd yn oed dim ond grynhoi y caeau unigol yn rhywbeth yr ydych fel arfer am ei wneud, felly, dilëwch y llinell. Nawr, i 'n sylweddol ymgychwyn y nod gwraidd, Rydw i'n mynd i gael i dopio mewn gwerthoedd ar gyfer pob un o'i feysydd gwahanol. Er enghraifft, ar gyfer gwerth Rwy'n gwybod fy mod am i ymgychwyn i 7, ac am nawr rwy'n mynd i osod y plentyn chwith i fod yn null a'r plentyn hawl i fod yn null. Great! Rydym wedi gwneud y rhan honno o'r fanyleb. 

Mae'r fanyleb i lawr ar waelod y dudalen 3 yn gofyn i mi greu tair nodau - un yn cynnwys 3, un yn cynnwys 6, ac un gyda 9 - ac yna gwifren i fyny felly mae'n edrych yn union fel ein diagram coeden ein bod yn siarad amdano'n flaenorol. Gadewch i ni wneud hynny yn weddol gyflym yma. Byddwch yn gweld yn gyflym iawn fy mod i'n mynd i ddechrau ysgrifennu criw o god dyblyg. Rydw i'n mynd i greu * nod a rydw i'n mynd i alw tri. Rydw i'n mynd i osod fod yn gyfartal i malloc (sizeof (nod)). Rydw i'n mynd i osod tri-> werth = 3. Tri -> left_child = NULL, tair -> NULL = hawl _child, yn ogystal. Mae hynny'n edrych yn eithaf tebyg i ymgychwyn y gwraidd, a dyna'n union beth Rydw i'n mynd i gael i wneud os byddaf yn dechrau ymgychwyn 6 a 9 yn ogystal. 'N annhymerus' yn gwneud hynny yn gyflym iawn yma - yn wir, yr wyf i'n mynd i wneud copi bach a gludo, a gwneud yn siŵr fy mod i - iawn.  Yn awr, rydw i wedi got ei gopïo a gallaf fynd yn ei flaen ac yn gosod hwn cyfartal i 6. Gallwch weld bod hyn yn cymryd dro ac nid yw'n super-effeithlon. Mewn dim ond ychydig bach, byddwn yn ysgrifennu swyddogaeth a fydd yn gwneud hyn i ni. Rwyf am i gymryd lle'r hyn gyda 9, lle hynny, 6. 

Nawr rydym wedi cael ein holl nodau creu a'u ymgychwyn. Rydym wedi cael ein gwreiddiau a bennwyd yn hafal i 7, neu sy'n cynnwys y gwerth 7, ein nod sy'n cynnwys 3, ein nod sy'n cynnwys 6, ac mae ein nod sy'n cynnwys 9. Ar y pwynt hwn, y cyfan mae'n rhaid i ni ei wneud yw popeth wifren i fyny. Y rheswm pam yr ymgychwyn yr holl awgrymiadau i null yn unig fel fy mod yn gwneud yn siŵr bod Nid oes gennyf unrhyw awgrymiadau uninitialized yno trwy ddamwain. A hefyd ers hynny, ar y pwynt hwn, dim ond rhaid i mewn gwirionedd yn cysylltu'r nodau i'w gilydd - i'r rhai eu bod yn gysylltiedig mewn gwirionedd i - nid oes rhaid i mi fynd drwyddo ac i wneud yn siwr bod yr holl nulls yn yno yn y mannau priodol. 

Gan ddechrau ar y gwraidd, yr wyf yn gwybod bod plentyn y gwreiddyn yn chwith yw 3. Gwn fod plentyn y gwraidd hawl yw 9. Ar ôl hynny, yn unig blentyn eraill yr wyf wedi gadael i mi boeni am yw 3 y plentyn iawn, sydd 6. Ar y pwynt hwn, mae'r cyfan yn edrych yn eithaf da. Byddwn yn dileu rhai o'r llinellau. Nawr popeth yn edrych yn eithaf da. Gadewch i ni fynd yn ôl at ein manyleb a gweld yr hyn sydd gennym i'w wneud nesaf. 

Ar y pwynt hwn, mae'n rhaid i ni ysgrifennu swyddogaeth a elwir yn 'cynnwys' gyda prototeip o 'yn cynnwys bool (canolradd gwerth)'. Ac mae hyn yn cynnwys swyddogaeth yn mynd i ddychwelyd yn wir  os yw'r goeden yn tynnu sylw at amrywiol gan ein gwreiddiau byd-eang  yn cynnwys y gwerth trosglwyddo i mewn i'r swyddogaeth a ffug fel arall. Gadewch i ni fynd yn ei flaen a gwneud hynny. Mae hyn yn mynd i fod yn union fel y am-edrych a wnaethom â llaw ar y iPad dim ond ychydig bach yn ôl. Dewch i chwyddo yn ôl mewn ychydig ac yn sgrolio i fyny. Rydym yn mynd i roi hyn swyddogaeth dde uwchben ein prif swyddogaeth fel nad oes raid i ni wneud unrhyw fath o brototeipio. Felly, bool yn cynnwys (int gwerth). Dyna ni. Mae ein datganiad boilerplate. Dim ond i wneud yn siŵr y bydd hyn yn llunio, Rydw i'n mynd i fynd yn ei flaen a dim ond ei osod yn gyfartal i ddychwelyd ffug. Ar hyn o bryd swyddogaeth hon nid yn unig fydd yn gwneud unrhyw beth a bob amser yn adrodd bod Nid yw gwerth yr ydym yn chwilio amdano yw yn y goeden. 

Ar y pwynt hwn, mae'n debyg ei fod yn syniad da - ers i ni wedi ysgrifennu criw cyfan o god ac nid ydym wedi ceisio hyd yn oed ei brofi eto - i wneud yn siŵr bod y cyfan yn llunio. Mae yna un neu ddau o bethau y mae'n rhaid i ni ei wneud i wneud yn siŵr y bydd hyn yn crynhoi. Yn gyntaf, gweld a ydym wedi bod yn defnyddio unrhyw swyddogaethau mewn unrhyw llyfrgelloedd nad ydym wedi cynnwys eto. Mae'r swyddogaethau rydym wedi defnyddio hyd yn hyn yn malloc, ac yna rydym ni hefyd wedi bod yn defnyddio'r math hwn - y math hwn nonstandard a elwir yn 'bool' - sydd wedi'i gynnwys yn y ffeil pennawd bool safonol. Rydym yn bendant yn awyddus i gynnwys bool.h safonol ar gyfer y math bool, ac rydym hefyd yn awyddus i gynnwys lib.h # safonol ar gyfer y llyfrgelloedd safonol sy'n cynnwys malloc, ac yn rhydd, a hynny i gyd. Felly, chwyddo allan, rydyn ni'n mynd i roi'r gorau iddi. Gadewch i ni geisio gwneud yn siŵr bod hyn mewn gwirionedd oedd crynhoi. Rydym yn gweld ei fod yn ei wneud, felly rydym ar y trywydd iawn. 

Gadewch i ni agor binary_tree.c eto. Mae'n llunio. Gadewch i ni fynd i lawr ac yn gwneud yn siŵr ein bod yn ychwanegu rhai galwadau i'n Yn cynnwys swyddogaeth - dim ond er mwyn gwneud yn siŵr bod i gyd yn dda ac yn dda. Er enghraifft, pan fyddwn yn gwneud rhai lookups yn ein coeden yn gynharach, rydym yn ceisio edrych ar y 6 gwerthoedd, 10, ac 1, ac roeddem yn gwybod bod 6 oedd yn y goeden, 10 Nid oedd yn y goeden, ac nid 1 yn y goeden chwaith. Gadewch i ni ddefnyddio'r galwadau hynny sampl fel ffordd at chyfrif i maes ai peidio Yn cynnwys ein swyddogaeth yn gweithio. Er mwyn gwneud hynny, dw i'n mynd i ddefnyddio'r swyddogaeth printf, ac rydym yn mynd i argraffu'r canlyniad yr alwad i cynnwys. Dw i'n mynd i roi mewn llinyn "yn cynnwys (% d) = oherwydd  rydyn ni'n mynd i plwg yn y gwerth yr ydym yn mynd i chwilio am, a =% s \ n "a defnyddio hynny fel ein llinyn fformat. Rydym yn unig yn mynd i weld - yn llythrennol argraffwch ar y sgrin - hyn sy'n edrych fel galwad swyddogaeth. Nid yw hyn mewn gwirionedd yn yr alwad swyddogaeth.  Mae hyn yn unig yw llinyn a gynlluniwyd i edrych fel galwad swyddogaeth. 

Nawr, rydyn ni'n mynd i dopio i mewn gwerthoedd. Rydym yn mynd i geisio cynnwys ar 6, ac yna beth ydym yn mynd i'w wneud yma yw defnyddio'r gweithredwr teiran. Gadewch i ni weld - yn cynnwys 6 - felly, yn awr yr wyf wedi cynnwys 6 a os yn cynnwys 6 yn wir, y llinyn ein bod ni'n mynd i'w anfon at gymeriad fformat y% s yn mynd i fod y llinyn "gwir". Gadewch i ni sgroliwch dros ychydig. Fel arall, rydym yn awyddus i anfon y llinyn "ffug" os yn cynnwys 6 yn dychwelyd ffug. Mae hyn ychydig yn goofy-edrych, ond yr wyf yn ffigwr efallai y byddwn yn ogystal yn dangos hyn y mae'r gweithredwr teiran edrych fel gan nad ydym wedi ei weld am dro. Bydd hyn yn neis, ffordd hwylus at chyfrif i maes os yw ein swyddogaeth Yn cynnwys yn gweithio. Rydw i'n mynd i sgrolio yn ôl dros y chwith, ac rydw i'n mynd i gopïo a gludo y llinell hon ychydig o weithiau. Mae'n newid rhai o'r gwerthoedd hyn o gwmpas, felly mae hyn yn mynd i fod yn 1, ac mae hyn yn mynd i fod yn 10. 

Ar y pwynt hwn mae gennym swyddogaeth Yn cynnwys 'n glws. Rydym wedi cael rhai profion, a chawn weld os yw hyn yn holl waith. Ar y pwynt hwn rydym wedi ysgrifennu cod rhai mwy. Amser i roi'r gorau iddi allan a gwneud yn siwr fod popeth yn dal llunio. Quit allan, ac yn awr gad i ni geisio gwneud goeden ddeuol eto. Wel, mae'n edrych fel ein bod wedi cael camgymeriad, ac rydym wedi got hyn yn glir yn datgan y swyddogaeth llyfrgell printf. Mae'n edrych fel y mae angen i fynd i mewn ac # yn cynnwys standardio.h. A chyda hynny, dylai popeth lunio. Rydym i gyd yn dda. Nawr gadewch i ni geisio rhedeg goeden ddeuaidd a gweld beth sy'n digwydd. Dyma ni,. / Binary_tree, ac rydym yn gweld bod, wrth i ni ddisgwyl - oherwydd nad ydym wedi rhoi ar waith yn cynnwys eto, neu yn hytrach, rydym wedi rhoi dim ond yn gyfnewid ffug - gwelwn ei fod yn unig yn dychwelyd ffug ar gyfer pob un ohonynt, fel bod ei gyd yn gweithio ar gyfer y rhan fwyaf yn eithaf da. 

Gadewch i ni fynd yn ôl i mewn ac mewn gwirionedd yn gweithredu yn cynnwys ar y pwynt hwn. Rydw i'n mynd i sgrolio i lawr, chwyddo i mewn, ac - cofiwch, mae'r algorithm a ddefnyddiwyd gennym oedd ein bod yn dechrau ar y nod gwraidd ac yna ar bob nod yr ydym yn dod ar eu traws, rydym yn gwneud cymhariaeth, ac yn seiliedig ar y gymhariaeth rydym naill ai yn symud i'r plentyn chwith neu i'r plentyn iawn. Mae hyn yn mynd i edrych yn debyg iawn i'r cod deuaidd chwilio ein bod wedi ysgrifennu yn gynharach yn y tymor. Pan fyddwn yn dechrau i ffwrdd, rydym yn gwybod ein bod yn awyddus i ddal gafael ar y nod ar hyn o bryd ein bod yn edrych arno, ac y nod ar hyn o bryd yn mynd i gael ei ymgychwyn i'r nod gwraidd. Ac yn awr, rydym yn mynd i gadw i fynd drwy'r coed, a chofiwch fod ein cyflwr rhoi'r gorau -  pan fyddwn yn gweithio mewn gwirionedd drwy'r enghraifft trwy llaw - oedd pan rydym yn dod ar draws nod null, nid pan fyddwn yn edrych ar blentyn null, ond yn hytrach pan ydym mewn gwirionedd yn symud i nod yn y goeden a dod o hyd ein bod yn nod null. Rydym yn mynd i ailadrodd hyd nes nad cyf yn hafal i null. A beth ydym yn mynd i'w wneud? Rydym yn mynd i brofi os (cyf - gwerth ==> werth), yna rydym yn gwybod ein bod wedi dod o hyd mewn gwirionedd yn y nod yr ydym yn chwilio amdano. Felly yma, gallwn ddychwelyd yn wir. Fel arall, rydym am weld a yw'r gwerth yn llai na gwerth. Os werth y nod ar hyn o bryd yn llai na gwerth yr ydym yn chwilio amdano, rydym yn mynd i symud i'r dde. Felly, cyf = cyf -> right_child, ac fel arall, rydym yn mynd i symud i'r chwith. cyf = cyf -> left_child;. Pretty syml. 

Mae'n debyg y byddwch yn cydnabod y ddolen sy'n edrych yn debyg iawn i'r hyn gan chwiliad deuaidd yn gynharach yn y tymor, ac eithrio hynny, rydym yn delio â isel, canol, ac yn uchel. Yma, rydym yn unig rhaid i ni edrych ar werth ar hyn o bryd, felly mae'n braf a syml. Gadewch i ni wneud yn siwr y cod hwn yn gweithio. Yn gyntaf, gwnewch yn siŵr ei fod yn llunio. Edrych fel y mae'n ei wneud. Gadewch i ni geisio rhedeg. Ac yn wir, bydd yn argraffu gwybod popeth yr ydym yn ei ddisgwyl. Mae'n canfod 6 yn y goeden, nid yw'n dod o hyd i 10 oherwydd nid 10 sydd yn y goeden, ac nid yw'n darganfod 1 naill ai oherwydd 1 ddim hefyd yn y goeden. Pethau Cool. 

Iawn. Gadewch i ni fynd yn ôl at ein manyleb a gweld beth sydd nesaf. Yn awr, mae eisiau ychwanegu nodau rhai mwy i ein coeden. Mae am i ychwanegu 5, 2, ac 8, a gwneud yn siŵr bod ein cynnwys cod dal i weithio yn ôl y disgwyl. Gadewch i ni fynd yn gwneud hynny. Ar y pwynt hwn, yn hytrach na gwneud y copi a gludo blino eto, gadewch i ni ysgrifennu swyddogaeth i mewn gwirionedd yn creu nod. Os byddwn yn sgroliwch i lawr yr holl ffordd i brif, gwelwn ein bod wedi bod yn gwneud hyn cod yn debyg iawn drosodd a throsodd bob tro yr ydym am ei greu nod. 

Gadewch i ni ysgrifennu swyddogaeth a fydd mewn gwirionedd yn adeiladu nod i ni a'i dychwelyd. Rydw i'n mynd i alw yn build_node. Rydw i'n mynd i adeiladu nod gyda gwerth penodol. Chwyddo i mewn yma. Y peth cyntaf i mi i'n mynd i wneud mewn gwirionedd yn creu lle ar gyfer y nod ar y domen. Felly, nod * n = malloc (sizeof (nod)); n -> Gwerth = gwerth; ac wedyn yma, Im 'jyst yn mynd i ymgychwyn holl feysydd i fod gwerthoedd priodol. Ac ar y diwedd un, byddwn yn dychwelyd ein nod. Iawn. Un peth i'w nodi yw bod y swyddogaeth hon iawn yma yn mynd i ddychwelyd pwyntydd i'r cof sydd wedi bod yn domen-ddyrannu. Beth braf am hyn yw bod y nod yn awr - mae'n rhaid i ni ddatgan hynny ar y domen oherwydd os ydym datgan ei fod ar y simnai ni fyddem yn gallu gwneud hynny yn y swyddogaeth hon fel hyn. Byddai hynny'n cof yn mynd allan o gwmpas ac y byddai'n annilys os ydym yn ceisio cael mynediad iddo yn nes ymlaen. Gan ein bod yn datgan domen-ddyrannu cof, rydym yn mynd i gael i gymryd gofal o ryddhau yn ddiweddarach nid ar gyfer ein rhaglen i ollwng unrhyw cof. Rydym wedi bod yn punting ar hynny am bopeth arall yn y cod yn unig ar gyfer mwyn symlrwydd ar y pryd, ond os ydych chi erioed wedi ysgrifennu swyddogaeth sy'n edrych fel hyn pan fyddwch wedi cael - mae rhai yn galw ei fod yn malloc neu realloc y tu mewn - ydych am wneud yn siŵr eich bod yn rhoi rhyw fath o sylwadau yma sy'n dweud, hey, chi'n gwybod, yn dychwelyd yn nod domen-ddyrannwyd ymgychwyn gyda'r gwerth basio i mewn. Ac yna ydych am wneud yn siŵr eich bod yn rhoi mewn rhyw fath o nodyn sy'n dweud rhaid i'r galwr ryddhau'r cof dychwelyd. Drwy hynny, os bydd rhywun erioed yn mynd ac yn defnyddio swyddogaeth honno, maent yn gwybod bod beth bynnag maent yn ei gael yn ôl oddi wrth y swyddogaeth Bydd ar ryw adeg bydd angen i gael eu rhyddhau. 

Gan dybio bod popeth yn iawn ac yn dda yma, gallwn fynd i lawr i ein cod ac yn disodli pob un o'r rhain llinellau iawn yma gyda galwadau i'n swyddogaeth node adeiladu. Gadewch i ni wneud hynny yn gyflym iawn. Mae'r rhan un nad ydym yn mynd i gymryd lle yn y rhan hon i lawr yma ar y gwaelod lle yr ydym mewn gwirionedd gwifren i fyny 'r nodau i bwyntio at ei gilydd, oherwydd na allwn ei wneud yn ein swyddogaeth. Ond, gadewch i ni wneud gwraidd = build_node (7); nod * tri = build_node (3); nod * 6 = build_node (6); nod * 9 = build_node (9);. Ac yn awr, rydym hefyd yn awyddus i ychwanegu nodau ar gyfer - nod * 5 = build_node (5); nod * 8 = build_node (8); a beth oedd y nod arall? Gadewch i ni weld yma. Rydym eisiau i hefyd yn ychwanegu 2 - nod * 2 = build_node (2);. Iawn. Ar y pwynt hwn, rydym yn gwybod ein bod wedi cael y 7, y 3, 9, a 6 holl gwifredig i fyny yn briodol, ond beth am y 5, 8, a'r 2? Er mwyn cadw popeth yn y drefn briodol, gwyddom fod tair plentyn cywir yw 6. Felly, os ydym yn mynd i ychwanegu y 5, y 5 hefyd yn perthyn yn yr ochr dde y goeden y mae 3 yw'r gwraidd, hynny 5 yn perthyn fel y plentyn chwith 6. Gallwn wneud hyn drwy ddweud, chwech -> left_child = phump; ac yna yr 8 perthyn fel y plentyn chwith 9, fel naw -> left_child = wyth; ac yna 2 yw'r plentyn chwith o 3, fel y gallwn wneud hynny i fyny yma - di -> left_child = dau;. Os nad oeddech yn eithaf dilyn ynghyd â hynny, yr wyf yn awgrymu eich bod yn tynnu allan eich hun. 

Iawn. Gadewch i ni achub y. Gadewch i ni fynd allan a gwneud yn siŵr ei llunio, ac yna gallwn ychwanegu yn ein galwadau cynnwys. Edrych fel popeth yn dal llunio. Gadewch i ni fynd i mewn ac ychwanegwch mewn rhai yn cynnwys galwadau. Unwaith eto, yr wyf i'n mynd i wneud ychydig bach o gopi a gludo. Nawr gadewch i ni chwilio am 5, 8, a 2. Iawn. Gadewch i ni wneud yn siwr bod hyn i gyd yn edrych yn dda o hyd. Great! Arbed a rhoi'r gorau iddi. Nawr gadewch i ni wneud, crynhoi, ac yn awr gadewch i ni redeg. O'r canlyniadau, mae'n edrych fel mae popeth yn gweithio jyst 'n glws ac yn iach. Great! Felly, nawr rydym wedi cael ein swyddogaeth Yn cynnwys ysgrifenedig. Gadewch i ni symud ymlaen a dechrau gweithio ar sut i osod nodau i mewn i'r goeden ers hynny, gan ein bod yn gwneud hynny ar hyn o bryd, nid yw pethau yn iawn 'n bert. 

Os awn yn ôl at y fanyleb, mae'n gofyn i ni ysgrifennu swyddogaeth o'r enw mewnosodwch - unwaith eto, dychwelyd bool O ran a fyddai modd i ni mewn gwirionedd yn gosod y nod i mewn i'r goeden - ac yna y gwerth i fewnosod y goeden wedi ei bennu fel y ddadl yn unig at ein swyddogaeth mewnosodwch. Byddwn yn dychwelyd yn wir pe gallem yn wir mewnosoder y gwerth nod yn cynnwys i mewn i'r goeden, sy'n golygu ein bod ni, un, roedd digon o gof, ac yna dau, na nod oedd eisoes yn bodoli yn y goeden ers hynny - cofiwch, nid ydym yn mynd i feddu ar werthoedd dyblyg yn y goeden, dim ond i wneud pethau syml. Iawn. Back i'r cod. Agor i fyny. Zoom mewn ychydig, yna sgroliwch i lawr. Gadewch i ni roi swyddogaeth nodwch dde uwchben y cynnwys. Unwaith eto, mae'n mynd i gael ei alw rhowch bool (int gwerth). Rhowch ofod ychydig yn fwy, ac yna, fel diofyn, gadewch i ni roi yn gyfnewid ffug ar y diwedd un. Nawr i lawr ar y gwaelod, gadewch i ni fynd yn ei flaen ac yn hytrach na llaw adeiladu'r nodau yn y brif ein hunain a gwifrau nhw i fyny i bwyntio at ei gilydd fel yr ydym yn ei wneud, byddwn yn dibynnu ar ein swyddogaeth nodwch i wneud hynny. Ni fyddwn yn dibynnu ar ein swyddogaeth nodwch i adeiladu y goeden gyfan o'r dechrau eto, ond yn hytrach byddwn yn cael gwared ar y llinellau - we'll sylwadau ar y llinellau hyn - sy'n adeiladu y 5 nodau, 8, a 2. Ac yn lle hynny, byddwn yn ychwanegu galwadau i'n swyddogaeth rhowch i wneud yn siŵr bod gweithio mewn gwirionedd. Yma rydym yn mynd. 

Nawr rydym wedi gwneud sylwadau ar y llinellau hyn. Dim ond 7, 3, 9, a 6 yn ein coeden ar y pwynt hwn. Er mwyn sicrhau bod hyn i gyd yn gweithio, gallwn ni chwyddo allan, yn gwneud ein coeden ddeuaidd, rhedeg, a gallwn weld bod cynnwys yn awr yn dweud wrthym ein bod yn hollol gywir - 5, 8, a 2 nad ydynt bellach yn y goeden. Ewch yn ôl i mewn i'r cod, a sut rydym yn mynd i fewnosod? Cofiwch yr hyn a wnaethom pan oeddem yn mewn gwirionedd yn gosod 5, 8, a 2 yn flaenorol. Rydym yn chwarae y gêm Plinko lle rydym yn dechrau yn y gwraidd, aeth i lawr yr un goeden gan un gan un hyd nes i ni ganfod y bwlch priodol, ac yna rydym yn wifrio yn y nod yn y fan a'r lle priodol. Rydym yn mynd i wneud yr un peth. Mae hyn yn y bôn fel ysgrifennu y cod a ddefnyddir yn y swyddogaeth yn cynnwys i ddod o hyd i'r fan lle y dylai'r nod fod, ac yna rydym yn jyst yn mynd i fewnosod y nod iawn yno. Gadewch i ni ddechrau gwneud hynny. 

Felly mae gennym nod * cyf = gwraidd; rydym yn jyst yn mynd i ddilyn y cod cynnwys nes i ni ddod o hyd nad yw'n hollol gweithio i ni. Rydym yn mynd i fynd drwy'r coed, er nad yw'r elfen bresennol yn null, ac os ydym yn dod o hyd i werth y cyf yn cyfateb i werth ein bod yn ceisio i fewnosod - yn dda, mae hyn yn un o'r achosion lle na allem mewn gwirionedd mewnosoder y nod i mewn i'r goeden oherwydd mae hyn yn golygu bod gennym werth dyblyg. Yma rydym yn wir yn mynd i ddychwelyd ffug. Arall yn awr, os cyf gwerth yn llai na gwerth, yn awr rydym yn gwybod ein bod yn symud i'r dde  oherwydd bod y gwerth yn perthyn yn hanner dde yr goeden cyf. Fel arall, rydym yn mynd i symud i'r chwith. Dyna y bôn ein Yn cynnwys gweithredu'n iawn yno. 

Ar y pwynt hwn, unwaith y byddwn wedi cwblhau hyn dolen tra, ein pwyntydd cyf yn mynd i fod yn pwyntio i null os nad yw'r swyddogaeth wedi dychwelyd yn barod. Rydym ni'n ac felly'n cael cyf yn y fan lle rydym am i fewnosod y nod newydd. Hyn sydd ar ôl i'w wneud yw mewn gwirionedd yn adeiladu'r nod newydd, y gallwn ei wneud yn eithaf hawdd. Gallwn ddefnyddio ein super-'n hylaw swyddogaeth nod adeiladu, ac yn rhywbeth nad ydym yn ei wneud yn gynharach - rydym yn unig fath o gymryd yn ganiataol ond erbyn hyn byddwn yn gwneud yn unig i wneud yn siŵr - byddwn yn profi i wneud yn siŵr bod y gwerth ddychwelwyd gan nod newydd oedd mewn gwirionedd yn Nid null, oherwydd nid ydym am i ddechrau fanteisio ar y cof os yw'n null. Gallwn brofi i wneud yn siŵr nad yw nod newydd yn hafal i null. Neu yn hytrach, gallwn ond yn gweld os yw'n mewn gwirionedd yn null, ac os yw'n null, yna gallwn fynd yn ôl ffug yn gynnar. 

Ar y pwynt hwn, mae'n rhaid i ni gwifren nod newydd yn ei fan a'r lle priodol yn y goeden. Os ydym yn edrych yn ôl ar brif a lle ein bod mewn gwirionedd gwifrau mewn gwerthoedd o'r blaen, rydym yn gweld bod y ffordd yr ydym yn ei wneud pan fyddwn yn awyddus i roi 3 yn y goeden Roedd rydym yn gweld y plentyn chwith y gwraidd. Pan fyddwn yn rhoi 9 yn y goeden, roedd rhaid i ni gael mynediad i'r plentyn iawn y gwreiddyn. Bu'n rhaid i ni gael pwyntydd i'r rhiant er mwyn rhoi gwerth newydd i mewn i'r goeden. Sgrolio yn ôl i fyny i fewnosod, nid yw hynny'n mynd i weithio yma yn eithaf oherwydd nad oes gennym pwyntydd rhiant. Yr hyn yr ydym am fod yn gallu ei wneud yw, ar y pwynt hwn, gwirio gwerth y rhiant a gweld - wel, diar, os werth y rhiant yn llai na'r gwerth cyfredol, yna dylai plentyn y rhiant hawl fydd y nod newydd; fel arall, dylai'r plentyn y rhiant chwith fod y nod newydd. Ond, nid ydym yn cael y pwyntydd rhiant yn eithaf eto. 

Er mwyn ei gael, rydym yn mewn gwirionedd yn mynd i gael ei olrhain wrth i ni fynd drwy'r coed a dod o hyd y fan a'r lle bo'n briodol yn ein dolen uchod. Gallwn wneud hynny drwy sgrolio yn ôl i fyny i ben ein swyddogaeth nodwch ac olrhain newidyn arall pwyntydd enw rhiant. Rydym yn mynd i osod fod yn gyfartal i null i ddechrau, ac yna bob tro y byddwn yn mynd drwy'r coed, ydym yn mynd i osod y pwyntydd rhiant i gyfateb y pwyntydd ar hyn o bryd. Gosod rhiant cyfartal i cyf. Fel hyn, bob tro y byddwn yn mynd drwy, rydym yn mynd i sicrhau fod y pwyntydd ar hyn o bryd yn cael cynyddran y pwyntydd rhiant yn dilyn hynny - dim ond un lefel yn uwch na'r pwyntydd ar hyn o bryd yn y goeden. Bod yr holl edrych yn eithaf da. 

Rwy'n credu yr un peth y byddwn yn dymuno addasu yw hyn yn adeiladu null nod dychwelyd. Er mwyn cael adeiladu nod i mewn gwirionedd yn llwyddiannus dychwelyd null, bydd rhaid i ni addasu cod hwnnw, oherwydd yma nad yw erioed, rydym yn profi i wneud yn siŵr bod malloc dychwelyd pwyntydd dilys. Felly, os yw (n = NULL!), Yna - os malloc dychwelyd pwyntydd dilys, yna byddwn yn ei ymgychwyn; fel arall, byddwn yn unig yn dychwelyd ac a fydd yn y pen draw dychwelyd null i ni. Nawr pawb yn edrych yn eithaf da. Gadewch i ni wneud yn siŵr bod hyn mewn gwirionedd yn llunio. Gwnewch goeden ddeuaidd, a oh, rydym wedi cael rhai pethau yn digwydd yma. 

Rydym wedi cael datganiad ymhlyg o swyddogaeth adeiladu nod. Unwaith eto, gyda'r rhain yn crynoadyddion, rydym yn mynd i ddechrau ar y brig. Beth sy'n rhaid hynny'n ei olygu yw fy mod yn galw adeiladu nod cyn i mi wedi datgan mewn gwirionedd. Gadewch i ni fynd yn ôl at y cod yn gyflym iawn. Sgroliwch i lawr, ac yn sicr ddigon, fy swyddogaeth mewnosodiad wedi'i ddatgan uwchben y swyddogaeth nod adeiladu, ond rwy'n ceisio defnyddio adeiladu nod y tu mewn mewnosoder. Rydw i'n mynd i fynd i mewn a chopi - ac yna gludwch y ffordd node adeiladu swyddogaeth yma ar y brig. Y ffordd honno, gobeithio a fydd yn gweithio. Gadewch i ni rhoi'r cynnig arall arni. Nawr mae'n gyd llunio. Mae popeth yn dda. 

Ond ar hyn o bryd, nid ydym wedi galw mewn gwirionedd ein swyddogaeth rhowch. Rydym yn unig yn gwybod ei fod yn llunio, felly gadewch i ni fynd i mewn ac yn rhoi rhai galwadau i mewn Gadewch i ni wneud hynny yn ein prif swyddogaeth. Yma, gwnaethom sylwadau ar 5, 8, a 2, ac wedyn nid ydym yn gwifren i fyny i lawr yma. Gadewch i ni wneud rhai galwadau i fewnosod, a gadewch i ni hefyd yn defnyddio yr un math o bethau yr ydym yn eu defnyddio pan fyddwn yn gwneud y galwadau printf i wneud yn siŵr bod popeth yn cael mewnosod yn gywir. Rydw i'n mynd i gopïo a gludo, ac yn hytrach na yn cynnwys ydym yn mynd i wneud mewnosod. Ac yn hytrach na 6, 10, ac 1, rydym yn mynd i ddefnyddio 5, 8, a 2. Dylai hyn, gobeithio, rhowch 5, 8, a 2 i mewn i'r goeden. Llunio. Mae popeth yn dda. Nawr byddwn mewn gwirionedd yn rhedeg ein rhaglen. 

Popeth dychwelyd ffug. Felly, nid yw 5, 8, a 2 yn mynd, ac mae'n edrych fel nad oedd Yn cynnwys dod o hyd iddynt chwaith. Beth sy'n digwydd? Gadewch i ni chwyddo allan. Y broblem gyntaf oedd hwnnw mewnosodwch yn ymddangos i ddychwelyd ffug, ac mae'n edrych fel hynny oherwydd i ni adael yn ein galwad yn ôl ffug, byth, ac rydym yn dychwelyd wir mewn gwirionedd. Gallwn drefnu hynny. Yr ail broblem yw, yn awr hyd yn oed os ydym yn ei wneud - arbed hyn, rhoi'r gorau i hyn, rhedeg wneud eto, wedi ei lunio, ac yna ei redeg - rydym yn gweld bod rhywbeth arall wedi digwydd yma. Mae'r 5, 8, a 2 byth yn cael eu canfod o hyd yn y goeden. Felly, beth sy'n mynd ymlaen? 

Gadewch i ni edrych ar hyn yn y cod. Gadewch i ni weld os allwn chyfrif hyn. Rydym yn dechrau gyda'r rhiant nad yw'n null. Rydym yn gosod y pwyntydd ar hyn o bryd cyfartal i'r pwyntydd gwraidd, ac rydym yn mynd i weithio ein ffordd i lawr drwy'r coed. Os nad yw'r nod ar hyn o bryd yn null, yna rydym yn gwybod ein bod yn gallu symud i lawr ychydig. Rydym yn gosod ein pwyntydd rhiant i fod yn gyfartal i'r pwyntydd ar hyn o bryd, edrych ar y gwerth - os yw'r gwerthoedd yr un fath ni ddychwelyd ffug. Os yw'r gwerthoedd yn llai ydym yn symud i'r dde; fel arall, rydym yn symud i'r chwith. Yna, rydym yn adeiladu nod. 'N annhymerus' chwyddo i mewn ychydig bach. Ac yma, rydyn ni'n mynd i geisio gwifren i fyny 'r gwerthoedd i fod yr un fath. Beth sy'n digwydd? Gawn ni weld os gall o bosibl Valgrind yn rhoi i ni awgrym. 

Rwy'n hoffi defnyddio Valgrind dim ond oherwydd Valgrind yn gyflym iawn yn rhedeg ac yn dweud wrthych os oes unrhyw gamgymeriadau cof. Pan rydym yn rhedeg Valgrind ar y cod, fel y gallwch weld hit here--Valgrind./binary_tree--and iawn fynd i mewn. Byddwch yn gweld nad oedd gennym unrhyw wall cof, felly mae'n edrych fel popeth yn iawn hyd yn hyn. Mae gennym rai gollwng cof, yr ydym yn gwybod, oherwydd nid ydym yn digwydd i ryddhau unrhyw un o'n nodau. Gadewch i ni geisio rhedeg GDB i weld beth sy'n digwydd mewn gwirionedd. Byddwn yn gwneud gdb. / Binary_tree. Mae'n luchio i fyny jyst ddirwya. Gadewch i ni osod pwynt torri ar mewnosodiad. Gadewch i ni redeg. Mae'n edrych yn debyg byth byddem ni'n ei alw mewn gwirionedd mewnosodiad. Mae'n edrych fel y broblem yn unig oedd bod pan fyddaf yn newid i lawr yma yn y prif - pob un o'r galwadau hyn printf gan cynnwys - Dwi byth yn newid mewn gwirionedd rhain i alw mewnosodiad. Nawr gadewch i ni roi cynnig arni. Gadewch i ni lunio. Mae pob edrych yn dda yno. Nawr gadewch i ni geisio rhedeg, gweld beth sy'n digwydd. Iawn! Mae popeth yn edrych yn eithaf da yno. 

Y peth olaf i feddwl amdano yw, a oes unrhyw achosion ymyl i daflen yma? Ac mae'n troi allan bod, yn dda, yr un achos ymyl sydd bob amser yn ddiddorol i feddwl am yw, beth fydd yn digwydd os bydd eich coeden yn wag ac rydych yn galw hyn yn swyddogaeth nodwch? A fydd yn gweithio? Wel, gadewch i ni roi cynnig arni. - Binary_tree c. - Mae'r ffordd yr ydym yn mynd i brofi hyn, rydym yn mynd i fynd i lawr at ein prif swyddogaeth, ac yn hytrach na gwifrau hyn nodau i fyny fel hyn, ni jyst yn mynd i wneud sylwadau ar y peth cyfan, ac yn hytrach na gwifrau i fyny 'r nodau ein hunain, gallwn mewn gwirionedd yn unig yn mynd ymlaen a dileu hyn i gyd. Rydym yn mynd i wneud popeth y mae galwad i fewnosod. Felly, gadewch i ni wneud - yn hytrach na 5, 8, a 2, rydym yn mynd i fewnosod 7, 3, a 9. Ac yna byddwn hefyd eisiau i fewnosod 6 ynghyd. Achub. Roi'r gorau iddi. Gwnewch goeden ddeuaidd. Mae i gyd yn llunio. Gall Rydym yn unig ei redeg fel y mae a gweld beth sy'n digwydd, ond mae hefyd yn mynd i fod yn wirioneddol bwysig i wneud yn siŵr bod Nid oes gennym unrhyw wallau cof, gan fod hyn yn un o'n hachosion ymyl ein bod yn gwybod am. 

Gadewch i ni wneud yn siwr ei fod yn gweithio'n dda o dan Valgrind, y byddwn yn ei wneud at jyst yn rhedeg Valgrind. / binary_tree. Mae'n edrych fel rydym yn wir yn cael un camgymeriad o un cyd-destun - gennym y wall. Beth ddigwyddodd? Valgrind mewn gwirionedd yn dweud wrthym lle y mae. Chwyddo allan ychydig. Mae'n edrych fel ei fod yn digwydd yn ein swyddogaeth nodwch, lle mae gennym ddarllen annilys o faint 4 yng mewnosoder, llinell 60. Gadewch i ni fynd yn ôl a gweld beth sy'n mynd ymlaen yma. Chwyddo allan 'n sylweddol gyflym. Rwyf am wneud yn siŵr nad yw'n mynd at ymyl y sgrîn er mwyn i ni weld popeth. Tynnwch hynny mewn ychydig bach. Iawn. Sgroliwch i lawr, ac mae'r broblem yn iawn yma. Beth fydd yn digwydd os ydym yn mynd i lawr ac mae ein nod ar hyn o bryd eisoes yn null, ein nod rhiant yn null, felly os ydym yn edrych i fyny ar y brig, dde yma - byth os yw hyn yn dolen tra mewn gwirionedd yn gweithredu oherwydd bod ein gwerth cyfredol yn null - ein gwreiddiau yn null felly cyf yn null - byth yna mae ein rhiant yn cael ei osod i ymg neu i werth dilys, felly, bydd rhiant hefyd yn null. Mae angen i ni gofio i wirio ar gyfer y erbyn i ni fynd i lawr yma, ac rydym yn dechrau defnyddio gwerth y rhiant. Felly, beth sy'n digwydd? Wel, os yw'r rhiant yn null - os (rhiant == NULL) - yna rydym yn gwybod bod Ni ddylai unrhyw beth yn y goeden. Mae'n rhaid i ni fod yn ceisio ei fewnosod yn y gwraidd. Gallwn wneud hynny drwy osod dim ond y gwreiddyn sy'n hafal i'r nod newydd. Yna, ar y pwynt hwn, nid ydym mewn gwirionedd eisiau mynd drwy'r pethau eraill. Yn hytrach, i'r dde yma, y ​​gallwn ei wneud naill ai arall-os-arall, neu gallem gyfuno popeth i fyny yma mewn arall, ond yma byddwn yn unig yn defnyddio arall ac yn ei wneud y ffordd honno. Nawr, rydym yn mynd i brofi i wneud yn siŵr nad yw ein rhiant yn null cyn hynny mewn gwirionedd yn ceisio mynediad i'w feysydd. Bydd hyn yn ein helpu i osgoi y wall. Felly, rydym yn rhoi'r gorau iddi, chwyddo allan, lunio, rhedeg. 

Dim gwallau, ond mae gennym griw o ollyngiadau cof oherwydd nad oeddem yn rhyddhau unrhyw un o'n nodau. Ond, os ydym yn mynd i fyny yma ac rydym yn edrych ar ein allbrint, rydym yn gweld bod, yn dda, yn edrych fel pob un o'n mewnosod yn dychwelyd yn wir, sydd yn dda. Mae'r mewnosod i gyd yn wir, ac yna y galwadau Yn cynnwys priodol hefyd yn wir. 

Da swydd! Mae'n edrych fel rydym wedi ysgrifennu yn llwyddiannus mewnosodiad. Dyna'r cyfan sydd gennym ar gyfer yr wythnos hon Set Problem Fanyleb. Un her hwyl i feddwl amdano yw sut y byddech mewn gwirionedd yn mynd i mewn ac yn rhydd pob un o'r nodau yn y goeden. Gallwn wneud hynny mewn nifer o ffyrdd gwahanol, ond byddaf yn gadael y bydd hyd i chi i arbrofi, ac fel her hwyl, ceisio gwneud yn siŵr y gallwch wneud yn siŵr bod yr adroddiad hwn Valgrind yn dychwelyd unrhyw wallau a dim gollyngiadau. 

Pob lwc ar yr wythnos hon problem Huffman set codio, ac fe welwn ni chi wythnos nesaf! [CS50.TV]