TechCodeview

Binārais koks nozīmē, ka mezglam var būt ne vairāk kā divi bērni. Šeit pats binārais nosaukums liek domāt, ka 'divi'; tāpēc katram mezglam var būt 0, 1 vai 2 bērni.

Izpratīsim bināro koku, izmantojot piemēru.

Iepriekš minētais koks ir binārs koks, jo katrā mezglā ir maksimāli divi bērni. Iepriekš minētā koka loģiskais attēlojums ir parādīts zemāk:

Iepriekš minētajā kokā mezglā 1 ir divi rādītāji, t.i., kreisais un labais rādītājs, kas norāda attiecīgi uz kreiso un labo mezglu. 2. mezglā ir abi mezgli (kreisais un labais mezgls); tāpēc tai ir divas norādes (pa kreisi un pa labi). Mezgli 3, 5 un 6 ir lapu mezgli, tāpēc visi šie mezgli satur NULL rādītājs gan kreisajā, gan labajā daļā.

Binārā koka īpašības

• Katrā i līmenī maksimālais mezglu skaits ir 2ⁱ.
• Koka augstums tiek definēts kā garākais ceļš no saknes mezgla līdz lapas mezglam. Iepriekš parādītā koka augstums ir vienāds ar 3. Tāpēc maksimālais mezglu skaits 3. augstumā ir vienāds ar (1+2+4+8) = 15. Kopumā maksimālais mezglu skaits, kas ir iespējams augstumā h ir (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Minimālais iespējamais mezglu skaits augstumā h ir vienāds ar h+1 .
• Ja mezglu skaits ir minimāls, tad koka augstums būtu maksimālais. Un otrādi, ja mezglu skaits ir maksimālais, tad koka augstums būtu minimāls.

Ja binārajā kokā ir 'n' mezglu skaits.

Minimālo augstumu var aprēķināt šādi:

Kā mēs to zinām,

n = 2^h+1-1

izslēdziet izstrādātāja režīmu

n+1 = 2^h+1

Paņemot baļķi no abām pusēm,

žurnāls₂(n+1) = log2(2^h+1)

žurnāls₂(n+1) = h+1

h = žurnāls₂(n+1) - 1

Maksimālo augstumu var aprēķināt šādi:

Kā mēs to zinām,

n = h+1

h = n-1

Bināro koku veidi

Ir četri bināro koku veidi:

Pilns/ pareizs/ stingrs Binārais koks Pilnīgs binārais koks Ideāls binārais koks Deģenerēts Binārais koks Līdzsvarots binārais koks

1. Pilns/ pareizs/ stingrs Binārais koks

Pilnais binārais koks ir pazīstams arī kā stingrs binārais koks. Koku var uzskatīt par pilnu bināro koku tikai tad, ja katrā mezglā ir jābūt 0 vai 2 bērniem. Pilnu bināro koku var definēt arī kā koku, kurā katrā mezglā ir jābūt 2 bērniem, izņemot lapu mezglus.

Apskatīsim vienkāršo pilnā binārā koka piemēru.

Iepriekš minētajā kokā mēs varam novērot, ka katrā mezglā ir nulle vai divi bērni; tāpēc tas ir pilns binārs koks.

Pilna binārā koka īpašības

• Lapu mezglu skaits ir vienāds ar iekšējo mezglu skaitu plus 1. Iepriekš minētajā piemērā iekšējo mezglu skaits ir 5; tāpēc lapu mezglu skaits ir vienāds ar 6.
• Maksimālais mezglu skaits ir tāds pats kā mezglu skaits binārajā kokā, t.i., 2^h+1-1.
• Minimālais mezglu skaits pilnā binārajā kokā ir 2*h-1.
• Pilna binārā koka minimālais augstums ir žurnāls₂(n+1) - 1.
• Pilna binārā koka maksimālo augstumu var aprēķināt šādi:

n= 2*h - 1

n+1 = 2*h

kad tika izgudrots pirmais dators

h = n+1/2

Pilnīgs binārais koks

Pilns binārais koks ir koks, kurā visi mezgli ir pilnībā aizpildīti, izņemot pēdējo līmeni. Pēdējā līmenī visiem mezgliem jābūt pēc iespējas atstātiem. Pilnībā binārajā kokā mezgli jāpievieno no kreisās puses.

Izveidosim pilnīgu bināro koku.

Iepriekš minētais koks ir pilnīgs binārais koks, jo visi mezgli ir pilnībā aizpildīti, un visi pēdējā līmeņa mezgli tiek pievienoti vispirms kreisajā pusē.

Pilnīga binārā koka īpašības

• Maksimālais mezglu skaits pilnā binārajā kokā ir 2^h+1- 1.
• Minimālais mezglu skaits pilnā binārajā kokā ir 2^h.
• Pilna binārā koka minimālais augstums ir žurnāls₂(n+1) - 1.
• Pilna binārā koka maksimālais augstums ir

Ideāls binārais koks

Koks ir ideāls binārs koks, ja visiem iekšējiem mezgliem ir 2 bērni un visi lapu mezgli atrodas vienā līmenī.

Apskatīsim vienkāršu ideāla binārā koka piemēru.

attēlu izlīdzināšana css

Zemāk esošais koks nav ideāls binārs koks, jo visi lapu mezgli nav vienā līmenī.

Piezīme. Visi ideālie binārie koki ir pilnīgi binārie koki, kā arī pilnie binārie koki, bet otrādi nav taisnība, t.i., visi pilnīgie binārie koki un pilnie binārie koki ir ideāli binārie koki.

Deģenerēts binārais koks

Deģenerēts binārais koks ir koks, kurā visiem iekšējiem mezgliem ir tikai viens bērns.

Izpratīsim deģenerētu bināro koku, izmantojot piemērus.

Iepriekš minētais koks ir deģenerēts binārs koks, jo visiem mezgliem ir tikai viens bērns. Tas ir pazīstams arī kā labi šķībs koks, jo visiem mezgliem ir tikai pareizais bērns.

Iepriekš minētais koks ir arī deģenerēts binārs koks, jo visiem mezgliem ir tikai viens bērns. Tas ir pazīstams arī kā pa kreisi šķībs koks, jo visos mezglos ir tikai kreisais bērns.

Līdzsvarots binārais koks

Līdzsvarotais binārais koks ir koks, kurā gan kreisais, gan labais koks atšķiras vismaz par 1. Piemēram, AVL un Sarkanmelni koki ir līdzsvaroti binārie koki.

Izpratīsim līdzsvaroto bināro koku, izmantojot piemērus.

Iepriekš minētais koks ir līdzsvarots binārs koks, jo atšķirība starp kreiso apakškoku un labo apakškoku ir nulle.

Iepriekš minētais koks nav līdzsvarots binārs koks, jo atšķirība starp kreiso apakškoku un labo apakškoku ir lielāka par 1.

Binārā koka ieviešana

Binārais koks tiek realizēts ar rādītāju palīdzību. Koka pirmo mezglu attēlo saknes rādītājs. Katrs koka mezgls sastāv no trim daļām, t.i., datiem, kreisā rādītāja un labā rādītāja. Lai izveidotu bināro koku, vispirms ir jāizveido mezgls. Mēs izveidosim lietotāja definētu mezglu, kā parādīts tālāk:

 struct node { int data, struct node *left, *right; } 

Iepriekš minētajā struktūrā datus ir vērtība, kreisais rādītājs satur kreisā mezgla adresi un labais rādītājs satur labā mezgla adresi.

Binārā koka programma C valodā

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Iepriekš minētais kods rekursīvi izsauc funkciju Create() un katrā rekursīvajā izsaukumā izveido jaunu mezglu. Kad visi mezgli ir izveidoti, tas veido bināro koka struktūru. Mezglu apmeklēšanas process ir pazīstams kā koka šķērsošana. Ir trīs veidu šķērsošanas veidi, ko izmanto, lai apmeklētu mezglu:

• Kārtības šķērsošana
• Iepriekšpasūtīšanas šķērsošana
• Pasta pasūtījumu šķērsošana