Определение количество узлов, имеющих лишь одного потомка - 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; }

Код к задаче: «Определение количество узлов, имеющих лишь одного потомка - C (СИ)»

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);
}

9   голосов, оценка 3.778 из 5


СОХРАНИТЬ ССЫЛКУ
Похожие ответы