Информатика и технология программирования


Деревья


Определение дерева имеет исключительно рекурсивную природу. Элемент этой структуры данных называется вершиной. Дерево представляет собой либо отдельную вершину, либо вершину, имеющую ограниченное число указателей другие деревья (ветвей). Нижележащие деревья для текущей вершины называются поддеревьями, а их вершины -потомками. По отношению к потомкам текущая вершина называется предком.

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


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; // учетом текущей вершины


}

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


Начало  Назад  Вперед