Лабораторная работа №4 (Вариант 1.3.2, Б-дерево) / ЯВУ_4_испр.листингБ-дерево
.docx#include<stdio.h>
#include<stdlib.h>
#include<locale.h>
struct tree{
tree *left1;
int key1;
tree *left2;
int key2;
tree *right1;
int key3;
tree *right2;
}*root=NULL;
int s=0;
void add_in_tree(tree* der,int a)
{
if(der->key3!=0)
{
if(a>der->key3)
{
if(der->right2)
add_in_tree(der->right2,a);
else
{
if(!der->right1)
{
der->right1=(tree*)calloc(1,sizeof(tree));
der->right1->key1=der->key3;
der->key3=0;
der->right1->key2=a;
}
else
{
if(der->right1->key3!=0)
{
int t;
t=der->key3;
der->key3=der->right1->key3;
der->right1->key3=0;
der->right2=(tree*)calloc(1,sizeof(tree));
der->right2->key1=t;
der->right2->key2=2;
der->right2->left1=der->right1->right2;
der->right1->right2=NULL;
}
else
{
der->right1->key2=der->key3;
der->key3=a;
}
}
}
}
else
if(a>der->key2)
{
if(der->right1)
add_in_tree(der->right1,a);
else
{
der->right1=(tree*)calloc(1,sizeof(tree));
der->right1->key1=a;
der->right2->key2=der->key3;
der->key3=0;
der->right1->right1=der->right2;
der->right2=NULL;
}
}
else
if(a>der->key1)
{
if(der->left2)
add_in_tree(der->right1,a);
else
{
der->left2=(tree*)calloc(1,sizeof(tree));
der->left2->key1=der->key1;
der->left2->key2=a;
der->left2->left1=der->left1;
der->left1=NULL;
der->key1=der->key2;
der->key2=der->key3;
der->left1=der->left2;
der->left2=der->right1;
der->right1=der->right2;
}
}
else
{
if(der->left1)
add_in_tree(der->left1,a);
else
{
if(!der->left2)
{
der->left2=(tree*)calloc(1,sizeof(tree));
der->left2->key1=a;
der->left2->key2=der->key1;
der->key1=der->key2;
der->key2=der->key3;
der->left1=der->left2;
der->left2=der->right1;
der->right1=der->right2;
}
else
{
if(der->left2->key3!=0)
{
int t=der->key1;
der->key1=der->left2->key1;
der->left1=(tree*)calloc(1,sizeof(tree));
der->left1->key1=a;
der->left1->key2=t;
der->left2->key1=der->left2->key2;
der->left2->key2=der->left2->key3;
der->left2->left1=der->left2->left2;
der->left2->left2=der->left2->right1;
der->left2->right1=der->left2->right2;
der->left2->right2=NULL;
}
else
{
der->left2->key3=der->key1;
der->key1=a;
}
}
}
}
}
else
{
if(der->key2==0)
{
if(a>der->key1)
der->key2=a;
else
{
der->key2=der->key1;
der->key1=a;
der->right1=der->left2;
der->left2=der->left1;
}
}
else
if(der->key3==0)
{
if(a>der->key2)
der->key3=a;
else
{
if(a>der->key1)
{
der->key3=der->key2;
der->key2=a;
der->right2=der->right1;
der->right1=der->left2;
}
else
{
der->key3=der->key2;
der->key2=der->key1;
der->key1=a;
der->right2=der->right1;
der->right1=der->left2;
der->left2=der->left1;
}
}
}
}
}
int sum(tree *der)
{
s+=(der->key1+der->key2+der->key3);
if(der->left1)
sum(der->left1);
if(der->left2)
sum(der->left2);
if(der->right1)
sum(der->right1);
if(der->right2)
sum(der->right2);
return s;
}
void main()
{
int d,b;
float srednee;
setlocale(LC_ALL,"Russian");
printf("Введите кол-во эл-ов, вводимых с клавиатуры : ");
scanf("%d",&d);
for(int i=0;i<d;i++)
{
printf("Введите ключ : ");
scanf("%d",&b);
if(i==0)
{
root=(tree*)calloc(1,sizeof(tree));
root->key1=b;
}
else
add_in_tree(root,b);
}
srednee = sum(root)/d;
printf("среднее значение ключей сильноветвящегося дерева= %f\n",srednee);
}