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

Tereklerdi binar kóriniske keltiriw algoritmı
Terek - bul sızıqsız baylanısqan maǵlıwmatlar strukturası bolıp tabıladı (qarang, sızılma ).

Terek óziniń tómendegi belgileri menen klassifikaciyalanadı :
- terekte sonday bir element bar, oǵan basqa elementlerden shaqırıq joq. Usı elementke terek túbiri dep ataladı ;
- terekte qálegen elementke shekli sandaǵı kórsetkishler járdeminde shaqırıq qılıw múmkin;
- terektiń hár bir elementi tek ǵana ózinden aldınǵı kelgen bir element menen baylanısqan. Terektiń hár bir túyini aralıq yamasa terminal (japıraq) bolıwı múmkin. Joqarıdaǵı sızılmada M1, M2 - aralıq, A, B, C, D, E - japıraqlar bolıp tabıladı. Terminal túyindiń ayriqsha klassifikaciyası onıń shaqları joq ekenligi bolıp tabıladı.
Biyiklik - bul terek basqıshı sanı. Joqarıdaǵı sızılma daǵı terek bálentligi ekige teń.
Terek túyinlerinen shıǵıp atırǵan shohlar sanı túyinnen shıǵıw dárejesi dep ataladı (Keltirilgen sızılmada M1 ushın shıǵıw dárejesi 2, M2 ushın bolsa 3 ke teń). Terekler shıǵıw dárejesi boyınsha klasslarǵa ajratıladı :
1) eger maksimal shıǵıw dárejesi m bolsa, ol halda bunday terek m -ne tártipli terek dep ataladı ;
2) eger shıǵıw dárejesi 0 yamasa m bolsa, ol halda tolıq m -ne tártipli terek boladı ;
3) eger maksimal shıǵıw dárejesi 2 bolsa, ol halda bunday terek binar terek dep ataladı ;
4) eger shıǵıw dárejesi 0 yamasa 2 bolsa, ol halda tolıq binar terek dep ataladı.
EXM yadında terekti ańlatıwa eń qolay usılı bul onı baylanısqan dizimler kórinisinde ańlatıw bolıp tabıladı. Dizim elementi túyin ma`nisi hám shıǵıw dárejesin óz ishine alıwshı informasion maydanǵa xamda shıǵıw dárejesine teń bolǵan kórsetkishler maydanına ıyelewi kerek (joqarıdası sızılma ), yaǵnıy elementtiń hár bir kórsetkishi bul elementti túyin uwılları bolǵan túyinlerge baǵdarın anıqlaydı.
Binar terekler eń kóp paydalaniletuǵın terekler túri esaplanadi.
Tereklerdi EXM yadında suwretleniwine kóre xar bir element tórtew maydanǵa iye jazıw esaplanadi. Usı maydanlar ma`nisi uyqas túrde jazıw gilti bolıp, basqa elementlerge shaqırıqtı ańlatadı, yaǵnıy shepke-tómenge, o'nga-tómenge hám jazıw tekstine.
Sonı este tutıw kerekki, terek payda qılınıp atırǵanda, otaga salıstırǵanda shep tárepdegi ul ma`nisi kishi giltga, oń tárepdegi ul bolsa úlken bahalı giltga iye boladı. Mısalı, tómendegi elementlerden binar terek quramız : 50, 46, 61, 48, 29, 55, 79. Ol tómendegi kóriniske iye boladı:

Nátiyjede, oń hám shep bólim terekleri birdey basqıshlı tártiplengen binar terek payda etdik. Eger terektiń oń hám shep bólim terekleri basqıshları ayırmashılıǵı birdan kishi bolsa, bunday terek ideal teń salmaqlılıqlanǵan terek dep ataladı. Joqarıda payda etken binar terekimiz ideal teń salmaqlılıqlanǵan terekke mısal boladı.
Binar terekti payda qılıw ushın EXM yadında elementler tómendegi túrde bolıwı kerek:

Noformal algoritm :
1. Terektiń xar bir túyininde úlken ulga uyqas shettegi shep shoxidan tısqarı barlıq shaqları kesip taslanadı.
2. Bir áke barlıq uwılları gorizontal sızıq menen jalǵanadı.
3. Payda etilgen strukturanıń xar bir túyininde úlken ul usı túyin tómeninde turǵan túyin esaplanadi (eger ol ámeldegi bolsa ).
Algoritm ámeller izbe-izligi tómende keltirilgen.

Terekler ústinde atqarılatuǵın ámeller:
1. Terek ko'ruvi (Obxod dereva).
2. Bólim terekti óshiriw.
3. Bólim terek qoyıw.
Terek ko'ruvini ámelge asırıw ushın tómendegi ush prosedurani orınlaw kerek:
1. Túbirdi qayta islew.
2. Shep tarmaq (shaq) ni qayta islew.
3. Oń tarmaq (shaq) ni qayta islew.