Обход дерева

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

Имеет смысл говорить о порядке обхода: в каком порядке вершины присутствуют в обходе. Наиболее естественным является порядок, который можно назвать порядком наследования царского престола: первыми после царя будет править старший сын и дети старшего сына, и внуки старшего сына. Лишь когда потомки старшего сына исчерпались, приходит очередь второго сына царя и его потомков. Затем третьего и т. п. Среди детей старшего сына царя действуют те же правила.

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

void visit_tree (Tree *node) {
    сделать желаемое действие для node;
    для каждого ребёнка узла node сделать (где child — очередной ребёнок)
        visit_tree (child);
}