[Powered by Google Translate] [Bölmə 7: Daha Rahat] [Rob Bowden] [Harvard Universiteti] [Bu CS50 edir] [CS50.TV] Bütün hüquqlar. Belə ki, mənim e-poçt bildirib kimi Bu ikili ağacı intensiv bölmə olacaq. Amma ki, bir çox suallar var. Beləliklə, biz cəhd və hər bir sual çıxartmaq olacaq və şeyler bütün yaxşı yollarından ağrılı ətraflı daxil. Belə ki, sağ əvvəlində biz ikili ağac və stuff nümunəsi təsvirlər keçir. Belə ki, burada, "ikili ağac bağlı siyahısı oxşar qovşaqlarının ki saxla sol 'uşaq' üçün biri əvəzinə bir pointer istisna olmaqla iki var və sağ 'uşaq üçün. " , Yalnız bir bağlı siyahı kimi ikili ağac Belə bu struct başqa iki göstəricilərinə malik olur. Üç göstəricilərinə üçün gedir hansı trinary ağacları, var yalnız ümumi göstərici olan N-ary ağacları var, sonra üçün kifayət qədər böyük olması malloc ki, bütün mümkün uşaqlar üçün kifayət qədər göstəricilər. Belə ikili ağac yalnız iki sabit sayda olur. Əgər istəyirsinizsə, bir unary ağac kimi bir bağlı siyahı verə bilər amma hər kəs ki çağırır düşünmürəm. "Ikili ağac node bir qutu və oxlar diaqram Draw hər bir uşaq göstərici null olduğu Nate sevimli nömrə, 7,. "olan Belə ki, iPad rejimi. 

Bu olduqca sadə olacaq. Biz yalnız bir node var olacaq, bir kvadrat kimi çəkmək lazımdır. Mən burada dəyərlər çəkmək lazımdır. Belə ki, dəyəri, burada gedəcək və sonra aşağı burada sol sol göstərici və sağ sağ göstərici olacaq. O sol və sağ göstərici adları zəng etmək üçün konvensiya belə Və bu çox deyil. Bu iki null olacaq. Bu yalnız null olacaq, yalnız null olacaq. Okay. Belə ki, burada geri. "A bağlı siyahı, biz yalnız bir göstərici saxlamaq üçün idi bütün əlaqədar siyahısı və ya bütün siyahı xatırlamaq üçün siyahısında ilk node. Eyni zamanda, ağacları ilə, yalnız bir göstərici saxlamaq üçün bütün ağac xatırlamaq üçün bir node. Bu node ağac "root" calle edir. Əvvəl sizin diaqram ilə qurmaq və ya yeni bir heç-heçə bir ikili ağac qutuları və oxlar anlatımı var ki, bu cür ilə sol sonra 3 dəyəri 7, 3 hüququnu sonra sağ 9 və sonra 6 ". Mən baş ki, bütün yadda bilərsiniz Bakalým. Belə ki, burada bizim kök qədər olacaq. Biz, yerdə biz kök zəng lazımdır ki, bir şey bir göstərici olacaq və bu oğlan işarə edir. İndi yeni node etmək biz sol, 3 nə var? 3 yeni node Belə ki, bu ilkin null göstərir. Mən yalnız N. qoymaq lazımdır İndi 7-sola getmək etmək istəyirəm. Beləliklə, biz indi bu adam baxımından bu göstərici dəyişir. Və biz eyni. Biz burada bir 9 istəyirəm olan ilkin yalnız null deyir. Biz, 9 Bu göstərici, point dəyişiklik olacaq və indi 3-sağa 6 qoymaq istəyirəm. Belə ki, olacaq - 6 olun. Və oğlan orada qeyd edəcək. Okay. Belə ki, bütün ki, bunu bizə soruşur. 

İndi bəzi terminologiya üzərində gedək. Biz artıq ağac kökü ağac üst-ən node nə danışdı. Bir 7 olan. Ağac altındakı qovşaqlarının yarpaqları deyilir. Yalnız uşaqlar kimi null malik olan hər hansı node bir yarpaq edir. Belə ki, bizim binar ağacı yalnız bir node varsa, olar, bir ağac bir yarpaq, və ki, var. "Ağac The 'boyu" Siz etmək mayaotu sayı üst bir yarpaq almaq üçün. " Biz ikinci daxil fərq almaq lazımdır balanslı və balanssız ikili ağacları arasında, bu ağac, lakin indi, ümumi hündürlüyü I, 3 deyərdim baxmayaraq mayaotu sayını hesablayır, əgər Siz 9 almaq üçün etmək üçün, o, həqiqətən 2 yalnız bir boyu var. Hal-hazırda bu, bir balanssız ikili ağac o müvafiq olur, lakin biz balanslaşdırılmış danışdı lazımdır. Belə ki, indi biz baxımından bir ağac qovşaqlarının haqqında danışmaq olar ağac digər qovşaqlarının nisbətən. Belə ki, indi biz valideynlər, uşaqlar, qardaşlar, əcdadları və nəsilləri var. Onlar nə demək, olduqca ümumi mənada var. Biz xahiş varsa - onun valideynləri. Belə ki, 3 əsas nədir? [Tələbələr] 7. >> Bəli. Əsas yalnız işarə nə olacaq. Sonra 7-uşaqlar nə var? [Tələbələr] 3 və 9. >> Bəli. "Uşaq" sözü uşaqlar deməkdir edək ki, bir nəvə kimi, çünki 6 belə tətbiq deyil. Biz nəslindən getmək Lakin sonra, belə 7 nəslindən nə var? [Tələbələr] 3, 6 və 9. >> Bəli. Kök node nəsli, ağac hər şey olacaq istisna olmaqla, bəlkə kök node özü, bu nəslindən hesab istəmirsinizsə. Və nəhayət, əcdadları, belə ki, əks istiqamətdə var. Belə ki, 6-babalarımızın nə var? [Tələbələr] 3 və 7. >> Bəli. 9 daxil deyil. Bu, yalnız kök birbaşa övlad geri var Sizin əcdadları olacaq. 

"Biz, bir ikili ağac əgər ağac hər node üçün 'əmr' demək sol öz nəslindən bütün az dəyərləri var və sağ olanları bütün böyük dəyərləri var. Məsələn, yuxarıda ağac sifariş lakin yalnız sifariş təşkili deyil olunur. " Ki, almaq, əvvəl bir sifariş ikili ağac da ikili axtarış ağac kimi tanınır. Burada, bir sifariş ikili ağac zəng üçün baş amma eşitməmişik ki, bir sifariş ikili ağac əvvəl deyilən və viktorina biz ikili axtarış ağac qoymaq üçün daha çox ehtimal olunur. Onlar bir və eyni edirik və bu ikili ağac və ikili axtarış ağac arasında fərq tanımaq vacibdir. A ikili ağac bir ağac ki, iki şeyə xal. Hər bir node iki şeyi göstərir. Bu işarə edən dəyərləri haqqında heç bir ağıl yoxdur. Bir ikili axtarış ağacı var ildən ki, burada istəyirəm biz, 7 getmək əgər sol bilirik ki, sonra biz bəlkə çata bilər ki, dəyərlərin bütün 7 sol gedən 7-dən az olmalıdır. Az 7-dən bütün dəyərlər 3 və 6 edək ki,. Həmin 7-sola bütün var. Biz 7 doğru getmək varsa, hər şey, 7-dən çox olmalıdır belə 9 7 hüququna, belə ki, biz yaxşı deyilik. Bu, ikili ağac belə deyil müntəzəm ikili ağac biz yalnız sol üst, 7 3 ola bilər 7-sola 9; heç heç dəyərlər sifariş var. O yorucu və lazımsız çünki İndi, biz, həqiqətən, bu nə olacaq lakin "siz hesab edə bilər kimi bir çox əmr ağacları çəkmək üçün cəhd edin nömrələri 7, 3, 9 istifadə edərək, və 6. Fərqli tədbirlərin nə qədər var? Hər birinin hündürlüyü nədir? " 

