Добрый день!
Поделитесь пожалуйста если есть хорошей ссылкой или литературой на информацию по бинарным деревьям. Интересно случайное дерево поиска и идеально сбалансированное дерево. Я код написал, но его так искритиковали. Я прямо уже не знаю как решить проблему.... Информации масса, но никам не получается справиться....
Код:
#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;
}