Skirtumas tarp pilno dvejetainio medžio ir pilno dvejetainio medžio

Visas dvejetainis medis prieš pilną dvejetainį medį

Dvejetainis medis yra medis, kuriame kiekvienas mazgas turi vieną ar du vaikus. Dvejetainiame medyje mazgas negali turėti daugiau nei du vaikai. Dvejetainiame medyje vaikai yra įvardijami kaip „kairieji“ ir „dešinieji“. Vaiko mazguose yra nuoroda į savo tėvą. Visas dvejetainis medis yra dvejetainis medis, kuriame visi dvejetainio medžio lygiai yra visiškai užpildyti, išskyrus paskutinį lygį. Neužpildytame lygyje mazgai pritvirtinami pradedant nuo kairiosios 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 tiksliai nulį ar du vaikus. Kitaip tariant, kiekvienas medžio mazgas, išskyrus lapus, turi lygiai du vaikus. 1 paveiksle pavaizduotas visas dvejetainis medis. Visame dvejetainiame medyje mazgų (n), sluoksnių (l) ir vidinių mazgų (i) skaičius yra susietas ypatingai, kad, jei žinote bet kurį iš jų, galite nustatyti kitus du vertės taip:

1. Jei visas dvejetainis medis turi vidinius mazgus:

- Lapų skaičius l = i + 1

- Bendras mazgų skaičius n = 2 * i + 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 pilnas dvejetainis medis turi l lapų:

- Bendras mazgų skaičius n = 2 * l-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į lygį. Taip pat paskutiniame lygyje mazgai turėtų būti tvirtinami pradedant nuo kairiosios padėties. Visas b dvejetainis medis, kurio aukštis h, atitinka šias sąlygas:

- Nuo šaknies mazgo esantis aukščiau paskutinio lygio lygis žymi visą dvejetainį medį, kurio aukštis h-1

- Viename ar daugiau paskutinio lygio mazgų gali būti 0 arba 1 vaikas

- Jei a, b yra du mazgai aukščiau paskutinio lygio, tada a turi daugiau vaikų nei b, jei ir tik tada, jei a yra kairėje nuo b

Kuo skiriasi pilnas dvejetainis medis ir pilnas dvejetainis medis?

Visiški dvejetainiai medžiai ir visiški dvejetainiai medžiai turi aiškų skirtumą. Nors visas dvejetainis medis yra dvejetainis medis, kuriame kiekvienas mazgas turi nulį ar du vaikus, 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, tokios kaip krūvos, turi būti ištisiniai dvejetainiai medžiai, tuo tarpu jos nebūtinai turi būti pilnos dvejetainės medienos. Jei yra visas dvejetainis medis, jei žinote bendrą mazgų skaičių, sluoksnių skaičių arba vidinių mazgų skaičių, kitus du galite rasti labai lengvai. Bet visas dvejetainis medis neturi ypatingos savybės, susijusios su šiais trim požymiais.