Структуры данных на основе деревьев

Дерево, лес, корень, лист, высота дерева, бинарное дерево

В программах бинарные деревья реализуют в виде структуры данных, узлы которой соответствуют вершинам дерева и содержат связанную с ней информацию, а также два указателя на его левого и правого потомка.

struct Node {
  any value; 
  Node *left;
  Node *right;
};

Для упрощения операций можно сделать дополнительные указатели на родительские узлы.

Произвольное упорядоченное дерево можно представить как двоичное, левый указатель будет содержать ссылку на первого потомка текущей вершины, а правый — на следующую родственную ей вершину.

Также можно добавить два указателя на родительский узел и предыдущую родственную вершину (DOM).