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

[mrcnn]

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

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

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

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

[ivank]

Какой структурой данных можно организовать хранение дерева?
Глубина дерева не ограничена.
Максимальное число ветвей на каждый узел - 4. »
struct Node {
Node *children[4];
};ня?

Дана матрица 10x10. Нужно обойти все элементы всеми возможными способами. Упростим задачу, предположив, что каждый узел можно посетить только один раз. Решение должно быть без рекурсии, и решение должно позволять возврат назад. »
Яндекс, друг молодёжи (http://yandex.ru/yandsearch?rpt=rad&text=%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%20%D0%B2%20%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83). Матрица - тот же граф, по сути. Вершины - клетки матрицы, рёбра - переходы по горизонтали/вертикали в соседние клетки. Без рекурсии не реализуется, можно обойтись банальным стеком, но по сути - та же рекурсия.

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

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

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