Skirtumas Tarp Visiško Dvejetainio Medžio Ir Viso Dvejetainio Medžio

2024 Autorius: Mildred Bawerman | [email protected]. Paskutinį kartą keistas: 2023-12-16 08:40

Pilnas dvejetainis medis vs visas dvejetainis medis

Dvejetainis medis yra medis, kuriame kiekvienas mazgas turi po vieną ar du vaikus. Dvejetainiame medyje mazgas negali turėti daugiau nei dviejų vaikų. Dvejetainiame medyje vaikai įvardijami kaip „kairieji“ir „dešinieji“. Vaiko mazguose yra nuoroda į savo tėvus. Pilnas dvejetainis medis yra dvejetainis medis, kuriame visi dvejetainio medžio lygiai yra visiškai užpildyti, išskyrus paskutinį. Neužpildytame lygyje mazgai pritvirtinami pradedant nuo kairiosios padėties. Pilnas dvinaris medis yra medis, kuriame kiekviename medžio mazge yra du vaikai, išskyrus medžio lapus.

Kas yra visasis dvejetainis medis?

Pilnasis dvejetainis medis yra dvejetainis medis, kuriame kiekvienas medžio mazgas turi lygiai nulį arba du vaikus. Kitaip tariant, kiekviename medžio mazge, išskyrus lapus, yra lygiai du vaikai. 1 paveiksle pavaizduotas visas dvejetainis medis. Pilnajame dvejetainiame medyje mazgų skaičius (n), langų skaičius (l) ir vidinių mazgų skaičius (i) yra ypatingai susieti taip, kad jei žinote kurį nors iš jų, galite nustatyti kitus du vertės:

1. Jei visas dvejetainis medis turi i vidinių mazgų:

- 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 visas 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 visi medžio lygiai yra visiškai užpildyti, išskyrus paskutinį. Be to, paskutiniame lygyje mazgai turėtų būti pritvirtinti nuo kairiosios padėties. Visas dvejetainis medis, kurio aukštis h, atitinka šias sąlygas:

- Iš šaknies mazgo aukštis virš paskutinio lygio reiškia 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štyje virš paskutinio lygio, tada a turi daugiau vaikų nei b tik tada, jei a yra kairėje b

Kuo skiriasi visasis dvejetainis medis ir visasis dvejetainis medis?

Visiškai dvejetainiai medžiai ir visiškai dvejetainiai medžiai turi aiškų skirtumą. Nors visas dvejetainis medis yra dvejetainis medis, kuriame kiekvienas mazgas turi nulį arba du vaikus, pilnas dvejetainis medis yra dvejetainis medis, kuriame visi dvejetainio medžio lygiai yra visiškai užpildyti, išskyrus paskutinį. Kai kurios specialios duomenų struktūros, pvz., Krūvos, turi būti visiškai dvejetainiai medžiai, o nebūtinai - dvejetainiai medžiai. Jei žinote visą dvinarį medį, jei žinote bendrą mazgų skaičių, lave skaičių arba vidinių mazgų skaičių, galite lengvai rasti kitus du. Tačiau visas dvejetainis medis neturi ypatingos savybės, siejančios tris atributus.