[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]