Случайное дерево поиска (СДП) - C (СИ)
Формулировка задачи:
for(i = 0; i < n; i++) { AddTree(root, mass[i]); } ...... ........ void AddTree(Tree *root, int D) { Tree **p = &root; while((*p) != NULL) { if(D < (*p)->data) p = &((*p)->pleft); else if(D > (*p)->data) p = &((*p)->preight); } if((*p) == NULL) { (*p) = (Tree**)malloc(sizeof(Tree*)); (*p)->data = D; (*p)->pleft = (*p)->preight = NULL; } }
procedure SDP(D: integer; var Root: pVertex); var p: ^pVertex; begin p := @Root; while p^ <> nil do if D < p^^.Data then p := @p^^.Left else if D > p^^.Data then p := @p^^.Right; if p^ = nil then begin new(p^); p^^.Data := D; p^^.Right := nil; p^^.Left := nil; end end; ... for i := 1 to n do SDP(a[i],Root2);
Решение задачи: «Случайное дерево поиска (СДП)»
textual
Листинг программы
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> struct tabTree { int data; struct tabTree *pleft; struct tabTree *preight; }; typedef struct tabTree Tree; /* Количество операций */ int op; /* Прототипы функций */ void AddTree(Tree **root, int D); Tree *BalansTree(int L, int R, int *mass); int TreeFind(Tree *p); int HeightTree(Tree *p); int Find(Tree *root, int X); /*********************/ void main() { Tree *root = NULL; int n, i, X; int *mass; system("chcp 1251 > nul"); printf("\n Введите количество вершин в дереве (N):"); scanf("%d", &n); system("cls"); printf("\n Массив случайных чисел:\n\n"); srand((unsigned)time(NULL)); mass = (int*)malloc(sizeof(int) * n); if(mass == NULL) { printf("Memory error!"); return; } for(i = 0; i < n; i++) { mass[i] = rand()%99 + 1; printf("%3d", mass[i]); if(i != 0 && i%10 == 0) printf("\n"); } for(i = 0; i < n; i++) { AddTree(&root, mass[i]); } printf("\n\n ***************************************************"); printf("\n ДЕРЕВО ПОСТРОЕНО!"); printf("\n ***************************************************"); printf("\n Введите вершину для поиска: "); scanf("%d", &X); printf("\n\n - Случайное дерево поиска (СДП)\n"); printf("\t Высота дерева: %d", HeightTree(root)); printf("\n\t %s деревом поиска", TreeFind(root) ? "Является" : "Не является"); printf("\n\t Вершина %sнайдена", Find(root, X) ? "" : "не "); printf("\n\t Количество операций: %d", op); root = BalansTree(0, n, mass); printf("\n\n - Идеально сбалансированное дерево поиска (ИСДП)\n"); printf("\t Высота дерева: %d", HeightTree(root)); printf("\n\t %s деревом поиска", TreeFind(root) ? "Является" : "Не является"); printf("\n\t Вершина %sнайдена", Find(root, X) ? "" : "не "); printf("\n\t Количество операций: %d", op); printf("\n\n"); free(mass); } /* Случайное дерево поиска (СДП) */ void AddTree(Tree **root, int D) { Tree **p = root; while((*p) != NULL) { if(D < (**p).data) p = &((**p).pleft); else p = &((**p).preight); } if((*p) == NULL) { (*p) = (Tree*)malloc(sizeof(Tree)); (**p).data = D; (**p).pleft = (**p).preight = NULL; } } /* Идеально сбалансированное дерево поиска (ИСДП) */ Tree *BalansTree(int L, int R, int *mass) { int m; Tree *p; if(L > R) return NULL; else { m = (L + R)/2; p = (Tree*)malloc(sizeof(Tree)); if(p == NULL) { printf("Memory error!"); exit(1);} p->data = mass[m]; p->pleft = BalansTree(L, m - 1, mass); p->preight = BalansTree(m + 1, R, mass); return p; } } /* Функция вычисления высоты дерева */ int HeightTree(Tree *p) { int pl = 0; int pr = 0; if(p == NULL) return 0; else { pl = HeightTree(p->pleft); pr = HeightTree(p->preight); return 1 + ((pl > pr) ? pl : pr); } } /* Является ли деревом поиска??? */ int TreeFind(Tree *p) { if ((p == NULL && (p->pleft != NULL && (p->data <= p->pleft->data || !TreeFind(p->pleft)))) || (p->preight != NULL && (p->data >= p->preight->data || !TreeFind(p->preight)))) return 0; else return 1; } /* Поиск вершины */ int Find(Tree *root, int X) { Tree *p = root; op = 0; while(p != NULL) { op++; if(p->data == X) return 1; else p = (p->data > X) ? p->pleft : p->preight; } return 0; }
Объяснение кода листинга программы
- Структура данных для представления дерева -
struct tabTree
. - Объявление переменных:
op
- количество операций;n
- количество вершин в дереве;i
- номер вершины;X
- искомый элемент.
- Заполнение массива случайными числами.
- Построение дерева путем вызова функции
AddTree
для каждой вершины массива. - Вывод информации о дереве:
- высота дерева;
- является ли дерево деревом поиска;
- найдена ли искомая вершина;
- количество операций.
- Создание идеально сбалансированного дерева путем вызова функции
BalansTree
для диапазона от 0 доn
. - Вывод информации об идеально сбалансированном дереве:
- высота дерева;
- является ли дерево деревом поиска;
- найдена ли искомая вершина;
- количество операций.
- Функция
AddTree
для добавления вершины в дерево. - Функция
BalansTree
для создания идеально сбалансированного дерева. - Функция
HeightTree
для вычисления высоты дерева. - Функция
TreeFind
для проверки, является ли дерево деревом поиска. - Функция
Find
для поиска вершины в дереве.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д