Поиск элемента в бинарном дереве - 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); } }
Объяснение кода листинга программы
- Функция search принимает два аргумента: PNode tree и const char * name.
- Если tree равно NULL, функция возвращает NULL.
- Если strcmp(tree->Name, name) равно 0, функция возвращает tree.
- Если tree не равно NULL, функция вызывает search для левого поддерева tree->left и name, и если результат не равен NULL, возвращает его.
- Если result поискового запроса в левом поддереве равен NULL, функция вызывает search для правого поддерева tree->right и name, и если результат не равен NULL, возвращает его.
- Если оба поддерева возвращают NULL, функция возвращает NULL.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д