[Powered by Google Translate] [Sehemu ya 7: Zaidi Starehe] [Rob Bowden] [Chuo Kikuu cha Harvard] [Hii ni CS50] [CS50.TV] Wote haki. Hivyo kama nilivyosema katika barua pepe yangu, hii itakuwa ni sehemu ya binary-mti-intensive. Lakini kuna si kwamba maswali mengi. Hivyo sisi ni kwenda kujaribu na kusogea nje ya kila swali na kuingia kwa undani chungu ya njia zote bora ya kufanya mambo. Hivyo haki ya mwanzo, sisi kupitia michoro ya sampuli ya miti binary na mambo ya ajabu. Hivyo hapa, "Kumbuka kwamba mti binary ina nodes sawa na wale wa orodha wanaohusishwa, isipokuwa badala ya pointer moja kuna mawili: moja kwa ajili ya 'mtoto' kushoto na moja kwa ajili ya 'mtoto' haki. " Hivyo mti binary ni kama orodha zilizounganishwa, ila struct ataenda kuwa na kuyatumia mbili. Kuna trinary miti, ambayo ni kwenda na kuyatumia tatu, kuna N-ary miti, ambayo tu pointer generic kwamba wewe kisha kuwa na malloc kuwa kubwa ya kutosha na kutosha kuyatumia kwa watoto wote iwezekanavyo. Hivyo binary mti hutokea tu kuwa na idadi ya mara kwa mara ya mbili. Kama unataka, unaweza kutoa orodha zilizounganishwa kama mti unary, lakini sidhani mtu yeyote anaiita hiyo. "Chora mchoro masanduku-na-mishale ya nodi binary mti zenye Nate favorite idadi, 7, ambapo kila mtoto ni pointer null. " Hivyo iPad mode. 

Ni kwenda kuwa pretty moja kwa moja. Sisi ni kwenda tu kuwa na node, mimi itabidi kuteka ni kama mraba. Na mimi itabidi kuteka maadili katika hapa. Hivyo thamani kwenda katika hapa, na kisha chini hapa tutaweza kuwa pointer wa kushoto juu ya kushoto na kulia pointer juu ya haki. Na ni mengi sana na hivyo mkataba kuiita kushoto na kulia, majina pointer. Yote haya ni kwenda kuwa null. Hiyo tu kuwa null, na kwamba itakuwa tu kuwa null. Sawa. Hivyo nyuma kwa hapa. "Pamoja na orodha wanaohusishwa, sisi tu alikuwa na kuhifadhi pointer na nodi ya kwanza katika orodha ili kukumbuka nzima wanaohusishwa orodha, au orodha nzima. Aidha, pamoja na miti, sisi tu kuhifadhi pointer na nodi ya moja ili kukumbuka mti mzima. Nodi Hii ni calle 'mzizi' ya mti. Kujenga juu ya mchoro wako kutoka kabla au kuteka moja mpya vile kwamba una maelezo ya masanduku-na-mishale ya mti binary na thamani ya 7, kisha 3 katika kushoto, kisha 9 juu ya haki, na kisha 6 juu ya haki ya 3. " Hebu angalia kama naweza kukumbuka yote ya kwamba katika kichwa changu. Hivyo hii ni kwenda kuwa mizizi yetu hapa. Tutaweza kuwa na baadhi ya pointer mahali fulani, kitu ambacho Tutamwita mizizi, na ni akizungumzia guy. Sasa kufanya nodi mpya, nini tuna, 3 upande wa kushoto? Hivyo nodi mpya na 3, na ni awali pointi null. Mimi itabidi kuweka N. Sasa tunataka kufanya kwamba kwenda upande wa kushoto wa 7. Hivyo sisi kubadili hili pointer sasa kumweka kwa guy. Na sisi kufanya hivyo. Tunataka 9 ya juu hapa ambayo awali tu anasema null. Sisi ni kwenda kubadilisha hii pointer, hatua kwa 9, na sasa tunataka kuweka 6 na haki ya 3. Hivyo ni kwenda - kufanya 6. Na kwamba guy nitawaelekezeni huko. Sawa. Basi hiyo ni wote inauliza tufanye. 

Sasa hebu kwenda juu ya baadhi ya istilahi. Sisi tayari kuongelea kuhusu jinsi mizizi ya mti ni nodi ya juu-wengi katika mti. moja zenye 7. nodes chini ya mti wanaitwa majani. Yoyote ambayo nodi tu ana null kama watoto wake ni jani. Hivyo inawezekana, kama binary yetu ni mti tu nodi moja, kwamba mti ni jani, na hiyo ni yake. "'Urefu' wa mti ni idadi ya humle una kufanya kupata kutoka juu na majani. " Tutaweza kupata ndani, katika pili, tofauti kati ya uwiano na unbalanced binary miti, lakini kwa sasa, urefu wa jumla ya mti huu Naweza kusema ni 3, ingawa kama wewe kuhesabu idadi ya humle una kufanya ili kupata 9, basi ni kweli tu urefu wa 2. Sasa hivi ni unbalanced binary mti, lakini tutaweza aliyesema kuhusu uwiano wakati anapata kuwa muhimu. Hivyo sasa tunaweza kuongea kuhusu nodes katika mti katika suala jamaa na nodes nyingine katika mti. Hivyo basi, tuna wazazi, watoto, ndugu, mababu, na wazao. Wao ni pretty akili ya kawaida, maana yake. Kama sisi kuuliza - wazazi wake. Hivyo kile ni mzazi wa 3? [Wanafunzi] 7. >> Yeah. mzazi ni kwenda tu kuwa kile pointi na wewe. Kisha nini ni watoto wa 7? [Wanafunzi] 3 na 9. >> Yeah. Ona kwamba "watoto" likiwa na maana ya watoto, hivyo 6 bila kuomba, kwa sababu ni kama mjukuu. Lakini basi kama sisi kwenda wazao, ili kile ni wazao wa 7? [Wanafunzi] 3, 6 na 9. >> Yeah. wazao wa nodi mzizi ni kwenda kuwa kila kitu katika mti, isipokuwa labda nodi mizizi yenyewe, kama huna kufikiria kwamba mtoto. Na hatimaye, mababu, hivyo ni kinyume mwelekeo. Kwa hiyo kile ni mababu wa 6? [Wanafunzi] 3 na 7. >> Yeah. 9 si pamoja. Ni tu moja kwa moja ukoo nyuma mizizi ni kwenda kuwa baba zenu. 

"Sisi tunasema kwamba mti binary 'kuamuru' kama kwa kila nodi katika mti, yote ya wazao wake kwa upande wa kushoto na maadili mdogo na wote wa wadogo juu ya haki na maadili zaidi. Kwa mfano, mti hapo juu ni amri lakini siyo tu inawezekana kuamuru utaratibu. " Kabla ya sisi kupata kwamba, kuamuru mti binary pia anajulikana kama mti binary tafuta. Hapa sisi kutokea kwa kuwa kuiita kuamuru binary mti, lakini sijawahi kusikia ni kuitwa kuamuru binary mti kabla, na juu ya chemsha bongo sisi ni zaidi ya uwezekano wa kuweka binary tafuta mti. Wao ni moja na sawa, na ni muhimu wewe kutambua tofauti kati ya mti na kisha binary mti tafuta. mti binary ni mti pointi kwa mambo mawili. Nodi ya kila pointi kwa mambo mawili. Hakuna hoja kuhusu maadili ambayo inaelekeza katika. Hivyo kama zaidi hapa, tangu ni binary tafuta mti, tunajua kwamba kama sisi kwenda kushoto ya 7, basi wote wa maadili ambayo tunaweza pengine kufikia kwa kwenda kushoto ya 7 na kuwa chini ya 7. Ona kwamba maadili yote chini ya 7 ni 3 na 6. Wale wote ni wa kushoto wa 7. Kama sisi kwenda kulia wa 7, kila kitu kina kuwa kubwa kuliko 7, hivyo 9 ni haki ya 7, hivyo sisi ni nzuri. Hii si kesi kwa mti binary, kwa mti wa kawaida kisha tunaweza tu 3 saa ya juu, 7 wa kushoto, 9 ya kushoto ya 7; hakuna kuagiza maadili wowote. Sasa, sisi si kweli kufanya hivyo kwa sababu ni tedious na unnecessary, lakini "kujaribu kuteka kama miti mingi kuamuru kama unaweza kufikiri ya kutumia namba 7, 3, 9, na 6. Ngapi mipangilio tofauti ni huko? Je, ni urefu wa kila mmoja? " 

