Toʻliq ikkilik daraxt va toʻliq ikkilik daraxt
Ikkilik daraxt - bu har bir tugunning bir yoki ikkita bolasi bo'lgan daraxt. Ikkilik daraxtda tugun ikkitadan ortiq bolaga ega bo'lishi mumkin emas. Ikkilik daraxtda bolalar "chap" va "o'ng" bolalar deb nomlanadi. Bola tugunlari ota-onasiga havolani o'z ichiga oladi. To'liq ikkilik daraxt - bu ikkilik daraxt bo'lib, unda oxirgi darajadan tashqari ikkilik daraxtning har bir darajasi to'liq to'ldirilgan. To'ldirilmagan darajada, tugunlar eng chap pozitsiyadan boshlab biriktiriladi. To'liq ikkilik daraxt - bu daraxtning barglaridan tashqari har bir tugunning ikkita bolasi bo'lgan daraxt.
Toʻliq ikkilik daraxt nima?
Toʻliq ikkilik daraxt ikkilik daraxt boʻlib, unda daraxtning har bir tugunida aynan nol yoki ikkita bola boʻladi. Boshqacha qilib aytganda, barglardan tashqari daraxtning har bir tugunida aniq ikkita bola bor. Quyidagi 1-rasmda to'liq ikkilik daraxt tasvirlangan. To'liq ikkilik daraxtda tugunlar soni (n), lavhalar soni (l) va ichki tugunlar soni (i) maxsus tarzda bog'langan, agar siz ulardan birini bilsangiz, qolgan ikkitasini aniqlashingiz mumkin. quyidagi qiymatlar:
1. Agar toʻliq binar daraxtda i ichki tugunlari boʻlsa:
– Barglar soni l=i+1
– Tugunlarning umumiy soni n=2i+1
2. Agar toʻliq binar daraxtda n ta tugun boʻlsa:
– Ichki tugunlar soni i=(n-1)/2
– Barglar soni l=(n+1)/2
3. Agar toʻliq ikkilik daraxtda l barg boʻlsa:
– Tugunlarning umumiy soni n=2l-1
– Ichki tugunlar soni i=l-1
Toʻliq ikkilik daraxt nima?
2-rasmda ko'rsatilganidek, to'liq ikkilik daraxt ikkilik daraxt bo'lib, unda oxirgi darajadan tashqari daraxtning barcha darajasi to'liq to'ldirilgan. Bundan tashqari, oxirgi darajada, tugunlar eng chap pozitsiyadan boshlab biriktirilishi kerak. h balandlikdagi toʻliq ikkilik daraxt quyidagi shartlarga javob beradi:
– Ildiz tugunidan oxirgi sathidan yuqori balandlik h-1 boʻlgan toʻliq ikkilik daraxtni ifodalaydi
– Oxirgi darajadagi bir yoki bir nechta tugunlarda 0 yoki 1 ta bola boʻlishi mumkin
– Agar a, b oxirgi sathdan yuqori darajadagi ikkita tugun boʻlsa, u holda a soni b ning chap tomonida joylashgan boʻlsa, b dan koʻproq bolaga ega boʻladi.
Toʻliq ikkilik daraxt va toʻliq ikkilik daraxt oʻrtasidagi farq nima?
Toʻliq ikkilik daraxtlar va toʻliq ikkilik daraxtlar aniq farqga ega. To'liq ikkilik daraxt har bir tugun nol yoki ikkita bolaga ega bo'lgan ikkilik daraxt bo'lsa, to'liq ikkilik daraxt ikkilik daraxt bo'lib, unda oxirgi darajadan tashqari ikkilik daraxtning har bir darajasi to'liq to'ldirilgan. Ba'zi maxsus ma'lumotlar tuzilmalari to'liq ikkilik daraxtlar bo'lishi kerak, ammo ular to'liq binar daraxtlar bo'lishi shart emas. To'liq ikkilik daraxtda, agar siz umumiy tugunlar sonini yoki lavlar sonini yoki ichki tugunlar sonini bilsangiz, qolgan ikkitasini juda oson topishingiz mumkin. Ammo toʻliq binar daraxt tezisning uchta atributiga tegishli maxsus xususiyatga ega emas.
