Всем известное DOM-дерево на самом деле тоже граф! Как, собственно, и любое другое дерево.

Дерево — это нецикличный связный граф. То есть это граф, в котором отсутствуют циклы и в котором каждую из вершин можно найти по пути из другой вершины. Чтобы было нагляднее, давайте посмотрим на небольшой пример поддерева DOM:

DOM-дерево

Это просто более частный случай графа. Давайте введём немного терминологии, чтобы не пугаться, когда она вдруг встретится:

• Корневой узел (или корень или корневая нода) — это нода, из которой наше дерево «начинается». В нашем примере это нода body.
• Лист — это ноды, в которых наше дерево «кончается»: у нас это h1, p, b, два li. То есть из которых больше нельзя «спуститься» ниже.
• Уровень — это число, которое показывает, насколько «низко» находится нода. Для body это 1, для b — 4.

Нет смысла рассматривать совсем простые операции над деревьями — вероятнее всего, вы уже их знаете. Так appendChild добавит в наше дерево новую связь с элементом, removeChild — порвёт нужную связь. Так же и с собственными реализациями деревьев это не составит труда. Давайте лучше попробуем это дерево пообходить!