Tutaweza kufanya wanandoa, lakini wazo kuu ni, hii ni katika hakuna njia ya uwakilishi wa kipekee wa mti binary zenye maadili haya. Wote tunahitaji ni baadhi mti binary kwamba ina 7, 3, 6, na 9. Mwingine iwezekanavyo moja halali itakuwa ni mzizi 3, kwenda kushoto na ni 6, kwenda kushoto na ni 7, kwenda kushoto na ni 9. Hiyo ni kikamilifu halali binary tafuta mti. Ni hayasaidii sana, kwa sababu ni kama tu orodha wanaohusishwa na wote wa kuyatumia haya ni null. Lakini ni mti halali. Yeah? [Mwanafunzi] Je, si maadili kuwa mkuu juu ya haki? Au ni hii -? >> Haya mimi maana ya kwenda njia nyingine. Kuna pia - yeah, hebu kubadili hilo. 9, 7, 6, 3. Nzuri samaki. Bado ina kutii kile tafuta binary mti zinatakiwa kufanya. Kwa hiyo kila kitu kwa upande wa kushoto ina kuwa chini ya nodi wowote. Tunaweza tu hoja, kusema, hii 6 na kuiweka hapa. Hapana, hatuwezi. Kwa nini mimi kuendelea kufanya hivyo? Hebu kufanya - hapa ni 6, hapa ni 7, 6 pointi 3. Hii bado ni halali binary tafuta mti. Je, ni makosa kama mimi - hebu angalia kama naweza kuja na mpangilio. Yeah, okay. Hiyo ni nini kibaya na mti? Mimi nadhani nimekuwa tayari kupeni dokezo kwamba kuna kitu kibaya. Kwa nini mimi kuendelea kufanya hivyo? Sawa. Hii inaonekana busara. Kama sisi kuangalia kila node, kama 7, kisha ya kushoto ya 7 ni 3. Hivyo tuna 3, jambo haki ya 3 ni 6. Na kama ukiangalia 6, jambo haki ya 6 ni 9. Hivyo kwa nini hii si halali binary tafuta mti? [Wanafunzi] 9 bado ni ya kushoto ya 7. >> Yeah. Ni lazima kuwa kweli kwamba wote maadili unaweza uwezekano wa kufikia kwa kwenda kushoto wa 7 ni chini ya 7. Kama sisi kwenda kushoto ya 7, tunapata 3 na bado tunaweza kupata 6, bado tunaweza kupata 9, lakini kwa kuwa wamekwenda chini ya 7, hatupaswi kuwa na uwezo wa kupata idadi hiyo ni kubwa kuliko 7. Hivyo hii si halali binary tafuta mti. 

Ndugu yangu kweli alikuwa swali mahojiano kwamba alikuwa kimsingi hii, tu code up kitu kuhalalisha kama mti ni binary tafuta mti, na hivyo jambo la kwanza alivyofanya mara tu kuangalia kuona ikiwa kushoto na kulia ni sahihi, na kisha iterate chini huko. Lakini huwezi kufanya hivyo; una kuweka wimbo ukweli kwamba sasa kwamba mimi tumeenda kushoto ya 7, kila kitu katika hii subtree lazima kiwe chini ya 7. algorithm sahihi inahitaji kuweka wimbo ya mipaka ya maadili inaweza uwezekano kuanguka in Sisi si kwenda kwa njia ya wote. Kuna ni nzuri upprepning uhusiano, ingawa sisi si wamezipata kwa wale, au sisi si kupata wale, kufafanua jinsi kuna kweli ni. Hivyo kuna 14 ya yao. wazo la jinsi gani kufanya hivyo mathematically ni kama, unaweza kuchukua yoyote moja kuwa nodi mizizi, na kisha kama mimi pick 7 kuwa mizizi nodi, basi kuna, kusema, baadhi idadi ambayo yanaweza kwenda kuwa nodi wangu wa kushoto, na kuna baadhi ya idadi ambayo inaweza kuwa nodi wangu wa kulia, lakini kama mimi n idadi jumla, basi kiasi kwamba anaweza kwenda kushoto pamoja na kiasi cha kwamba anaweza kwenda kulia ni n - 1. Hivyo idadi iliyobaki, wanatakiwa kuwa na uwezo wa kwenda aidha kwa upande wa kushoto au kulia. Inaonekana vigumu kuwa, kama mimi kuweka 3 kwanza kisha kila kitu ina kwenda kushoto, lakini kama mimi kuweka 7, basi baadhi ya mambo yanaweza kwenda kushoto na baadhi ya mambo yanaweza kwenda kulia. Na kwa ''3 kwanza mimi maana kila kitu wanaweza kwenda kulia. Ni kweli, wewe tu na kufikiri juu yake kama, mambo mangapi unaweza kwenda kwenye ngazi ya pili ya mti. Na inakuja nje kuwa 14; au unaweza kuteka wote, na kisha utapata 14. 

Tukirudi hapa, "Aliamrisha miti binary ni baridi kwa sababu tunaweza kutafuta njia yao katika njia sawa sana kutafuta juu ya safu Iliyopangwa. Kwa kufanya hivyo, sisi kuanza katika mizizi na kazi njia yetu chini ya mti kuelekea majani, kuangalia maadili ya kila nodi dhidi ya maadili sisi ni kwa ajili ya kutafuta. Kama thamani ya nodi ya sasa ni chini ya thamani sisi ni kuangalia kwa, kwenda karibu na mtoto nodi wa kulia. Vinginevyo, unaweza kwenda kwa mtoto nodi la kushoto. Katika hatua nyingine, wewe utakuwa aidha kupata thamani wewe ni kuangalia kwa, au utasikia kukimbia katika null, kuonyesha thamani si katika mti. " Nina redraw mti tulikuwa kabla; kwamba itabidi kuchukua pili. Lakini tunataka kuangalia juu kama 6, 10, na 1 ni katika mti. Hivyo ilikuwa ni nini, 7, 9, 3, 6. Sawa. idadi unataka kuangalia juu, tunataka kuangalia up 6. Jinsi gani hii algorithm kazi? Naam, sisi pia kuwa baadhi ya pointer mizizi ya mti wetu. Na tunataka kwenda kwa mizizi na kusema, hii ni sawa na thamani thamani sisi ni kwa ajili ya kutafuta? Hivyo sisi ni kuangalia kwa 6, hivyo si sawa. Hivyo sisi kuendelea, na sasa tunasema, sawa, hivyo ni chini ya 6 7. Je inamaanisha tunataka kwenda upande wa kushoto, au kufanya sisi unataka kwenda upande wa kulia? [Mwanafunzi] kushoto. >> Yeah. Ni kwa kiasi kikubwa rahisi, wote una kufanya ni kuteka moja iwezekanavyo nodi ya mti na kisha wewe don't - badala ya kujaribu kufikiri katika kichwa yako, sawa, kama ni kidogo, je, mimi kwenda kushoto au kwenda kulia, kuangalia tu picha hii, ni wazi kwamba mimi kwenda kushoto ikiwa nodi hii ni mkubwa kuliko thamani ya kuwa mimi nina kuangalia kwa. Hivyo wewe kwenda kushoto, sasa mimi nina saa 3. Nataka - 3 ni chini ya thamani nina kuangalia kwa, ambayo ni 6. Hivyo sisi kwenda kulia, na sasa mimi kuishia katika 6, ambayo ni thamani nina kuangalia kwa, hivyo mimi kurudi kweli. thamani ijayo mimi naenda kwa kuangalia ni 10. Sawa. Hivyo 10, sasa, ni kwenda - kukatwa kwamba - kwenda kufuata mizizi. Sasa, 10 ni kwenda kuwa mkuu zaidi kuliko 7, hivyo nataka kuangalia kwa haki. Mimi naenda kuja hapa, 10 ni kwenda kuwa mkuu zaidi kuliko 9, hivyo mimi nina kwenda unataka kuangalia kwa haki. Mimi kuja hapa, lakini zaidi ya hapa sasa mimi nina katika null. Nifanye nini kama mimi hit null? [Mwanafunzi] Kurudi uongo? >> Yeah. Sikuweza kupata 10. 1 ni kwenda kuwa kesi karibu kufanana, isipokuwa tu kwenda kuwa flipped; badala ya kuangalia chini upande wa kulia, mimi nina kwenda kuangalia chini upande wa kushoto. 

Sasa nadhani sisi kweli kupata code. Hapa ni wapi - kufungua appliance CS50 na navigate njia yako huko, lakini pia unaweza tu kufanya hivyo katika nafasi. Ni pengine bora ya kufanya hivyo katika nafasi, kwa sababu tunaweza kufanya kazi katika nafasi. "Kwanza tutaweza haja aina mpya ufafanuzi kwa nodi binary mti zenye maadili int. Kutumia boilerplate typedef chini, kuunda aina mpya ya ufafanuzi kwa nodi katika mti binary. Kama wewe kukwama. . . "Blah, blah, blah Sawa.. Hivyo basi, tulenge boilerplate hapa, typedef struct nodi, na nodi. Yeah, okay. Kwa hiyo kile ni mashamba tunakwenda unataka katika nodi zetu? [Mwanafunzi] Int na kisha kuyatumia mbili? >> Int thamani, kuyatumia mbili? Je, mimi kuandika kuyatumia? [Mwanafunzi] Struct. >> Mimi lazima zoom in Yeah, hivyo struct nodi * kushoto, na struct nodi * haki. Na kumbuka mjadala toka mara ya mwisho, kwamba hii haina mantiki, hii haina mantiki, hii haina mantiki. Unahitaji kila kitu huko ili kufafanua hili struct ya kujirudia. Sawa, hivyo kwamba ni nini mti wetu ni kwenda kuangalia kama. Kama sisi alifanya mti trinary, basi nodi ili kuangalia kama B2 B1, struct nodi * B3, ambapo b ni tawi - kweli, nimekuwa zaidi waliposikia kushoto, katikati, kulia, lakini chochote. Sisi tu huduma kuhusu binary, hivyo haki, kushoto. "Sasa kutangaza kimataifa nodi * variable kwa mizizi ya mti." Hivyo sisi hamtaweza kufanya hivyo. Ili kufanya mambo kidogo vigumu zaidi na zaidi ya jumla, hatutakuwa na kimataifa nodi kutofautiana. Badala yake, katika kuu sisi kutangaza mambo yetu yote ya nodi, na hiyo ina maana kwamba chini, wakati sisi kuanza mbio yetu ina kazi na Insert yetu kazi, badala ya ina yetu inafanya kazi tu kwa kutumia hii ya kimataifa nodi variable, sisi itawabidi kuchukua kama hoja mti kwamba tunataka ni mchakato. Baada ya variable kimataifa ilitakiwa kufanya mambo rahisi. Sisi ni kwenda kufanya mambo magumu. Sasa kuchukua dakika au hivyo tu kufanya jambo la aina hii, ambapo ndani ya kuu unataka kujenga mti huu, na kwamba wote unataka kufanya. Jaribu na kujenga mti huu katika kazi yako kuu. 

