[Powered by Google Translate] [Adran 7: Mwy cyfforddus] [Rob Bowden] [Harvard University] [Mae hyn yn CS50] [CS50.TV] Mae pob hawl. Felly, fel y dywedais yn fy e-bost, mae hyn yn mynd i fod yn rhan deuaidd-tree-ddwys. Ond nid oes yw bod llawer o gwestiynau. Felly, rydym yn mynd i geisio tynnu allan bob cwestiwn ac yn mynd i fanylder poenus o'r holl ffyrdd gorau o wneud pethau. Felly, i'r dde ar y dechrau, rydym yn mynd trwy luniadau sampl o goed deuaidd a stwff. Felly yma, "Cofiwch fod coeden ddeuaidd wedi nodau tebyg i'r rhai o restr cysylltiedig, ac eithrio yn lle un pwyntydd mae dau: un ar gyfer 'plentyn' y chwith ac un ar gyfer yr hawl 'plentyn'. " Felly goeden ddeuaidd yn union fel rhestr cysylltiedig, heblaw am y strwythur yn mynd i gael dau awgrymiadau. Mae coed trinary, sydd yn mynd i gael tri awgrymiadau, mae yna N-ary coed, a dim ond yn cael pwyntydd generig eich bod yn rhaid i malloc i fod yn ddigon mawr i gael awgrymiadau ddigon i holl blant y bo modd. Felly goeden ddeuaidd unig fydd yn digwydd i gael nifer cyson o ddau. Os hoffech, gallwch roi rhestr cysylltiedig fel coeden unary, ond nid wyf yn meddwl fod neb yn ei alw hynny. "Tynnwch ddiagram flychau-a-saethau o nod goeden ddeuol cynnwys Nate rhif hoff, 7, lle mae pob plentyn yn pwyntydd nwl. " Modd Felly iPad. 

Mae'n mynd i fod yn eithaf syml. Rydym yn unig yn mynd i gael nod, 'n annhymerus' tynnu fel sgwâr. A byddaf yn tynnu y gwerthoedd yma. Felly, bydd y gwerth yn mynd i mewn yma, ac yna i lawr yma byddwn yn cael y pwyntydd chwith ar y chwith a'r dde pwyntydd ar y dde. Ac mae'n iawn felly confensiwn i alw yn chwith a dde, enwau'r pwyntydd. Mae'r ddau o'r rhain yn mynd i fod yn null. Yn unig fydd honno null, ac y bydd dim ond yn null. Iawn. Felly cefn i yma. "Gyda rhestr cysylltiedig, dim ond bu'n rhaid i storio pwyntydd at y nod cyntaf yn y rhestr er mwyn cofio y rhestr gyfan sy'n gysylltiedig, neu restr gyfan. Yn yr un modd, gyda choed, dim ond rhaid i chi storio pwyntydd i un nod er mwyn cofio y goeden gyfan. Mae'r nod yn Calle y 'wraidd' y goeden. Adeiladu ar eich diagram o'r cyfnod cyn neu lunio un newydd fel bod gennych ddarlun flychau-a-saethau ar goeden ddeuaidd gyda gwerth 7, yna 3 yn y chwith, yna 9 ar y dde, ac yna 6 ar y dde o'r 3. " Gawn ni weld os gallaf gofio hynny i gyd yn fy mhen. Felly, mae hyn yn mynd i fod yn ein gwreiddiau i fyny yma. Byddwn yn cael rhywfaint o pwyntydd yn rhywle, rhywbeth y byddwn yn galw gwraidd, ac mae'n pwyntio at y boi. Nawr i wneud nod newydd, yr hyn sydd gennym, y 3 ar y chwith? Felly, nod newydd gyda 3, ac mae'n dechrau pwyntiau null. 'N annhymerus' jyst yn rhoi N. Nawr rydym am i wneud i hynny fynd i'r chwith o 7. Felly, rydym yn newid y pwyntydd yn hyn bwyntio at y boi. Ac rydym yn gwneud yr un peth. Rydym eisiau 9 dros yma sy'n dechrau yn unig yn dweud null. Rydym yn mynd i newid y pwyntydd, pwynt i 9, ac yn awr yr ydym am roi 6 i dde o 3. Felly, mae'n mynd i - wneud 6. A bydd y dyn pwyntio yno. Iawn. Felly dyna i gyd mae'n gofyn i ni ei wneud. 

Nawr gadewch i ni fynd dros rai termau. Rydym eisoes yn siarad am sut y mae gwraidd y goeden yn y nod uchaf y rhan fwyaf yn y goeden. Mae'r un yn cynnwys 7. Mae'r nodau ar waelod y goeden yn cael eu galw y dail. Unrhyw nod a dim ond wedi null fel ei phlant yn deilen. Felly mae'n bosibl, os bydd ein coeden ddeuaidd yn unig yw nod sengl, bod coeden yn deilen, a dyna ni. "Mae'r 'uchder' y goeden yn y nifer o hopys rhaid i chi wneud ei gael o'r brig i'r deilen. " Byddwn yn mynd i mewn, mewn eiliad, y gwahaniaeth rhwng y coed deuaidd cytbwys ac anghytbwys, ond ar hyn o bryd, mae'r uchder cyffredinol y goeden Byddwn yn ei ddweud yw 3, er os ydych yn cyfrif y nifer o hopys rhaid i chi wneud er mwyn cael i 9, yna mae'n mewn gwirionedd dim ond uchder o 2. Ar hyn o bryd mae hyn yn goeden ddeuaidd anghytbwys, ond byddwn yn siarad am cytbwys pan mae'n mynd i fod yn berthnasol. Felly nawr gallwn ni siarad am nodau mewn coeden o ran perthynas i'r nodau eraill yn y goeden. Felly, nawr rydym wedi rhieni, plant, brodyr a chwiorydd, hynafiaid, a disgynyddion. Maent yn synnwyr cyffredin 'n bert, yr hyn y maent yn ei olygu. Os byddwn yn gofyn - mae'n rhieni. Felly beth yw rhiant o 3? [Myfyrwyr] 7. >> Yeah. Mae'r rhiant yn unig yn mynd i fod pa bwyntiau i chi. Yna, beth yw'r plant o 7? [Mae myfyrwyr yn] 3 a 9. >> Yeah. Noder bod "plant" yn llythrennol yn golygu plant, felly ni fyddent 6 yn gymwys, am ei fod yn debyg i ŵyr neu wyres. Ond yna, os ydym yn mynd ddisgynyddion, felly beth yn ddisgynyddion o 7? [Mae myfyrwyr yn] 3, 6 a 9. >> Yeah. Mae disgynyddion y nod gwraidd yn mynd i fod popeth yn y goeden, ac eithrio efallai y nod gwraidd ei hun, os nad ydych am i ystyried y ddisgynnydd. Ac yn olaf, hynafiaid, felly ei fod yn y cyfeiriad arall. Felly beth yw'r hynafiaid o 6? [Mae myfyrwyr yn] 3 a 7. >> Yeah. 9 Nid yn cael ei gynnwys. Dim ond y cefn llinach uniongyrchol at wraidd yn mynd i fod eich hynafiaid. 

"Rydym yn dweud bod coeden ddeuaidd ei 'archebu' os ar gyfer pob nod yn y goeden, ei holl ddisgynyddion ar y chwith werthoedd llai a phob un o'r rhai ar y dde yn cael gwerthoedd uwch. Er enghraifft, y goeden uchod yn cael ei archebu, ond nid yw'r trefniant ond yn bosibl archebu. " Cyn i ni gyrraedd y sefyllfa honno, goeden ddeuaidd gorchymyn ei adnabod hefyd fel coeden chwiliad deuaidd. Yma rydym yn digwydd bod yn galw ei goeden ddeuaidd archebu, ond dydw i erioed wedi clywed ei alw goeden ddeuaidd archebwyd cyn, ac ar gwis ydym yn llawer mwy tebygol o roi coeden chwiliad deuaidd. Maent yn un ac yr un fath, ac mae'n bwysig eich bod yn cydnabod y gwahaniaeth rhwng y goeden ddeuaidd coed a chwiliad deuaidd. Mae coeden ddeuaidd yn unig yw coeden sy'n pwyntio at ddau beth. Mae pob nod yn cyfeirio at ddau beth. Nid oes rhesymeg am y gwerthoedd y mae'n cyfeirio at. Felly hoffi dros yma, gan ei fod yn goeden chwiliad deuaidd, rydym yn gwybod os ydym yn mynd i'r chwith o 7, yna mae'r holl werthoedd y gallwn o bosibl cyrraedd drwy fynd i'r chwith o 7 fod yn llai na 7. Sylwch fod yr holl werth sy'n llai na 7 yn 3 a 6. Mae'r rheini i gyd i'r chwith o 7. Os ydym yn mynd i'r dde o'r 7, rhaid i bopeth fod yn fwy na 7, hynny 9 ar y dde o 7, felly rydym yn dda. Nid yw hyn yn wir am goeden ddeuaidd, am goeden ddeuaidd rheolaidd y gallwn dim ond wedi 3 ar y brig, 7 ar y chwith, 9 i'r chwith o 7; does dim archebu o werthoedd o gwbl. Yn awr, ni fyddwn mewn gwirionedd yn gwneud hyn oherwydd ei fod yn ddiflas ac yn ddiangen, ond "ceisio tynnu coed archebu cymaint ag y gallwch chi feddwl am ddefnyddio y 7 rhifau, 3, 9, a 6. Faint o drefniadau gwahanol sydd ar gael? Beth yw uchder pob un? " 

