Деревья

Вершину дерева можно определить таким образом:

struct tree
{
int val; // Значение элемента

tree *child[4]; // Указатели на потомков

};

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

//------------------------------------------------------bk55-02.cpp

//------Рекурсивный обход дерева

void ScanTree(tree *p)
{
int i;
if (p == NULL) return; // следующей вершины нет

for (i=0; i&#60 4; i++) // рекурсивный обход

ScanTree(p-&#62child[i]); // потомков с передачей

} // указателей на них

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

//------------------------------------------------------bk55-03.cpp

//------Минимальная длина ветвей дерева

int M inDepth(tree *p)
{ int i, m in, nn;
if (p == NULL) return 0; // следующей вершины нет

for (min = MinDepth(p-&#62child[0], i=1; i&#60 4; i++)
{ // обход потомков

nn = MinDepth(p-&#62child[i]);
if (nn &#62 max) max = nn;
} // возвращается глубина с

return min + 1; // учетом текущей вершины

}

Другой достаточно тривиальной процедурой является включение нового элемента в дерево.