Biz bir neçə edəcəyik, amma əsas ideya bu heç bir şəkildə bu dəyərləri olan bir ikili ağac nadir təmsil edir. Bəzi ikili 7 olan ağac, 3, 6, 9, biz lazım deyil. Digər mümkün etibarlı bir, kök 3 olardı sola getmək və 6 var, sol getmək və 7 var, sola getmək və 9 deyil. Bu mükəmməl etibarlı ikili axtarış ağac. Yalnız bir bağlı siyahı kimi, çünki çox faydalı deyil və bu göstəricilər bütün yalnız null var. Amma cari ağac. Evet? [Tələbə] dəyərlərinə doğru böyük olmamalıdır varmı? Və ya bu - >> Bu Mən başqa yol getmək idi. Da var - Bəli, ki, keçid imkan verir. 9, 7, 6, 3. Yaxşı tutmaq. Bu hələ bir ikili ağac axtarış ehtimal olunur nə itaət var. Belə ki, sol üçün hər hansı bir node-dən az olmalıdır. Biz yalnız, demək, bu, 6 hərəkət və burada qoymaq bilər. Xeyr, biz bilməz. Niyə bunu saxlayırsınız? Nə edək - burada 6, burada 7, 3-6 xal edir. Bu hələ etibarlı ikili axtarış ağac. Mən bir tənzimləmə ilə gəlmək olar əgər in görək - Mən nə səhv. Bəli, tamam. Bu ağac ilə nə səhvdir? Mən artıq siz bu yanlış bir şey var ki, bir ipucu verdiyseniz danışarlar. Niyə bunu saxlayırsınız? Okay. Bu ağlabatan görünür. Biz hər node, 7 kimi, sonra 7-sola baxmaq Əgər 3. Beləliklə, biz 3 var, 3 sağ üçün şey bir 6. 6 baxmaq əgər, 6 sağa şey 9 edir. Belə ki, niyə bu düzgün ikili axtarış ağac deyil? [Tələbələr] 9 7 sola davam edir. >> Bəli. Bu bəlkə 7-sola gedərək çata bilər bütün dəyərlərin 7-dən az olan doğru olmalıdır. Biz 7 sol getmək varsa, biz 3 almaq və biz hələ 6 bilərsiniz biz hələ, 9 almaq, lakin az 7 getdi edərək bilərsiniz biz 7 daha çox olan bir sıra əldə edə bilməz. Belə ki, bu düzgün ikili axtarış ağac deyil. 

Qardaşım həqiqətən müsahibə sual idi ki doğrulamak üçün bir şey əsasən bu, yalnız kod idi bir ağac bir ikili axtarış ağac, istər və belə etdi ilk şey yalnız yoxlamaq görmək idi sol və sağ doğru və əgər orada təkrarlamaq. Amma bunu yalnız bilməz; siz track saxlamaq Mən 7 sol getdi sonra indi ki, bu subtree hər 7-dən az olmalıdır. Düzgün alqoritm takip lazımdır dəyərlər bəlkə daxil olmaq olar ki, sınırların Biz onların bütün vasitəsilə getmək olmaz. Bir gözəl təkrar əlaqə var biz o kazanılmış deyil, ya da o almaq deyil, baxmayaraq ki, həqiqətən var necə çox müəyyən. Belə ki, onların 14 var. Bunu necə fikri riyazi, kimi Əgər kök node olmaq üçün hər hansı bir bir seçə bilərsiniz və sonra, kök node olmaq 7 seçin əgər sonra mənim sol node ola bilərsiniz ki, bəzi nömrələri, demək, var və sağ node ola bilər ki, bəzi nömrələr var, amma sonra ümumi sayı, sol to məbləği n əgər plus hüququ to məbləği n - 1. Belə ki, qalan nömrələri, onlar sol və ya sağ ya getmək mümkün olmalıdır. Bu, mən sonra ilk 3 qoymaq əgər hər şey sol getmək var ki, çətin görünür amma 7 qoymaq, onda bir şeyi sol bilərsiniz və bəzi şeylər sağa bilərsiniz. Və '3 ilk 'Mən hər şeyi doğru edə bilərsiniz deməkdir. Bu, həqiqətən, siz yalnız kimi, bu barədə düşünmək lazımdır necə bir çox şeyi ağac növbəti səviyyədə davam edə bilər. Və ya onların bütün cəlb edə bilər və o, 14 olduğu ortaya çıxır və sonra 14 almaq lazımdır. 

Burada geri Going, Biz onların vasitəsilə axtarış edə bilərsiniz, çünki "açar sözlər, ikili ağacların sərin bir sıralanır array üzərində axtarış çox oxşar şəkildə. Bunu etmək üçün, biz kök başlamaq və ağac aşağı yolumuza iş yarpaqları doğru, biz aradığınız dəyərlərə qarşı hər node dəyərləri yoxlanılması. Cari node dəyəri dəyəri az, biz, aradığınız Siz node hüququ uşaq yanında gedin. Əks halda, siz node sol uşaq gedin. Bəzi noktada, ya aradığınız dəyəri tapa bilərsiniz, və ya bir null daxil olacaq dəyəri ifadə edən ağac deyil. " Düşünürəm ki, biz əvvəl idi ağac yenidən müəyyən etmək üçün var, ikinci bir almaq lazımdır. Amma biz 6, 10, və 1 ağac olub yuxarı baxmaq istəyirəm. Belə ki, nə, 7, 9, 3, 6. Okay. Siz baxmaq istədiyiniz nömrələri, biz 6 yuxarı baxmaq istəyirəm. Bu necə alqoritmi çalışır? Bəli, biz də ağac bəzi kök göstərici var. Və biz kök getmək və demək istəyirəm ki, biz aradığınız dəyərinə bərabər bu dəyəri? Belə ki, 6 arıyorsanız, belə ki, bərabər deyil. Belə 6 7 az, tamam, biz davam və indi biz deyirik. Ki, biz sola getmək istəyirəm deməkdir, ya da sağ getmək istəyirsiniz? [Tələbə] Sol. >> Bəli. Bu xeyli asan, siz bütün ağac biri mümkün node cəlb edilir və sonra don't - Sizin baş düşünməyə çalışır əvəzinə, tamam az varsa, mən sola getmək və ya doğru getmək yoxdur yalnız bu şəkil baxaraq, mən sola getmək çox aydındır Bu node I arıyorum ki, dəyəri daha çox olsun. Belə ki, indi 3 deyiləm, sol gedin. Mən istəyirəm - 3 6 I arıyorum dəyəri azdır. Beləliklə, biz doğru getmək, və indi, 6 son I əsl qayıtmaq mən, arıyorum dəyəri edir. Mən baxmaq gedirəm növbəti dəyəri 10 edir. Okay. Kök izləmək niyyətindədir - ki, kəsmə - 10 Beləliklə, indi gedir. İndi 10 7 daha çox olacaq, belə ki, mən sağ baxmaq istəyirəm. Mən buraya gəlmək üçün gedirəm, 10, 9 daha çox olacaq mən sağ baxmaq istəyirəm gedirəm. Mən buraya gəlib, lakin burada indi null da deyiləm. Mən null hit əgər mən nə etməliyəm? [Tələbə] yalan qayıt? >> Bəli. 10 tapmadı. 1 təxminən eyni halda olacaq, istisna olmaqla, yalnız Çevrilmiş olacaq; axtarır əvəzinə sağ aşağı, mən sol aşağı baxmaq gedirəm. 

İndi biz, həqiqətən kodu almaq edirəm. Burada - Bu CS50 cihaz açmaq və orada sizin yolu gedin lakin siz də yer bunu yalnız bilər. Bu, yəqin ki, yer bunu ideal deyil biz yer işləyə bilər, çünki. "Birinci biz int dəyərləri olan bir ikili ağac node üçün yeni tipli definition lazımdır. Aşağıda typedef də boilerplate istifadə edərək, ikili ağac bir node üçün yeni bir növü definition yaradır. Zorlandığınız varsa. . . "Blah, blah, blah. OK. Belə nin burada boilerplate qoymaq bildirin typedef struct node və node. Bəli, tamam. Belə ki, biz node istədiyiniz olacaq sahələri hansılardır? [Tələbə] iki göstəricilərinə sonra Int və? >> Int dəyəri iki göstəricilərinə? Necə göstəricilərinə yazmaq edirsiniz? [Tələbə] Struct. >> I, Bəli, belə struct node * yazmayıblar da zoom olmalıdır və struct node * hüququ. Və, son zaman müzakirə xatırlayıram Bu heç bir əhəmiyyət kəsb edir ki, bu, heç bir əhəmiyyət kəsb edir Bu heç bir əhəmiyyət kəsb edir. Siz bu recursive struct müəyyən etmək üçün orada hər şey lazımdır. OK, nə bizim ağac kimi baxmaq edir ki. Biz bir trinary ağac idi, onda bir node B1, B2, struct node * b3 kimi görünə bilər b filialı olduğu - əslində, mən daha çox, orta, sağ deyil, nə tərk eşitdim. Biz yalnız ikili qayğı, belə ki, sağ, sol. "İndi ağac kökü üçün qlobal node * dəyişən bəyan edir." Belə ki, biz bunu fikrində deyilik. Şeyi bir az daha çətin və daha ümumiləşdirilmiş etmək üçün, biz qlobal node dəyişən olmayacaq. Əksinə, əsas biz bütün node şeyi bəyan biz çalışan başlattığınızda və ki, aşağıda deməkdir bizim başqa funksiyası və insert funksiyası, yerinə şey yalnız, bu qlobal node dəyişən istifadə funksiyası biz emal etmək istəyirəm ki, bir arqument kimi ağac almaq üçün olacaq. Qlobal dəyişən olan şeyi daha asan idi. Biz hər şeyi daha etmək olacaq. İndi şey bu cür etmək yalnız bir dəqiqə və ya almaq içərisində əsas sizə bu ağacı yaratmaq istəyirik ki, siz istədiyiniz bütün yerləşir. Keçir və əsas funksiyası bu ağac tikmək. 

