A

Dvejetainis medis

Yra įvairių dvejetainių medžių rūšys bet čia mes kalbėsime apie skirtumą Pilnas dvejetainis medis ir Pilnas dvejetainis medis .

Visas dvejetainis medis:

Pilnas dvejetainis medis yra dvejetainis medis, kuriame visi mazgai turi 0 arba 2 palikuonis . Kitaip tariant, pilnas dvejetainis medis yra dvejetainis medis, kuriame visi mazgai, išskyrus lapų mazgus, turi du palikuonis.

mašinraščio jungiklis

Visas dvejetainis medis

atrankos rūšiavimas

Leisti, i būti vidinių mazgų skaičius
n turi būti bendras mazgų skaičius
l būti lapų skaičiumi
l būti lygių skaičiumi

Tada

Lapų skaičius yra (i + 1) .
Bendras mazgų skaičius yra (2i + 1) .
Vidinių mazgų skaičius yra (n – 1) / 2 .
Lapų skaičius yra (n + 1) / 2 .
Bendras mazgų skaičius yra (2l – 1) .
Vidinių mazgų skaičius yra (l – 1) .
Lapų skaičius yra didžiausias (2^l-1) .

Visas dvejetainis medis:

Sakoma, kad dvejetainis medis yra a pilnas dvejetainis medis jei visi jo lygiai, išskyrus galbūt paskutinį lygį, turi didžiausią galimų mazgų skaičių ir visi mazgai paskutinis lygis rodomas kuo toliau į kairę .

Visiškas dvejetainis medis

Yra 2 taškai, kuriuos galite atpažinti iš čia,

1. Visada pirmiausia turi būti užpildyta kairioji lapo mazgo pusė.
2. Nebūtina, kad paskutinis lapo mazgas turėtų tinkamą brolį ir seserį.

Peržiūrėkite šiuos pavyzdžius, kad geriau suprastumėte visą ir pilną dvejetainį medį.

java8 funkcijos

1 pavyzdys:

Nei pilnas, nei pilnas

• Mazgas C todėl turi tik vieną vaiką, tai nėra pilnas dvejetainis medis.
• Mazgas C taip pat turi dešinį vaiką, bet neturi kairiojo vaiko, todėl tai taip pat nėra pilnas dvejetainis medis.

Taigi aukščiau parodytas dvejetainis medis yra nei pilnas, nei pilnas dvejetainis medis.

2 pavyzdys:

burbulų rūšiavimas algoritme

Pilnas, bet ne pilnas

• Visi mazgai turi vieną 0 arba 2 palikuonys, todėl tai pilnas dvejetainis medis .
Tai nėra pilnas dvejetainis medis, nes mazgas B neturi vaikų, o mazgas C turi vaikų, o pagal pilną dvejetainį medį mazgai turėtų būti užpildyti iš kairė pusė .

Taigi aukščiau parodytas dvejetainis medis yra a Pilnas dvejetainis medis ir tai yra nėra pilnas dvejetainis medis.

3 pavyzdys:

Pilnas, bet ne pilnas

Tai pilnas dvejetainis medis, nes visi mazgai yra užpildyti.
• Mazgas B turi tik vieną vaiką, todėl tai nėra pilnas dvejetainis medis.

Taigi aukščiau parodytas dvejetainis medis yra a Pilnas dvejetainis medis ir tai yra ne pilnas dvejetainis medis.

4 pavyzdys:

Pilnas ir pilnas

kompiuterių tipai

• Tai yra Pilnas dvejetainis medis, nes visi mazgai yra liko užpildytas .
• Visi mazgai turi vieną 0 arba 2 palikuonys, todėl tai yra a pilnas dvejetainis medis .

Taigi aukščiau parodytas dvejetainis medis yra tiek pilnas, tiek pilnas dvejetainis medis.