Sawa. Hivyo hawana hata kuwa yalijengwa mti njia nzima bado. Lakini mtu yeyote kuwa kitu ningeweza kuvuta up kuonyesha jinsi mtu anaweza kuanza kujenga mti vile? [Mwanafunzi] Mtu wa banging, kujaribu kupata nje. [Bowden] Yeyote starehe na mti ujenzi yao? [Mwanafunzi] Uhakika. Ni si kufanyika. >> Ni faini. Tunaweza tu kumaliza - oh, unaweza kuokoa yake? Hooray. Hivyo hapa tuna - oh, mimi nina kidogo kukatwa. Am I zoomed katika? Zoom katika, tembeza nje. >> Nina swali. >> Yeah? [Mwanafunzi] Wakati unaweza kufafanua struct, ni mambo kama initialized kwa kitu chochote? [Bowden] No >> Sawa. Hivyo ingekuwa initialize - [Bowden] No Wakati unaweza kufafanua, au wakati kutangaza struct, si initialized na default; ni kama tu kama wewe kutangaza int. Ni hasa kitu kimoja. Ni kama kila moja ya mashamba yake binafsi unaweza kuwa na thamani ya takataka ndani yake. >> Na inawezekana define - au kutangaza struct katika njia ambayo haina initialize yao? [Bowden] Ndiyo. Hivyo, njia ya mkato initialization syntax ni kwenda kuangalia kama - Kuna njia mbili za tunaweza kufanya hivyo. Nadhani tunapaswa kukusanya ni kufanya Clang uhakika pia gani hii. utaratibu wa hoja kwamba anakuja katika struct, kuweka kama utaratibu wa hoja ndani ya hizi braces curly. Hivyo kama unataka initialize kwa 9 na kushoto kuwa batili na kisha haki itakuwa batili, itakuwa 9, null, null. mbadala ni, na mhariri hapendi hii syntax, na hivyo anadhani nataka block mpya, lakini mbadala ni kitu kama - hapa, mimi itabidi kuweka kwenye mstari mpya. Unaweza kupanga kusema, mimi kusahau syntax halisi. Hivyo unaweza kupanga kuyashughulikia kwa jina, na kusema, . C, au. Thamani = 9, kushoto. = Null. Mimi guessing haya haja ya kuwa na koma. . Haki = null, hivyo njia hii huna kweli wanahitaji kujua utaratibu wa struct, na wakati wewe ni kusoma, ni zaidi ya wazi kuhusu nini thamani ni kuwa initialized kwa. 

Hii hutokea kwa kuwa moja ya mambo ambayo - hivyo, kwa sehemu kubwa, C + + ni superset ya C. Unaweza kuchukua C code, hoja ni juu ya C + +, na ni lazima kukusanya. Hii ni moja ya mambo ambayo C + + hakiingiliani, hivyo watu huwa si ya kufanya hivyo. Mimi sijui kama hiyo ni sababu tu watu huwa si ya kufanya hivyo, lakini kesi ambapo mimi zinahitajika kutumia ni zinahitajika kufanya kazi na C + + na hivyo sikuweza kutumia hii. Mfano mwingine wa kitu ambacho hana kazi na C + + ni jinsi malloc anarudi "Kosa *," kitaalam, lakini unaweza tu kusema Char * x = malloc chochote, na itakuwa moja kwa moja kutupwa katika * Char. Kwamba kutupwa moja kwa moja haina kutokea katika C + +. Hiyo si kukusanya, na ungependa waziwazi haja ya kusema Char *, malloc, chochote, kuwatupia * Char. Kuna mambo mengi ambayo C na C + + hawakubaliani juu, lakini wale ni mbili. Hivyo tutaweza kwenda kwa syntax hii. Lakini hata kama sisi hawakuwa kwenda kwa syntax kwamba, nini ni - inaweza kuwa na makosa na hili? [Mwanafunzi] mimi hawana haja ya dereference yake? >> Yeah. Kumbuka kwamba mshale ana dereference thabiti, na hivyo wakati tuko tu kushughulika na struct, tunataka kutumia. kupata saa ndani ya uwanja wa struct. Na wakati tu sisi kutumia mshale ni wakati tunataka kufanya - vizuri, mshale ni sawa na - hiyo ndiyo ingekuwa na maana kama mimi kutumika mshale. Njia zote mshale ni, dereference hii, sasa mimi nina katika struct, na mimi tunaweza kupata shamba. Aidha kupata shamba moja kwa moja au dereference na kupata shamba - Nadhani hii inapaswa kuwa thamani. Lakini hapa mimi nina kushughulika na struct tu, si pointer struct, na hivyo siwezi kutumia mshale. Lakini jambo la aina hii tunaweza kufanya kwa ajili nodes wote. Oh, Mungu wangu. Hii ni 6, 7, na 3. Kisha tunaweza kuanzisha matawi katika mti yetu, tunaweza kuwa 7 - tunaweza kuwa, kushoto wake wanapaswa kumweka kwa 3. Hivyo ni jinsi gani sisi kufanya hivyo? [Wanafunzi, unintelligible] >> Yeah. anuani ya node3, na kama hakuwa na anuani, basi tu bila kukusanya. Lakini kumbuka kwamba hawa ni kuyatumia na nodi ijayo. haki lazima kumweka kwa 9, na 3 wanapaswa kumweka juu ya haki ya 6. Nadhani hii ni kuweka wote. Maoni yoyote au maswali? [Mwanafunzi, unintelligible] mzizi ni kwenda kuwa 7. Tunaweza tu kusema nodi * PTR = au mizizi, = & node7. 

Kwa madhumuni yetu, sisi ni kwenda kuwa kushughulika na Insert, hivyo sisi ni kwenda unataka kuandika kazi na kuingiza ndani ya mti huu binary na Insert ni inevitably kwenda kuwaita malloc kujenga nodi mpya kwa ajili ya mti huu. Basi mambo ni kwenda kupata messy na ukweli kwamba baadhi nodes sasa ni juu ya stack na nodes nyingine ni kwenda kuishia juu ya lundo wakati sisi Insert yao. Hii ni kikamilifu halali, lakini kwa sababu tu sisi ni uwezo wa kufanya hivyo kwenye stack ni kwa sababu ni mfano vile contrived kwamba sisi kujua mti zinatakiwa kuwa yalijengwa kama 7, 3, 6, 9. Kama hatukuwa na hii, basi tusingekuwa na malloc katika nafasi ya kwanza. Kama tutaweza kuona kidogo baadaye, sisi lazima malloc'ing. Hivi sasa ni kikamilifu busara ya kuweka kwenye stack, lakini hebu kubadili hili kwa utekelezaji malloc. Hivyo kila moja ya haya ni sasa kwenda kuwa kitu kama nodi * node9 = malloc (sizeof (node)). Na sasa sisi itawabidi kufanya hundi yetu. kama (node9 == null) - sikutaka kwamba - kurudi 1, na kisha tunaweza kufanya node9-> kwa sababu sasa ni pointer, thamani = 6, node9-> kushoto = null, node9-> kulia = null, na sisi itawabidi kufanya hivyo kwa kila nodes hizo. Hivyo badala yake, hebu kuiweka ndani ya kazi tofauti. Hebu kuiita nodi * build_node, na hii ni sawa na kiasi fulani APIs sisi kutoa kwa Huffman coding. Sisi kukupa kazi initializer kwa mti na deconstructor "kazi" kwa ajili ya miti na wale sawa kwa misitu. 

