Ce este un copac binar?

Un copac binar este o structură de date în formă de copac în care fiecare nod are cel mult doi descendenți: stâng și drept.

Proprietăți principale:

• Rădăcină (Root): Nodul cel mai de sus al copacului.
• Nod (Node): Elementul copacului care conține date și legături către descendenții săi.
• Copil (Child): Nodul situat direct sub alt nod (părinte).
• Părinte (Parent): Nodul care are unul sau mai mulți descendenți direct sub el.
• Frunză (Leaf): Nod fără descendenți.
• Ramură (Branch): Calea de la rădăcină la frunză.
• Subcopac (Subtree): Copac format dintr-un nod și toți descendenții săi.

Tipuri diferite de copaci binari:

• Copac binar complet (Full Binary Tree): Fiecare nod are 0 sau 2 descendenți.
• Copac binar perfect (Perfect Binary Tree): Toate nivelurile, cu excepția ultimei, sunt complet umplute, iar pe ultimul nivel toți nodurile sunt plasate cât mai la stânga.
• Copac binar echilibrat (Balanced Binary Tree): Înălțimea subcopacilor stâng și drept ai oricărui nod diferă cel mult cu 1. Exemplu: copac AVL, copac roșu-negru.
• Copac binar degenerat (Degenerate Binary Tree): Fiecare nod are cel mult un descendent. În esență, este o listă legată.

Se aplică în diferiți algoritmi și structuri de date, cum ar fi copacii binari de căutare, heap-urile, copacii sintactici.