Толук бинардык дарак менен толук экилик дарак
Экилик дарак - ар бир түйүндө бир же эки бала бар дарак. Бинардык даракта түйүндө экиден ашык бала болушу мүмкүн эмес. Экилик даракта балдар "сол" жана "оң" балдар деп аталат. Бала түйүндөр алардын ата-энесине шилтемени камтыйт. Толук экилик дарак - бул экилик дарак, анда экилик дарактын ар бир деңгээли акыркы деңгээлден башкасы толугу менен толтурулган. Толтурулбаган деңгээлде түйүндөр эң сол жактагы абалдан баштап бекитилет. Толук бинардык дарак - дарактын жалбырактарынан башка дарактын ар бир түйүнүндө эки бала бар дарак.
Толук бинардык дарак деген эмне?
Толук экилик дарак - дарактын ар бир түйүнүндө так нөл же эки бала бар бинардык дарак. Башкача айтканда, жалбырактан башка дарактын ар бир түйүнүндө так эки бала бар. Төмөндөгү 1-сүрөт толук бинардык даракты сүрөттөйт. Толук бинардык даракта түйүндөрдүн саны (n), лейкалардын саны (l) жана ички түйүндөрдүн саны (i) өзгөчө түрдө байланышкан, ошондуктан алардын кайсынысын билсеңиз, калган экөөнү аныктай аласыз. төмөнкүдөй маанилер:
1. Эгерде толук бинардык дарактын i ички түйүндөрү болсо:
– Жалбырактардын саны l=i+1
– түйүндөрдүн жалпы саны n=2i+1
2. Эгерде толук бинардык дарактын n түйүнү болсо:
– Ички түйүндөрдүн саны i=(n-1)/2
– Жалбырактардын саны l=(n+1)/2
3. Эгерде толук экилик дарактын l жалбырактары болсо:
– Түйүндөрдүн жалпы саны n=2l-1
– Ички түйүндөрдүн саны i=l-1
Толук экилик дарак деген эмне?
2-сүрөттө көрсөтүлгөндөй, толук экилик дарак - акыркы деңгээлден башка дарактын бардык деңгээли толугу менен толтурулган бинардык дарак. Ошондой эле, акыркы деңгээлде, түйүндөр эң сол жактагы абалдан баштап тиркелиши керек. h бийиктиктеги толук бинардык дарак төмөнкү шарттарга жооп берет:
– Тамыр түйүнүнөн акыркы деңгээлдин үстүндөгү деңгээл h-1 бийиктигиндеги толук бинардык даракты билдирет
– Акыркы деңгээлдеги бир же бир нече түйүндө 0 же 1 бала болушу мүмкүн
– Эгерде a, b акыркы деңгээлден жогору деңгээлдеги эки түйүн болсо, анда а бдан көп балалуу болот, эгерде а b'нин сол жагында болсо гана
Толук экилик дарак менен толук экилик дарактын ортосунда кандай айырма бар?
Толук бинардык дарактар менен толук бинардык дарактарда так айырма бар. Толук экилик дарак ар бир түйүн нөл же эки баласы бар бинардык дарак болсо, толук бинардык дарак - акыркы деңгээлден башка экилик дарактын ар бир деңгээли толугу менен толтурулган бинардык дарак. Үймөктөр сыяктуу кээ бир атайын маалымат структуралары толук бинардык дарактар болушу керек, ал эми алар толук бинардык дарактар болбошу керек. Толук экилик даракта, эгерде сиз жалпы түйүндөрдүн санын же лавелердин санын же ички түйүндөрдүн санын билсеңиз, калган экөөнү оңой таба аласыз. Бирок толук экилик дарактын үч атрибутка тиешелүү өзгөчө касиети жок.
