Поиск элемента в бинарном дереве - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Разработать программу, формирующую динамическую структуру данных для хранения генеалогического дерева. Каждая вершина дерева должна содержать следующую информацию: имя и год рождения. Вопрос по синтаксису языка СИ. Если в написанной ниже программе попытаться добавить на третий уровень генеалогического дерева лист, который должен будет исходить из листа-матери на втором уровне, то программа благополучно вылетит. Это связано с функцией "Search". Дело в том, что при рекурсивном обходе бинарного дерева, оператор "return" необъяснимым для меня образом завершает не только выполнение функции, вызванной из функции, но и все открытые при помощи рекурсии до этого функции. Help, please
/*Компилятор Code::Blocks 13.12 
Selected compiler GNU GCC Compiler*/
 
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
 
struct Node {
    char Name[40];
    int Year;
    struct Node *left;
    struct Node *right;
 };
typedef struct Node *PNode;
 
PNode Search (PNode Tree, char Name[]) {
    if ( ! Tree ) return;
    Search(Tree->left, Name);
    if (strcmp(Tree->Name, Name) == 0)
        return Tree;
    Search(Tree->right, Name);
 };
 
PNode CreateLeaf () {
    char Name[40];
    int Year;
    PNode NewNode = malloc(sizeof(struct Node));
    printf("Введите имя: ");
    scanf("%s", &Name);
    printf("Введите дату рождения: ");
    scanf("%d", &Year);
    strcpy(NewNode->Name, Name);
    NewNode->Year = Year;
    NewNode->left = NULL;
    NewNode->right = NULL;
    return NewNode;
 };
 
void ShowAllLeafs (PNode Tree) {
    if ( ! Tree ) return;
    ShowAllLeafs(Tree->left);
    printf("%s - %d\n", Tree->Name, Tree->Year);
    ShowAllLeafs(Tree->right);
 };
 
void main () {
    PNode Root, p1;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    printf("    Создайте корень генеалогического дерева\n");
    Root = CreateLeaf();
    int input;
    char Name[40];
    while ( 1 ) {
        system("cls");
        printf("1. Добавить лист к генеалогическому дереву\n");
        printf("2. Вывести всю введённую информацию\n");
        printf("3. Выход\n");
        scanf( "%d", &input );
        switch (input) {
            case 1:
                system("cls");
                printf("Введите имя листа, к которому хотите обратиться: ");
                scanf("%s", Name);
                p1 = Search(Root, Name);
                printf("\n    Добавление матери...\n");
                p1->left = CreateLeaf();
                printf("\n    Добавление отца...\n");
                p1->right = CreateLeaf();
                break;
            case 2:
                system("cls");
                ShowAllLeafs(Root);
                getch();
                break;
            case 3:
                return;
            default :
                break;
         }
     }
     return;
 };

Решение задачи: «Поиск элемента в бинарном дереве»

textual
Листинг программы
PNode search(PNode tree, const char * name) {
    if ( ! tree )
        return NULL;
    else if ( strcmp(tree->Name, name) == 0 )
        return tree;
    else {
        PNode p = search(tree->left, name);
        return ( p ) ? p : search(tree->right, name);
    }
}

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

  1. Функция search принимает два аргумента: PNode tree и const char * name.
  2. Если tree равно NULL, функция возвращает NULL.
  3. Если strcmp(tree->Name, name) равно 0, функция возвращает tree.
  4. Если tree не равно NULL, функция вызывает search для левого поддерева tree->left и name, и если результат не равен NULL, возвращает его.
  5. Если result поискового запроса в левом поддереве равен NULL, функция вызывает search для правого поддерева tree->right и name, и если результат не равен NULL, возвращает его.
  6. Если оба поддерева возвращают NULL, функция возвращает NULL.

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

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