Visas dvejetainis medis prieš visą dvejetainį medį
Dvejetainis medis yra medis, kuriame kiekvienas mazgas turi vieną ar du vaikus. Dvejetainiame medyje mazgas negali turėti daugiau nei dviejų vaikų. Dvejetainiame medyje vaikai įvardijami kaip „kairieji“ir „dešiniai“. Antriniuose mazguose yra nuoroda į jų tėvą. Visas dvejetainis medis yra dvejetainis medis, kuriame visi dvejetainio medžio lygiai yra visiškai užpildyti, išskyrus paskutinį. Neužpildytame lygyje mazgai tvirtinami pradedant nuo tolimiausios kairės padėties. Pilnas dvejetainis medis yra medis, kuriame kiekvienas medžio mazgas turi du vaikus, išskyrus medžio lapus.
Kas yra visas dvejetainis medis?
Visas dvejetainis medis yra dvejetainis medis, kuriame kiekvienas medžio mazgas turi lygiai nulį arba du vaikus. Kitaip tariant, kiekvienas medžio mazgas, išskyrus lapus, turi lygiai du vaikus. 1 paveiksle žemiau pavaizduotas visas dvejetainis medis. Visame dvejetainiame medyje mazgų skaičius (n), kanalų skaičius (l) ir vidinių mazgų skaičius (i) yra susietas ypatingu būdu, todėl, jei žinote kurį nors iš jų, galite nustatyti kitus du reikšmės taip:
1. Jei visas dvejetainis medis turi i vidinius mazgus:
– Lapų skaičius l=i+1
– Bendras mazgų skaičius n=2i+1
2. Jei visas dvejetainis medis turi n mazgų:
– Vidinių mazgų skaičius i=(n-1)/2
– Lapų skaičius l=(n+1)/2
3. Jei visas dvejetainis medis turi l lapų:
– Bendras mazgų skaičius n=2l-1
– Vidinių mazgų skaičius i=l-1
Kas yra pilnas dvejetainis medis?
Kaip parodyta 2 paveiksle, visas dvejetainis medis yra dvejetainis medis, kuriame kiekvienas medžio lygis yra visiškai užpildytas, išskyrus paskutinį. Be to, paskutiniame lygyje mazgai turėtų būti tvirtinami pradedant nuo tolimiausios kairiosios padėties. Visas dvejetainis h aukščio medis atitinka šias sąlygas:
– Iš šakninio mazgo aukščiau paskutinio lygio esantis lygis reiškia visą dvejetainį medį, kurio aukštis h-1
– Vienas ar keli paskutinio lygio mazgai gali turėti 0 arba 1 vaikų
– Jei a, b yra du mazgai aukščiau už paskutinį lygį, tada a turi daugiau vaikų nei b tada ir tik tada, jei a yra kairėje nuo b
Kuo skiriasi pilnas dvejetainis medis nuo viso dvejetainio medžio?
Visi dvejetainiai medžiai ir pilni dvejetainiai medžiai turi aiškų skirtumą. Visas dvejetainis medis yra dvejetainis medis, kuriame kiekvienas mazgas turi nulį arba du vaikus, o visas dvejetainis medis yra dvejetainis medis, kuriame visi dvejetainio medžio lygiai yra visiškai užpildyti, išskyrus paskutinį lygį. Kai kurios specialios duomenų struktūros, pvz., krūvos, turi būti pilni dvejetainiai medžiai, o nebūtinai turi būti pilni dvejetainiai medžiai. Visame dvejetainiame medyje, jei žinote bendrą mazgų skaičių arba lavų skaičių arba vidinių mazgų skaičių, galite labai lengvai rasti kitus du. Tačiau visas dvejetainis medis neturi specialios savybės, susijusios su trimis atributais.
