Arbori de top

Un arbore este o structură de date neliniară. Acesta este folosit pentru a reprezenta relații ierarhice care au relații una-la-multe.

Terminologie (luată din botanică și genealogie)

Un arbore este o colecție de elemente, numite noduri sau vârfuri, și relații ("părinte") între ele, formând o structură ierarhică a nodurilor.

Relațiile dintre nodurile unui copac (din genealogie):

nodul superior (vertex) se numește părinte (strămoș).

inferior - descendent (vârf fiu sau copil).

Definițiile nodurilor sunt din botanică.

Vârful cel mai de sus este rădăcina. iar vârfurile cele mai joase sunt frunzele. Vertexele care nu au descendenți sunt terminale (prin relații) sau frunze (prin definiții). Vertexurile terminale sunt noduri interne.

frații Node - fiu (descendent)

fruntea de sus

Copacii sunt definiți recursiv. adică un copac cu tipul de bază T este

sau o structură goală (un copac gol, o rădăcină);

sau un nod de tip T cu un număr finit de structuri arborice de același tip T. numite subtrere.

astfel - Un copac fără ramuri cu un vârf este un arbore gol sau zero.

Rădăcina copacului se află la nivelul zero.

Nivelul maxim al oricărui vârf al arborelui este adâncimea (de la rădăcină la nod) sau înălțimea (de la nod la foaia maximă șters). Prin urmare, valoarea maximă. nivelul rădăcinilor = 0.

Nivelul maxim al tuturor vârfurilor se numește adâncimea copacului.

Numărul descendenților imediat al unui nod de copaci (nod) se numește gradul vârfului (nodului).

Gradul maxim al tuturor vârfurilor este gradul arborelui.

Numărul de ramuri de la rădăcină la vârf este lungimea căii către acest vârf.

Astfel. rădăcina are o lungime de traiectorie de 0, lungimea căii liniilor sale drepte (adică, asociată cu o ramură) a descendenților este 1 și așa mai departe. Vârful la nivelul i are lungimea căii i.

Lungimea căii interne a arborelui este suma lungimilor căii pentru fiecare dintre vârfurile sale.

Lungimea căii externe a arborelui este suma lungimilor căilor tuturor vârfurilor speciale care completează arborele astfel încât gradele tuturor vârfurilor să fie egale cu gradul arborelui:

lungime externă. drumuri de copaci =