Byddwn yn gwneud cwpl, ond y prif syniad yw, hyn mewn unrhyw ffordd yn ddarlun unigryw o goeden ddeuaidd sy'n cynnwys y gwerthoedd hyn. Y cyfan sydd ei angen yw rhywfaint o goeden ddeuaidd sy'n cynnwys 7, 3, 6, a 9. Byddai un arall dilys posibl fyddai y gwraidd yw 3, ewch i'r chwith ac mae'n 6, ewch i'r chwith ac mae'n 7, ewch i'r chwith ac mae'n 9. Mae hynny'n goeden ddeuol berffaith ddilys chwilio. Dyw hi ddim yn ddefnyddiol iawn, am ei fod yn union fel rhestr cysylltiedig a phob un o'r pwyntiau yn unig null. Ond mae'n goeden dilys. Yeah? [Myfyrwyr] Peidiwch â gwerthoedd rhaid i fod yn fwy ar y dde? Neu a yw hyn -? Mae'r rhain yn >> wyf i fod i fynd y ffordd arall. Mae hefyd - ie, gadewch i ni newid hynny. 9, 7, 6, 3. Helfa dda. Mae dal i ufuddhau beth yw deuaidd chwilio coeden i fod i'w wneud. Felly popeth ar y chwith wedi i fod yn llai nag unrhyw nod penodol. Gallai Rydym yn unig yn symud, dyweder, hyn 6 a'i roi yma. Na, ni allwn. Pam ydw i'n barhau i wneud hynny? Gadewch i ni wneud - dyma yw 6, dyma yw 7, 6 pwynt i 3. Mae hyn yn dal i fod yn goeden ddeuaidd chwilio dilys. Beth sydd o'i le os byddaf yn - gadewch i ni weld os gallaf ddod o hyd i drefniant. Yeah, iawn. Felly beth sydd o'i le ar y goeden? Amcana i wedi roi ichi yn barod awgrym bod rhywbeth o'i le ag ef. Pam ydw i'n barhau i wneud hynny? Iawn. Mae hyn yn edrych yn rhesymol. Os ydym yn edrych ar bob nod, fel 7, yna i'r chwith o 7 yn 3. Felly mae gennym 3, y peth i'r dde o 3 o 6. Ac os ydych yn edrych yn 6, y peth i'r dde o 6 yn 9. Felly pam nad yw hyn yn goeden ddeuaidd chwilio ddilys? [Mae myfyrwyr yn] 9 yn dal ar y chwith o 7. >> Yeah. Rhaid iddo fod yn wir bod yr holl werthoedd y gallwch o bosibl cyrraedd trwy fynd i'r chwith o 7 yn llai na 7. Os ydym yn mynd i'r chwith o 7, rydym yn cael i 3 a gallwn yn dal i gael i 6, gallwn dal i gael i 9, ond drwy gael mynd yn llai na 7, Ni ddylem fod yn gallu cyrraedd nifer sy'n fwy na 7. Felly, nid yw hyn yn goeden ddeuaidd chwilio dilys. 

Mae fy mrawd mewn gwirionedd yn cael cwestiwn cyfweliad a oedd yn y bôn hyn, dim ond cod o hyd i rywbeth i ddilysu a yw coeden yn goeden chwiliad deuaidd, ac felly y peth cyntaf a wnaeth oedd dim ond edrych i weld os y chwith a dde yn gywir, ac yna ailadrodd lawr yno. Ond nid ydych yn gallu gwneud hynny; rhaid i chi gadw golwg y ffaith bod yn awr fy mod i wedi mynd i'r chwith o'r 7, mae'n rhaid i bopeth yn y Terfynau Chwilio yn llai na 7. Mae algorithm cywir angen i gadw golwg o'r terfynau y gall y gwerthoedd o bosibl syrthio i mewn Ni fyddwn yn mynd drwy bob un ohonynt. Mae yna berthynas gylchol braf, er nad ydym wedi gotten i rheini, neu ni fyddwn yn mynd i'r rheini, diffinio faint ohonynt mewn gwirionedd. Felly mae 14 ohonynt. Mae'r syniad o sut y byddech yn ei wneud fathemategol yn debyg, gallwch ddewis unrhyw un sengl i fod yn nod gwraidd, ac yna, os wyf yn dewis 7 i fod yn nod gwraidd, yna mae, dyweder, rhai rhifau a all fynd yn fy nod chwith, ac mae rhai rhifau a all fod yn fy nod iawn, ond os wyf wedi n cyfanswm, yna bydd y swm y gellir mynd i'r chwith yn ogystal â'r swm y gellir mynd i'r dde yn n - 1. Felly, y niferoedd sy'n weddill, rhaid iddynt fod yn gallu mynd naill ai i'r chwith neu'r dde. Mae'n ymddangos yn anodd, os wyf yn rhoi 3 gyntaf, yna rhaid i bopeth fynd i'r chwith, ond os wyf yn rhoi 7, yna gall rhai pethau fynd i'r chwith a gall y rhai pethau yn mynd i'r dde. A thrwy '3 'cyntaf i mi yn golygu y gall popeth yn mynd i'r dde. Mae'n wir, os oes gen ti i feddwl am y peth fel, sut y gall llawer o bethau yn mynd ar y lefel nesaf y goeden. Ac mae'n dod allan i fod yn 14 oed; neu gallwch dynnu pob un ohonynt, ac yna byddwch yn cael 14. 

Mynd yn ôl yma, "Gorchmynnwyd coed deuaidd yn oer oherwydd gallwn chwilio drwyddynt mewn ffordd debyg iawn i chwilio dros amrywiaeth datrys. I wneud hynny, rydym yn dechrau wrth wraidd ac yn gweithio ein ffordd i lawr y goeden tuag at ddail, gwirio gwerthoedd pob nod yn erbyn y gwerthoedd rydym yn chwilio am. Os werth y nod ar hyn o bryd yn llai na gwerth yr ydym yn chwilio amdano, byddwch yn mynd nesaf at blentyn y nod yn iawn. Fel arall, byddwch yn mynd i blentyn y nod o chwith. Ar ryw bwynt, byddwch naill ai yn dod o hyd i'r gwerth rydych chi'n chwilio amdano, neu byddwch yn rhedeg i mewn null, Nid yw dangos y gwerth sydd yn y goeden. " Rhaid i mi ail-lunio'r goeden oedd gennym o'r blaen; bydd yn cymryd eiliad. Ond rydym am edrych i fyny a 6, 10, ac 1 yn y goeden. Felly, beth oedd yno, 7, 9, 3, 6. Iawn. Mae'r niferoedd ydych am edrych i fyny, rydym yn awyddus i edrych i fyny 6. Sut mae hyn yn gweithio algorithm? Wel, mae gennym hefyd rai pwyntydd wraidd i'n goeden. Ac byddem yn mynd at wraidd a dweud, mae hyn yn gyfwerth â gwerth rydym yn chwilio amdano? Felly, rydym yn chwilio am 6, felly nid yw'n gyfartal. Felly, rydym yn dal i fynd, ac yn awr rydym yn dweud, iawn, felly 6 yn llai na 7. Ydy hynny'n golygu ein bod am fynd i'r chwith, neu a ydym am fynd i'r dde? [Myfyrwyr] Chwith. >> Yeah. Mae'n llawer haws, y cyfan mae'n rhaid i chi ei wneud yw tynnu un nod bosibl y goeden ac yna i chi peidiwch - yn hytrach na cheisio meddwl yn eich pen, iawn, os yw'n llai, ydw i'n mynd ar y chwith neu ewch i'r dde, dim ond yn edrych ar y darlun hwn, mae'n glir iawn bod rhaid i mi fynd i'r chwith os yw hyn nod yn fwy na'r gwerth a Im 'yn chwilio amdano. Felly, byddwch yn mynd i'r chwith, nawr rwy'n yn 3. Rwyf am - 3 yn llai na'r gwerth rwy'n chwilio amdano, sef 6. Felly, rydym yn mynd i'r dde, ac yn awr yr wyf yn y pen draw yn 6, sef y gwerth rwy'n chwilio amdano, felly yr wyf yn dychwelyd yn wir. Mae gwerth nesaf rwy'n mynd i chwilio amdano yw 10. Iawn. Felly 10, yn awr, yn mynd i - torri i ffwrdd hynny - yn mynd i ddilyn y gwraidd. Yn awr, 10 yn mynd i fod yn fwy na 7, felly yr wyf am edrych ar y dde. Rydw i'n mynd i ddod draw yma, mae 10 yn mynd i fod yn fwy na 9, felly dwi'n mynd i eisiau edrych ar y dde. Rwy'n dod draw yma, ond dros yma nawr rwy'n yn null. Beth ddylwn i ei wneud os byddaf yn taro null? [Myfyrwyr] Dychwelyd ffug? >> Yeah. Doeddwn i ddim yn dod o hyd i 10. 1 yn mynd i fod yn achos bron yn union yr un fath, ac eithrio mai dim ond yn mynd i gael eu flipped; yn hytrach nag edrych i lawr yr ochr dde, dw i'n mynd i edrych i lawr yr ochr chwith. 

Nawr Rwy'n credu ein bod mewn gwirionedd yn cael i cod. Dyma lle - agor i fyny 'r offer CS50 a llywio eich ffordd yno, ond gall dim ond i chi hefyd wneud yn y gofod. Mae'n debyg ddelfrydol i wneud hynny yn y gofod, oherwydd fe allwn ni weithio yn y gofod. "Yn gyntaf byddwn angen diffiniad math newydd ar gyfer nod goeden ddeuol sy'n cynnwys gwerthoedd int. Gan ddefnyddio'r boilerplate typedef isod, creu diffiniad math newydd ar gyfer nod mewn coeden deuaidd. Os ewch i drafferthion. . . "Blah, blah, blah. Iawn. Felly, gadewch i ni roi'r boilerplate yma, nod strwythur typedef, a nod. Yeah, iawn. Felly beth yw'r meysydd rydym yn mynd i eisiau yn ein nod? [Myfyrwyr] Int ac yna dau awgrymiadau? >> Int werth, dau awgrymiadau? Sut ydw i'n ysgrifennu'r awgrymiadau? [Myfyrwyr] strwythur. >> Dylwn chwyddo i mewn Yeah, felly strwythur nod * chwith, a strwythur nod * dde. A chofiwch y drafodaeth o'r tro diwethaf, bod hyn yn gwneud unrhyw synnwyr, mae hyn yn gwneud unrhyw synnwyr, mae hyn yn gwneud unrhyw synnwyr. Mae angen popeth yno er mwyn diffinio y strwythur ailadroddus. Iawn, felly dyna beth mae ein coeden yn mynd i edrych fel. Pe baem yn gwneud coeden trinary, yna gallai nod yn edrych fel, b2 b1, strwythur nod * b3, lle b yn gangen - mewn gwirionedd, yr wyf wedi clywed mwy gadael iddo, canol, i'r dde, ond beth bynnag. Byddwn ond yn gofalu am deuaidd, felly dde, i'r chwith. "Nawr datgan newidyn nod * byd-eang am wraidd y goeden." Felly nid ydym yn mynd i wneud hynny. Er mwyn gwneud pethau ychydig yn fwy anodd ac yn fwy cyffredinol, ni fydd gennym newidyn nod byd-eang. Yn lle hynny, yn y brif byddwn yn datgan ein holl bethau nod, ac mae hynny'n golygu bod isod, pan fyddwn yn dechrau rhedeg Yn cynnwys ein swyddogaeth a'n swyddogaeth rhowch yn ei le, yn hytrach na o'n Yn cynnwys swyddogaeth ddefnyddio dim ond y newidyn nod byd-eang, rydym yn mynd i gael ei gymryd fel dadl y goeden yr ydym am i brosesu. Mae cael y newidyn byd-eang oedd i fod i wneud pethau'n haws. Rydym yn mynd i wneud pethau'n anoddach. Nawr gymryd munud neu ddau i ddim ond gwneud y math hwn o beth, lle y tu mewn o brif ydych am greu y goeden hon, a dyna i gyd rydych am ei wneud. Ceisiwch ac adeiladu y goeden hon yn eich prif swyddogaeth. 

