Ağac iyerarxik verilənləri təsvir edən qeyri-xətti strukturdur: fayl sistemi, HTML sənədinin DOM-u, təşkilat sxemi, ifadə ağacı. Ağac əlaqəli siyahının ümumiləşməsidir: hər düyünün bir next yerinə bir neçə uşağı var. Dövr yoxdur və hər düyünün (kökdən başqa) tam bir valideyni var.
Terminlər
| Termin | Mənası |
|---|---|
| Kök (root) | valideyni olmayan yeganə düyün |
| Yarpaq (leaf) | uşağı olmayan düyün |
| Valideyn / uşaq / qardaş | birbaşa yuxarı / aşağı / eyni valideynin digər uşaqları |
| Əcdad / nəsil | yol üzrə yuxarıdakı / aşağıdakı düyünlər |
| Dərinlik (depth) | kökdən düyünə qədər kənarların sayı (kökün dərinliyi 0) |
| Hündürlük (height) | düyündən ən dərin yarpağa qədər kənarların sayı (yarpağınki 0) |
| Səviyyə (level) | eyni dərinlikdəki düyünlər |
| Alt ağac | düyün və onun bütün nəsilləri |
| Dərəcə (degree) | düyünün uşaqlarının sayı |
Ağacın hündürlüyü kökün hündürlüyüdür. n düyünlü ağacda n - 1 kənar var.
Düyün sinfi
class TreeNode:
def __init__(self, value, children=None):
self.value = value
self.children = children or []
def sample():
return TreeNode("A", [
TreeNode("B", [TreeNode("E"), TreeNode("F")]),
TreeNode("C"),
TreeNode("D", [TreeNode("G")]),
])
def height(node):
return 1 + max((height(c) for c in node.children), default=-1)