Hivyo hapa tunakwenda kuwa na kazi initializer tu kujenga nodi kwa ajili yetu. Na ni kwenda kuangalia kiasi pretty hasa kama hii. Na mimi hata kwenda kuwa wavivu na si kubadili jina la kutofautiana, ingawa node9 haina mantiki tena. Oh, mimi nadhani thamani node9 wa haifai kuwa 6. Sasa tunaweza kurudi node9. Na hapa sisi lazima kurudi null. Kila mtu kukubaliana kwamba kazi kujenga-a-nodi? Hivyo sasa tunaweza kuwaita tu kwamba kujenga yoyote ya nodi thamani aliyopewa na kuyatumia null. Sasa tunaweza kuwaita kuwa, tunaweza kufanya nodi * node9 = build_node (9). Na hebu kufanya. . . 6, 3, 7, 6, 3, 7. Na sasa tunataka kuanzisha kuyatumia huo, ila sasa kila kitu tayari katika suala la kuyatumia hivyo hakuna haja tena ya anuani. Sawa. Basi nini jambo la mwisho nataka kufanya? Kuna kosa-kuangalia kwamba mimi si kufanya. Gani kujenga nodi kurudi? [Mwanafunzi, unintelligible] >> Yeah. Kama malloc alishindwa, hivyo itabidi kurudi null. Hivyo nina kwenda kwa lazily kuiweka chini hapa badala ya kufanya kwa kila hali. Kama (node9 == null, au - hata rahisi, hii ni sawa tu kama si node9. Hivyo kama si node9, au si node6, au si node3, au si node7, kurudi 1. Labda sisi lazima magazeti malloc wameshindwa, au kitu. [Mwanafunzi] Je uongo sawa null vile vile? [Bowden] yoyote thamani sifuri ni uongo. Hivyo ni thamani null sifuri. Zero ni thamani sifuri. Uongo ni thamani sifuri. Yoyote - pretty much tu 2 maadili sifuri ni batili na sifuri, uongo ni hash hufafanuliwa kama sifuri. Hiyo pia inatumika kama hatuwezi kutangaza variable kimataifa. Kama sisi tulikuwa na nodi * mizizi hapa juu, basi - kitu kizuri kuhusu vigezo kimataifa ni kwamba wao daima kuwa na thamani ya awali. Hiyo si kweli wa kazi, jinsi ya ndani ya hapa, kama tuna, kama, nodi * au x nodi. Sisi hatuna wazo nini x.value, x.whatever, au tunaweza magazeti yao na wanaweza kuwa holela. Hiyo si kweli ya vigezo kimataifa. Hivyo nodi mizizi au x nodi. By default, kila kitu kilicho duniani, kama si wazi initialized kwa thamani baadhi, ina thamani ya sifuri kama thamani yake. Hivyo hapa, nodi * mizizi, sisi si wazi initialize kwa kitu chochote, hivyo default thamani yake itakuwa null, ambayo ni thamani ya sifuri ya kuyatumia. thamani default ya x ni kwenda maana kwamba x.value ni sifuri, x.left ni null, na x.right ni null. Hivyo kwa vile ni struct, wote wa mashamba ya struct itakuwa sifuri maadili. Hatuna haja ya kutumia kwamba hapa, ingawa. [Mwanafunzi] structs ni tofauti kuliko vigezo vingine, na vigezo vingine ni takataka maadili, haya ni ya zeros? [Bowden] Nyengine maadili pia. Hivyo katika x, x itakuwa sifuri. Kama ni katika upeo wa kimataifa, ina thamani ya awali. >> Sawa. [Bowden] Ama thamani ya awali wewe akampa au sifuri. Nadhani kwamba inachukua huduma ya yote haya. 

Sawa. Hivyo sehemu ya pili ya swali anauliza, "Sasa tunataka kuandika kazi kuitwa ina kwa mfano wa bool ina thamani int. " Sisi si kwenda kufanya bool ina thamani int. Mfano wetu ni kwenda kuangalia kama bool ina (thamani int. Na kisha sisi ni pia kwenda kupita mti kwamba ni lazima kuangalia kuona kama ana kwamba thamani. Hivyo nodi * mti). Sawa. Na kisha tunaweza kuiita na kitu kama, labda tutaweza wanataka printf au kitu. Ina 6, mizizi yetu. Kwamba lazima kurudi moja, au kweli, ambapo ina 5 mzizi lazima kurudi uongo. Hivyo kuchukua pili kutekeleza hili. Unaweza kufanya hivyo aidha iteratively au recursively. Jambo zuri kuhusu njia tumekuwa kuweka mambo juu ni kwamba ni kunafaa kwa ufumbuzi yetu ya kujirudia rahisi kuliko njia ya kimataifa-variable alivyofanya. Kwa sababu kama sisi tu ina thamani int, basi hatuna njia ya recursing chini subtrees. Tunataka kuwa na tofauti msaidizi kazi kwamba recurses chini subtrees kwa ajili yetu. Lakini tangu tumekuwa iliyopita ni kuchukua mti kama hoja, ambayo ni lazima daima wamekuwa katika nafasi ya kwanza, sasa tunaweza recurse kwa urahisi zaidi. Hivyo iterative au kujirudia, tutaweza kwenda juu ya wote, lakini tutaweza kuona kwamba ncha ya kujirudia up kuwa rahisi kabisa. Sawa. Je, mtu yeyote kuwa na kitu tunaweza kufanya kazi na? 

[Mwanafunzi] Mimi nimepata iterative ufumbuzi. >> Sawa, iterative. Okay, hii inaonekana ni nzuri. Hivyo, wanataka kutembea kwetu kwa njia hiyo? [Mwanafunzi] Uhakika. Basi, mimi kuweka variable temp kupata nodi ya kwanza ya mti. Na kisha mimi tu looped kupitia wakati temp haina null sawa, hivyo wakati bado alikuwa katika mti, mimi nadhani. Na kama thamani ni sawa na thamani ya kwamba ni temp akizungumzia, kisha kuirudisha kwamba thamani. Vinginevyo, ni hundi kama ni upande wa kulia au kushoto. Kama umewahi kupata hali ambapo hakuna mti zaidi, kisha kuirudisha - ni exits kitanzi na anarudi uongo. [Bowden] Sawa. Hivyo kwamba inaonekana nzuri. Mtu yeyote kuwa maoni yoyote juu ya kitu chochote? Sina usahihi maoni wakati wote. Jambo moja tunaweza kufanya ni hii guy. Oh, ni kwenda longish kidogo. Mimi itabidi kurekebisha up. Sawa. 

Kila mmoja anapaswa kukumbuka jinsi ternary kazi. Kuna dhahiri imekuwa Quizzes katika kipindi cha kwamba kukupa kazi pamoja na operator ternary, na kusema, kutafsiri hii, kufanya kitu ambacho si kutumia ternary. Hivyo hii ni kesi ya kawaida sana ya wakati mimi kudhani kutumia ternary, ambapo kama hali baadhi kuweka variable na kitu, mwingine kuweka kwamba variable sawa na kitu kingine. Hiyo ni kitu ambacho mara nyingi sana inaweza kubadilishwa katika aina hii ya jambo ambapo kuweka kwamba kutofautiana kwa hii - au, vizuri, hii ni kweli? Kisha hii, pengine hii. [Mwanafunzi] moja ya kwanza ni kama kweli, haki? [Bowden] Yeah. njia ya mimi daima kusoma ni, temp sawa thamani kubwa zaidi kuliko thamani temp, basi hii, pengine hii. Ni kuuliza swali. Je, ni kubwa? Kisha kufanya jambo la kwanza. Mwingine kufanya kitu cha pili. Mimi daima karibu - koloni, mimi tu - katika kichwa changu, mimi kusoma kama mwingine. 

Je, mtu yeyote kuwa na ufumbuzi kujirudia? Sawa. Hii moja tunakwenda - inaweza tayari kuwa kubwa, lakini sisi ni kwenda kufanya ni bora zaidi. Hii ni pretty kiasi sawa exact wazo. Ni tu, vizuri, unataka kueleza? [Mwanafunzi] Uhakika. Hivyo sisi ni kuhakikisha kwamba mti si null kwanza, kwa sababu kama mti ni null basi ni kwenda na kurudi uongo kwa sababu sisi si kupatikana. Na kama bado kuna mti, tunaingia katika - sisi kwanza kuangalia kama thamani ni nodi sasa. Kurudi kweli kama ilivyo, na kama si sisi recurse upande wa kushoto au kulia. Je, kwamba sauti sahihi? >> MM-hmm. (Mkataba) Hivyo taarifa kwamba hii ni karibu - kimuundo ni sawa na ufumbuzi iterative. Ni tu kwamba badala ya recursing, tulikuwa na kitanzi wakati. Na kesi ya msingi hapa ambapo mti haina null sawa ilikuwa hali ya chini ambayo sisi kuvunja nje ya kitanzi wakati. Wao ni sawa sana. Lakini sisi ni kwenda kuchukua hatua hii moja zaidi. Sasa, sisi kufanya kitu kimoja hapa. Angalia tuko kurudi kitu kimoja katika wote wa mistari haya, isipokuwa kwa moja hoja ni tofauti. Hivyo sisi ni kwenda kufanya kwamba katika ternary. I hit chaguo kitu, na alifanya ishara. Sawa. Hivyo sisi ni kwenda na kurudi ina kuwa. Hii ni kupata kuwa nyingi mistari, vizuri, zoomed katika ni. Kawaida, kama kitu Stylistic, sidhani watu wengi kuweka nafasi baada ya mshale, lakini mimi nadhani kama wewe ni thabiti, ni faini. Kama thamani ni chini ya thamani ya mti, tunataka recurse kushoto mti, mwingine tunataka recurse juu ya haki ya mti. Hivyo kwamba ilikuwa hatua moja ya kufanya kuangalia hii ndogo. Hatua mbili za kufanya kuangalia hii ndogo ndogo - tunaweza kutenganisha hii kwa mistari mingi. Sawa. Hatua mbili za kufanya ni kuangalia ni ndogo hapa, hivyo kurudi thamani sawa na mti thamani, au ina chochote. 

Hili ni jambo muhimu. Mimi nina uhakika kama yeye alisema ni wazi katika darasa, lakini ni wito mfupi-mzunguko tathmini. Wazo hapa ni thamani == mti thamani. Kama hiyo ni kweli, basi hii ni kweli, na tunataka 'au' kuwa na chochote ni zaidi ya hapa. Hivyo bila hata kufikiria juu ya chochote ni zaidi ya hapa, kile ni usemi mzima kwenda na kurudi? [Mwanafunzi] Kweli? >> Yeah, kwa sababu ya kweli ya kitu chochote, or'd - au kweli or'd na kitu chochote ni lazima kweli. Hivyo kwa haraka kama sisi kuona kurudi thamani = mti thamani, sisi ni kwenda tu kurudi kweli. Si hata kwenda recurse zaidi ina chini ya mstari. Tunaweza kuchukua hatua hii moja zaidi. Kurudi mti haina null sawa na hii yote. Ni alifanya hivyo kazi moja-line. Hii pia ni mfano wa tathmini mfupi mzunguko. Lakini sasa ni wazo sawa - badala ya - hivyo kama mti haina sawa null - au, vizuri, kama mti gani null sawa, ambayo ni kesi mbaya, kama mti sawa null, basi hali ya kwanza ni kwenda kuwa uongo. Hivyo uongo anded na kitu chochote ni kwenda kuwa nini? [Mwanafunzi] Uongo. >> Yeah. Hii ni nusu nyingine ya tathmini short-mzunguko, ambapo kama mti haina sawa null, basi sisi si kwenda hata kwenda - au kama mti gani null sawa, basi sisi si kwenda kufanya thamani == mti thamani. Sisi ni kwenda tu mara moja kurudi uongo. Ambayo ni muhimu, kwani kama ilivyokuwa si mfupi-mzunguko kutathmini, basi kama mti gani null sawa, hii hali ya pili ni kwenda kosa seg, kwa sababu mti-> thamani dereferencing null. Basi hiyo ni kwamba. Wanaweza kufanya hili - kuhama mara moja zaidi. Hili ni jambo la kawaida sana pia, si kufanya hii line moja na hili, lakini ni jambo la kawaida katika hali, labda si haki hapa, lakini kama (mti = null!, na mti-> thamani == thamani), kufanya chochote. Hii ni hali ya kawaida sana, ambapo badala ya kuwa kuvunja hii katika ikiwa mbili, ambapo kama, ni null mti? Okay, siyo null, hivyo sasa ni thamani mti sawa na thamani? Je hii. Badala yake, hali hii, hii kamwe seg kosa sababu itakuwa kuvunja nje kama hii hutokea kwa kuwa null. Naam, mimi nadhani kama mti yako ni pointer kabisa batili, bado inaweza seg kosa, lakini haiwezi seg kosa kama mti ni null. Kama walikuwa null, ingekuwa kuvunja nje kabla ya milele dereferenced pointer katika nafasi ya kwanza. [Mwanafunzi] Je hii inayoitwa wavivu tathmini? 

[Bowden] tathmini Lazy ni jambo tofauti. Tathmini wavivu ni zaidi kama wewe kuuliza kwa thamani, kuuliza kwa mahesabu ya thamani, aina, lakini huna haja ya mara moja. Hivyo mpaka wewe kweli haja yake, si tathmini. Hii si hasa kitu kimoja, lakini katika pset Huffman, inasema kwamba sisi "lazily" kuandika. sababu sisi kufanya hivyo ni kwa sababu sisi ni kweli buffering kuandika - hatutaki kuandika bits mmoja kwa wakati, au ka mmoja kwa wakati, sisi badala wanataka kupata chunk ya ka. Kisha mara moja tuna chunk ya ka, basi tutaweza kuandika ni nje. Hata kama wewe ni kuuliza kuandika - na fwrite na fread kufanya aina moja ya kitu. Wao buffer wasomaji wako na anaandika. Hata kama wewe ni kuuliza kuandika mara moja, labda si. Na huwezi kuwa na uhakika kwamba mambo yanaenda kuwa imeandikwa mpaka wewe piga hfclose au chochote ni, ambayo kisha anasema, sawa, mimi nina kufunga faili yangu, kwamba maana ningependa bora uandike kila kitu Sikuwaandikia bado. Ni hakuna haja ya kuandika kila kitu nje mpaka wewe ni kufunga faili, na kisha inahitaji. Basi hiyo ni kile tu wavivu - waits mpaka ina kutokea. Hii - kuchukua 51 na utasikia uende ndani yake kwa undani zaidi, kwa sababu OCaml na kila kitu katika 51, kila kitu ni recursion. Hakuna ufumbuzi iterative, kimsingi. Kila kitu ni recursion, na tathmini wavivu ni kwenda kuwa muhimu kwa ajili ya kura ya mazingira ambapo, kama hakuwa na lazily kutathmini, kwamba ingekuwa na maana - Mfano ni mito, ambayo ni kubwa kwa muda mrefu. Katika nadharia, unaweza kufikiria idadi ya asili kama mkondo wa 1-2-3-4-5-6-7, Hivyo lazily tathmini mambo ni faini. Nikisema mimi nataka namba kumi, kisha naweza kutathmini hadi idadi ya kumi. Kama mimi nataka namba mia, naweza kutathmini hadi idadi mia. Bila tathmini wavivu, basi ni kwenda kujaribu kutathmini idadi yote mara moja. Wewe ni kutathmini idadi kubwa wengi, na kwamba si tu iwezekanavyo. Hivyo kuna mengi ya mazingira ambapo wavivu tathmini ni tu muhimu kwa kupata mambo ya kufanya kazi. 

Sasa tunataka kuandika Insert ambapo Insert ni kwenda kuwa vile vile kubadilisha katika ufafanuzi wake. Hivyo sasa hivi ni bool Insert (int thamani). Sisi ni kwenda na mabadiliko ya kwamba ili Insert bool (int thamani, nodi * mti). Sisi ni kweli kwenda na mabadiliko ya kwamba tena katika kidogo, tutaweza kuona nini. Na hebu hoja build_node, tu kwa ajili ya heck yake, juu Insert hivyo hatuna kuandika mfano kazi. Ambayo ni dokezo kwamba utaenda kuwa na kutumia build_node katika Insert. Sawa. Chukua dakika kwa ajili hiyo. Nadhani mimi kuokolewa marekebisho kama unataka kuvuta kutoka kwamba, au, angalau, mimi sasa. Nilitaka mapumziko kidogo kufikiria juu ya mantiki ya Insert, kama huwezi kufikiria hivyo. Kimsingi, utakuwa tu milele kuwa inserting katika majani. Kama, kama mimi Insert 1, basi mimi nina inevitably kwenda kuwa inserting 1 - Mimi umebadirisha hadi nyeusi - I'll kuwa inserting 1 zaidi ya hapa. Au kama mimi Insert 4, nataka kuwa inserting 4 zaidi ya hapa. Hivyo hakuna jambo gani wewe, wewe utaenda inserting katika jani. Wote una kufanya ni iterate chini ya mti mpaka kupata na nodi kwamba wanapaswa kuwa mzazi wa nodi, mzazi nodi mpya, na kisha kubadili pointer wake wa kushoto au kulia, kutegemea kama ni zaidi au chini ya nodi ya sasa. Mabadiliko ya kwamba pointer kwa uhakika na nodi ya mwezi mpya. Hivyo iterate chini ya mti, kufanya uhakika jani na nodi ya mwezi. Pia kufikiria kuhusu nini kuwa inakataza hali ya aina kabla, ambapo mimi yalijengwa mti binary ambapo ilikuwa sahihi kama wewe tu inaonekana kwenye nodi moja, lakini 9 ilikuwa upande wa kushoto wa 7 kama wewe iterated chini njia yote. Basi hiyo ni vigumu katika hali hii, tangu - Msidhani kuhusu inserting 9 au kitu; kwenye nodi sana kwanza, Mimi nina kwenda kuona 7 na Mimi tu anaenda kwenda kulia. Hivyo hakuna jambo nini mimi, kama mimi nina kuingiza kwa kwenda jani, na kwa kutumia majani ya algorithm inafaa, itakavyo kuwa vigumu kwa mimi Insert 9 ya kushoto ya 7 kwa sababu kwa haraka kama mimi hit 7 mimi nina kwenda kwa haki. Je, mtu yeyote kuwa na kitu kuanza na? [Mwanafunzi] Mimi kufanya. >> Uhakika. [Mwanafunzi, unintelligible] [Nyengine mwanafunzi, unintelligible] [Bowden] Ni appreciated. Sawa. Wanataka kueleza? 

[Mwanafunzi] Tangu Tunajua kwamba sisi walikuwa inserting mpya nodes katika mwisho wa mti, Mimi looped kupitia mti iteratively mpaka mimi got nodi kwamba alisema kwa null. Na kisha niliamua kuweka ama upande wa kulia au wa kushoto kutumia hii variable kulia, ni aliniambia ambapo kuiweka. Na kisha, kimsingi, mimi tu alifanya kwamba mwisho - kwamba nodi temp uhakika na nodi ya mwezi kuwa ni kujenga, ama upande wa kushoto au upande wa kulia, kutegemea na nini thamani kuume ulikuwa. Mwisho, mimi kuweka mpya wa nodi unafanya thamani kwa thamani ya kupima yake. [Bowden] Sawa, hivyo mimi kuona suala moja hapa. Hii ni kama 95% ya njia pale. suala moja kwamba mimi kuona, vizuri, haina mtu yeyote mwingine kuona suala hilo? Je, ni hali ya chini ambayo wao kuvunja nje ya kitanzi? [Mwanafunzi] Kama ni temp null? >> Yeah. Hivyo ni jinsi wewe kuvunja nje ya kitanzi ni kama temp ni null. Lakini nini mimi hapa hapa? Mimi dereference temp, ambayo ni inevitably null. Hivyo kitu kingine unahitaji kufanya ni si tu kuweka wimbo mpaka temp ni null, unataka kuweka wimbo wa mzazi wakati wote. Sisi pia wanataka nodi * mzazi, mimi nadhani sisi inaweza kuendelea kuwa katika null mara ya kwanza. Hii ni kwenda kuwa na tabia weird kwa mizizi ya mti, lakini tutaweza kupata kwamba. Kama thamani ni kubwa zaidi kuliko chochote, kisha temp = temp haki. Lakini kabla ya sisi kufanya hivyo, mzazi = temp. Au ni wazazi daima kwenda temp sawa? Ni kwamba kesi? Kama temp si null, basi mimi naenda kwa hoja chini, hakuna jambo gani, na nodi ambayo ni temp mzazi. Hivyo mzazi kwenda kuwa temp, na kisha mimi hoja temp chini. Sasa temp ni null, lakini pointi mzazi na mzazi wa kitu ambacho ni null. Hivyo hapa chini, mimi sitaki kuweka haki sawa na 1. Hivyo mimi wakiongozwa na haki, hivyo kama haki = 1, na mimi nadhani wewe pia wanataka kufanya - kama hoja kwa upande wa kushoto, unataka kuweka haki sawa ya 0. Au mwingine kama wewe milele hoja ya haki. Hivyo haki = 0. Kama haki = 1, sasa tunataka kufanya mzazi haki pointer newnode, mwingine tunataka kufanya mzazi kushoto pointer newnode. Maswali juu ya hilo? Sawa. Hivyo hii ni njia ya sisi - vizuri, kwa kweli, badala ya kufanya hivyo, sisi nusu inatarajiwa wewe kutumia build_node. Na kisha kama newnode sawa null, kurudi uongo. Hiyo ni kwamba. Sasa, hii ni kile sisi inatarajiwa kufanya. 

Hii ni nini ufumbuzi wafanyakazi kufanya. Sikubaliani na hii kama njia ya "haki" ya kwenda kuhusu hilo lakini hii ni kikamilifu faini na itakuwa kazi. Jambo moja kwamba ni kidogo weird hivi sasa ni kama mti huanza mbali kama null, sisi kupita katika mti null. Nadhani inategemea jinsi unaweza kufafanua tabia ya kupita katika mti null. Mimi kudhani kwamba kama wewe kupita katika mti null, kisha kuingiza thamani katika mti null lazima tu kurudi mti ambapo thamani tu ni kwamba nodi moja. Je, watu kukubaliana na kwamba? Unaweza, kama alitaka, ikiwa wewe kupita katika mti null na unataka Insert thamani ndani yake, kurudi uongo. Ni juu yako na kufafanua kwamba. Kwa kufanya jambo la kwanza mimi alisema na kisha - vizuri, utaenda kuwa na matatizo ya kufanya hivyo, kwa sababu itakuwa rahisi kama tungekuwa na pointer kimataifa kwa kitu, lakini hatuna, hivyo kama mti ni null, kuna kitu tunaweza kufanya juu ya hilo. Tunaweza tu kurudi uongo. Hivyo nina kwenda kubadili Insert. Sisi kitaalam inaweza kubadili tu haki hii hapa, jinsi gani iterating juu ya mambo, lakini nina kwenda na mabadiliko Insert kuchukua nodi ** mti. Double kuyatumia. Hii ina maana gani? Badala ya kushughulika na kuyatumia kwa nodes, kitu nitakacho kuwa manipulating ni hii pointer. Mimi naenda kuwa manipulating hii pointer. Mimi naenda kuwa manipulating kuyatumia moja kwa moja. Hii hufanya akili tangu, kufikiri juu ya chini - vizuri sasa hivi pointi null. Nini nataka kufanya ni kuendesha hii pointer kwa uhakika na si null. Mimi nataka kwa uhakika na nodi yangu mpya. Kama mimi tu kuweka wimbo wa kuyatumia na kuyatumia yangu, basi mimi si haja ya kuweka wimbo wa pointer mzazi. Naweza tu kuweka wimbo kuona kama pointer ni akizungumzia null, na kama pointer ni akizungumzia null, mabadiliko hayo kwa uhakika na nodi nataka. Na ninaweza mabadiliko hayo kwa kuwa nina pointer pointer. Hebu angalia hii hivi sasa. Unaweza kweli kufanya hivyo recursively pretty urahisi. Je, tunataka kufanya hivyo? Ndiyo, sisi kufanya. 

Hebu kuona recursively. Kwanza, ni nini msingi wetu kesi kwenda kuwa? Karibu daima msingi wetu kesi; lakini kwa kweli, hii ni aina ya gumu. Kwanza mambo ya kwanza, kama (mti == null) Nadhani sisi ni kwenda tu kurudi uongo. Hii ni tofauti na null mti yako kuwa. Hii ni pointer pointer mizizi yako kuwa null ambayo ina maana kwamba mizizi yako pointer haipo. Hivyo hapa chini, kama mimi kufanya nodi * - wacha tu kutumia tena hii. Node * mzizi = null, na kisha mimi naenda kuwaita Insert kwa kufanya kitu kama, Insert 4 ndani ya mizizi &. Hivyo & mizizi, mizizi ya mti ikiwa ni * nodi kisha & mzizi ni kwenda kuwa ** nodi. Hii ni halali. Katika kesi hiyo, mti, hapa juu, mti si null - au Insert. Hapa. Mti si null; * mti ni null, ambayo ni nzuri kwa sababu kama * mti ni null, naweza kuendesha ni kwa sasa uhakika na kile Mimi nataka kumweka kwa. Lakini kama mti ni null, kwamba maana mimi tu alifika hapa na alisema null. Hiyo haina mantiki. Mimi siwezi kufanya kitu na kwamba. Kama mti ni null, kurudi uongo. Hivyo mimi kimsingi tayari alisema nini msingi wetu kesi halisi ni. Na kile kwamba kwenda kuwa? [Mwanafunzi, unintelligible] [Bowden] Ndiyo. Hivyo kama (* mti == null). Hii inahusiana na kesi zaidi ya hapa ambapo kama pointer yangu nyekundu ni pointer mimi nina ililenga, hivyo kama mimi nina ililenga pointer hii, sasa mimi nina ililenga pointer hii. Sasa mimi nina ililenga pointer hii. Hivyo kama pointer yangu nyekundu, ambayo ni nodi wangu **, ni milele - kama *, pointer yangu nyekundu, ni milele null, hiyo ina maana kwamba mimi niko kwenye kesi ambapo mimi nina kulenga pointer kwamba pointi - hii ni pointer kwamba ni mali ya jani. Mimi nataka kubadili hili pointer kwa uhakika na nodi yangu mpya. Njoo nyuma zaidi ya hapa. Newnode yangu tu kuwa nodi * n = build_node (thamani) kisha n, ikiwa n = null, kurudi uongo. Mwingine tunataka kubadili kile pointer sasa akizungumzia kwa sasa uhakika na nodi wetu wapya kujengwa. Tunaweza kweli kufanya hivyo hapa. Badala ya kusema n, tunasema * mti = ikiwa mti *. Kila mtu kuelewa kwamba? Kwamba kwa kushughulika na kuyatumia kwa kuyatumia, tunaweza kubadili kuyatumia null kwa uhakika na mambo tunataka yao kwa uhakika na. Hiyo ni msingi wetu kesi. 

Sasa upprepning yetu, au recursion yetu, ni kwenda kuwa ni sawa na recursions mengine yote tumekuwa kufanya. Sisi ni kwenda unataka Insert thamani, na sasa mimi naenda kutumia ternary tena, lakini nini ni hali yetu ya kwenda kuwa? Nini ni sisi ni kuangalia kwa kuamua kama tunataka kwenda kushoto au kulia? Hebu kufanya hivyo katika hatua tofauti. Kama (thamani <) nini? [Mwanafunzi] thamani ya mti? [Bowden] Basi kumbuka kwamba mimi nina sasa - [Wanafunzi, unintelligible] [Bowden] Yeah, hivyo hapa hapa, hebu kusema kwamba hii arrow kijani ni mfano wa nini sasa ni mti, ni pointer pointer hii. Hivyo kwamba maana mimi ni pointer pointer 3. dereference mara mbili akapiga nzuri. Nifanye - jinsi gani mimi kufanya hivyo? [Mwanafunzi] Dereference mara moja, na kisha kufanya mshale njia? [Bowden] Basi (* mti) ni dereference mara moja, -> thamani anaenda kunipa thamani ya nodi kwamba mimi nina moja akizungumzia. Hivyo siwezi pia kuandika ** tree.value kama unapendelea kwamba. Aidha kazi. Kama kwamba ni kesi, kisha Mimi nataka kuwaita Insert na thamani. Na kile nodi yangu updated ** kwenda kuwa? Nataka kwenda kwa upande wa kushoto, hivyo ** tree.left ni kwenda kuwa wangu wa kushoto. Na mimi nataka pointer kitu hivyo kwamba kama kushoto kuishia kuwa pointer null, Naweza kurekebisha kwa uhakika na nodi yangu mpya. 

Na kesi nyingine inaweza kuwa sawa sana. Hebu kweli kufanya kwamba ternary yangu hivi sasa. Ingiza thamani kama thamani <(** mti). Thamani. Kisha tunataka update ** wetu wa kushoto, mwingine tunataka update ** yetu kwa haki. [Mwanafunzi] Je, hiyo kupata pointer pointer? [Bowden] Kumbuka kwamba - ** tree.right ni nyota wa nodi. [Mwanafunzi, unintelligible] >> Yeah. ** Tree.right ni kama hii pointer au kitu. Hivyo kwa kuchukua pointer kwamba, anipaye nini nataka ya pointer guy kwamba. [Mwanafunzi] Inawezekana sisi kwenda juu tena kwa nini sisi ni kutumia kuyatumia mbili? [Bowden] Yeah. Hivyo - hapana, unaweza, na kwamba ufumbuzi kabla ya ilikuwa ni njia ya kufanya hivyo bila ya kufanya kuyatumia mbili. Unahitaji kuwa na uwezo wa kuelewa kutumia kuyatumia mbili, na hii ni ufumbuzi safi. Pia, ona kwamba, kile kinachotokea kama mti wangu - kile kinachotokea kama mzizi yangu ilikuwa null? Nini kinatokea kama mimi kufanya kesi hii hapa hapa? Hivyo nodi * mzizi = null, ingiza 4 ndani ya mizizi &. Nini mizizi kwenda kuwa baada ya hili? [Mwanafunzi, unintelligible] >> Yeah. Mizizi thamani ni kwenda kuwa 4. Mizizi kushoto ni kwenda kuwa null, mzizi haki ni kwenda kuwa null. Katika kesi ambapo hatukuwa kupita mizizi na anuani, hatukuweza kurekebisha mizizi. Katika kesi ambapo mti - mizizi ambapo alikuwa null, sisi tu alikuwa na kurudi uongo. Kuna kitu tunaweza kufanya. Hatuwezi kuingiza nodi katika mti tupu. Lakini sasa tunaweza; sisi tu kufanya mti tupu ndani ya mti mmoja wa nodi. Ambayo ni kawaida njia inatarajiwa kwamba ni walidhani kazi. 

Aidha, hii ni kwa kiasi kikubwa mfupi kuliko pia kuweka wimbo wa mzazi, na hivyo iterate chini njia yote. Sasa nina mzazi wangu, na mimi tu na mzazi wangu wa kulia pointer chochote. Badala yake, kama sisi alifanya hivyo iteratively, ni d kuwa wazo moja na kitanzi wakati. Lakini badala ya kuwa ili kukabiliana na mzazi pointer yangu, badala pointer yangu sasa itakuwa jambo kwamba mimi nina moja kwa moja kubadilisha kwa uhakika na nodi yangu mpya. Mimi wala kuwa na kushughulika na kama ni akizungumzia kushoto. Mimi wala kuwa na kushughulika na kama ni akizungumzia haki. Ni tu chochote pointer hii, mimi nina kwenda kuweka kwa uhakika na nodi yangu mpya. Kila mtu kuelewa jinsi kazi? Kama siyo kwa nini tunataka kufanya ni njia hii, lakini angalau kwamba kazi hii kama suluhisho? [Mwanafunzi] wapi sisi kurudi kweli? [Bowden] Hiyo pengine hapa hapa. Kama sisi usahihi kuingiza, kurudi kweli. Mwingine, chini hapa tunakwenda unataka kurudi anarudi Insert chochote. 

Na nini maalum kuhusu kazi hii ya kujirudia? Ni mkia kujirudia, hivyo muda mrefu kama sisi kukusanya na optimization baadhi, itakuwa kutambua kuwa na wewe kamwe kupata kufurika stack kutoka hii, hata kama mti yetu ina urefu wa 10,000 au milioni 10. [Mwanafunzi, unintelligible] [Bowden] nadhani ni gani katika Dash - au nini optimization ngazi inahitajika kwa ajili ya recursion mkia na kutambuliwa. Nadhani inatambua - GCC na Clang pia kuwa na maana tofauti kwa viwango vyao optimization. Mimi nataka kusema ni DashO 2, kwa uhakika kwamba ni mapenzi kutambua recursion mkia. Lakini sisi - unaweza kujenga kama mfano Fibonocci au kitu. Siyo rahisi kwa mtihani na hii, kwa sababu ni vigumu kujenga mti binary kwamba hivyo kubwa. Lakini yeah, nadhani ni DashO 2, kwamba kama wewe kukusanya na DashO 2, itakuwa kuangalia kwa recursion mkia na optimize kwamba nje. Turudi kwa - Insert ni literally jambo la mwisho ni mahitaji. Turudi kwa Insert juu hapa ambapo sisi ni kwenda kufanya wazo moja. Ni utakuwa bado kuwa na flaw ya kutokuwa na uwezo wa kushughulikia kabisa wakati mizizi yenyewe ni null, au kuingia zamani ni null, lakini badala ya kushughulika na pointer mzazi, hebu kuomba mantiki hiyo hiyo ya kuyatumia kutunza na kuyatumia. Kama hapa sisi kushika nodi zetu ** cur, na hatuna haja ya kuweka wimbo wa kulia tena, lakini nodi ** cur = & mti. Na sasa wakati wetu kitanzi ni kwenda kuwa wakati * cur haina null sawa. Hawana haja ya kuweka wimbo wa wazazi tena. Hawana haja ya kuweka wimbo wa kushoto na kulia. Na mimi itabidi kuiita temp, kwa sababu tuko tayari kutumia temp. Sawa. Hivyo kama (thamani> * temp), kisha & (* temp) -> kulia mwingine temp = & (* temp) -> kushoto. Na sasa, katika hatua hii, baada ya hii kitanzi wakati, Mimi tu kufanya hivyo kwa sababu labda ni rahisi kufikiri juu iteratively kuliko recursively, lakini baada ya hii kitanzi wakati, * Temp ni pointer tunataka kubadili. 

Kabla ya hapo tulikuwa mzazi, na sisi alitaka mabadiliko aidha kushoto mzazi au mzazi wa kulia, lakini kama tunataka kubadili mzazi wa kulia, kisha * temp ni mzazi wa kulia, na tunaweza kubadilisha hiyo moja kwa moja. Hivyo hapa chini, tunaweza kufanya * temp = newnode, na hiyo ni yake. Hivyo taarifa, wote sisi gani katika hii ilikuwa kuchukua mstari wa kanuni. Ili kuweka wimbo wa mzazi katika yote ni nyongeza ya jitihada. Hapa, kama sisi tu kuweka wimbo wa pointer pointer, na hata kama sisi alitaka kujikwamua hizi braces wote curly sasa, kufanya ni kuangalia mfupi. Hii sasa ni exact ufumbuzi, lakini wachache mstari wa kanuni. Mara baada ya kuanza hii kutambua kama ufumbuzi halali, pia ni rahisi sababu ya juu kuliko kama, sawa, kwa nini nina hii bendera kulia int? Hiyo ina maana gani? Oh, ni akionyesha kwamba kila wakati mimi kwenda kulia, nahitaji kuweka, mwingine kama mimi kwenda kushoto nahitaji kuweka kwa sifuri. Hapa, mimi hawana sababu juu ya kwamba, ni rahisi tu kufikiria. Maswali? [Mwanafunzi, unintelligible] >> Yeah. Okay, kwa hivyo katika kidogo mwisho - Nadhani moja ya haraka na rahisi kazi tunaweza kufanya ni, let's - pamoja, mimi nadhani, kujaribu na kuandika ina kazi ambayo haina huduma kama ni binary tafuta mti. Hii ina kazi lazima kurudi kweli kama mahali popote katika mti huu jumla binary ni thamani sisi ni kuangalia kwa. Basi hebu kwanza kufanya hivyo recursively na kisha tutaweza kufanya hivyo iteratively. Tunaweza kweli tu kufanya hivyo pamoja, kwa sababu hii ni ya kwenda kuwa kweli mfupi. 

Nini msingi wangu kesi kwenda kuwa? [Mwanafunzi, unintelligible] [Bowden] Hivyo kama (mti == null), basi nini? [Mwanafunzi] Kurudi uongo. [Bowden] Else, vizuri, sihitaji mwingine. Kama ilikuwa msingi yangu nyingine kesi. [Mwanafunzi] Tree wa thamani? >> Yeah. Hivyo kama (mti-> thamani == thamani. Kumbuka hatuna nyuma * nodi, si nodi ** s? Ina kamwe haja ya kutumia ** nodi, tangu sisi si kubadilisha kuyatumia. Sisi ni tu traversing yao. Kama kwamba hutokea, basi tunataka kurudi kweli. Mwingine tunataka traverse watoto. Hivyo hatuwezi kufikiri kuhusu kama kila kitu kwa upande wa kushoto ni chini na kila kitu kwa kulia, ni mkubwa. Hivyo kile ni hali yetu ya kwenda kuwa hapa - au, nini sisi kwenda kufanya? [Mwanafunzi, unintelligible] >> Yeah. Kurudi ina (thamani, mti-> kushoto) au ina (thamani, mti-> kulia). Na kwamba ni. Na taarifa kuna baadhi ya tathmini short-mzunguko, ambapo kama sisi kutokea kwa kupata thamani katika mti wa kushoto, sisi kamwe haja ya kuangalia mti wa kulia. Hiyo ni kazi nzima. Sasa hebu kufanya hivyo iteratively, ambayo ni kwenda kuwa chini nice. Tutaweza kuchukua kuanza kawaida ya cur nodi * = mti. Wakati (cur = null!). Haraka kwenda kuona tatizo. Kama cur - nje hapa, kama sisi milele kuvunja nje ya hili, kisha tumekuwa kukimbia nje ya mambo ya kuangalia, hivyo kurudi uongo. Kama (cur-> thamani == thamani), kurudi kweli. Hivyo sasa, sisi ni katika nafasi - sisi hatujui kama tunataka kwenda kushoto au kulia. Hivyo kiholela, hebu tu kwenda kushoto. Nimekuwa wazi kukimbia katika suala ambapo nimekuwa kabisa kutelekezwa kila kitu - Nami milele tu kuangalia upande wa kushoto wa mti. Mimi kamwe chochote ambacho ni kuangalia mtoto haki ya kitu chochote. Je, mimi kurekebisha hili? [Mwanafunzi] Una kuweka wimbo wa kushoto na kulia katika stack. [Bowden] Yeah. Basi hebu kufanya hivyo struct orodha, nodi * n, na kisha nodi ** ijayo? Nadhani kwamba kazi nzuri. Tunataka kwenda juu ya kushoto, au let's - hapa juu. Struct orodha orodha =, hivyo itabidi kuanza nje katika orodha hii struct. * = Orodha null. Ili kwenda kuwa orodha yetu zilizounganishwa ya subtrees kwamba tuna skipped juu. Sisi ni kwenda Traverse kushoto sasa, lakini tangu sisi inevitably haja ya kurudi kwa haki, Sisi ni kwenda kuweka upande wa kulia ndani ya struct orodha yetu. Kisha sisi itabidi new_list au struct, struct orodha *, new_list = malloc (sizeof (orodha)). Mimi naenda kupuuza kosa-kuangalia kwamba, lakini unapaswa kuangalia kuona kama ni null. New_list nodi ni kwenda kwa uhakika na - oh, hiyo ndiyo sababu nilitaka it up hapa. Ni kwenda na kumweka kwa orodha ya pili struct. Hiyo tu jinsi wanaohusishwa orodha ya kazi. Hii ni sawa kama orodha int wanaohusishwa ila tuko tu kuondoa int na * nodi. Ni sawa. Hivyo new_list, thamani ya new_list nodi zetu, ni kwenda kuwa cur-> kulia. thamani ya yetu new_list-> ijayo itakuwa ni orodha yetu ya awali, na kisha tunakwenda update orodha yetu kwa uhakika na new_list. 

Sasa tunahitaji baadhi ya aina ya njia ya mambo kuunganisha, kama tuna traversed nzima kushoto subtree. Sasa tunahitaji vuta stuff nje ya hayo, kama cur ni null; hatutaki tu kurudi uongo. Tunataka sasa vuta nje katika orodha yetu mpya. njia rahisi ya kufanya hivyo - vizuri, kwa kweli, kuna nyingi njia ya kufanya hili. Mtu yeyote kuwa pendekezo? Ambapo mimi lazima kufanya hivyo au jinsi mimi lazima kufanya hivyo? Sisi tu dakika kadhaa, lakini mapendekezo yoyote? Badala ya - njia moja, badala ya hali yetu ya kuwa wakati, nini sasa tuko kuangalia si null, badala ya sisi ni kwenda kuendelea kwenda mpaka orodha yetu yenyewe ni null. Hivyo kama orodha yetu kuishia kuwa null, kisha sisi kukimbia nje ya mambo kwa kuangalia, kutafuta zaidi. Lakini hiyo ina maana kwamba jambo la kwanza katika orodha yetu ni kwenda tu kuwa nodi kwanza. kitu ya kwanza kabisa itakuwa - sisi tena haja ya kuona kwamba. Hivyo orodha-> n itakuwa mti wetu. orodha-> ijayo itakuwa ni null. Na sasa wakati orodha haina null sawa. Cur ni kwenda kuvuta kitu kutoka orodha yetu. Hivyo cur inaenda sawa orodha-> n. Na kisha orodha ni kwenda sawa orodha-> n, au orodha-> ijayo. Hivyo kama cur thamani sawa na thamani. Sasa tunaweza kuongeza wote haki yetu pointer na pointer wetu wa kushoto muda mrefu kama wao siyo null. Hapa chini, mimi nadhani tunapaswa wamefanya hivyo katika nafasi ya kwanza. Kama (cur-> kulia =! Null) basi sisi ni kwenda Insert kwamba nodi katika orodha yetu. Kama (cur-> kushoto), hii ni kidogo kidogo ya kazi ya ziada, lakini ni nzuri. Kama (cur-> kushoto =! Null), na sisi ni kwenda Insert kushoto katika orodha yetu wanaohusishwa, na kwamba lazima iwe hivyo. Sisi iterate - kwa muda mrefu kama tuna kitu katika orodha yetu, tuna mwingine nodi kuangalia. Hivyo sisi kuangalia nodi kwamba, sisi kuendeleza orodha yetu ya moja ijayo. Kama nodi kwamba ni thamani sisi ni kuangalia kwa, tunaweza kurudi kweli. Mwingine Insert wote wetu subtrees kushoto na kulia, muda mrefu kama wao siyo null, katika orodha yetu ili sisi inevitably kwenda juu yao. Hivyo kama walikuwa si null, mizizi ya mti ikiwa wetu pointer zimeelekezwa kwa mambo mawili, kisha saa ya kwanza sisi vunjwa kitu nje hivyo orodha yetu kuishia kuwa null. Na kisha sisi kuweka mambo mawili nyuma katika, hivyo sasa orodha yetu ni ya kawaida 2. Kisha tunakwenda kitanzi nyuma juu na sisi ni tu kwenda kuvuta, hebu sema, pointer kushoto wa mizizi nodi zetu. Na kwamba nitaendelea yanafanyika, sisi kuishia looping juu ya kila kitu. 

Ona kwamba hii ilikuwa ngumu zaidi kwa kiasi kikubwa katika ufumbuzi kujirudia. Na nimekuwa alisema mara nyingi kwamba ufumbuzi kujirudia kawaida ana mengi kwa pamoja na iterative ufumbuzi. Hapa hii ni nini hasa ufumbuzi kujirudia ni kufanya. mabadiliko tu ni kwamba badala ya kutumia implicitly stack, stack mpango, kama njia yako ya kuweka wimbo wa nini nodes wewe bado haja ya kutembelea, sasa una kupanga kutumia orodha zilizounganishwa. Katika kesi zote wewe ni kuweka wimbo wa nini nodi bado inahitaji alitembelea. Katika kesi ya kujirudia ni rahisi tu kwa sababu stack unatekelezwa kwa wewe kama stack mpango. Ona kwamba orodha hii wanaohusishwa, ni stack. Chochote sisi tu ya kuweka juu ya stack ni mara moja nini tuko kwenda kuvuta mbali stack kutembelea ijayo. Sisi ni nje ya muda, lakini maswali yoyote? [Mwanafunzi, unintelligible] [Bowden] Yeah. Hivyo kama tuna orodha yetu zilizounganishwa, sasa inaenda kwa guy hii, na sasa tuko tu kuendeleza orodha yetu zilizounganishwa kuzingatia guy. Sisi ni traversing zaidi ya orodha wanaohusishwa katika mstari huo. Na kisha mimi nadhani sisi wamkomboe orodha yetu zilizounganishwa na stuff mara moja kabla ya kurejea kweli au uongo, tunahitaji iterate juu ya orodha yetu wanaohusishwa na daima chini hapa, mimi nadhani, kama sisi cur haki si sawa, kuongeza kuwa, hivyo sasa tunataka huru cur kwa sababu, vizuri, hatukuwa kusahau kabisa kuhusu orodha? Yeah. Hivyo kwamba ni nini tunataka kufanya hapa. Wapi pointer? Cur alikuwa kisha - tunataka orodha struct * 10 sawa na orodha inayofuata. Bure orodha, orodha = temp. Na katika kesi ambapo sisi kurudi kweli, hatuna haja ya iterate juu ya salio ya orodha yetu zilizounganishwa kumkomboa mambo. Jambo zuri kuhusu ufumbuzi kujirudia ni kumkomboa mambo njia tu factorings popping mbali stack ambayo kitatokea kwa ajili yenu. Hivyo tumeenda kutoka kitu ambacho ni kama mistari 3 ya maadili ngumu-kwa-kufikiri kuhusu- kitu ambacho ni kikubwa zaidi wengi ngumu-kwa-kufikiri-kuhusu mstari wa kanuni. Tena maswali? Wote haki. Sisi ni nzuri. Bye! [CS50.TV]