Рассмотреть алгоритмы обхода дерева в прямом, обратном и внутреннем порядке. Использовать рекурсию.
Алгоритм обхода дерева в прямом порядке (рекурсивный)
посетить корень
посетить каждое поддерево в прямом порядке
Необходимые данные:
массив son - список узлов и сыновей для них
числовые массивы left и right
void Obhod_Dereva_Prymoi_Poryadok (int node) // функция получает в качестве аргумента номер узла
{
printf ("%d\n", son[node]); // где массив son хранит "сыновей"
if (left[node] != 0) Obhod_Dereva_Prymoi_Poryadok (left[node]);
if (right[node] != 0) Obhod_Dereva_Prymoi_Poryadok (right[node]);
return;
}Алгоритм обхода дерева в обратном порядке (рекурсивный)
посетить каждое поддерево в обратном порядке
посетить корень
Необходимые данные:
массив son - список узлов и сыновей для них
числовые массивы left и right
void Obhod_Dereva_Obratniy_Poryadok (int node) // функция получает в качестве аргумента номер узла
{
if (left[node] != 0) Obhod_Dereva_Obratniy_Poryadok (left[node]);
if (right[node] != 0) Obhod_Dereva_Obratniy_Poryadok (right[node]);
printf ("%d\n", son[node]); // где массив son хранит "сыновей"
return;
}Алгоритм обхода дерева во внутреннем порядке (рекурсивный)
Необходимые данные:
массив son - список узлов и сыновей для них
числовые массивы left и right
void Obhod_Dereva_Vnutr_Poryadok (int node) // функция получает в качестве аргумента номер узла
{
if (left[node] != 0) Obhod_Dereva_Vnutr_Poryadok (left[node]);
printf ("%d\n", son[node]); // где массив son хранит "сыновей"
if (right[node] != 0) Obhod_Dereva_Vnutr_Poryadok (right[node]);
return;
}
Ключевые слова:
алгоритм обхода дерева, прямой обратный и внутренний порядок обхода, дерево, обход, рекурсия