Okay. Belə ki, hətta hələ ağac bütün yol inşa etmək yoxdur. Amma hər kəs mən qoparmaq bilər bir şey var bir belə bir ağac tikintisi başlamaq bilər necə göstərmək üçün? [Tələbə] Biri nin tarpıltı, çıxmaq üçün çalışırıq. [Bowden] onların ağac tikintisi ilə rahat kəs? [Tələbə] Sure. Bu işlər deyil. Bu gözəl var >>. Biz yalnız bitirmək bilər - oh, siz onu saxlaya bilərsiniz? Yaşasın. Belə ki, burada biz var - oh, mən bir az kəsmək alıram. Mən zoomed Am? Zoom həyata diyirləyin. Mən bir sual var >>. >> Evet? [Tələbə] Siz struct müəyyən zaman, bir şey üçün başlatılmış kimi şeylər var? [Bowden] No >> OK. Beləliklə, siz başlamaq lazımdır - [Bowden] saylı bir struct siz müəyyən zaman və ya bəyan edərkən, bu ismarıcları başlatılmış deyil, bir int bəyan əgər yalnız kimi. Bu tam eyni şey. Onun fərdi sahələrində hər kimi bu bir zibil dəyər ola bilər. Bir struct və ya bəyan etmək - >> Və müəyyən etmək mümkündür Bunu bir şəkildə başlamaq? [Bowden] Bəli. Belə ki, qısa başlatma sintaksis kimi gedir - Bunu iki yol var. Edirəm ki, tərtib etməlidir əmin cingilti etmək də bu yoxdur. The struct gəlir ki, dəlilləri qaydası Bu qıvrım aşırma daxilində dəlilləri sifarişi kimi qoydu. Siz 9 üçün başlamaq istəyirəm və sol Belə ki, əgər sağ, null ola null edilir və o, null, null 9 olardı. , Alternativ və redaktoru bu sintaksis kimi deyil və bu, yeni bir blok istəyirəm düşünür lakin alternativ bir şey kimi - burada, yeni bir xətt üzərində qoymaq lazımdır. Siz aydın deyə bilərsiniz, mən dəqiq sintaksis unutmayın. Belə ki, açıq-aydın, adı onlara müraciət və demək olar . C, və ya. Value = 9,. Sol = NULL. Mən vergülləri olmaq üçün bu ehtiyac təxmin edirəm. . Sağda = NULL, belə deyil, bu yolla faktiki olaraq, struct sifarişi bilmək lazımdır və bu oxu etdiyiniz zaman, daha aydın deyil nə dəyəri başlatılmış olunur var. 

Bu hər bir olur - belə ki, çox hissəsi üçün, C + + C bir superset edir Siz C + +, və tərtib etməli üzərində hərəkət, C kodu bilər. Bu C + + bilmir ki, hər şeyi biridir, belə ki, insanlar bunu üçün edirlər. Ki, insanlar bunu deyil meyli yeganə səbəbi var, mən bilmirəm ancaq istifadə etmək üçün lazım olduğu halda C + + və mən bu istifadə edə bilmədi ilə işləmək lazımdır. Ki, bir şey başqa bir misal C + + ilə iş deyil necə malloc, texniki, "etibarsız *" a qayıdır lakin yalnız, char * x = malloc nə deyə bilər və avtomatik olaraq bir char * üçün tökmə olunacaq. Bu avtomatik cast olmaz C + +. Tərtib deyil, və açıq-aydın demək lazımdır ki, char * malloc, nə olursa olsun, bir char * üçün salmaq. C və C + + haqqında deyiləm ki, bir çox şeyi yoxdur lakin bu iki. Beləliklə, biz bu sintaksis ilə gedəcəyəm. Ancaq biz sintaksis ilə getmədi, hətta, nə - bu yanlış ola bilər? [Tələbə] Mən dereference buna ehtiyac yoxdur? >> Bəli. , Ok bir gizli dereference ki saxla və biz yalnız bir struct ilə məşğul olduğunuz zaman biz istifadə etmək istəyirik. bu struct bir sahə daxilində əldə etmək. Və biz arrow istifadə yalnız vaxt biz nə istəyirik zaman - yaxşı arrow bərabərdir - ki arrow istifadə əgər demək olardı budur. Bütün arrow vasitələri, dereference bu, indi bir struct ilə Ben və mən sahəsində əldə edə bilərsiniz. Birbaşa və ya dereference sahəsində almaq və bu sahədə əldə - Mən bu dəyəri olmalıdır danışarlar. Amma burada mən, bir struct, bir struct bir pointer ilə məşğul oldum və mən arrow istifadə edə bilməz. Lakin şey bu cür biz bütün qovşaqlarının üçün nə edə bilər. Pərvərdigara. Bu 6, 7, 3-dir. Sonra ağac filial bilərsiniz, biz 7 ola bilər - biz, onun sol 3 qeyd olunmalıdır ola bilər. Belə ki, necə ki, biz etməliyəm? [Tələbələr, anlaşılmaz] >> Bəli. Node3 yerləşdiyi ünvan, və ünvan olmasaydı, o, yalnız tərtib deyil. Lakin bu növbəti qovşaqlarının to göstəricilərinə ki, xatırlayıram. Hüququ, 9 qeyd etməlidir və 3 6 hüququna qeyd edilməlidir. Mən bu bütün set olduğunu düşünürəm. Hər hansı bir şərh və ya sualınız? [Tələbə, anlaşılmaz] kök 7 olacaq. Biz yalnız node demək olar * Ptr = və ya kök, = & node7. 

Bizim məqsədləri üçün, biz, insert ilə məşğul olmaq üçün olacaq biz bu ikili ağac daxil bir funksiyası yazmaq üçün olacaq və insert qaçılmaz bu ağac üçün yeni node yaratmaq malloc zəng edir. Belə şeylər faktı ilə messy almaq üçün gedir ki, bəzi qovşaqlarının yığını üzərində hazırda və digər qovşaqlarının biz onlara daxil olduqda yığın haqqında son edir. Bu mükəmməl etibarlıdır, lakin yeganə səbəbi biz yığını bu nə edirik Biz bilirik ki, belə bir göstərdi Məsələn, çünki edir ağac 7, 3, 6, 9 kimi inşa edilməsi nəzərdə tutulur. Biz bu olmasaydı, onda biz ilk növbədə malloc üçün deyil. Biz bir az sonra görəcəksiniz ki, biz malloc'ing edilməlidir. Hal-hazırda o, baca qoymaq üçün mükəmməl məqbul deyil amma üzrə malloc həyata keçirilməsi bu dəyişdirmək imkan verir. Belə ki, bu hər indi bir şey kimi olacaq node * node9 = malloc (sizeof (node)). İndi biz çek var olacaq. (== NULL node9) əgər - Mən o istəmir - 1 qayıtmaq, indi bir pointer, çünki biz, node9-> edə bilərsiniz value = 6, node9-> tərk = NULL, node9-> sağda = NULL, və biz bu qovşaqlarının hər biri üçün bunu etmək olacaq. Belə ki, əvəzinə isə ayrı bir funksiyası daxilində qoymaq bildirin. Gəlin, bu node * build_node zəng və bu biz Huffman coding üçün təmin API üçün bir qədər oxşardır. Biz ağac siz initializer funksiyaları vermək və deconstructor o ağacların və meşələrin üçün eyni "funksiyaları". 

