TechCodeview

Бинарно стабло значи да чвор може имати највише два детета. Овде, само бинарно име сугерише да 'два'; стога, сваки чвор може имати 0, 1 или 2 детета.

Хајде да разумемо бинарно стабло кроз пример.

Горње стабло је бинарно стабло јер сваки чвор садржи највише два детета. Логички приказ горњег стабла је дат у наставку:

У горњем стаблу, чвор 1 садржи два показивача, односно леви и десни показивач који показују на леви и десни чвор. Чвор 2 садржи оба чвора (леви и десни чвор); дакле, има два показивача (леви и десни). Чворови 3, 5 и 6 су листови, тако да сви ови чворови садрже НУЛА показивач на левом и десном делу.

Особине бинарног стабла

• На сваком нивоу и, максималан број чворова је 2^и.
• Висина стабла се дефинише као најдужи пут од коренског чвора до лисног чвора. Стабло које је приказано изнад има висину једнаку 3. Према томе, максималан број чворова на висини 3 је једнак (1+2+4+8) = 15. Уопштено, максимални број чворова могући на висини х је (2⁰+ 2¹+ 2²+….2^х) = 2^х+1-1.
• Минималан број могућих чворова на висини х је једнак х+1 .
• Ако је број чворова минималан, онда би висина стабла била максимална. Насупрот томе, ако је број чворова максималан, онда би висина стабла била минимална.

Ако постоји 'н' број чворова у бинарном стаблу.

Минимална висина се може израчунати као:

Као што знамо,

н = 2^х+1-1

н+1 = 2^х+1

Узимајући балван са обе стране,

Пријава₂(н+1) = лог2(2^х+1)

алгоритми за сортирање спајањем сортирања

Пријава₂(н+1) = х+1

х = лог₂(н+1) - 1

Максимална висина се може израчунати као:

Као што знамо,

н = х+1

х= н-1

Врсте бинарног стабла

Постоје четири типа бинарног стабла:

Пуно/ правилно/ строго Бинарно дрво Комплетно бинарно стабло Савршено бинарно дрво Дегенерисано бинарно дрво Балансирано бинарно дрво

1. Пуно/ правилно/ строго Бинарно дрво

Пуно бинарно стабло је такође познато као строго бинарно стабло. Стабло се може сматрати пуним бинарним стаблом само ако сваки чвор мора да садржи 0 или 2 детета. Пуно бинарно стабло се такође може дефинисати као стабло у коме сваки чвор мора да садржи 2 детета осим чворова листа.

Погледајмо једноставан пример пуног бинарног стабла.

У горњем стаблу, можемо приметити да сваки чвор садржи или нула или два детета; дакле, то је пуно бинарно стабло.

Својства пуног бинарног стабла

• Број лисних чворова је једнак броју унутрашњих чворова плус 1. У горњем примеру, број унутрашњих чворова је 5; дакле, број чворова листа је једнак 6.
• Максималан број чворова је исти као и број чворова у бинарном стаблу, тј. 2^х+1-1.
• Минимални број чворова у пуном бинарном стаблу је 2*х-1.
• Минимална висина пуног бинарног стабла је Пријава₂(н+1) - 1.
• Максимална висина пуног бинарног стабла може се израчунати као:

н= 2*х - 1

н+1 = 2*х

х = н+1/2

Комплетно бинарно стабло

Комплетно бинарно стабло је дрво у коме су сви чворови потпуно попуњени осим последњег нивоа. У последњем нивоу, сви чворови морају бити што је могуће левији. У потпуном бинарном стаблу, чворове треба додати са леве стране.

Хајде да направимо комплетно бинарно стабло.

Горње стабло је комплетно бинарно стабло јер су сви чворови потпуно попуњени, а сви чворови последњег нивоа се прво додају лево.

Особине комплетног бинарног стабла

мапа типопис

• Максималан број чворова у комплетном бинарном стаблу је 2^х+1- 1.
• Минимални број чворова у комплетном бинарном стаблу је 2^х.
• Минимална висина комплетног бинарног стабла је Пријава₂(н+1) - 1.
• Максимална висина комплетног бинарног стабла је

Савршено бинарно дрво

Дрво је савршено бинарно стабло ако сви унутрашњи чворови имају 2 детета, а сви чворови листа су на истом нивоу.

Погледајмо једноставан пример савршеног бинарног стабла.

Доле стабло није савршено бинарно стабло јер сви чворови листа нису на истом нивоу.

Напомена: Сва савршена бинарна стабла су комплетна бинарна стабла као и пуно бинарно стабло, али обрнуто није тачно, тј. сва комплетна бинарна стабла и пуна бинарна стабла су савршена бинарна стабла.

Дегенерисано бинарно дрво

Дегенерисано бинарно стабло је дрво у коме сви унутрашњи чворови имају само једно потомство.

Хајде да разумемо дегенерисано бинарно стабло кроз примере.

Горње стабло је дегенерисано бинарно стабло јер сви чворови имају само једно дете. Такође је познато као десно искошено дрво јер сви чворови имају само право дете.

Горње стабло је такође дегенерисано бинарно стабло јер сви чворови имају само једно дете. Такође је познато и као лево искошено дрво јер сви чворови имају само лево дете.

Уравнотежено бинарно стабло

предности инстаграма за личну употребу

Уравнотежено бинарно стабло је дрво у коме се и лево и десно стабло разликују за највише 1. На пример, АВЛ и Црвено-црно дрвеће су уравнотежено бинарно стабло.

Хајде да разумемо уравнотежено бинарно стабло кроз примере.

Горње стабло је уравнотежено бинарно стабло јер је разлика између левог подстабла и десног подстабла нула.

Горње стабло није уравнотежено бинарно стабло јер је разлика између левог и десног подстабла већа од 1.

Имплементација бинарног стабла

Бинарно стабло се имплементира уз помоћ показивача. Први чвор у стаблу је представљен коренским показивачем. Сваки чвор у стаблу састоји се од три дела, тј. података, левог показивача и десног показивача. Да бисмо креирали бинарно стабло, прво морамо да креирамо чвор. Направићемо кориснички дефинисани чвор као што је приказано у наставку:

 struct node { int data, struct node *left, *right; } 

У горњој структури, података је вредност, леви показивач садржи адресу левог чвора и десни показивач садржи адресу десног чвора.

Програм бинарног стабла у Ц

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Горњи код позива функцију цреате() рекурзивно и креира нови чвор при сваком рекурзивном позиву. Када се креирају сви чворови, онда формира структуру бинарног стабла. Процес посете чворовима познат је као обилазак дрвета. Постоје три типа обиласка који се користе за посету чвору:

• Инордер траверсал
• Преордер траверсал
• Промет поштанских налога