Случайное дерево поиска (СДП) - 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;
}

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

  1. Структура данных для представления дерева - struct tabTree.
  2. Объявление переменных:
    • op - количество операций;
    • n - количество вершин в дереве;
    • i - номер вершины;
    • X - искомый элемент.
  3. Заполнение массива случайными числами.
  4. Построение дерева путем вызова функции AddTree для каждой вершины массива.
  5. Вывод информации о дереве:
    • высота дерева;
    • является ли дерево деревом поиска;
    • найдена ли искомая вершина;
    • количество операций.
  6. Создание идеально сбалансированного дерева путем вызова функции BalansTree для диапазона от 0 до n.
  7. Вывод информации об идеально сбалансированном дереве:
    • высота дерева;
    • является ли дерево деревом поиска;
    • найдена ли искомая вершина;
    • количество операций.
  8. Функция AddTree для добавления вершины в дерево.
  9. Функция BalansTree для создания идеально сбалансированного дерева.
  10. Функция HeightTree для вычисления высоты дерева.
  11. Функция TreeFind для проверки, является ли дерево деревом поиска.
  12. Функция Find для поиска вершины в дереве.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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