рекурсивный обход дерева
В качестве примера использования указателей на структуры приведем фрагмент программы, вычисляющий количество вершин бинарного дерева. Бинарным деревом называется связный граф без циклов, у которого одна вершина отмечена как корневая, а все вершины упорядочены иерархически по длине пути от корня к вершине. У каждой вершины должно быть не больше двух сыновей, причем задан их порядок (левый и правый сыновья).
Вершина дерева описывается структурой TreeNode, которая рассматривалась в предыдущем разделе. Если у вершины один из сыновей отсутствует, то соответствующий указатель содержит нулевой адрес.
Для подсчета числа вершин дерева используем функцию numNodes с прототипом
int numNodes(const struct TreeNode *root);
Ей передается константный указатель на корневую вершину дерева или поддерева. Функция возвращает суммарное число вершин дерева или поддерева. Эта функция легко реализуется с помощью рекурсии: достаточно подсчитать число вершин для каждого из двух поддеревьев, соответствующих левому и правому сыновьям корневой вершины, сложить их и прибавить к сумме единицу. Если левый или правый сын отсутствует, то соответствующее слагаемое равно нулю. Вот фрагмент программы, реализующий функцию numNodes.
// Описание структуры, представляющей вершину дерева struct TreeNode { struct TreeNode *parent; // Указатель на отца, struct TreeNode *left; // на левого сына, struct TreeNode *right; // на правого сына void *value; // Значение в вершине };
// Рекурсивная реализация функции, // вычисляющей число вершин дерева. // Вход: указатель на корень поддерева // Возвращаемое значение: число вершин поддерева int numNodes(const struct TreeNode *root) { int num = 0; if (root == 0) { // Для нулевого указателя на корень return 0; // возвращаем ноль }
if (root->left != 0) { // Есть левый сын => num += numNodes(root->left); // вызываем функцию } // для левого сына
if (root->right != 0) { // Есть правый сын => num += numNodes(root->right); // вызываем ф-цию } // для правого сына
return num + 1; // Возвращаем суммарное число вершин }
Здесь неоднократно применялась операция стрелочка ?> для доступа к полю структуры через указатель на нее.