Iawn. Felly, nid oes hyd yn oed yn rhaid i wedi adeiladu y goeden y ffordd gyfan eto. Ond mae unrhyw un gael rhywbeth y gallwn dynnu i fyny i ddangos sut y gallai un ddechrau adeiladu o'r fath goeden? [Myfyrwyr] guro rhywun, yn ceisio mynd allan. [Bowden] unrhyw un gyfforddus gyda'u adeiladu coeden? [Myfyrwyr] Cadarn. Dyw hi ddim yn ei wneud. >> Mae'n iawn. Gallwn orffen - oh, allwch chi ei gadw? Hwre. Felly dyma gennym - oh, rwy'n ychydig yn torri i ffwrdd. Ydw i'n chwyddo i mewn? Chwyddo i mewn, sgrolio allan. >> Mae gen i gwestiwn. >> Yeah? [Myfyrwyr] Pan fyddwch yn diffinio strwythur, yw pethau fel ymgychwyn i unrhyw beth? [Bowden] Rhif >> Iawn. Felly, byddai'n rhaid i chi ymgychwyn - [Bowden] Rhif Pan fyddwch yn diffinio, neu pan fyddwch yn datgan strwythur, nad yw'n cael ei ymgychwyn yn rhagosodedig; mae'n union fel os ydych yn datgan int. Mae'n union yr un peth. Mae fel pob un o'i meysydd unigol yn gallu cael gwerth garbage ynddo. >> A yw'n bosibl diffinio - neu i ddatgan strwythur mewn ffordd a wna ymgychwyn nhw? [Bowden] Ydw. Felly, cystrawen shortcut initialization yn mynd i edrych fel - Mae dwy ffordd y gallwn wneud hyn. Rwy'n meddwl y dylem lunio ei i wneud yn siwr Clang hefyd yn gwneud hyn. Mae'r gorchymyn o ddadleuon sy'n dod i mewn i'r strwythur, i chi roi fel trefn y dadleuon y tu mewn o'r rhain braces cyrliog. Felly, os ydych am i ymgychwyn i 9 a gadawodd ei null ac yna i'r dde yn null, byddai'n 9, null, null. Y dewis arall yw, ac nid y golygydd ddim yn hoffi y gystrawen, ac mae'n credu yr wyf am gael bloc newydd, ond y dewis arall yw rhywbeth fel - yma, byddaf yn ei roi ar linell newydd. Gallwch ddweud yn benodol, yr wyf yn anghofio y gystrawen union. Felly, gallwch chi fynd i'r afael yn benodol drwy eu henwi, a dweud, . C, neu. Werth = 9,. NULL = chwith. Rwy'n dyfalu angen i'r rhain fod atalnodau. . I'r dde = NULL, felly mae hyn yn ffordd nad ydych yn ei wneud mewn gwirionedd mae angen i chi wybod y drefn y strwythur, a phan fyddwch chi'n darllen hwn, mae'n llawer mwy penodol am yr hyn y gwerth sy'n cael ei ymgychwyn i. 

Mae hyn yn digwydd i fod yn un o'r pethau hynny - felly, ar gyfer y rhan fwyaf, C + + yn uwchset o C. Gallwch gymryd C cod, symud drosodd i C + +, a dylai lunio. Mae hwn yn un o'r pethau y C + + Nid yw'n cefnogi, felly mae pobl yn tueddu i beidio â gwneud hynny. Nid wyf yn gwybod os dyna'r unig reswm mae pobl yn tueddu i beidio â gwneud hynny, ond yr achos lle roedd angen i mi ei ddefnyddio hangen i weithio gyda C + +, ac felly ni allwn ddefnyddio hyn. Nid yw enghraifft arall o rywbeth yw hynny'n gweithio gyda C + + yn sut malloc yn dychwelyd "* ddi-rym," dechnegol, ond gallech ddweud torgoch * x beth bynnag malloc =, a bydd yn awtomatig yn cael ei bwrw i * torgoch. Nid yw cast awtomatig yn digwydd mewn C + +. Ni fyddai hynny'n lunio, a byddech yn benodol rhaid i chi ddweud * torgoch, malloc, beth bynnag, i fwrw ef i * torgoch. Nid oes llawer o bethau y C a C + + yn anghytuno ar, ond y rhai yn ddau. Felly, byddwn yn mynd â'r chystrawen. Ond hyd yn oed os nad ydym yn mynd â'r cystrawen, beth yw - a allai fod o'i le ar hyn? [Myfyrwyr] Nid oes angen i mi ei dereference? >> Yeah. Cofiwch bod y saeth yn cael dereference ymhlyg, ac felly pan fyddwn yn unig yn delio â strwythur, ydym am eu defnyddio. i gyrraedd y tu mewn maes y strwythur. Ac mae'r amser yn unig yr ydym yn defnyddio saeth yw pan fyddwn am ei wneud - yn dda, saeth yn cyfateb i - dyna beth y byddai wedi golygu os byddaf yn defnyddio saeth. Pob dull saeth yn, dereference hyn, nawr rwy'n mewn strwythur, a gallaf gael y maes. Naill ai cael y cae yn uniongyrchol neu dereference a chael y maes - Amcana dylai hyn fod yn werth. Ond dyma rwy'n delio gyda dim ond nid strwythur, pwyntydd i strwythur, ac felly ni allaf ddefnyddio'r saeth. Ond y math hwn o beth y gallwn ei wneud ar gyfer yr holl nodau. O fy Nuw. Mae hyn yn 6, 7, a 3. Yna, gallwn sefydlu canghennau yn ein coeden, gallwn gael 7 - gallwn gael, ei chwith dylai pwynt i 3. Felly, sut ydyn ni'n gwneud hynny? [Myfyrwyr, annealladwy] >> Yeah. Mae'r cyfeiriad node3, ac os nad oedd gennych gyfeiriad, yna ni fyddai dim ond llunio. Ond cofiwch bod y rhain yn awgrymiadau ar gyfer nodau nesaf. Dylai'r hawl gyfeirio at 9, a 3 Dylai bwyntio ar yr hawl i 6. Rwy'n credu bod hyn i gyd yn set. Unrhyw sylwadau neu gwestiynau? [Myfyrwyr, annealladwy] Mae'r gwreiddyn yn mynd i fod yn 7. Gallwn ddweud nod * ptr = neu wreiddyn, = & node7. 

At ein dibenion ni, rydym yn mynd i fod yn delio gyda mewnosodiad, felly rydym yn mynd i eisiau i ysgrifennu swyddogaeth i fewnosod i mewn i'r goeden ddeuaidd a rhowch yn ei le yn anochel yn mynd i alw malloc i greu nod newydd ar gyfer y goeden. Felly mae pethau yn mynd i gael anniben â'r ffaith bod rhai nodau Ar hyn o bryd ar y simnai a nodau eraill yn mynd i roi diwedd ar i fyny ar y domen pan fyddwn yn mewnosod nhw. Mae hyn yn berffaith ddilys, ond yr unig reswm rydym yn gallu gwneud hyn ar y simnai oherwydd ei fod yn enghraifft mor ddyfeisgar ein bod yn gwybod y goeden i fod i gael ei hadeiladu fel 7, 3, 6, 9. Os nad oedd gennym hyn, yna ni fyddai rhaid i ni malloc yn y lle cyntaf. Fel byddwn yn gweld ychydig yn ddiweddarach, dylem fod yn malloc'ing. Ar hyn o bryd mae'n hollol resymol i'w roi ar y corn, ond gadewch i ni newid hyn i weithredu malloc. Felly mae gan bob un o'r rhain yn awr yn mynd i fod yn rhywbeth fel nod * node9 = malloc (sizeof (nod)). Ac yn awr rydym yn mynd i gael i wneud ein siec. os (node9 == NULL) - doeddwn i ddim eisiau hynny - dychwelyd 1, ac yna gallwn wneud node9-> oherwydd erbyn hyn mae'n pwyntydd, gwerth = 6, node9-> adael = NULL, node9-> dde = NULL, ac rydym yn mynd i gael i wneud hynny ar gyfer pob un o'r nodau. Felly, yn lle hynny, gadewch i ni roi y tu mewn swyddogaeth ar wahân. Gadewch i ni ei alw nod * build_node, ac mae hyn yn weddol debyg i APIs rydym yn darparu ar gyfer codio Huffman. Rydym yn rhoi i chi swyddogaethau initializer i goeden a deconstructor "swyddogaethau" ar gyfer y coed a'r un fath ar gyfer coedwigoedd. 

