Kas yra pilnas dvejetainis medis?
Visą dvejetainį medį galima apibrėžti kaip a dvejetainis medis kurioje visi mazgai turi 0 arba du vaikus. Kitaip tariant, visą dvejetainį medį galima apibrėžti kaip dvejetainį medį, kuriame visi mazgai turi du vaikus, išskyrus lapų mazgus.
Žemiau esantis medis yra pilnas dvejetainis medis:
Aukščiau pateiktas medis yra pilnas dvejetainis medis, nes visi mazgai, išskyrus lapų mazgus, turi du vaikus.
Visa dvejetainio medžio teorema:
Laikykite dvejetainį medį T netuščiu medžiu, tada:
- Tegul aš būsiu vidiniai medžio mazgai, o L – lapo mazgas medyje, tada lapų mazgų skaičius būtų lygus:
L = I + 1 - Jei T turi, I vidinių mazgų skaičius ir N yra bendras mazgų skaičius, tada bendras mazgų skaičius būtų lygus:
N = 2I + 1 - Jei T yra „N“ bendras mazgų skaičius, o „I“ yra vidinių mazgų skaičius, tada vidinių mazgų skaičius būtų lygus:
I = (N-1)/2 - Jei „T“ turi „N“ bendrą mazgų skaičių, o „L“ yra lapų mazgų skaičius, tada lapų mazgų skaičius būtų lygus:
L = (N+1)/2 - Jei „T“ yra „L“ lapų mazgų skaičius, bendras mazgų skaičius būtų lygus:
N = 2L - 1 - Jei „T“ turi „L“ lapų mazgų skaičių, o „I“ yra vidinių mazgų skaičius, tada vidinių mazgų skaičius būtų lygus:
I = L - 1
Kas yra pilnas dvejetainis medis?
Sakoma, kad dvejetainis medis yra pilnas dvejetainis medis, kai visi lygiai yra visiškai užpildyti, išskyrus paskutinį lygį, kuris užpildomas iš kairės.
Žemiau esantis medis yra pilnas dvejetainis medis:
Visas dvejetainis medis yra panašus į visą dvejetainį medį, išskyrus du skirtumus, kurie pateikiami toliau:
- Lapo mazgo užpildymas turi prasidėti nuo kairiosios pusės.
- Nebūtina, kad paskutinis lapo mazgas turi turėti tinkamą brolį ir seserį.
Supraskime pirmiau minėtus dalykus per pavyzdį:
Apsvarstykite toliau pateiktą medį:
Aukščiau pateiktas medis yra pilnas dvejetainis medis, bet ne pilnas dvejetainis medis, nes 6 mazgas neturi savo dešiniojo brolio.
Visiško dvejetainio medžio sukūrimas
Tarkime, kad turime 6 elementų masyvą, kaip parodyta žemiau:
Aukščiau pateiktame masyve yra 6 elementai, t. y. 1, 2, 3, 4, 5, 6. Toliau pateikiami veiksmai, kuriuos reikia atlikti norint sukurti visą dvejetainį medį:
1 žingsnis: Pirmiausia pasirinksime pirmąjį masyvo elementą, ty 1, ir sukursime šakninį medžio mazgą. Pirmajame lygyje galimų elementų skaičius yra 1.
2 žingsnis: Dabar pasirinksime antrąjį ir trečiąjį masyvo elementus. Laikykite antrąjį ir trečiąjį masyvo elementus kaip kairįjį ir dešinįjį šakninio mazgo antrinį elementą, kaip parodyta toliau:
Kaip matome aukščiau, antrojo lygio elementų skaičius yra 2.
3 veiksmas: Dabar mes pasirinksime kitus du elementus iš masyvo, ty 4 ir 5. Laikykite šiuos du elementus 2 mazgo kairėje ir dešinėje, kaip parodyta toliau:
Kaip matome aukščiau, 4 ir 5 mazgai yra atitinkamai kairysis ir dešinysis 2 mazgo vaikai.
4 veiksmas: Dabar pasirinksime paskutinį masyvo elementą, t. y. 6, ir paliksime jį kaip kairįjį mazgo 3 atžalą, nes žinome, kad pilname dvejetainiame medyje mazgai užpildomi iš kairės pusės, kaip parodyta žemiau:
Kaip matome, antrame lygyje yra 3 elementai.
užblokuoti kontaktai
Supraskime skirtumus tarp pilno ir pilno dvejetainio medžio per vaizdus.
- Žemiau parodytas dvejetainis medis nėra nei pilnas, nei pilnas dvejetainis medis. Tai nėra pilnas dvejetainis medis, nes 3 mazgas turi tik vieną atžalą. Tai taip pat nėra pilnas dvejetainis medis, nes mazgai turi būti užpildyti iš kairės pusės, tačiau 3 mazgas turi dešinįjį, o kairįjį – ne.
- Dvejetainis medis, kuris parodytas žemiau, yra pilnas dvejetainis medis, bet ne pilnas dvejetainis medis. Tai pilnas dvejetainis medis, nes visi mazgai turi 0 arba 2 vaikus. Tai nėra pilnas dvejetainis medis, nes 3 mazgas neturi vaikų, o 2 mazgas turi savo vaikus ir mes žinome, kad mazgai turi būti užpildyti iš kairės pusės pilname dvejetainiame medyje.
- Žemiau parodytas dvejetainis medis yra pilnas dvejetainis medis, bet ne pilnas dvejetainis medis. Tai pilnas dvejetainis medis, nes visi mazgai yra užpildyti. Tai nėra pilnas dvejetainis medis, nes 2 mazgas turi tik vieną atžalą.
- Žemiau parodytas dvejetainis medis yra pilnas ir pilnas dvejetainis medis. Tai pilnas dvejetainis medis, nes visi mazgai yra užpildyti. Tai pilnas dvejetainis medis, nes visi mazgai turi 0 arba 2 vaikus.
