Программирование на языке высокого уровня. Марапулец Ю.В. - 79 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

printf ("Input N: \n");
scanf ("%d", &N); // ввод количества элементов массива
mass=(int *)malloc(N*sizeof(int));
for (int i=0; i<N; i++)
mass[i]=i+1;
printf ("Sum = %d\n", Sum (mass, 0, N-1)); // вызов функции
free(mass);
}
4. Функция, которая производит обход бинарного дерева.
Ранее при рассмотрении темы бинарные деревья было создано дерево бинарного
поиска, обход которого производился обычной функцией PrintTree(). Использование в
данном случае рекурсивной функции существенно упростит программный код, так как
дерево само является рекурсивной структурой данных (каждое поддерево также являет-
ся деревом). В общем виде функцию обхода всех узлов дерева можно описать следую-
щим образом [8]:
function NodeWay ( дерево )
{
NodeWay ( левое поддерево )
посещение корня
NodeWay ( правое поддерево )
}
Можно обходить дерево и в другом порядке, например, сначала корень, потом
поддеревья, но приведенная функция позволяет получить на выходе отсортированную
последовательность ключей, поскольку сначала посещаются вершины с меньшими клю-
чами, расположенные в левом поддереве. Таким образом, деревья поиска можно приме-
нять для сортировки значений. При обходе дерева узлы не удаляются.
Рассмотрим пример исходного кода рекурсивной функции обхода дерева, пример
которого приведен в разделе бинарные деревья. Для этого создадим рекурсивную функ-
цию PrintTreeRecurs(). Вторым параметром в нее передается целая переменная, опреде-
ляющая, на каком уровне находится узел. Корень находится на уровне 0. Следует отме-
тить, что функция обхода дерева длиной всего в несколько строк может напечатать де-
рево любого размера - важно только следить, чтобы рекурсивные вызовы не переполни-
ли стек. В результате выполнения программы (для выполнения просто замените в при-
веденном коде функцию PrintTree на PrintTreeRecurs) дерево печатается по горизонтали
так, что корень находится слева. Если повернуть ответ на 90 градусов вправо и зеркаль-
но перевернуть, получится схема, аналогичная дереву, приведенному на рисунке. Следу-
ет обратить внимание, что все элементы выводятся в порядке возрастания. Перед значе-
нием узла для имитации структуры дерева выводится символы табуляции в количестве,
пропорциональном уровню узла:
1
6
8
10
20
21
25
30
79
      printf ("Input N: \n");
      scanf ("%d", &N);        // ввод количества элементов массива
      mass=(int *)malloc(N*sizeof(int));
      for (int i=0; i

Страницы