Felly dyma ni yn mynd i gael swyddogaeth initializer i ddim ond adeiladu nod i ni. Ac mae'n mynd i edrych yn bert lawer yn union fel hyn. Ac yr wyf ddim hyd yn oed yn mynd i fod yn ddiog ac nid newid enw'r newidyn, er node9 yn gwneud unrhyw synnwyr anymore. O, rwy'n dyfalu node9 yn werth ddylai fod wedi bod yn 6. Nawr gallwn ddychwelyd node9. Ac yma y dylem ddychwelyd null. Mae pawb yn cytuno ar y swyddogaeth adeiladu-a-nod? Felly, yn awr yn gallu rydym yn unig alw hynny i adeiladu unrhyw nod gyda gwerth a roddir ac awgrymiadau null. Nawr gallwn alw hynny, gallwn wneud nod * node9 = build_node (9). A gadewch i ni ei wneud. . . 6, 3, 7, 6, 3, 7. Ac yn awr rydym am i sefydlu'r awgrymiadau un, ac eithrio nawr mae popeth sydd eisoes o ran arwyddion felly nid oes angen y cyfeiriad. Iawn. Felly beth yw'r peth olaf yr wyf am ei wneud? Mae gwall-gwirio nad wyf i'n gwneud. Beth yw adeiladu dychwelyd nod? [Myfyrwyr, annealladwy] >> Yeah. Os malloc methu, bydd yn dychwelyd null. Felly, yr wyf i'n mynd i lazily roi i lawr yma yn hytrach na gwneud yn amod ar gyfer pob un. Os (node9 == NULL, neu - hyd yn oed yn symlach, mae hyn yn gyfwerth â dim ond os nad node9. Felly, os nad node9, neu beidio node6, neu beidio node3, neu beidio node7, yn dychwelyd 1. Efallai y dylem argraffu methu malloc, neu rywbeth. [Myfyrwyr] A yw ffug cyfartal i null hefyd? [Bowden] Unrhyw gwerth sero yn ffug. Felly null yn werth sero. Zero yn werth sero. Ffug yn werth sero. Bydd unrhyw - 'n bert lawer yr 2 yn unig gwerthoedd sero yn null a sero, ffug yn unig hash a ddiffinnir fel sero. Mae hynny hefyd yn berthnasol os ydym yn datgan amrywiol byd-eang. Os oedd gennym wraidd * nod yma, yna - y peth braf am newidynnau byd-eang yw eu bod bob amser yn cael gwerth cychwynnol. Nid yw hynny'n wir am swyddogaethau, sut tu mewn yma, os ydym yn cael, fel, * node neu'n x nod. Nid oes gennym unrhyw syniad beth x.value, x.whatever, neu gallem eu hargraffu a gallent fod yn fympwyol. Nid yw hynny'n wir o newidynnau byd-eang. Felly nod gwraidd neu x nod. Yn ddiofyn, mae popeth sy'n fyd-eang, os nad ymgychwyn benodol i ryw werth, mae iddo werth sero fel ei werth. Felly yma, gwraidd * nod, nid ydym yn benodol ymgychwyn i unrhyw beth, felly bydd ei gwerth diofyn yn null, sef gwerth sero o awgrymiadau. Mae gwerth rhagosodedig x yn mynd i olygu bod x.value yn sero, x.left yn null, ac x.right yn null. Felly, gan ei fod yn strwythur, bydd yr holl feysydd y strwythur fod yn sero gwerthoedd. Nid oes angen i ddefnyddio hynny yma, er. [Myfyrwyr] Mae'r structs yn wahanol na newidynnau eraill, ac mae'r newidynnau eraill yn gwerthoedd garbage; mae'r rhain yn zeros? [Bowden] gwerthoedd eraill hefyd. Felly, yn x, bydd x fod yn sero. Os yw'n ar gwmpas byd-eang, mae ganddo werth cychwynnol. >> Iawn. [Bowden] Naill ai y gwerth cychwynnol a roesoch iddo neu sero. Rwy'n credu bod yn gofalu am hyn i gyd. 

