Tema: Teń salmaqlılıqlanǵan binar terekler joba

TEMA: Teń salmaqlılıqlanǵan binar terekler
JOBA:

1. 
   Binar hám kóptarmaqlı terekler.
   
2. 
   Tereklerdi binar kóriniske keltiriw algoritmı.
   
3. 
   Tereksiman maǵlıwmatlar strukturaları.
   

Binar hám kóptarmaqlı terekler
Jańa obiekt yamasa túsiniklerge anıq túsindirme kirgiziwdiń eń tiykarǵı qaǵıydalarınan biri bul onıń tariypida sizge aldınan málim hám túsinikli bolǵan atamalardan paydalanıp anıqlama beriw bolıp tabıladı. Sol sebepli, tariyplerde tiykarınano'z sheńberinden shette bolǵan sózlerdi qóllaw nadurıs. Basqa tárepden, óz-ózin túsindiriwshi programmalıq túsinikler júdá kóp. Bunday tariypler rekursiv tariypler dep ataladı hám tiykarınan sheksiz jıynaqlarǵa tariyp berilgende paydalanıladı. Bunday jıynaqǵa tariyp berilgende, barlıq elementler kestein beriw múmkinshiliksiz, hám júdá kata anıq jıynaqlar ushın nátiyjesiz. Sol sebepli, eń qolay usıl bul obiekt sol jıynaqǵa tiyisli yamasa tiyisli emesligin anıqlaw. Rekursiv tariypler eki bólekten ibarat. Birinshi bóleginde, jıynaqtıń tiykar etip alınǵan elementleri jaylastırıladı. Ekinshi bóleginde, tiykar etip alınǵan yamasa aldın paydalanılǵan elementlerden paydalanilmagan halda jańa obiektler jaratıw ushın qaǵıydalar beriledi. Bul qaǵıydalarǵa jańa obiektlerdi jaratıwda qayta -qayta shaqırıq etiledi. Mısal ushın, natural sanlar kompleksin jaratıw ushın, bir tiykar element, 0, bir tárepleme, hám 1 boyınsha inkrementlash procesi tómendegishe beriledi:
1. 0 ∈ N; 4
2. eger n ∈ N bolsa, keyin (n + 1) ∈ N;
3. N jıynaqta basqa obiektler joq.
Bul qaǵıydalarǵa kóre, natural sanlar kompleksi N tómendegi birliklerden shólkemlesken: 0, 0 + 1, 0 + 1 + 1, 0 + 1 + 1 + 1, hám t.b. N jıynaq biz natural sanlar dep atawshi obiektlerdi óz ishine alar eken, tariypga birpara tártipsiz (qopal ) elementler kestesi de kiredi. Siz quramalı sanlar ústinde arnawlı specifikaciyadan paydalanıp arifmetik ámeller orınlawdı oyda sawlelendire alasızba?
Usınıń sebepinen, tómendegi Arab nomerlerinen shólkemlesken málim shegaralı muǵdarlardan paydalanaib túsindirme keltiriw qolaylaw :
1. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ∈ N;
2. eger n ∈ N bolsa, keyin n0, n1, n2, n3, n4, n5, n6, n7, n8, n9 ∈ N;
3. bular natural sanlar esaplanadı.
Sonday eken, N tiykar etip alınǵan 0 den 9 ǵa shekem bolǵan sanlardan dúzilgen kombinatsiyalardan dúzilgen sanlardı da óz ishine qamtıp alar eken. Rekursiv tariypler eki qıylı maqsette xızmet etedi: joqarıda belgilengeni sıyaqlı, jańa elementler jaratıw hám saylanǵan elemeent sol jıynaqǵa tiyisli yamasa tiyisli emesligin testlab beriw. Testlew processinde bunı sheshiw quramalı bolatuǵın bolsa, ol san ápiwayılaw kóriniske kelmegenshe ápiwayılashtirilib barıladı. Mısal ushın, 123 natural sonmi? N jıynaqtı túsindiriwshi tariypdagi ekinshi jaǵdayǵa tiykarınan 123 ∈ N boladı, eger 12∈ N hám birinshi jaǵdayǵa tiykarınan 3 ∈ N bolǵanda, 12 ∈ N boladı, eger 1 ∈ N hám 2 ∈ N bolǵandava ekewi de Nga tiyisli boladı. Berilgen mısaldaǵı sıyaqlı sannı quramalı kórinisten ápiwayılaw kóriniske ótkera alıw áhmiyetli, sol sıyaqlı 9. 3. 3 bólekte kórip ótetuǵın tez saralaw usılınan paydalanıw nátiyjeli. Rekursiv tariypler tiykarınan nomerler izbe-izligi hám funksiyalardı anıqlawda paydalanıladı.
Funksiyaǵa shaqırıq etilgende ne júz boladı? Funksiya formal parametrlerge iye bolsa, ámeldegi aktual parametrler qimatlariga ózgertiliwi kerek. Bunnan taashqari, sistema programma juwmaqlawshı exe atqarılıwın qay jerge saqlap dawam ettiriwi kerekligini biliwi kerek. Funksiyalar basqa at menen, yamasa tiykarǵı programma (the function main ()) menen de shaqırılıwı múmkin. Funksiyanı qay jerden shaqırıp alıw, sistema tárepinen saqlap qolinshi kerek boladı. Bul qaytıw adreslerin tiykarǵı yadta saqlap barıw arqalı ámelge asırılıwı múmkin, lekin bizge qansha jay kerekligi belgisiz bolsa, onıń ushın kóp awısıq jay ajıratıp ketiw jaramaydı. Funksiyaǵa shaqırıwlarda bolsa adres qaytarıwǵa qaraǵanda kóbirek maǵlıwmatlar saqlap qalınıwi kerek. Sol sebepli, steklardan paydalanıp dinamikalıq jaylastırıw jaqsı nátiyjelerge alıp keledi. Biraq, funksiyaǵa shaqırıqta qanday maǵlıwmatlar saqlanıp qalıwı kerek? Birinshiden, lokal ózgeriwshiler toplanıwı kerek. Eger x lokal ózgeriwshisiniń daǵazası ámeldegi bolǵan f (1) funksiya, x ózgeriwshin lokal daǵaza etiwshi f (2) funksiyaǵa shaqırıq qilsa, sistema bul eki x ózgeriwshilerdi parıqlay alıwı kerek. Eger f2 () x ózgeriwshin isletse, ol jaǵdayda óz x ini ańlatadı ; eger f2 () x ga baha belgilese, ol jaǵdayda f (1) ga tiyisli bolǵan x ózgermeytuǵınnan qaldırilishi kerek. Qashanda f (2) tamamlanılǵanda, f1 () f (2) ga shaqırıq bólindinen aldın jeke x ga ózlestirilgen bahadan paydalanıwı múmkin. Bul házirgi ko'rilayotgan funksiya óz-ózine rekursiv shaqırıq etkendegi bólekte, f (1) f (2) dek birdey funksiya bolǵanda zárúrli. Sistema bul eki x ózgeriwshilerdi qanday parıqlaydı? main () ni óz ishine alıwshı hár bir funksiyanıń jaǵdayı olardıń quramındaǵı barlıq lokal ózgeriwshiler, funksiya parametrleriniń bahaları hám funksiyaǵa shaqırıq qay jerden baslanıwı kerekligini kórsetiwshi adres indikatorlari arqalı xarakterlenedi. Barlıq sol maǵlıwmatlardı ózinde saqlawshı maǵlıwmatlar maydanı aktivatsiya esabatı (activation record) yamasa stek (kompyuterdiń maǵlıwmatlar toplantuǵın sisteması ) ramkası (stack frame) dep ataladı hám stek (kompyuterdiń maǵlıwmatlar toplantuǵın jayı ) de saqlanadı. Aktivatsiya esabatı talay waqıtqa shekem funksiya óziniń ámel sheńberin joǵatpaǵan halda saqlanadı. Bul esabat - funksiyanıń jeke ulıwma birlestirilgen maǵlıwmatlar jayı bolıp, ol jaǵdayda programmalardıń jaqsı jumısqa túsiwi ushın zárúr bolǵan barlıq maǵlıwmatlar saqlanadı. Aktivatsiya maǵlıwmatları ádetde kóp saqlanmaydi, sebebi olar funksiya jumısqa túsirilgende dinamikalıq jaylasadı hám funksiyadan shıǵılǵanda jaylasıwınan shetlesedi. Tek ǵana main () funksiyasındaǵı maǵlıwmatlar talay waqıt saqlanadı.
Ádetde aktivatsiya esabatı (rekordi) tómendegi maǵlıwmatlardı ózinde saqlaydı :
■ Funksiyanıń barlıq parametrleri ushın bahalar, dızbek yacheykalari jaylasqan mánzillerdi hám ózgeriwshilerdi saqlaydı hám barlıq basqa maǵlıwmatlar bántlerinen nusqa aladı.
■ Hár qaysı halda, hár qay jerde saqlanıwı múmkin bolǵan lokal ózgeriwshilerdiń qayerde saqlanıwın kórsetiwshi deskriptor hám kórsetkishlarinigina saqlaydı.
■ Shaqırıq etiwshiniń adresin hám ámeldegi shaqırıwlar jaǵdayın qadaǵalaw etedi.
■ Shaqırıq kórsetkishleriniń dinamikalıq baylanısın támiyinlep turadı.
■ Funksiya qaytarǵan baha void retinde daǵaza etińmeydi. Sebebi, aktivatsiya procesi kólemi bir shaqırıqtan basqasına parıq etiwi múmkin, qaytarılǵan baha shaqırıq aktivatsiyasiniń ońında jaylasadı.