Определение количество узлов, имеющих лишь одного потомка - C (СИ)
Формулировка задачи:
Функция (potomki) считает значение некорректно. Прошу помощи знающих людей.
#include <stdio.h> #include <stdlib.h> #include <locale.h> struct tree { int key; char symbol; struct tree *left; struct tree *right; }; typedef struct tree TreeNode; typedef TreeNode *Tree; int menu(); void add(Tree&, int, char); void find(Tree, int); Tree del(Tree&, int); void print(Tree, int); int potomki(Tree r, int, int); void del_all(Tree &); int result; int f = 0; int main() { int key; char symbol; Tree Root = NULL; setlocale(LC_ALL, "rus"); while (1) { switch (menu()) { case 1: { printf("Введите ключ: "); scanf("%d", &key); if (key<0) break; printf("Введите символ: "); scanf("\n%c", &symbol); add(Root, key, symbol); } break; case 2: printf("Введите ключ для поиска: "); scanf("%d", &key); find(Root, key); break; case 3: if (Root != NULL) { printf("Введите ключ для удаления: "); scanf("%d", &key); del(Root, key); } else printf("Дерево пустое.\n"); break; case 4: if (Root != NULL) { printf("\n"); print(Root, 0); } else printf("Дерево пустое.\n"); break; case 5: if(Root == NULL) printf("Дерево не существует.\n"); else { printf("Uzlov s 1 potomkom: %d", potomki(Root, 0, 0)); } break; case 6: del_all(Root); if (Root == NULL) printf("Дерево удалено\n"); else printf("Ошибка\n"); return 0; default: printf("Неверное значение. Введите еще раз.\n"); menu(); break; } } } //_______________________________________________________________________________________ int menu() { int x; printf("\n\tМеню:\n"); printf("1 - Добавить дерево\n"); printf("2 - Поиск узла по ключу\n"); printf("3 - Удаление узла по ключу\n"); printf("4 - Вывод дерева\n"); printf("5 - Количество узлов c одним потомком\n"); printf("6 - Завершение программы\n"); printf("Ваш выбор: "); scanf("%d", &x); return x; } //_______________________________________________________________________________________ void add(Tree &r, int key, char symbol) { if (r == NULL) // Если дерево не создано { r = (Tree)malloc(sizeof(TreeNode)); if (r != NULL) { r->key = key; r->symbol = symbol; r->left = NULL; r->right = NULL; } else printf("Ошибка добавления элемента\n"); } else if (key < r->key) add(r->left, key, symbol); else if (key > r->key) add(r->right, key, symbol); } //_______________________________________________________________________________________ void find(Tree r, int key) { if (r != NULL) { find(r->left, key); if (r->key == key) printf("Ключ %d содержит [%c]\n", r->key, r->symbol); find(r->right, key); } } //_______________________________________________________________________________________ Tree del(Tree &r, int key) { Tree Del = r, Prev_Del = NULL, R, Prev_R; // Del, Pred_Del – удаляемый элемент и его предыдущий (родитель); // R, Pred_R – элемент, на который заменяется удаленный, и его родитель; while (Del != NULL && Del->key != key) //Поиск удаляемого элемента и его родителя по ключу key { Prev_Del = Del; if (Del->key > key) Del = Del->left; else Del = Del->right; } if (Del == NULL) // Элемент не найден { printf("Отсутствует ключ\n"); return r; } //Поиск элемента R для замены if (Del->right == NULL) R = Del->left; //не нашли справа else if (Del->left == NULL) R = Del->right; else { Prev_R = Del; // Ищем самый правый узел в левом поддереве R = Del->left; while (R->right != NULL) { Prev_R = R; R = R->right; } if (Prev_R == Del) // Нашли элемент для замены R и его родителя Pred_R R->right = Del->right; else { R->right = Del->right; Prev_R->right = R->left; R->left = Del->left; } } if (Del == r) r = R; // Удаляя корень, заменяем его на R else if (Del->key < Prev_Del->key) Prev_Del->left = R; // Поддерево R присоединяем к родителю удаляемого узла else Prev_Del->right = R; printf("\nЭлемент %d[%c] удален\n", Del->key, Del->symbol); free(Del); return r; } //_______________________________________________________________________________________ void print(Tree r, int l) { if (!r) return; print(r->right, l + 1); // Вывод правого поддерева for (int i = 0; i<l; i++) printf(" "); printf("%d", r->key); printf("[%c]\n\n", r->symbol); print(r->left, l + 1); // Вывод левого поддерева } //_______________________________________________________________________________________ int potomki(Tree r, int level, int kol) { if (r) { if (r->left != NULL && r->right == NULL) kol++; //printf("%d ", kol); potomki(r->left, level + 1, kol); } if (r) { if (r->right != NULL && r->left == NULL) kol++; //printf("%d ", kol); potomki(r->right, level + 1, kol); } return kol; } //________________________________________________________________________________________ void del_all(Tree &r) { if (r != NULL) { del_all(r->left); del_all(r->right); free(r); } r = NULL; }
Решение задачи: «Определение количество узлов, имеющих лишь одного потомка»
textual
Листинг программы
int potomki(Tree r) { int kol = 0; if (!r) return 0; if ((r->left == NULL) ^ (r->right == NULL)) kol = 1; return kol + potomki(r->left) + potomki(r->right); }
Объяснение кода листинга программы
В данном коде реализуется рекурсивный алгоритм для определения количества узлов в дереве, которые имеют лишь одного потомка.
- В первой строке определяется входной параметр функции - Tree r.
- Если дерево пустое, то возвращается 0.
- Если у дерева есть только один узел (левый или правый), то возвращается 1.
- Если у дерева есть два потомка (левый и правый), то выполняется проверка: если один из них пустой, то возвращается 1.
- Если оба потомка не пустые, то вызывается рекурсивная функция для обоих потомков и результат их вызовов добавляется к общему результату.
- Возвращается общее количество узлов, имеющих лишь одного потомка.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д