Belə ki, burada biz initializer funksiya olacaq yalnız bizim üçün bir node qurmaq. Və məhz bu kimi olduqca çox baxmaq olacaq. Mən hətta tənbəl olacaq və dəyişən adının dəyişdirilməsi deyiləm node9 artıq heç bir əhəmiyyət kəsb edir, baxmayaraq ki,. Oh, mən node9 dəyəri 6 olmuşdur olmamalıdır danışarlar. İndi node9 ola bilər. Burada biz null qaytarmalıdır. Hər kəs ki, build-a-node funksiyası razıyam? Belə ki, indi biz yalnız bir dəyəri və null göstəricilərinə hər hansı node qurmaq üçün zəng edə bilərsiniz. İndi ki, zəng edə bilərsiniz, biz node * node9 = build_node (9) edə bilərsiniz. Və nin bunu bildirin. . . 6, 3, 7, 6, 3, 7. İndi biz, eyni göstəricilər qurmaq istəyirəm indi başqa hər şey göstəricilər baxımından artıq var belə artıq ünvanı lazımdır. Okay. Mən istəyirəm son şey nədir? Mən bunu deyiləm ki, bir səhv yoxlanılması var. Node qaytarılması nə qurmaq deyil? [Tələbə, anlaşılmaz] >> Bəli. Malloc uğursuz varsa, null qayıtmaq lazımdır. Mən tənbəlcəsinə əvəzinə hər şərait bunu burada yazmaq arkasýndayým. Əgər (node9 == NULL, və ya - hətta sadə, Bu yalnız əgər node9 bərabərdir. Əgər node9, və ya node6, və ya node3, və ya node7 Belə ki, 1 qayıtmaq. Bəlkə biz malloc bilmədi, və ya bir şey çap olunmalıdır. [Tələbə] həmçinin null bərabər yalan mı? [Bowden] Hər sıfır dəyəri yalan. Belə null sıfır dəyəri. Zero sıfır dəyəri. Asma sıfır dəyəri. Hər hansı - olduqca çox yalnız 2 sıfır dəyərlər null və sıfır olan, yalan sıfır kimi müəyyən yalnız hash edir. Biz qlobal dəyişən bəyan halda da tətbiq edilir. Biz burada node * root malik idi, əgər sonra - qlobal dəyişənlər haqqında gözəl şey həmişə ilkin dəyər var. Bu funksiyaları doğru deyil, necə içərisində burada, biz varsa, kimi, node * və ya node x. Biz heç bir fikir nə x.value, x.whatever var və ya biz onları çap edə bilər və onlar ixtiyari ola bilər. Bu qlobal dəyişənlər doğru deyil. Belə node kök və ya node x. Mənim cari olaraq, qlobal ki, hər şey, əgər açıq-aydın, bəzi dəyəri başlatılmış onun dəyəri sıfır dəyəri var. Belə ki, burada node * kök, biz açıq-aydın bir şey üçün başlamaq deyil Beləliklə, default dəyəri göstəricilər üzrə sıfır dəyəri olan null olacaq. X-u mənim dəyəri x.value sıfır olduğunu demək gedir x.left null və x.right null edir. Bir struct edir, çünki struct sahələrində bütün sıfır dəyərləri olacaq. Biz də, burada istifadə etmək lazım deyil. [Tələbə] Bu structs digər dəyişənlərin fərqli və digər dəyişənlər var zibil dəyərlər, bu adet sıfır var? Çox [Bowden] Digər dəyərlər. Belə ki, X, x sıfır olacaq. Qlobal miqyası da varsa, bu ilkin dəyər var. Okay. >> [Bowden] Ya ya sıfır verdi ilkin dəyəri. Mən bütün bu qayğı düşünürəm. 

Okay. Belə ki, sual növbəti hissəsi, xahiş "İndi biz ehtiva adlı funksiyası yazmaq üçün bool bir prototip ilə int dəyəri düzəlişlər ". Biz bool int dəyəri düzəlişlər etmək istəmirik. Bizim prototip kimi baxmaq edir bool (int dəyər var. Və biz də ağac keçmək olacaq bu ki, dəyəri görmek üçün yoxlanılması lazımdır. Belə node * ağac). Okay. Və sonra biz kimi bir şey ilə zəng edə bilərsiniz bəlkə biz printf və ya bir şey lazımdır. 6, bizim kök ehtiva edir. Bir və ya doğru, geri ki, şey isə 5 kök yalan qaytarmalıdır. Belə ki, bu həyata keçirilməsi üçün ikinci almaq. Siz ya iteratively və ya recursively bunu edə bilərsiniz. Biz hər şeyi müəyyən etdik yol haqqında gözəl şey olduğunu daha asan bizim recursive həll özünü verir qlobal dəyişən yol idi artıq. Biz yalnız əgər int dəyəri düzəlişlər Çünki, biz subtrees aşağı recursing heç bir yol var. Biz bizim üçün subtrees aşağı recurses ayrı bir köməkçi funksiyası var idi. Amma biz değiştirdik ildən bir arqument kimi ağac etmək bu həmişə birinci yerdə olardım indi biz recurse daha asan ola bilər. Belə ki, iterativ ya recursive, biz həm də gedəcəyəm lakin biz olduqca asan olan qədər ki recursive başa görəcəksiniz. Okay. Hər kəs biz ilə işləyə bilər bir şey varmı? 

[Tələbə] Mən bir həll iterativ var. >> Bütün hüququ, iterativ. OK, bu yaxşı görünür. Belə ki, onun vasitəsilə bizə gəzmək istəyirsiniz? [Tələbə] Sure. Mən ağac ilk node almaq üçün bir temp dəyişən seçin. Və sonra mən yalnız, temp bərabər null deyil isə vasitəsilə looped belə ağac hələ də isə hərhalda. Dəyəri dəyərinə bərabər olduqda və temp, işarə edir ki, sonra bu dəyər qaytarır. O sağ və ya sol tərəfdən əgər Əks halda, bu yoxlayır. Əgər artıq ağac var bir vəziyyət almaq, əgər bu çıxışları loop və saxta qaytarır - sonra qaytarır. [Bowden] Okay. Belə ki, yaxşı görünür. Hər kəs bir şey haqqında hər hansı bir şərh yoxdur? Mən düzgün şərh yoxdur. Biz nə edə bilər bir şey bu adam deyil. Oh, bu bir az uzunsov getmək olacaq. Hesab edirəm ki düzəltmək lazımdır. Okay. 

Hər kəs ternary necə yadda olmalıdır. Mütləq keçmiş var viktorina edilmişdir ki, bir ternary operatoru ilə bir funksiyası vermək və ternary istifadə etmir ki, bir şey etmək, demək bu tərcümə. Mən ternary istifadə edirəm Belə ki, bu bir çox halda, bir vəziyyət bir şey bir dəyişən təyin yerləşir əgər başqa başqa bir şey eyni dəyişən seçin. Çox tez-tez şey bu cür çevrildi bilər ki, bir şey ki, bu ki, dəyişən müəyyən - və ya, yaxşı, bu doğrudur? Sonra bu, başqa bu. [Tələbə] ilk bir doğru, sağ əgər? [Bowden] Bəli. Mən həmişə oxumaq yolu, temp, temp dəyər daha çox dəyər bərabərdir bu, başqa bu. Bu sualı var. Daha çox deyilmi? Sonra ilk şey. Else ikinci şey. Demək olar ki, həmişə - kolonda, yalnız - başımda, mən başqa oxuyun. 

Hər kəs bir recursive həlli varmı? Okay. Biz olacaq Bu - bu artıq böyük ola bilər ancaq daha yaxşı olacaq. Bu olduqca çox eyni dəqiq fikirdir. Bu, yalnız var, yaxşı, siz izah etmək istəyirsiniz? [Tələbə] Sure. Belə ki, biz, ağac ilk null əmin edirik ağac null əgər onda biz bunu aşkar deyil, çünki yalan geri olacaq, çünki. Və ağac hələ var, biz getmək - dəyəri cari node Əgər biz ilk yoxlayın. Əgər doğru qayıdın və sol və ya sağ əgər biz recurse. Ki, səs uyğun mu? >> Mm-hmm. (Sazişi) Beləliklə, bu demək olar ki, qeyd - Bu iterativ həll struktur çox bənzər. Əvəzinə recursing, biz bir müddət loop ki, yalnız var. Və ağac bərabər null deyil burada əsas işi biz isə loop çıxdı altında vəziyyətdə idi. Onlar çox oxşar istəyirik. Amma bu bir addım olacaq. İndi biz burada eyni şey. Bu xətlərin həm də eyni şey qaytarılması edirik dikkat, başqa bir dəlil fərqlidir. Beləliklə, biz bir ternary o etmək olacaq. I seçimi bir şey təşkil edib və bu, rəmzi etdi. Okay. Belə ki, biz geri olacaq ki, var. Bu edir zoomed, yaxşı, çox xətləri olmaq olur. Adətən, bir üslub şey kimi, mən bir çox insanlar hesab etmirəm ok sonra boşluq qoyub, amma siz ardıcıl istəyirsinizsə, bu gözəl var danışarlar. Dəyər ağac dəyərindən az olduqda, biz ağac sol recurse istəyirəm başqa biz ağac sağ recurse istəyirəm. Belə ki, bu göz kiçik edilməsi addım idi. Bu göz kiçik edilməsi iki addım - biz çox xətləri bu ayıra bilməz. Okay. Bu kiçik baxmaq edilməsi Addım iki, burada belə geri dəyər ağac dəyər bərabərdir, və ya hər şey. 

Bu əhəmiyyətli bir şey. O sinif aşkar etdi, mən əmin deyiləm lakin bu qısa qapanmasına qiymətləndirilməsi deyirlər. Burada fikir dəyəri == ağac dəyəri. Doğrudur ki, bu doğrudur və biz istəyirik 'və ya' ki, burada nə ilə. Belə ki, hətta burada nə düşünmədən, geri gedən bütün ifadə nədir? [Tələbə] True? >> Bəli, çünki bir şey doğru, or'd - bir şey ilə və ya doğru or'd mütləq doğrudur. Belə ki, tezliklə biz geri value = ağac dəyəri bax biz yalnız doğru geri olacaq. Hətta recurse getmir daha line aşağı edir. Biz bu bir addım bilər. Arxiv ağac bərabər null və bütün bu deyil. Bu bir-line funksiyası etdi. Bu da qısa qapanma qiymətləndirilməsi nümunəsidir. Amma indi eyni fikirdir - əvəzinə - əgər ağac deyil bərabər null edir - yaxşı və ya, ağac bərabər null etsə, o, pis halda ağac null bərabərdir, onda birinci şərt yalan olacaq. Bir şey ilə anded Belə yalan nə olacaq? [Tələbə] Asma. >> Bəli. Bu, qısa qapanma qiymətləndirilməsi digər yarısı Ü ağac, biz hətta getmək üçün bərabər null getmir əgər - ağac bərabər null əgər və ya, sonra biz dəyər == ağac dəyəri nə deyil. Biz yalnız dərhal yalan geri olacaq. Qısa qapanma qiymətləndirmək deyil əgər bəri hansı, vacibdir ağac bərabər null əgər, sonra bu ikinci vəziyyətdə, seg günah edir ağac-> dəyəri null dereferencing çünki. Belə ki, var. Bu edə bilərsiniz - bir dəfə artıq tutulub. Bu, bu, bu bir xətt edilməsi deyil, həmçinin bir çox şey lakin burada bəlkə şəraitində ortaq bir şey deyil lakin (ağac! = NULL və ağac-> dəyəri == dəyəri), nə əgər. Bu çox ümumi vəziyyəti, harada əvəzinə olan iki ifs bu qırmaq, istədiyim, ağac null edir? OK, bu, null deyil, belə ki, indi dəyərinə bərabər ağac dəyəri? Bu etməyin. Bunun əvəzinə, bu vəziyyəti, bu günah seg heç vaxt bu null olmaq olur, əgər çıxmaq olacaq. Sizin ağac tamamilə etibarsız göstərici olduqda Bəli, mən tapmaq, hələ, günah seg bilər ağac null əgər ancaq bu günahı seg bilməz. Bu null Əgər siz ilk növbədə göstərici dereferenced əvvəl, çıxmaq olardı. [Tələbə] Bu adlandırılan tənbəl qiymətləndirilməsi mı? 

[Bowden] Lazy qiymətləndirilməsi ayrı bir şeydir. Lazy qiymətləndirmə, bir dəyər üçün xahiş daha kimi bir dəyəri cür hesablamaq üçün xahiş, lakin dərhal ehtiyac yoxdur. Siz həqiqətən ehtiyac qədər Belə ki, qiymətləndirdi deyil. Bu tam eyni şey deyil, lakin Huffman pset olaraq, biz "tənbəlcəsinə" yazmaq söyləyir. Biz əslində yazma buffering edirik, çünki biz bunu səbəbi - biz, bir zaman fərdi bit yazmaq istəmirəm və ya bir zamanda fərdi bytes biz əvəzinə bayt yığın almaq istəyirəm. Biz bayt yığın var bir dəfə sonra, sonra biz onu yazmaq lazımdır. Yazmaq xahiş baxmayaraq - və fwrite və fread şey eyni cür edin. Onlar oxuyur və yazır bufer. Dərhal yazmaq üçün xahiş baxmayaraq, yəqin ki, olmayacaq. Və şeyi yazılı olacaq əmin ola bilməz siz hfclose zəng və ya hər hansı qədər ki, sonra deyir ki, tamam, mən, mənim fayl bağlanması alıram Mən daha yaxşı hələ yazılı olmayan hər şey yazmaq istədiyiniz deməkdir. Bu, heç hər şeyi yazmaq lazımdır ki, Dosyayı bağlanması, sonra qədər bu lazımdır. Belə ki, yalnız nə tənbəl - bu baş var qədər gözləyir. Bu - 51 almaq və daha çox ətraflı daxil olacaq 51 OCaml və hər şey, hər şey recursion çünki. Heç əsasən, həllər iterativ var. Hər şey recursion və tənbəl qiymətləndirmə edir hallarda bir çox üçün əhəmiyyətli olacaq siz tənbəlcəsinə qiymətləndirmək olmasaydı yerləşir ki, deməkdir - Məsələn sonsuz uzun olan axınları var. Nəzəri olaraq, siz 1-2-3-4-5-6-7 bir sel kimi təbii nömrələri hesab edə bilər Belə ki, tənbəlcəsinə qiymətləndirilir şey gözəl olur. Mən onuncu sayı istəyirsiniz, onda mən onuncu sayı qədər qiymətləndirmək olar. Mən yüzüncü sayı istəyirsinizsə, onda mən yüzüncü sayı qədər qiymətləndirmək olar. Tənbəl qiymətləndirmə olmadan, o, dərhal bütün nömrələri qiymətləndirmək üçün cəhd olacaq. Siz sonsuz bir çox nömrələri qiymətləndirilməsi edirik ki, yalnız mümkün deyil. Belə hallar çox olduğu tənbəl qiymətləndirilməsi şeyi işləmək yalnız vacibdir. 

İndi daxil olacaq yerləşir daxil yazmaq üçün eynilə onun müəyyən dəyişir. Belə ki, hazırda bu bool insert (int) dəyəri var. Biz bool insert (int dəyəri node * ağacı) ki, dəyişiklik olacaq. Biz həqiqətən bir bit bir daha dəyişiklik olacaq, biz niyə görəcəksiniz. Və edək, yalnız onun heck üçün build_node hərəkət biz bir funksiyası prototip yazmaq üçün yoxdur belə yuxarıda daxil edin. Hansı insert ilə build_node istifadə olacaq ki, bir ipucu edir. Okay. Üçün bir dəqiqə edin. Siz ki, çəkmək istəyirsinizsə, mən yenidən xilas edirəm və ya, ən azı, mən artıq idi. Mən, insert məntiqi düşünmək bir qədər fasilə istədi siz hesab edə bilər. Ümumiyyətlə, yalnız heç yarpaqları da daxil ediləcək. I 1 daxil, əgər kimi, sonra qaçılmaz 1 daxil etmək gidiyorum - Mən qara dəyişdirmək lazımdır - I'll burada 1 daxil edilir. I 4 daxil və ya, mən burada artıq 4 daxil olmaq istəyirəm. Heç nə fərqi Belə ki, bir yarpaq da daxil etmək olacaq. Siz var Bütün Siz node almaq qədər ağac aşağı təkrarlamaq deyil ki node ana, yeni node ana olmalıdır və sonra asılı olaraq, onun sağ və ya sol pointer dəyişdirmək bu və ya daha çox cari node az deyil. Yeni node qeyd etmək ki, pointer dəyişdirin. Belə ki, ağac aşağı təkrarlamaq yeni node üçün yarpaq point etmək. Həmçinin bundan əvvəl vəziyyət növü qadağan niyə düşünmək, doğru olduğu Mən binar ağac inşa yerləşir yalnız bir node baxdı, əgər bütün yol aşağı iterated ancaq 9 7 solunda idi. Belə ki, bu ssenari mümkün deyil - haqqında 9 və ya bir şey daxil düşünürəm; ilk node da, Mən 7 görmək və mən yalnız doğru getmək üçün gedirəm gedirəm. Belə ki, bir yarpaq gedən daxil oldum, mən nə fərqi yoxdur və müvafiq alqoritmi istifadə edərək, bir yarpaq üçün mənə 7 sol 9 daxil etmək üçün mümkün olacaq kimi tezliklə mən 7 hit Mən doğru getmək üçün gedirəm, çünki. Hər başlamaq üçün bir şey varmı? [Tələbə] Mən bunu. >> Sure. [Tələbə, anlaşılmaz] [Digər tələbəsı, anlaşılmaz] [Bowden] Bu yüksək qiymətləndirib edir. Okay. Izah etmək istəyirsiniz? 

Biz daxil bilirsiniz ki, ildən [Tələbə] ağac sonunda yeni qovşaqlarının, Mən iteratively ağac vasitəsilə looped Mən null işarə bir node var qədər. Və sonra sağ və ya sol tərəfdə ya qoymaq üçün qərar bu hüququ dəyişən istifadə, bu yerləşir qoymaq üçün mənə. Və sonra, mahiyyətcə, yalnız ötən etdi - o yaradan ki, yeni node ki, temp node point, sol tərəfində və ya sağ ya dəyəri doğru nə asılı olaraq. Nəhayət, mən öz test dəyəri yeni node dəyəri. [Bowden] Okay, mən burada bir məsələ oldu. Bu orada yolu 95% kimi. Görürəm ki, bir məsələ də, hər kəsdən bir məsələ görür? Onlar loop çıxmaq altında hal nədir? [Tələbə] temp null deyil? >> Bəli. Temp null əgər Beləliklə, siz loop çıxmaq necə. Amma burada nə etməliyəm? Qaçılmaz null olan mən dereference temp. Beləliklə, siz nə etmək lazımdır başqa bir şey temp null qədər yalnız, track saxlamaq deyil bütün zaman əsas takip etmək istəyirəm. Biz də node * valideyn istəyirəm ki, biz null ilk ki saxlaya bilərsiniz danışarlar. Bu, ağac kökü üçün qəribə davranış üçün gedir lakin biz almaq lazımdır. Dəyəri nə daha böyükdür, onda temp = temp hüququ. Amma əvvəl ki, valideyn = temp. Və ya valideynlər həmişə bərabər temp gedir? Halda ki? Temp null deyil, onda mən, nə olursa olsun, aşağı hərəkət gedirəm temp ana olan bir node. Belə ki, valideyn temp olacaq, sonra aşağı temp hərəkət. İndi temp null, lakin null ki şey müəssisəyə valideyn xal. Belə ki, aşağı burada, mən sağ 1 bərabərdir təyin etmək istəmirəm. Mən, belə ki, sağ = 1, əgər sağ köçürülüb və mən də etmək istəyirəm tapmaq - Siz sol hərəkət etsəniz, 0 hüququ bərabər qurmaq istəyirik. Və ya başqa heç sağa hərəkət edin. Belə ki, sağ = 0. Sağ = 1 varsa, indi biz əsas sağ göstərici newnode etmək başqa biz valideyn sol göstərici newnode etmək istəyirəm. Ki Suallar? Okay. Beləliklə, bu yolla biz - də, faktiki olaraq, əvəzinə bu etdiyini, biz yarısı siz build_node istifadə gözlənilir. Newnode null bərabər, əgər, sonra saxta qayıtmaq. Ki, var. İndi bu biz nə gözlənilir budur. 

Bu heyət həllər nə edir. Mən bu barədə gedən "doğru" yolu kimi bu razı lakin bu gözəl gözəl və işləyəcək. İndi bir az qəribə doğru bir şey deyil ağac null kimi off başlayır, biz bir null ağac keçir. Mən bunu bir null ağac keçən davranışı müəyyən asılıdır danışarlar. Mən sizə bir null ağac keçmək əgər edirəm sonra null ağac daxil dəyəri daxil yalnız dəyər ki, bir node olduğu bir ağac qaytarmalıdır. Insanlar razısınızmı? Siz ola bilər, siz istəyirdi, Bir null ağac keçmək əgər və bunu bir dəyər əlavə etmək istəyirik, saxta qayıtmaq. Bu müəyyən qədər sizin üçün deyil. Mən o bildirib və ilk şey - çünki yaxşı, siz sorun bunu etmək olacaq biz şey üçün qlobal göstərici olsaydı, bu, daha asan olardı ağac null əgər ancaq ki, biz bu barədə nə edə heç bir şey var deyil. Biz yalnız yalan ola bilər. Mən insert dəyişdirmək üçün gedirəm. Biz texniki yalnız burada, bu doğru dəyişə bilər necə ki, şeyə iterating oldu amma bir node ** ağac etmək üçün daxil dəyişdirmək üçün gedirəm. Cüt göstəricilər. Bu nə deməkdir? Əvəzində qovşaqlarının üçün göstəricilər ilə məşğul olan, Mən manipulyasiya etmək gidiyorum şey bu göstəricisidir. Mən bu göstərici manipulyasiya üçün gedirəm. Mən birbaşa göstəricilərinə manipulyasiya üçün gedirəm. , Aşağı düşünmək ildən bu mənada edir - də, hazırda bu bal null üçün. Mən istəyirəm null deyil işaret üçün bu göstərici manipulyasiya edir. Mən bunu mənim yeni node qeyd etmək istəyirəm. Mən yalnız mənim göstəricilərinə to göstəricilərinə takip Əgər sonra mən bir valideyn göstərici izlemek ehtiyac yoxdur. Mən yalnız göstərici null işarə edir görmek üçün takip edə bilərsiniz və pointer işarə edir əgər null üçün Mən istəyirəm node qeyd etmək dəyişdirin. Mən göstərici bir pointer çünki Mən onu dəyişə bilərsiniz. Indi bu hüququ bax edək. Siz, həqiqətən, recursively olduqca asanlıqla bunu edə bilərsiniz. Biz bunu istəyirsiniz? Bəli, biz edirik. 

Nin recursively görmək edək. Birincisi, nə bizim əsas işi olacaq? Demək olar ki, həmişə bizim əsas işi, ancaq faktiki olaraq, bu çətin növ edir. Ilk ilk şey, əgər (ağac == NULL) Mən yalnız yalan qayıtmaq olacaq danışarlar. Bu ağac olan null fərqlidir. Bu kök göstərici null olan göstəricisidir olan kök göstərici mövcud deyil deməkdir. Belə ki, aşağı burada, mən əgər node * - nin bu təkrar edək. Node * root = NULL, və sonra mən kimi bir şey etməklə insert zəng gedirəm və kök daxil 4 daxil edin. Belə & kök, kök bir node * Əgər sonra və kök bir node ** olacaq. Bu etibarlıdır. Burada Bu halda, ağac, ya daxil - ağac null deyil. Burada. Tree null deyil; * ağac null ki, gözəl olan * ağac null, onda mən bu manipulyasiya bilər, çünki İndi mən onu qeyd etmək istəyirəm nə qeyd etmək. Ağac null olsa ki, mən yalnız burada gəldi və null dedi deməkdir. Mənada deyil. Hesab edirəm ki, bir şey edə bilməz. Ağac null varsa, yalan qayıtmaq. Mən əsasən artıq real baza halda nə dedi. Və nə olacaq? [Tələbə, anlaşılmaz] [Bowden] Bəli. Belə ki, (* ağac == NULL) əgər. Bu burada işə aid mənim qırmızı göstərici göstəricisidir, mən diqqət edirəm, burada Mən bu göstərici diqqət alıram kimi, belə ki, indi bu göstərici diqqət edirəm. İndi bu göstərici diqqət edirəm. Belə ki, əgər mənim node ** olan mənim qırmızı göstərici, daim - * Əgər mənim qırmızı pointer, heç null edir ki, mən bir pointer işarə diqqət alıram olduğu halda am deməkdir - bu bir yarpaq aid bir göstəricisidir. Mən yeni node işaret üçün bu göstərici dəyişə istəyirəm. Burada geri gel. Mənim newnode yalnız node * n = build_node (dəyər) olacaq sonra n, n = NULL əgər yalan qayıtmaq. Else biz göstərici hazırda işarə nə dəyişdirmək istədiyiniz indi bizim yeni inşa node qeyd etmək. Biz əslində burada edə bilərsiniz. Əvəzində n deyərək, biz demək * ağac = * ağac əgər. Hər kəs başa düşürük ki? Bu göstəricilər üçün göstəricilər ilə məşğul olaraq, biz onları qeyd etmək istəyirəm şeyi qeyd etmək null göstəricilərinə dəyişə bilərsiniz. Bu bizim əsas işi var. 

İndi təkrar və ya bizim recursion, biz bunu etdik bütün digər recursions çox oxşar olacaq. Biz, dəyəri daxil etmək istəyirəm olacaq və indi mən yenə ternary istifadə gedirəm, amma nə bizim vəziyyətdə olacaq? Biz biz sol və ya sağ getmək istəyirəm karar üçün nə aradığınız edir? Ayrı-ayrı addımlar bunu edək. Əgər (dəyər <) nə? [Tələbə] Ağac dəyəri? [Bowden] Mən hazırda Ben unutmayın - [Tələbələr, anlaşılmaz] [Bowden] Bəli, belə burada, deyək ki, bu yaşıl arrow ağac hazırda nə Məsələn, bu göstərici bir göstəricisidir. Belə ki, 3-bir göstərici bir pointer am deməkdir. Bu dereference iki dəfə yaxşı keçdi. Mən nə - necə ki etməliyəm? [Tələbə] dəfə Dereference, sonra nə arrow yol? [Bowden] Belə (* ağacı) bir dereference edir -> dəyər mənə dolayı işarə edirəm ki node dəyəri vermək niyyətindədir. Mən də sizə tercih əgər tree.value ** yaza bilərsiniz. Işləri Ya. O halda, mən dəyəri daxil zəng etmək istəyirəm. Nə mənim yenilənir node ** olacaq? Mən sol getmək istəyirəm, belə ki, ** tree.left mənim sol olacaq. Mən o şey üçün pointer istəyirəm ki, sol null göstərici olan qədər başa əgər, Mən yeni node qeyd etmək onu dəyişə bilərsiniz. 

Və digər halda çox oxşar ola bilər. Nin həqiqətən mənim ternary ki, hazırda edək. Əgər dəyər <(** ağac). Dəyəri dəyər daxil edin. Sonra, sol bizim ** güncellemek istəyirsinizsə başqa biz sağ bizim ** yeniləmək istəyirəm. [Tələbə] ki pointer üçün pointer almaq mı? [Bowden] unutmayın - ** tree.right bir node ulduz edir. [Tələbə, anlaşılmaz] >> Bəli. ** Tree.right bu göstərici ya bir şey kimi. Belə ki, bir pointer alaraq ki, mən istədiyiniz nə mənə verir ki, oğlan üçün pointer edir. Biz iki göstəricilərinə istifadə niyə [Tələbə] biz yenidən getmək bilər? [Bowden] Bəli. Belə ki, - heç əvvəl bilər və həll iki göstəricilərinə etmədən bunu bir yol idi. Siz iki göstəricilərinə istifadə anlamaq lazımdır və bu təmiz həll edir. Həmçinin, mənim ağac ne olur ki, qeyd - mənim kök null idi nə olur? Mən burada, bu halda bunu ne olur? Belə node * root = NULL, & kök daxil 4 daxil edin. Kök bu sonra nə olacaq? [Tələbə, anlaşılmaz] >> Bəli. Root dəyəri 4 olacaq. Root sol null olacaq, kök sağ null olacaq. Halda biz, ünvanı kök keçməyən biz kök dəyişdirmək bilmədi. Halda, burada ağac - kök null olduğu biz yalnız yalan qayıtmaq idi. Biz edə heç bir şey yoxdur. Biz boş ağac bir node ekleyemezsiniz. Amma indi biz, biz yalnız bir node ağac daxil boş ağac olun. Hansı adətən bu iş ehtimal ki, gözlənilən yoldur. 

Bundan əlavə, bu xeyli qısa həmçinin müəssisənin track saxlanılması, və siz bütün yol aşağı təkrarlamaq. İndi mənim valideyn var və mən yalnız hər hansı mənim ana sağ göstərici var. Biz iteratively bu idi əgər əvəzinə, bir müddət loop ilə eyni fikir olardı. Lakin əvəzinə mənim ana göstərici ilə məşğul olan, əvəzinə mənim cari göstərici şey olacaq Mən birbaşa mənim yeni node qeyd etmək değiştirmeyle edirəm ki,. Mən bunu sol işarə olsun ilə məşğul yoxdur. Mən doğru işarə olsun ilə məşğul yoxdur. Bu göstərici, mən yeni node qeyd etmək müəyyən etmək gidiyorum nə olursa olsun yalnız deyil. Hər kəs bunu necə anlamaq? Əgər biz niyə bu şəkildə etmək istəyirəm lakin ən azı bu bir həll kimi işlər? [Tələbə] Harada biz doğru qayıtmaq edirsiniz? [Bowden] Burada yəqin ki. Biz doğru bu daxil edin, doğru geri. Else, aşağı burada daxil yekunları nə qayıtmaq istəyirəm olacaq. 

Və bu recursive funksiyası barədə xüsusi nedir? O, belə uzun bəzi optimallaşdırılması ilə tərtib kimi, recursive quyruq var ki, bu etiraf edəcək və bu bir yığın daşqın almaq heç vaxt bizim ağac 10,000 ya 10 milyon hündürlüyü belə. [Tələbə, anlaşılmaz] [Bowden] Mən onu Daş da bunu edirəm - və ya nə optimallaşdırılması səviyyəsi tanınmış bir quyruq recursion üçün tələb olunur. Mən bunu etiraf edirəm - GCC və cingilti həmçinin onların optimallaşdırılması səviyyəsi üçün müxtəlif mənaları var. Mən onu quyruq recursion tanımaq əmin üçün DashO 2, demək istəyirəm. Amma biz - Bir Fibonocci Məsələn filan kimi qurmaq bilər. O qurmaq çətindir, çünki bu test asan deyil belə böyük olduğunu bir ikili ağac. Lakin Bəli, mən bu DashO 2, hesab siz DashO 2 ilə tərtib, bu quyruq recursion üçün görünür və optimize ki. Nin geri edək - daxil sözün ehtiyacı son şey. Buraya daxil geri edək biz eyni fikri nə olacaq yerləşir. Bu hələ tamamilə idarə edə olan deyil flaw olacaq kök itself null, və ya son giriş, null zaman əvəzində bir valideyn göstərici ilə məşğul olan, nin göstəricilərinə əməl göstəricilərinə eyni məntiq tətbiq edək. Burada Əgər biz node ** hh saxlamaq və biz, sağ artıq takip ehtiyac yoxdur lakin node ** hh = & ağac. İndi bizim isə loop * hh bərabər null deyil isə olacaq. Artıq valideynlər izlemek üçün ehtiyac yoxdur. Sol və sağ izlemek ehtiyac yoxdur. Biz artıq temp istifadə etdiyiniz, çünki mən, bu temp zəng edəcəyik. Okay. Beləliklə, əgər (dəyər> * temp), sonra və (* temp) -> sağ başqa temp = & (* temp) -> ayrıldı. İndi, bu nöqtədə bu isə loop sonra, Bəlkə bu barədə iteratively recursively çox düşünmək daha asandır, çünki yalnız bunu lakin bu isə loop sonra, * Temp biz dəyişdirmək istədiyiniz göstəricisidir. 

Əvvəl, valideyn idi və biz valideyn sol və ya valideyn sağ ya dəyişdirmək istədi lakin biz valideyn doğru dəyişdirmək istəyirsinizsə, sonra * temp valideyn sağ və biz birbaşa dəyişdirə bilərsiniz. Belə ki, aşağı burada, biz * temp = newnode edə bilər ki, bu. Bildiriş Beləliklə, biz bu idi bütün kodu xətləri çıxarmaq idi. Əlavə səy edir ki, bütün əsas izlemek üçün. Burada biz yalnız göstərici üçün pointer takip əgər, və biz bütün bu qıvrım aşırma qurtarmaq istəyirdi, hətta, bu qısa baxmaq olun. Bu, indi eyni həll lakin kodu az xətləri. Sonra, bir etibarlı həlli kimi tanınması başlamaq o, tamam, həmçinin kimi çox haqqında səbəbdən daha asandır niyə mən int doğru bu bayrağı var? Ki, nə deməkdir? Oh, bu signifying ki, Mən getmək hər zaman, mən müəyyən etmək lazımdır Mən sol Əgər başqa mən sıfıra müəyyən etmək lazımdır. Burada bu barədə səbəbi yoxdur, bu barədə düşünmək yalnız daha asan var. Suallar? [Tələbə, anlaşılmaz] >> Bəli. OK, belə ki, son bit - Ki, biz nə edə bilər bir tez və asan funksiyası tapmaq let's - birlikdə hərhalda bir funksiyası olan cəhd və yazmaq bir ikili axtarış ağac olub ki, qayğı deyil. Bu funksiya doğru qayıtmalıdırlar şey əgər hər hansı bu ümumi ikili ağac biz aradığınız dəyəri. Beləliklə, biz iteratively bunu edəcəyik sonra ilk recursively bunu bildirin və. Bu, həqiqətən qısa olacaq, çünki həqiqətən yalnız, o, birlikdə edə bilərsiniz. 

Mənim baza halda nə olacaq? [Tələbə, anlaşılmaz] [Bowden] Beləliklə, əgər (ağac == NULL), sonra nə? [Tələbə] yalan qayıt. [Bowden] Else, yaxşı, mən başqa ehtiyac yoxdur. Əgər mənim digər əsas işi idi. [Tələbə] Tree dəyəri? >> Bəli. Belə ki, (ağac-> dəyəri == dəyər əgər. Biz node ** s, node * geri deyilik edək? Şey, bir node ** istifadə etmək lazımdır heç vaxt biz göstəricilərinə değiştirmeyle deyil çünki. Biz yalnız onlara traversing edirik. Ki, olur, onda biz doğru qayıtmaq istəyirəm. Else biz uşaqlar axır istəyirəm. Beləliklə, biz sola hər şey azdır olub Səbəb bilməz və sağ hər şeyi böyükdür. Belə ki, nə bizim şəraiti burada olacaq - və ya, biz nə edəcəyik? [Tələbə, anlaşılmaz] >> Bəli. Arxiv şey (dəyər, ağac-> sol) və ya (dəyər, ağac-> sağ) ehtiva edir. Və bu. Və bəzi qısa qapanmasına qiymətləndirilməsi var bildiriş biz sol ağac dəyəri tapmaq üçün baş Əgər, doğru ağac baxmaq lazımdır heç vaxt. Bütün funksiyası var. İndi iteratively bunu edək az gözəl gedir. Biz node * hh = ağac adi start olacaq. Halda (hh! = NULL). Tez bir problem görəcəksiniz. Əgər hh - buradan, biz heç bu çıxmaq əgər, sonra baxmaq üçün şeyi tökülmək etdik, belə ki, saxta qayıtmaq. (Hh-> dəyəri == dəyəri), doğru geri edin. Beləliklə, biz bir yer var - biz sol və ya sağ getmək istəyirəm bilmirəm. Belə ki, özbaşına isə yalnız sol gedək. Mən açıq-aşkar mən tamamilə hər şeyi tərk etdik bir məsələ daxil etdik - Mən yalnız heç bir ağac sol yoxlayacaq. Mən heç bir hüququ uşaq bir şey yoxlamaq heç vaxt. Bunu nasıl düzeltirim? [Tələbə] Siz yığını ilə sol və sağ takip var. [Bowden] Bəli. Belə ki, bu imkan struct siyahısı node * n, sonra node ** Növbəti? Mən gözəl işlər olduğunu düşünürəm. Qədər burada - Biz sol, və ya let's artıq getmək istəyirəm. Struct list list =, bu başlamaq lazımdır bu struct siyahısına həyata. * List = NULL. Belə ki, bizim bağlı siyahısı olacaq biz artıq atlandı ki subtrees edir. Biz indi tərk axır gedir lakin biz qaçılmaz doğru geri gəlmək lazımdır bəri, Biz struct siyahısı içərisində sağ saxlamaq olacaq. Sonra biz new_list və ya struct lazımdır struct list *, new_list = malloc (sizeof (siyahısı)). Hesab edirəm ki, səhv yoxlanılması ignore gedirəm, amma əgər bu null kontrol etməlidir. O qeyd olacaq node New_list - Mən burada bu qədər istəyirdi nə oh ki, var. Bu ikinci struct siyahısına qeyd edəcək. Bu siyahıları work bağlı yalnız nasıl. Bu int bağlı siyahısı eyni istisna olmaqla, biz yalnız node * ilə int əvəz edirik. Bu tam eyni deyil. Belə new_list, bizim new_list node dəyəri hh> hüququ olacaq. Bizim dəyəri new_list-> sonrakı orijinal siyahısı gedir və sonra new_list qeyd etmək siyahısını yeniləmək üçün olacaq. 

İndi çəkərək şeyi yol bir növ lazımdır biz bütün sol subtree keçdiyi var kimi. İndi biz bu məhsulları çıxarmaq lazımdır kimi hh null deyil, biz yalnız yalan qayıtmaq istəmirəm. Biz indi yeni siyahısını xaricində çəkmək istəyirəm. Bunu bir rahat - də, faktiki olaraq, bunu çox yolları var. Hər kəs bir təklif var? Harada bu və ya necə bunu etməlidir etməliyəm? Biz yalnız bir neçə dəqiqə, lakin heç bir təklif? Əvəzinə - bir yol əvəzinə bizim vəziyyətinin isə olmaqla, nə biz hazırda da arıyorsanız, null deyil əvəzinə biz sadalanması onu null qədər getmək davam edirik. Bizim siyahısı, null olan qədər başa əgər sonra, axtarmaq üzərində axtarış şeyi tökülmək var. Amma bizim siyahıda ilk şey yalnız ilk node olacaq deməkdir. Ilk şey olacaq - biz artıq görmək lazımdır. Belə siyahısı> n bizim ağac olacaq. list-> gələn null olacaq. İndi list bərabər null deyil isə. Cur bizim siyahıdan bir şey çəkmək niyyətindədir. Belə hh bərabər siyahısı> n gedir. Və sonra list bərabər siyahısı> n gedən, və ya siyahısı> sonrakı olunur. Belə ki, əgər hh dəyər dəyər bərabərdir. İndi bizim sağ göstərici və sol pointer də əlavə edə bilərsiniz kimi uzun onlar null deyilik kimi. Burada Down, biz etmişik lazım tapmaq ilk növbədə. Əgər (hh> doğru! = NULL) sonra biz siyahısına daxil olan node daxil edir. Əgər (hh> sol), bu əlavə iş bir az, ancaq gözəl var. Əgər (hh> sol! = NULL) və biz bağlıdır siyahısına sol daxil olacaq və bu olmalıdır. Biz təkrarlamaq - kimi uzun biz siyahısına bir şey var, biz baxmaq üçün başqa bir node var. Beləliklə, biz ki, node baxmaq biz növbəti bir siyahısını inkişaf. Ki node biz aradığınız dəyəri, biz doğru ola bilər. Else, həm də bizim sol və sağ subtrees daxil onlar null deyilik kimi uzun kimi, bizim siyahısına daxil biz istər-istəməz onlara getmək üçün. Onlar null deyil, əgər bizim kök göstərici iki şeyi qeyd, əgər listemize null olan qədər başa belə sonra ilk biz bir şey çıxardı. Və sonra biz geri iki şey qoymaq, indi listemize ölçüsü 2 edir. , Sonra biz geri loop olacaq və biz yalnız çəkmək olacaq nin, bizim kök node sol göstərici deyək. Və yalnız baş saxlamaq lazımdır, biz hər şeyə loop çıxacağıq. 

Bu daha çox mürəkkəb idi edək ki, bu recursive həlli. Mən neçə dəfə bildirib etdik bu recursive həll adətən həlli iterativ ortaq çox var. Burada bu recursive həll edir məhz budur. Yalnız dəyişiklik yerine dolayısı yığını istifadə, proqram yığını deyil Siz hələ müraciət etmək lazım qovşaqlarının track saxlanılması üçün yol kimi, İndi aydın şəkildə bağlı siyahısını istifadə etmək lazımdır. Nə node hələ ziyarət lazımdır və hər iki halda siz track saxlanılır. Bu recursive halda yalnız daha asan var çünki bir yığın proqram yığını kimi həyata keçirilir. Bu bağlı siyahısı, bir yığın edək ki. Biz yalnız yığını qoymaq olursa olsun biz növbəti səfər yığını qoparmaq olacaq nə dərhal edir. Biz hər hansı bir sualınız vaxt həyata istəyirik, ancaq? [Tələbə, anlaşılmaz] [Bowden] Bəli. Biz bağlı siyahısı var əgər, cari, bu oğlan qeyd edir və indi yalnız bu oğlan diqqət bizim bağlı list inkişaf edirik. Biz istiqamətində bağlı list üzərində traversing edirik. Və sonra biz əlaqəli siyahısı və stuff azad etməlidir tapmaq bir doğru və ya yalan qaytarılması əvvəl biz ehtiyac bizim bağlı list üzərində təkrarlamaq və həmişə aşağı burada, mən tapmaq biz hh sağ bərabər olmadıqda, belə ki, indi biz azad etmək istəyirik, əlavə hh çünki, yaxşı, biz tamamilə siyahısı unuda idi? Bəli. Belə ki, biz burada etmək istəyirəm nə. İmleci harada? Cur idi - biz struct siyahısına * 10 növbəti liste bərabərdir istəyirəm. Pulsuz siyahısı list = temp. Və halda biz doğru qayıtmaq, burada biz təkrarlamaq lazımdır şeyi azad bizim bağlı siyahı qalan artıq. Bu recursive həlli haqqında gözəl şey şey azad edilir yalnız sizin üçün nə edəcək yığını off yaratma factorings deməkdir. Belə ki, hard-to-beyin haqqında kodu 3 xətt kimi bir şey olan getdi sonra əhəmiyyətli dərəcədə daha çox bir şey çətin-to-hesab-haqqında kodu satır. Hər hansı bir daha suallar? Bütün hüquqlar. Biz yaxşı edirik. Bye! [CS50.TV]