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

Объяснение кода листинга программы

В данном коде реализуется рекурсивный алгоритм для определения количества узлов в дереве, которые имеют лишь одного потомка.

  1. В первой строке определяется входной параметр функции - Tree r.
  2. Если дерево пустое, то возвращается 0.
  3. Если у дерева есть только один узел (левый или правый), то возвращается 1.
  4. Если у дерева есть два потомка (левый и правый), то выполняется проверка: если один из них пустой, то возвращается 1.
  5. Если оба потомка не пустые, то вызывается рекурсивная функция для обоих потомков и результат их вызовов добавляется к общему результату.
  6. Возвращается общее количество узлов, имеющих лишь одного потомка.

Оцени полезность:

9   голосов , оценка 3.778 из 5
Похожие ответы