TechCodeview

Dvejetainis medis reiškia, kad mazgas gali turėti ne daugiau kaip du vaikus. Čia pats dvejetainis pavadinimas rodo, kad „du“; todėl kiekvienas mazgas gali turėti 0, 1 arba 2 vaikus.

Supraskime dvejetainį medį per pavyzdį.

Aukščiau pateiktas medis yra dvejetainis, nes kiekviename mazge yra daugiausiai du vaikai. Aukščiau pateikto medžio loginis vaizdas pateiktas žemiau:

Aukščiau pateiktame medyje 1 mazge yra du rodyklės, t. y. kairysis ir dešinysis rodyklė, nukreipianti atitinkamai į kairįjį ir dešinįjį mazgus. 2 mazge yra abu mazgai (kairysis ir dešinysis mazgas); todėl jame yra dvi rodyklės (kairėje ir dešinėje). 3, 5 ir 6 mazgai yra lapų mazgai, todėl visuose šiuose mazguose yra NULL rodyklė tiek kairėje, tiek dešinėje dalyse.

Dvejetainio medžio savybės

• Kiekviename i lygyje didžiausias mazgų skaičius yra 2ⁱ.
• Medžio aukštis apibrėžiamas kaip ilgiausias kelias nuo šaknies mazgo iki lapo mazgo. Aukščiau parodyto medžio aukštis lygus 3. Todėl maksimalus mazgų skaičius 3 aukštyje yra lygus (1+2+4+8) = 15. Apskritai maksimalus mazgų skaičius aukštyje h yra (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Mažiausias galimas mazgų skaičius aukštyje h lygus h+1 .
• Jei mazgų skaičius yra minimalus, tada medžio aukštis būtų maksimalus. Ir atvirkščiai, jei mazgų skaičius yra maksimalus, tada medžio aukštis būtų minimalus.

Jei dvejetainiame medyje yra „n“ mazgų.

Mažiausias aukštis gali būti apskaičiuojamas taip:

Kaip žinome,

n = 2^h+1-1

n+1 = 2^h+1

Paėmus rąstą iš abiejų pusių,

žurnalas₂(n+1) = log2(2^h+1)

žurnalas₂(n+1) = h+1

h = log₂(n+1) – 1

Didžiausią aukštį galima apskaičiuoti taip:

Kaip žinome,

n = h+1

h = n-1

Dvejetainių medžių rūšys

Yra keturi dvejetainio medžio tipai:

Pilnas/ tinkamas/ griežtas dvejetainis medis Pilnas dvejetainis medis Tobulas dvejetainis medis Degeneruotas dvejetainis medis Subalansuotas dvejetainis medis

1. Pilnas/ tinkamas/ griežtas dvejetainis medis

Visas dvejetainis medis taip pat žinomas kaip griežtas dvejetainis medis. Medis gali būti laikomas pilnu dvejetainiu medžiu, jei kiekviename mazge turi būti 0 arba 2 vaikai. Visą dvejetainį medį taip pat galima apibrėžti kaip medį, kuriame kiekviename mazge turi būti 2 vaikai, išskyrus lapų mazgus.

Pažvelkime į paprastą viso dvejetainio medžio pavyzdį.

alfa beta genėjimo pavyzdys

Aukščiau pateiktame medyje galime pastebėti, kad kiekviename mazge yra nulis arba du vaikai; todėl tai yra pilnas dvejetainis medis.

Viso dvejetainio medžio savybės

• Lapų mazgų skaičius lygus vidinių mazgų skaičiui plius 1. Aukščiau pateiktame pavyzdyje vidinių mazgų skaičius yra 5; todėl lapų mazgų skaičius lygus 6.
• Maksimalus mazgų skaičius yra toks pat kaip mazgų skaičius dvejetainiame medyje, t. y. 2^h+1-1.
• Minimalus mazgų skaičius visame dvejetainiame medyje yra 2*h-1.
• Mažiausias viso dvejetainio medžio aukštis yra žurnalas₂(n+1) – 1.
• Didžiausias viso dvejetainio medžio aukštis gali būti apskaičiuotas taip:

n= 2*h – 1

n+1 = 2*h

h = n+1/2

Pilnas dvejetainis medis

Visas dvejetainis medis yra medis, kuriame visi mazgai yra visiškai užpildyti, išskyrus paskutinį lygį. Paskutiniame lygyje visi mazgai turi būti kiek įmanoma palikti. Visame dvejetainiame medyje mazgai turėtų būti pridedami iš kairės.

Sukurkime pilną dvejetainį medį.

Aukščiau pateiktas medis yra pilnas dvejetainis medis, nes visi mazgai yra visiškai užpildyti, o visi paskutinio lygio mazgai pirmiausia pridedami kairėje.

Visiško dvejetainio medžio savybės

• Maksimalus mazgų skaičius pilname dvejetainiame medyje yra 2^h+1– 1.
• Mažiausias mazgų skaičius pilname dvejetainiame medyje yra 2^h.
• Mažiausias viso dvejetainio medžio aukštis yra žurnalas₂(n+1) – 1.
• Didžiausias viso dvejetainio medžio aukštis yra

Tobulas dvejetainis medis

Medis yra tobulas dvejetainis medis, jei visi vidiniai mazgai turi 2 vaikus, o visi lapų mazgai yra tame pačiame lygyje.

Pažvelkime į paprastą tobulo dvejetainio medžio pavyzdį.

Žemiau esantis medis nėra tobulas dvejetainis medis, nes visi lapų mazgai nėra tame pačiame lygyje.

Pastaba: visi tobuli dvejetainiai medžiai yra ir pilni dvejetainiai medžiai, bet ir atvirkščiai, netiesa, t. y. visi dvejetainiai medžiai ir pilni dvejetainiai medžiai yra tobuli dvejetainiai medžiai.

Degeneruotas dvejetainis medis

Degeneruotas dvejetainis medis yra medis, kuriame visi vidiniai mazgai turi tik vieną atžalą.

Supraskime Degenerate dvejetainį medį per pavyzdžius.

Aukščiau pateiktas medis yra išsigimęs dvejetainis medis, nes visi mazgai turi tik vieną vaiką. Jis taip pat žinomas kaip į dešinę pakreiptas medis, nes visi mazgai turi tik dešinįjį vaiką.

Aukščiau pateiktas medis taip pat yra išsigimęs dvejetainis medis, nes visi mazgai turi tik vieną vaiką. Jis taip pat žinomas kaip į kairę nukreiptas medis, nes visuose mazguose yra tik kairysis vaikas.

Subalansuotas dvejetainis medis

Subalansuotas dvejetainis medis yra medis, kuriame ir kairysis, ir dešinysis medžiai skiriasi ne daugiau kaip 1. Pavyzdžiui, AVL ir Raudonai juodi medžiai yra subalansuotas dvejetainis medis.

Supraskime subalansuotą dvejetainį medį per pavyzdžius.

Aukščiau pateiktas medis yra subalansuotas dvejetainis medis, nes skirtumas tarp kairiojo ir dešiniojo pomedžio yra nulis.

java poeilutė yra

Aukščiau pateiktas medis nėra subalansuotas dvejetainis medis, nes skirtumas tarp kairiojo ir dešiniojo pomedžio yra didesnis nei 1.

Dvejetainio medžio įgyvendinimas

Dvejetainis medis įgyvendinamas rodyklių pagalba. Pirmasis medžio mazgas vaizduojamas šaknies žymekliu. Kiekvienas medžio mazgas susideda iš trijų dalių, ty duomenų, kairiojo ir dešiniojo rodyklės. Norėdami sukurti dvejetainį medį, pirmiausia turime sukurti mazgą. Sukursime vartotojo apibrėžtą mazgą, kaip parodyta toliau:

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

Aukščiau pateiktoje struktūroje duomenis yra vertė, kairysis žymeklis yra kairiojo mazgo adresas ir dešinysis rodyklė yra dešiniojo mazgo adresas.

Dvejetainio medžio programa C

 #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; } } 

Aukščiau pateiktas kodas rekursyviai iškviečia funkciją create() ir kiekvienam rekursiniam iškvietimui sukuria naują mazgą. Sukūrus visus mazgus, susidaro dvejetainė medžio struktūra. Apsilankymo mazguose procesas žinomas kaip medžio apvažiavimas. Norint aplankyti mazgą, naudojami trijų tipų perėjimai:

• Užsakymo perėjimas
• Išankstinis pervažiavimas
• Pašto siuntų pervežimas