Iawn. Felly, y rhan nesaf y cwestiwn yn gofyn, "Nawr rydym yn awyddus i ysgrifennu swyddogaeth a elwir yn cynnwys gyda prototeip o bool yn cynnwys gwerth int. " Nid ydym yn mynd i wneud bool yn cynnwys gwerth int. Mae ein prototeip yn mynd i edrych fel bool yn cynnwys (gwerth int. Ac yna rydym hefyd yn mynd i basio y goeden y dylai fod yn gwirio i weld a yw'n ei werth. Felly, nod * goeden). Iawn. Ac yna gallwn ei alw gyda rhywbeth fel, efallai y byddwn eisiau printf neu rywbeth. Yn cynnwys 6, ein gwreiddiau. Y dylai ddychwelyd un, neu yn wir, tra yn cynnwys 5 Dylai gwraidd ddychwelyd ffug. Felly, am eiliad, i weithredu hyn. Gallwch ei wneud naill ai yn iteraidd neu'n ailadroddus. Y peth braf am y ffordd yr ydym wedi gosod pethau i fyny yw bod mae'n cynnig ei hun i ein ateb recursive yn llawer haws na'r ffordd fyd-eang-amrywiol wnaeth. Oherwydd os ydym yn unig yn cael cynnwys gwerth int, yna nid oes gennym unrhyw ffordd o recursing i lawr subtrees. Byddai'n rhaid i ni gael swyddogaeth gynorthwyydd ar wahân sy'n recurses i lawr y subtrees i ni. Ond ers i ni wedi newid i gymryd y goeden fel dadl, y dylai fod bob amser wedi bod yn y lle cyntaf, yn awr rydym yn gallu recurse yn haws. Felly ailadroddol neu ailadroddus, byddwn yn mynd dros y ddau, ond byddwn yn gweld bod yn dod i ben i fyny recursive fod yn eithaf hawdd. Iawn. Oes gan unrhyw un rhywbeth y gallwn weithio gyda? 

[Myfyrwyr] Mae gen i ailadroddol ateb. >> Mae pob hawl, ailadroddol. Iawn, mae hyn yn edrych yn dda. Felly, yn awyddus i gerdded i ni drwyddo? [Myfyrwyr] Cadarn. Felly, yr wyf yn gosod newidyn dros dro i gael y nod cyntaf y goeden. Ac yna Fi jyst dolennog drwy er nad dros dro yn null cyfartal, felly er yn dal yn y coed, yr wyf yn dyfalu. Ac os bydd y gwerth yn cyfateb i werth y temp yn pwyntio at, yna mae'n dychwelyd y gwerth. Fel arall, mae'n gwirio os yw'n ar yr ochr dde neu'r ochr chwith. Os ydych chi erioed wedi cael sefyllfa lle nad oes coed mwy, yna mae'n dychwelyd - mae'n gadael y ddolen ac yn dychwelyd ffug. [Bowden] Iawn. Felly dyna ymddangos yn dda. Dylai unrhyw un gennych unrhyw sylwadau ar unrhyw beth? Nid oes gennyf unrhyw sylwadau cywirdeb o gwbl. Yr un peth y gallwn ei wneud yn y boi. O, mae'n mynd i fynd gyd gyda'i gilydd ychydig. 'N annhymerus' atgyweiria hynny. Iawn. 

Dylai pawb yn cofio sut deiran yn gweithio. Mae wedi bendant wedi cwisiau yn y gorffennol sy'n rhoi i chi swyddogaeth gyda gweithredydd teiran, a dweud, cyfieithu hyn, wneud rhywbeth nad yw'n defnyddio teiran. Felly, mae hyn yn achos cyffredin iawn pan fyddwn yn meddwl i ddefnyddio teiran, lle os yw rhai amod a osodir newidyn i rywbeth, gosod y newidyn arall yr un i rywbeth arall. Mae hynny'n rhywbeth y gall yn aml iawn yn cael ei drawsnewid i mewn i math hwn o beth os ydynt wedi'u y newidyn i hyn - neu, yn dda, mae hyn yn wir? Yna hyn, arall y. [Myfyrwyr] Mae'r un cyntaf yw os yw'n wir, dde? [Bowden] Yeah. Y ffordd yr wyf bob amser yn darllen y mae, dros dro yn dychwelyd gwerth yn fwy na gwerth dros dro, yna mae hyn, arall y. Mae'n gofyn cwestiwn. A yw'n fwy? Yna gwneud y peth cyntaf. Arall gwneud y peth ail. Yr wyf yn bron bob amser - y colon, Fi jyst - yn fy mhen, yr wyf yn darllen fel arall. 

Oes gan unrhyw un ateb recursive? Iawn. Mae hyn yn un rydym ni'n mynd i - gallai fod eisoes yn wych, ond rydym ni'n mynd i'w wneud yn hyd yn oed yn well. Dyma 'n bert lawer y syniad union yr un. Mae'n jyst, wel, ydych chi eisiau i esbonio? [Myfyrwyr] Cadarn. Felly, rydym yn gwneud yn siŵr nad yw'r goeden yn null gyntaf, oherwydd os bydd y goeden yn null, yna mae'n mynd i ddychwelyd ffug oherwydd nad ydym wedi dod o hyd iddo. Ac os oes dal i fod yn goeden, byddwn yn mynd - yn gyntaf wirio a yw'r gwerth yn y nod ar hyn o bryd. Dychwelyd wir os ydyw, ac os nad ydym yn recurse ar y chwith neu i'r dde. A yw hynny'n gadarn yn briodol? >> Mm-hmm. (Cytundeb) Felly sylwi bod hyn bron - strwythurol yn debyg iawn i'r ateb ailadroddol. Mae'n dim ond bod yn lle recursing, cawsom dolen gyfnod. Ac mae'r achos sylfaenol yma lle nad yw coed yn null cyfartal oedd cyflwr o dan yr ydym dorrodd allan o'r ddolen tra. Maen nhw'n debyg iawn. Ond rydym yn mynd i gymryd hyn un cam ymhellach. Nawr, rydym yn gwneud yr un peth yma. Hysbysiad rydym yn dychwelyd yr un peth yn y ddau llinellau hyn, heblaw am un ddadl yn wahanol. Felly, rydym yn mynd i wneud hynny i mewn i teiran. Yr wyf yn taro rhywbeth opsiwn, a gwnaeth symbol. Iawn. Felly, rydym yn mynd i ddychwelyd yn cynnwys hynny. Mae hyn yn mynd i fod yn llinellau lluosog, yn dda, chwyddo i mewn ag y mae. Fel arfer, fel peth arddull, nid wyf yn meddwl llawer o bobl rhoi bwlch ar ôl y saeth, ond mae'n debyg os ydych yn gyson, mae'n iawn. Os gwerth yn llai na gwerth coed, rydym am i recurse ar y chwith coed, arall yr ydym yn awyddus i recurse goeden ar y dde. Felly dyna oedd y cam cyntaf o wneud hyn yn edrych yn llai. Cam dau o wneud hyn yn edrych yn llai - gallwn wahanu'r hyn i linellau lluosog. Iawn. Cam dau o wneud iddo edrych yn llai yma, felly gwerth dychwelyd hafal werth coed, neu sy'n cynnwys beth bynnag. 

Mae hwn yn beth pwysig. Dwi ddim yn siŵr os dywedodd ei fod yn eglur yn y dosbarth, ond fe'i gelwir byr-cylched werthuso. Y syniad yma yw gwerth == gwerth coed. Os yw hynny'n wir, yna mae hyn yn wir, ac rydym am i 'neu' bod gyda beth bynnag sydd dros yma. Felly, heb hyd yn oed feddwl am beth bynnag sydd dros yma, beth yw'r ymadrodd cyfan yn mynd i ddychwelyd? [Myfyrwyr] Gwir? >> Yeah, oherwydd yn wir am unrhyw beth, or'd - or'd neu yn wir gydag unrhyw beth o reidrwydd yn wir. Felly, cyn gynted ag y gwelwn werth dychwelyd gwerth coed =, rydym yn jyst yn mynd i ddychwelyd yn wir. Nid hyd yn oed yn mynd i recurse bellach yn cynnwys i lawr y llinell. Gallwn gymryd hyn un cam ymhellach. Nid yw'r goeden Dychwelyd yn null cyfartal a hyn i gyd. Mae'n ei gwneud yn swyddogaeth un llinell. Mae hyn hefyd yn enghraifft o gylched byr-werthuso. Ond yn awr mae'n un syniad - yn hytrach na - felly os coeden nad yw'n null cyfartal - neu, yn dda, os goeden yn null cyfartal, sydd yn wir ddrwg, os goeden hafal null, yna mae'r amod cyntaf yn mynd i fod yn ffug. Felly, ffug anded ag unrhyw beth yn mynd i fod yn beth? [Myfyrwyr] Anghywir. >> Yeah. Mae hyn yn yr hanner arall byr-cylched gwerthuso, lle os goeden yn null nid gyfartal, yna nid ydym yn mynd i hyd yn oed fynd - neu os goeden yn null cyfartal, yna nid ydym yn mynd i wneud gwerth == gwerth coed. Rydym yn unig yn mynd i ddychwelyd ar unwaith ffug. Pa yn bwysig, oherwydd os nad oedd byr-cylched werthuso, yna os goeden yn null cyfartal, mae hyn yn ail amod yn mynd i seg fai, oherwydd bod coed> werth yn dereferencing null. Felly dyna hynny. A all wneud hyn - newid unwaith dros. Mae hyn yn beth cyffredin iawn hefyd, beidio â gwneud y llinell hon un â hyn, ond mae'n beth cyffredin mewn amgylchiadau, efallai na dde yma, ond os (goeden! = NULL, a gwerth == coed> werth), gwneud beth bynnag. Mae hwn yn gyflwr cyffredin iawn, lle yn hytrach na chael i dorri hyn i ddau IFS, lle hoffi, yw'r null goeden? Iawn, nid yw'n null, felly nawr yw'r gwerth coed cyfartal i werth? Gwnewch hyn. Yn hytrach, y cyflwr hwn, ni fydd hyn yn SEG bai oherwydd bydd yn torri allan os bydd hyn yn digwydd i fod yn null. Wel, yr wyf yn dyfalu os yw eich coeden yn hollol annilys pwyntydd, gall fod yn dal SEG fai, ond ni all SEG bai os coeden yn null. Pe bai'n null, byddai'n torri allan cyn i chi dereferenced erioed y pwyntydd yn y lle cyntaf. [Myfyrwyr] A yw hyn yn werthusiad ddiog elwir? 

Gwerthuso [Bowden] Lazy yn beth ar wahân. Gwerthuso Lazy yn fwy fel chi ofyn am werth, byddwch yn gofyn i gyfrifo gwerth, math o, ond nid oes angen ar unwaith. Felly, hyd nes y byddwch ei angen mewn gwirionedd, nid yw'n cael ei werthuso. Nid yw hyn yn union yr un peth, ond yn y pset Huffman, ei fod yn dweud ein bod yn "ddiog" ysgrifennu. Y rheswm rydym yn ei wneud hynny oherwydd ein bod mewn gwirionedd yn clustogi y ysgrifennu - nid ydym am i ysgrifennu darnau unigol ar y tro, neu bytes unigol ar y tro, rydym yn lle hynny am gael darn o bytes. Yna, unwaith y bydd gennym darn o bytes, yna byddwn yn ysgrifennu arni. Hyd yn oed er byddwch yn gofyn iddo ysgrifennu - a fwrite a fread gwneud yr un math o beth. Maent yn clustogi eich darllen ac ysgrifennu. Hyd yn oed er byddwch yn gofyn i ysgrifennu ar unwaith, mae'n debyg nad fydd. Ac ni allwch fod yn siwr bod pethau'n mynd i gael ei ysgrifennu hyd nes y byddwch yn ffonio hfclose neu beth bynnag ydyw, sydd wedyn yn dweud, iawn, dwi'n cau fy ffeil, sy'n golygu y byddai'n well i mi ysgrifennu popeth Nid wyf wedi ysgrifennu eto. Mae wedi oes angen i chi ysgrifennu popeth allan nes eich bod yn cau y ffeil, ac yna mae angen iddo. Felly dyna'n union yr hyn ddiog - mae'n aros hyd nes y mae'n rhaid iddo ddigwydd. Mae hyn yn - cymryd 51 a byddwch yn mynd i mewn iddo yn fwy manwl, oherwydd OCaml a phopeth mewn 51, mae popeth yn dychweliad. Nid oes unrhyw atebion ailadroddol, yn y bôn. Mae popeth yn dychweliad, a gwerthuso diog yn mynd i fod yn bwysig ar gyfer llawer o amgylchiadau lle, os nad oeddech yn ddiog gwerthuso, a fyddai'n golygu - Mae'r enghraifft yn nentydd, sydd yn eithriadol hir. Mewn theori, gallwch feddwl am y rhifau naturiol fel ffrwd o 1-2-3-4-5-6-7, Pethau Felly lazily gwerthuso yn iawn. Os wyf yn dweud fy mod am i'r rhif degfed, yna gallaf werthuso hyd at y nifer degfed. Os ydw i am i'r rhif ganfed, yna gallaf werthuso hyd at y nifer canfed. Heb werthusiad ddiog, yna mae'n mynd i geisio i werthuso'r holl rifau ar unwaith. Rydych yn gwerthuso nifer anfeidrol lawer, ac nad dim ond y bo modd. Felly, mae yna lawer o amgylchiadau lle gwerthuso ddiog yn unig yn hanfodol i gael pethau i weithio. 

Nawr rydym am i ysgrifennu nodwch lle rhowch yn ei le yn mynd i fod ran newid yn ei ddiffiniad. Felly, ar hyn o bryd mae'n mewnosod bool (gwerth int). Rydym yn mynd i newid hynny i mewnosodwch bool (int gwerth, nod * coeden). Rydym yn wir yn mynd i newid hynny eto mewn ychydig, byddwn yn gweld pam. A gadewch i ni symud build_node, dim ond ar gyfer y Heck ohono, uchod yn mewnosod felly nid ydym yn rhaid i chi ysgrifennu prototeip swyddogaeth. Pa yn awgrym eich bod yn mynd i gael ei defnyddio build_node yn mewnosod. Iawn. Cymerwch funud ar gyfer hynny. Rwy'n credu fy mod arbed yr adolygiad os ydych am dynnu hynny, neu, o leiaf, yr wyf yn gwneud yn awr. Roeddwn i eisiau cael seibiant bach i feddwl am y rhesymeg mewnosoder, os nad ydych yn gallu meddwl amdano. Yn y bôn, byddwch ond byth yn cael ei fewnosod yn y dail. Fel, os wyf yn mewnosod 1, yna rwy'n anochel yn mynd i gael ei gosod 1 - 'N annhymerus' newid i ddu - I'll yn gosod 1 dros yma. Neu os byddaf yn ychwanegu 4, hoffwn gael eu gosod 4 dros yma. Felly, dim ots beth ydych yn ei wneud, rydych yn mynd i gael eu gosod ar y ddeilen. Y cyfan sydd raid i chi ei wneud yw ailadrodd i lawr y goeden nes i chi gyrraedd y nod a ddylai fod yn rhiant y nod, rhiant y nod newydd, ac yna newid ei pwyntydd ar y chwith neu i'r dde, yn dibynnu ar p'un a mae'n fwy na neu'n llai na'r nod ar hyn o bryd. Newid y pwyntydd i bwyntio at eich nod newydd. Felly, ailadrodd i lawr y goeden, yn gwneud y pwynt ddeilen at y nod newydd. Hefyd yn meddwl am pam sy'n gwahardd y math o sefyllfa o'r blaen, lle yr wyf yn adeiladu y goeden ddeuaidd lle'r oedd yn gywir os mai dim ond edrych ar nod unigol, ond 9 oedd i'r chwith o 7 os ydych Ailadroddodd i lawr yr holl ffordd. Felly, mae hyn yn amhosibl yn y sefyllfa hon, ers hynny - meddwl am osod 9 neu rhywbeth; yn y nod cyntaf, Dw i'n mynd i weld 7 a Im 'jyst yn mynd i fynd ar y dde. Felly, dim ots beth ddylwn i ei wneud, os ydw i'n gosod trwy fynd i deilen, ac i deilen gan ddefnyddio algorithm priodol, mae'n mynd i fod yn amhosibl i mi i fewnosod 9 i'r chwith o 7 oherwydd cyn gynted ag y taro 7 Rwyf i'n mynd i fynd ar y dde. Oes gan unrhyw un rywbeth i ddechrau? [Myfyrwyr] ddylwn i ei wneud. >> Cadarn. [Myfyrwyr, annealladwy] [Fyfyrwyr eraill, annealladwy] [Bowden] Mae'n cael ei werthfawrogi. Iawn. Eisiau esbonio? 

[Myfyrwyr] Ers i ni wybod ein bod yn mewnosod nodau newydd ar ddiwedd y goeden, I dolennog drwy'r goeden iteraidd hyd nes i mi gyrraedd sefyllfa o nod a dynnodd sylw at null. Ac yna penderfynais ei roi naill ai ar yr ochr dde neu'r ochr chwith defnyddio'r newidyn hwn iawn, mae'n dweud wrthyf ble i roi. Ac yna, yn y bôn, Fi jyst gwneud y diwedd - bod dros dro pwynt nod at y nod newydd ei bod yn creu, naill ai ar yr ochr chwith neu ar yr ochr dde, yn dibynnu ar beth yw gwerth iawn oedd. Yn olaf, yr wyf yn gosod y gwerth nod newydd i'r gwerth ei brofi. [Bowden] Iawn, felly yr wyf yn gweld un mater yma. Mae hyn yn debyg 95% o'r ffordd yno. Y mater un yr wyf yn gweld, yn dda, oes unrhyw un arall ei weld yn broblem? Beth yw'r amgylchiadau o dan ba maent yn torri allan o'r cylch? [Myfyrwyr] Os yw'r tymheredd yn null? >> Yeah. Felly, sut byddwch yn torri allan o'r cylch yw os dros dro yn null. Ond beth ddylwn i ei wneud iawn yma? Dros dro dereference I, sydd yn anochel yn null. Felly nid yw'r peth arall sydd angen i chi ei wneud yw jyst cadw trac nes dros dro yn null, ydych chi am gadw golwg ar y rhiant bob amser. Rydym hefyd am riant * nod, mae'n debyg y gallwn gadw hynny yn null ar y dechrau. Mae hyn yn mynd i gael ymddygiad rhyfedd i wraidd y goeden, ond byddwn yn mynd i hynny. Os werth yn fwy na'r beth bynnag, ac yna i'r dde dros dro temp =. Ond cyn i ni wneud hynny, rhiant = temp. Neu a rhieni bob amser yn mynd i dros dro cyfartal? A yw hynny'n wir? Os nad yw dros dro yn null, yna dwi'n mynd i symud i lawr, ni waeth beth, i nod y tymheredd yn rhiant. Felly rhiant yn mynd i fod dros dro, ac yna byddaf yn symud dros dro i lawr. Nawr dros dro yn null, ond mae'n tynnu sylw rhieni at y rhiant y peth sydd yn null. Felly i lawr yma, nid wyf am osod i'r dde yn hafal i 1. Felly symudais i'r dde, felly os gywir = 1, ac yr wyf yn dyfalu y byddwch hefyd am ei wneud - os byddwch yn symud i'r chwith, ydych chi eisiau i osod hawl gyfartal i 0. Neu arall, os ydych chi erioed wedi symud i'r dde. Felly, i'r dde = 0. Os cywir = 1, yn awr rydym eisiau gwneud y pwyntydd rhiant newnode iawn, arall rydym eisiau gwneud y pwyntydd rhiant newnode chwith. Cwestiynau ar hynny? Iawn. Felly, mae hyn yn y ffordd yr ydym yn - wel, mewn gwirionedd, yn hytrach na gwneud hyn, rydym yn disgwyl i chi 1/2 i ddefnyddio build_node. Ac yna os newnode hafal null, yn dychwelyd ffug. Dyna hynny. Yn awr, dyma beth yr ydym yn disgwyl i chi ei wneud. 

Dyma beth yw'r atebion staff yn ei wneud. Yr wyf yn anghytuno â hyn fel y "cywir" ffordd o fynd am y peth ond mae hyn yn berffaith iawn a bydd yn gweithio. Un peth sy'n hawl rhyfedd ychydig yn awr yw os yw'r goeden yn dechrau i ffwrdd fel null, rydym yn pasio mewn coeden null. Amcana mae'n dibynnu ar sut yr ydych yn diffinio ymddygiad basio mewn coeden null. Byddwn yn meddwl, os byddwch yn mynd heibio mewn coeden null, Yna gosod y gwerth i mewn i goeden null dylai fynd yn ôl coeden lle mae'r gwerth yn unig yw bod nod sengl. Ydy pobl yn cytuno â hynny? Gallech, os ydych yn dymuno, os byddwch yn mynd heibio mewn coeden null a'ch bod eisiau mewnosod gwerth i mewn iddo, yn dychwelyd ffug. Mae i fyny i chi i ddiffinio hynny. Er mwyn gwneud y peth cyntaf i mi ddweud, ac yna - yn dda, rydych chi'n mynd i gael trafferth gwneud hynny, oherwydd byddai'n haws pe bai gennym bwyntydd byd-eang at y peth, ond nid ydym yn ei wneud, felly os goeden yn null, does dim byd y gallwn ei wneud am hynny. Gallwn fynd yn ôl ffug. Felly dw i'n mynd i newid mewnosodiad. Rydym gallai dechnegol dim ond newid y dde yma, sut mae'n ailadrodd dros bethau, ond rwy'n mynd i newid rhowch yn ei le i gymryd nod ** coeden. Awgrymiadau dwbl. Beth yw ystyr hyn? Yn hytrach na delio â awgrymiadau i nodau, y peth yr wyf i'n mynd i gael eu trin yn y pwyntydd. Rydw i'n mynd i gael eu trin y pwyntydd. Rydw i'n mynd i gael eu trin awgrymiadau yn uniongyrchol. Mae hyn yn gwneud synnwyr ers hynny, meddyliwch am i lawr - yn dda, ar hyn o bryd mae hyn pwyntiau i'w null. Hyn yr wyf am ei wneud yw trin y pwyntydd i bwyntio at beidio null. Yr wyf am iddo bwyntio at fy nod newydd. Os Fi jyst cadw cofnod o awgrymiadau i fy awgrymiadau, yna nid oes angen i mi gadw golwg ar pwyntydd rhiant. Gall Fi jyst cadw golwg i weld os yw'r pwyntydd yn pwyntio at null, ac os bydd y pwyntydd yn pwyntio at null, newid i gyfeirio at y nod rwyf eisiau. A allaf newid ers i mi gael pwyntydd i'r pwyntydd. Gadewch i ni weld hyn yn awr. Gallwch wneud hynny mewn gwirionedd yn eithaf ailadroddus yn hawdd. A ydym eisiau gwneud hynny? Oes, rydym yn ei wneud. 

Gadewch i ni weld ei ailadroddus. Yn gyntaf, beth yw ein achos sylfaenol yn mynd i fod? Mae bron bob amser yn ein achos sylfaenol, ond mewn gwirionedd, mae hyn yn fath o anodd. Pethau cyntaf yn gyntaf, os (coeden == NULL) Amcana rydym yn jyst yn mynd i ddychwelyd ffug. Mae hyn yn wahanol i'ch null coed lles. Mae hyn yn y pwyntydd i'r pwyntydd eich gwreiddiau yn null sy'n golygu nad yw eich pwyntydd gwraidd yn bodoli. Felly i lawr yma, os wyf yn gwneud * nod - gadewch i ni dim ond ailddefnyddio'r hyn. Node * gwraidd = NULL, ac yna yr wyf i'n mynd i alw rhowch yn ei le drwy wneud rhywbeth fel, rhowch 4 i & gwraidd. So & gwraidd, os gwraidd yn * nod yna & gwraidd yn mynd i fod yn ** nod. Mae hyn yn ddilys. Yn yr achos hwn, coed, hyd yma, Nid yw'r goeden yn null - neu rhowch. Yma. Nid yw'r goeden yn null; * goeden yn null, sy'n iawn oherwydd os goeden * yn null, yna gallaf drin ei yn hyn gyfeirio at yr hyn yr wyf am iddo bwyntio at. Ond os goeden yn null, sy'n golygu fy mod yn unig yn dod i lawr yma a dweud null. Nid yw hynny'n gwneud synnwyr. Nid wyf yn gallu gwneud unrhyw beth â hynny. Os goeden yn null, yn dychwelyd ffug. Felly, yr wyf eisoes wedi dweud y bôn yr hyn y mae ein achos sylfaenol go iawn. A beth yw bod yn mynd i fod? [Myfyrwyr, annealladwy] [Bowden] Ydw. Felly, os (* coeden == NULL). Mae hyn yn ymwneud ag achos dros yma lle os bydd fy pwyntydd coch yn y pwyntydd rwy'n canolbwyntio ar, felly fel fy mod yn canolbwyntio ar y pwyntydd, nawr rwy'n canolbwyntio ar y pwyntydd. Nawr rwy'n canolbwyntio ar y pwyntydd. Felly, os yw fy pwyntydd coch, sef fy ** nod, byth - os *, fy pwyntydd coch, byth yn null, hynny'n golygu fy mod yn yr achos lle dwi'n canolbwyntio ar pwyntydd y pwyntiau - mae hwn yn pwyntydd sy'n perthyn i ddeilen. Rwyf am newid y pwyntydd i bwyntio at fy nod newydd. Dewch yn ôl dros yma. Bydd fy newnode yn unig fod nod * n = build_node (gwerth) Yna, n, os yw n = NULL, yn dychwelyd ffug. Arall ydym am newid yr hyn y pwyntydd ar hyn o bryd pwyntio at yn hyn bwyntio at ein nod newydd gael eu hadeiladu. Gallwn yn gwneud hynny yma. Yn hytrach na dweud n, yr ydym yn dweud * coeden = os * goeden. Mae pawb yn deall hynny? Drwy ymdrin ag awgrymiadau i awgrymiadau, gallwn ni newid awgrymiadau null cyfeirio at bethau yr ydym am iddynt gyfeirio atynt. Dyna ein achos sylfaenol. 

Nawr ein eto, neu ein dychweliad, yn mynd i fod yn debyg iawn i'r holl recursions eraill rydym wedi bod yn ei wneud. Rydym yn mynd i eisiau i fewnosod gwerth, ac yn awr yr wyf i'n mynd i ddefnyddio deiran eto, ond beth yw ein cyflwr yn mynd i fod? Beth ydyw rydym yn chwilio amdano i benderfynu a ydym am fynd i'r chwith neu i'r dde? Gadewch i ni ei wneud mewn camau ar wahân. Os (gwerth <) beth? [Myfyrwyr] werth y goeden? [Bowden] Felly cofiwch fy mod ar hyn o bryd - [Myfyrwyr, annealladwy] [Bowden] Yeah, felly dde yma, gadewch i ni ddweud bod y saeth werdd yn enghraifft o'r hyn y goeden ar hyn o bryd yw, yn pwyntydd at y pwyntydd. Felly mae hynny'n golygu fy mod yn pwyntydd i pwyntydd i 3. Mae'r dereference ddwywaith yn swnio'n dda. Beth ydw i'n - sut ydw i'n gwneud hynny? [Myfyrwyr] dereference unwaith, ac yna gwneud saeth y ffordd honno? [Bowden] Felly (* coeden) yw'r dereference unwaith, -> werth yn mynd i roi i mi gwerth y nod fy mod i'n anuniongyrchol gan bwyntio at. Felly gallaf hefyd ysgrifennu ei ** tree.value os yw'n well gennych hynny. Naill ai yn gweithio. Os mai dyna'r achos, yna yr wyf am alw mewnosod â gwerth. A beth yw fy nod ddiweddaru ** mynd i fod? Dw i eisiau mynd i'r chwith, felly ** tree.left yn mynd i fod yn fy chwith. Ac yr wyf am i'r pwyntydd i'r peth felly os bydd y chwith yn dod i ben i fyny yn y pwyntydd null, Gallaf addasu i gyfeirio at fy nod newydd. 

A gall yr achos arall yn debyg iawn. Gadewch i ni mewn gwirionedd yn gwneud bod fy teiran ar hyn o bryd. Rhowch werth os werth <(** coeden). Werth. Yna, rydym yn awyddus i ddiweddaru ein ** ar y chwith, arall yr ydym yn awyddus i ddiweddaru ein ** ar y dde. [Myfyrwyr] yw hynny'n cael y pwyntydd i'r pwyntydd? [Bowden] Cofiwch fod - ** tree.right yn seren nod. [Myfyrwyr, annealladwy] >> Yeah. ** Tree.right fel hyn pwyntydd neu rywbeth. Felly, drwy gymryd pwyntydd hynny, y mae yn rhoi i mi yr hyn yr wyf eisiau y pwyntydd i'r dyn. [Myfyrwyr] A gawn ni fynd dros eto pam ein bod yn defnyddio y ddau awgrymiadau? [Bowden] Yeah. Felly - na, allwch, a bod ateb cyn yn ffordd o wneud hyn heb wneud dau awgrymiadau. Mae angen i chi allu deall gan ddefnyddio dau awgrymiadau, ac mae hyn yn ateb glanach. Hefyd, yn sylwi bod, beth fydd yn digwydd os bydd fy coeden - beth sy'n digwydd os yw fy gwraidd yn null? Beth fydd yn digwydd os wyf yn gwneud yr achos hwn iawn yma? Felly, nod * gwraidd = NULL, rhowch 4 i & gwraidd. Beth yw gwraidd mynd i fod ar ôl hyn? [Myfyrwyr, annealladwy] >> Yeah. Gwerth Root yn mynd i fod yn 4. Chwith Root yn mynd i fod yn null, hawl gwraidd yn mynd i fod yn null. Yn yr achos lle nad oeddem yn pasio wraidd ôl cyfeiriad, nid oeddem yn gallu addasu gwraidd. Yn yr achos lle y goeden - lle gwraidd yn null, rydym yn unig wedi dychwelyd ffug. Does dim byd y gallem ei wneud. Ni allwn gosod nod i mewn i goeden wag. Ond yn awr rydym yn gallu; byddwn yn gwneud coeden wag i mewn i goeden un nod. Pa un yw fel arfer yn y ffordd y disgwylir ei fod yn fod i weithio. 

Ar ben hynny, mae hyn yn sylweddol fyrrach na'r hefyd yn cadw golwg ar y rhiant, ac felly i chi ailadrodd i lawr yr holl ffordd. Nawr rwyf wedi fy rhieni, a Fi jyst wedi fy rhieni pwyntydd hawl i beth bynnag. Yn lle hynny, os ydym yn gwneud hyn iteraidd, byddwn yn cael yr un syniad gyda dolen gyfnod. Ond yn hytrach na gorfod delio gyda fy pwyntydd rhiant, yn hytrach na byddai fy pwyntydd ar hyn o bryd fod y peth fy mod yn uniongyrchol addasu i bwyntio at fy nod newydd. Nid oes gennyf i ddelio ag a yw'n pwyntio i'r chwith. Nid oes gennyf i ddelio ag a yw'n pwyntio i'r dde. Dim ond beth bynnag y pwyntydd yw, dwi'n mynd i osod i bwyntio at fy nod newydd. Mae pawb yn deall sut mae'n gweithio? Os na, pam ydym ni eisiau ei wneud fel hyn, ond o leiaf bod hyn yn gweithio fel ateb? [Myfyrwyr] Ble rydyn ni'n dychwelyd yn wir? [Bowden] Mae hynny'n debyg iawn yma. Os ydym yn gywir rhowch ef, yn dychwelyd yn wir. Else, i lawr yma rydym yn mynd i eisiau dychwelyd ffurflenni rhowch beth bynnag. 

A beth sy'n arbennig am y swyddogaeth recursive? Mae'n gynffon recursive, felly cyn belled ag y llunio gyda rhywfaint o optimization, bydd yn cydnabod hynny ac na fyddwch byth yn cael gorlif pentwr o hyn, hyd yn oed os yw ein coed yn cael uchder o 10,000 neu 10 miliwn. [Myfyrwyr, annealladwy] [Bowden] Rwy'n credu y mae'n ei wneud yn Dash - neu ba lefel optimeiddio ei angen ar gyfer dychweliad gynffon i gael ei gydnabod. Rwy'n credu ei fod yn cydnabod - Cyngor Gwynedd a Clang hefyd yn cael ystyron gwahanol ar gyfer eu lefelau Optimization. Hoffwn i ddweud ei fod DashO 2, yn sicr y bydd yn cydnabod dychweliad gynffon. Ond ni - gallech adeiladu fel enghraifft rywbeth Fibonocci neu. Nid yw'n hawdd i brofi â hyn, oherwydd ei fod yn anodd i adeiladu goeden ddeuaidd sydd mor fawr. Ond yeah, yr wyf yn meddwl ei fod yn DashO 2, sy'n os ydych yn llunio gyda DashO 2, bydd yn edrych am dychweliad gynffon a gwneud y gorau hynny. Gadewch i ni fynd yn ôl i - rhowch llythrennol y peth olaf sydd ei angen. Gadewch i ni fynd yn ôl i'r mewnosodiad dros yma lle'r ydym yn mynd i wneud yr un syniad. Bydd yn dal i gael y flaw o beidio â bod yn gallu ymdrin yn gyfan gwbl pan fydd y gwreiddiau ei hun yn null, neu y cofnod diwethaf yn null, ond yn hytrach na delio gyda pwyntydd rhiant, gadewch i ni wneud cais yr un rhesymeg o awgrymiadau gan gadw at awgrymiadau. Os dyma rydym yn cadw ein nod ** cyf, ac nid oes angen i ni gadw golwg ar hawl i anymore, ond nod ** cyf = & goeden. Ac yn awr mae ein dolen tra yn mynd i fod er nad cyf * yn null cyfartal. Nid oes angen i gadw golwg ar rieni anymore. Nid oes angen i gadw golwg ar y chwith ac i'r dde. A byddaf yn ei alw dros dro, oherwydd ein bod eisoes yn defnyddio dros dro. Iawn. Felly os (gwerth> * dros dro), Yna, & (* dros dro) -> dde arall dros dro = & (* dros dro) -> chwith. Ac yn awr, yn y fan hon, ar ôl y ddolen tra, Dim ond gwneud hyn oherwydd efallai ei fod yn haws i feddwl am iteraidd na recursively, ond ar ôl hyn dolen tra, * Dros dro yn y pwyntydd yr ydym am ei newid. 

Cyn i ni gael rhiant, ac rydym yn awyddus i newid chwith rhiant naill neu'r rhiant hawl, ond os ydym am newid i'r dde rhiant, yna * dros dro yn iawn rhiant, a gallwn ei newid yn uniongyrchol. Felly i lawr yma, y ​​gallwn ei wneud dros dro * = newnode, a dyna ni. Felly rhybudd, y cyfan a wnaethom yn hyn yn cymryd allan linellau o god. Er mwyn cadw golwg ar y rhiant ym mhopeth sydd yn ymdrech ychwanegol. Yma, os ydym yn unig yn cadw golwg ar y pwyntydd i'r pwyntydd, a hyd yn oed os ydym am gael gwared o'r holl braces cyrliog yn awr, gwneud iddo edrych yn fyrrach. Mae hyn yn awr yw un ateb yn union, ond llinellau llai o god. Pan fyddwch yn dechrau cydnabod hyn fel ateb dilys, mae hefyd yn haws i resymu am na tebyg, iawn, pam ydw i'n cael y faner ar y dde int? Beth mae hynny'n ei olygu? O, mae'n dynodi ei bob tro rwy'n mynd yn iawn, mae angen i mi ei osod, arall os byddaf yn mynd ar ôl rhaid i mi osod i sero. Yma, nid oes gennyf reswm i am hynny; mae'n haws i feddwl amdano. Cwestiynau? [Myfyrwyr, annealladwy] >> Yeah. Iawn, felly yn y rhan olaf - Amcana un swyddogaeth cyflym a hawdd y gallwn ni ei wneud yw, let's - gyda'n gilydd, mae'n debyg, ceisiwch ysgrifennu yn cynnwys swyddogaeth nad yw'n gofalu a yw'n goeden chwiliad deuaidd. Mae hyn yn cynnwys y dylai swyddogaeth ddychwelyd wir os unrhyw le yn y goeden ddeuaidd cyffredinol yw gwerth rydym yn chwilio am. Felly, gadewch i ni cyntaf sydd ei recursively ac yna byddwn yn gwneud hynny iteraidd. Gallwn mewn gwirionedd dim ond ei wneud gyda'n gilydd, gan fod hyn yn mynd i fod yn brin iawn. 

Beth yw fy achos sylfaenol yn mynd i fod? [Myfyrwyr, annealladwy] [Bowden] Felly os (coeden == NULL), yna beth? [Myfyrwyr] Dychwelyd ffug. [Bowden] Else, wel, dwi ddim yn angen y arall. Os oedd fy achos sylfaenol eraill. [Myfyrwyr] Coed yn werth? >> Yeah. Felly os (gwerth == coed> werth. Hysbysiad rydym yn ôl i beidio â * nod, nod ** s? Ni fydd Yn cynnwys angen i chi ddefnyddio ** nod, gan nad ydym yn addasu awgrymiadau. Rydym yn unig yn croesi nhw. Os bydd hynny'n digwydd, yna rydym eisiau dychwelyd yn wir. Arall rydym am i groesi'r plant. Felly, ni allwn resymu ynghylch a phopeth ar y chwith yn llai a phopeth ar y dde yn fwy. Felly beth yw ein cyflwr yn mynd i fod yma - neu, beth ydyn ni'n mynd i'w wneud? [Myfyrwyr, annealladwy] >> Yeah. Dychwelyd yn cynnwys (gwerth, coed-> chwith) neu'n cynnwys (gwerth, coed-> dde). A dyna ni. Ac yn sylwi bod peth gwerthuso byr-cylched, lle os ydym yn digwydd i ddod o hyd i'r gwerth yn y goeden ar y chwith, ni byth angen i edrych ar y goeden gywir. Dyna y swyddogaeth gyfan. Nawr, gadewch i ni ei wneud iteraidd, sydd yn mynd i fod yn llai 'n glws. Byddwn yn cymryd y cychwyn arferol o cyf nod * = goeden. Er (cyf! = NULL). Yn gyflym yn mynd i weld problem. Os cyf - allan yma, os ydym byth yn dorri allan o hyn, yna rydym ni wedi rhedeg allan o bethau i edrych arnynt, felly dychwelyd ffug. Os (cyf-> == gwerth gwerth), yn dychwelyd yn wir. Felly nawr, rydym wedi cyrraedd lle - nid ydym yn gwybod a ydym am fynd i'r chwith neu i'r dde. Felly fympwyol, gadewch i ni dim ond yn mynd i'r chwith. Rydw i wedi rhedeg yn amlwg i fater lle dwi 'di gadael yn llwyr bopeth - Byddaf ond yn edrych ar yr ochr chwith y goeden. Ni fyddaf byth yn gwirio unrhyw beth sydd yn blentyn hawl i unrhyw beth. Sut ydw i'n atgyweiria hon? [Myfyrwyr] Mae'n rhaid i chi gadw golwg ar y chwith a'r dde mewn pentwr. [Bowden] Yeah. Felly, gadewch i ni ei gwneud yn strwythur rhestr, nod * n, ac yna nod ** nesaf? Credaf fod yn gweithio iawn. Rydym yn awyddus i fynd dros y chwith, neu let's - hyd yma. Strwythur = rhestr rhestr, bydd yn dechrau allan ar y rhestr hon strwythur. * Rhestr = null. Felly, mae hynny'n mynd i fod yn rhestr cysylltiedig o subtrees yr ydym wedi hepgor drosodd. Rydym yn mynd i deithio ar draws i'r chwith yn awr, ond gan ein bod yn anochel angen i ni ddod yn ôl i'r dde, Rydym yn mynd i gadw'r ochr dde y tu mewn i strwythur ein rhestr. Yna, bydd gennym new_list neu strwythur, strwythur rhestr *, new_list = malloc (sizeof (rhestr)). Rydw i'n mynd i anwybyddu gwall-wirio hynny, ond dylech edrych i weld os yw'n null. New_list y nod, mae'n mynd i gyfeirio at - oh, dyna pam yr wyf am i fyny yma. Mae'n mynd i gyfeirio at restr strwythur arall. Dyna pa mor cysylltiedig rhestrau gwaith. Mae hyn yr un fath fel rhestr int cysylltiedig ac eithrio ni jyst yn disodli int gyda * nod. Mae'n union yr un fath. Felly new_list, gwerth ein nod new_list, yn mynd i fod yn cyf-> dde. Mae gwerth ein new_list-> nesaf yn mynd i fod yn ein rhestr wreiddiol, ac yna rydym yn mynd i ddiweddaru ein rhestr i gyfeirio at new_list. 

Nawr rydym angen rhyw fath o ffordd o bethau tynnu, fel yr ydym wedi croesi'r Terfynau Chwilio cyfan chwith. Nawr mae angen i ni dynnu pethau allan ohono, fel cyf yn null, nid ydym am i ddim ond dychwelyd ffug. Rydym yn awyddus i dynnu y tu allan yn awr ar ein rhestr newydd. Ffordd gyfleus o wneud hyn - wel, mewn gwirionedd, mae nifer o ffyrdd o wneud hyn. Dylai unrhyw un gennych awgrym? Ble ddylwn i ei wneud hyn neu sut y dylwn wneud hyn? Dim ond cwpl o funudau, ond bydd unrhyw awgrymiadau? Yn hytrach na - un ffordd, yn hytrach na bod yn ein cyflwr tra, nid yr hyn rydym yn hyn o bryd yn edrych arno yw null, yn lle hynny rydym ni'n mynd i barhau i fynd hyd nes ein rhestr ei hun yn null. Felly, os yw ein rhestr yn dod i ben i fyny fod yn null, hynny rydym wedi rhedeg allan o bethau i chwilio am, i chwilio drosodd. Ond mae hynny'n golygu mai'r peth cyntaf yn ein rhestr yn unig yn mynd i fod y nod cyntaf. Bydd Y peth cyntaf fod - ni nid oes angen i weld hynny. Felly rhestr-> Bydd n fydd ein coeden. rhestr-> nesaf yn mynd i fod yn null. Ac yn awr er nad rhestr yn null cyfartal. Cyf yn mynd i dynnu rhywbeth oddi ar ein rhestr. Felly cyf yn mynd i'r rhestr-> gyfartal n. Ac yna rhestr yn mynd i'r rhestr-> gyfartal n, neu restr-> nesaf. Felly gwerth cyf os yn dychwelyd gwerth. Nawr gallwn ychwanegu y ddau ein pwyntydd iawn ac mae ein pwyntydd ar y chwith cyn belled nad ydynt yn null. Down yma, mae'n debyg y dylem fod wedi gwneud hynny yn y lle cyntaf. Os (cyf-> iawn! = NULL) yna rydym yn mynd i osod y nod yn ein rhestr. Os (cyf-> chwith), mae hyn yn ychydig o waith ychwanegol, ond mae'n iawn. Os (cyf-> chwith! = NULL), ac rydym yn mynd i fewnosod y chwith i mewn i'n rhestr cysylltiedig, a dylai hynny fod yn. Rydym yn ailadrodd - cyn belled ag y byddwn wedi rhywbeth yn ein rhestr, mae gennym nod arall i edrych ar. Felly, rydym yn edrych ar y nod, rydym yn datblygu ein rhestr i'r un nesaf. Os yw'r nod yn y gwerth yr ydym yn chwilio amdano, gallwn ddychwelyd yn wir. Arall rhowch ddau subtrees y chwith a dde, cyn belled nad ydynt yn null, yn ein rhestr fel ein bod yn anochel yn mynd drostynt. Felly, os nad oeddent yn null, os yw ein pwyntydd gwreiddiau tynnu sylw at ddau beth, yna ar y dechrau rydym yn tynnu rhywbeth allan felly mae ein rhestr yn dod i ben i fyny fod yn null. Ac yna rydym yn rhoi dau beth yn ôl, felly, yn awr ein rhestr o faint 2. Yna rydym yn mynd i dolen yn ôl i fyny ac rydym yn jyst yn mynd i dynnu, gadewch i ni ddweud, y pwyntydd chwith ein nod gwraidd. A bydd mai dim ond cadw digwydd; byddwn yn y pen draw dolennu dros bopeth. 

Sylwch fod hyn yn llawer mwy cymhleth yn yr ateb ailadroddus. Ac yr wyf wedi dweud sawl gwaith fod yr ateb recursive fel arfer yn lawer yn gyffredin â'r ailadroddol ateb. Yma, mae hyn yn union beth yw'r ateb ailadroddus yn ei wneud. Yr unig newid yw, yn lle ymhlyg defnyddio'r corn, y pentwr rhaglen, fel eich ffordd o gadw golwg ar yr hyn nodau angen i chi ymweld â nhw, nawr mae'n rhaid i chi yn benodol defnyddio rhestr cysylltiedig. Yn y ddau achos eich bod yn cadw golwg ar yr hyn nod dal i fod angen ymweld â hwy. Yn yr achos recursive mae'n haws oherwydd bod pentwr yn cael ei weithredu i chi fel y pentwr rhaglen. Sylwch fod y rhestr hon yn gysylltiedig, mae'n pentwr. Beth bynnag rydym yn unig ei roi ar y corn yn union beth yr ydym yn mynd i dynnu oddi ar y pentwr i ymweld nesaf. Rydym yn allan o amser, ond bydd unrhyw gwestiynau? [Myfyrwyr, annealladwy] [Bowden] Yeah. Felly, os ydym wedi ein rhestr cysylltiedig, ar hyn o bryd yn mynd i gyfeirio at y boi, ac yn awr rydym yn unig yn hyrwyddo ein rhestr cysylltiedig i ganolbwyntio ar y dyn. Rydym yn croesi dros y rhestr cysylltiedig yn y llinell honno. Ac yna mae'n debyg y dylem ryddhau ein rhestr cysylltiedig a phethau unwaith cyn dychwelyd yn wir neu'n anwir, mae angen i ni ailadrodd dros ein rhestr gysylltiedig a bob amser i lawr yma, mi dybiaf, os ydym yn cyf ddim yn iawn yn hafal i, ychwanegu, felly nawr rydym am i ryddhau cyf oherwydd, wel, wnaethon ni llwyr anghofio am y rhestr? Yeah. Felly dyna beth rydym eisiau ei wneud yma. Ble mae'r pwyntydd? Cyf oedd ar y pryd - rydym am i restr strwythur * 10 yn dychwelyd rhestr nesaf. Rhestr am ddim, rhestr = temp. Ac yn yr achos lle byddwn yn dychwelyd wir, mae angen i ailadrodd dros y gweddill ein rhestr cysylltiedig rhyddhau pethau. Y peth braf am yr ateb recursive yn rhyddhau pethau yn unig yn golygu factorings popping oddi ar y pentwr a fydd yn digwydd i chi. Felly, rydym wedi mynd o rywbeth sy'n debyg 3 llinellau o anodd-i-feddwl-am god i rywbeth sydd dipyn llawer mwy anodd-i-feddwl-am linellau o god. Unrhyw mwy o gwestiynau? Mae pob hawl. Rydym yn dda. Hwyl! [CS50.TV]