Деревья, обход матрицы
 

Какой структурой данных можно организовать хранение дерева?
Глубина дерева не ограничена.
Максимальное число ветвей на каждый узел - 4.

Предположим, задача следующая:
Дана матрица 10x10. Нужно обойти все элементы всеми возможными способами. Упростим задачу, предположив, что каждый узел можно посетить только один раз. Решение должно быть без рекурсии, и решение должно позволять возврат назад.

Как вариант другая задача, обойти матрицу 10x10, состоящую из 1 и 2, так чтобы не была посещена ни одна 1. Элемент можно посетить несколько раз.

Каким образом решаются подобные задачи?

ня?

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

Те же яйца, вид сбоку. Вершины - клетки содержащие "2", рёбра - переходы в соседние двойки. Проблему составляет разрешение переходить назад. Вот такая матрица обычным поиском в глубину не обойдётся:
Для того, чтобы её обойти можно завести ещё одну матрицу - со счётчиком посещений вершины. И при очередном шаге поиска всегда идти в вершину с наименьшим числом посещений. В частности для матрицы приведённой выше, если мы начали путь в точке (2,1), то через 5 ходов матрица со счётчиками будет выглядеть так (соответственно находимся в точке (2,3)):
после этого, надо перейти в (1,3):и в (2,3) на следующем шаге _не_ пойдём, т.к. там счётчик 1, а в (1,4) - пойдём, т.к. там ноль.

Можно доказать, что этот алгоритм всегда обходит все вершины, входящие в компоненту связности. Хотя, вероятно, и не самым оптимальным способом (не за минимальное число шагов).

В общем, читайте нормальный книжки по структурам данных и алгоритмам. Их много. Стандартные алгоритмы почти всегда можно адаптировать под свою задачу.