define _CRT_SECURE_NO_WARNI NGS include stdafx int uroven количество у

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
int uroven=0;//количество уровней
int dobavlenno=0;//переменная рассказывающая о том сколько лементов уже добавленно на этом уровне
int z = 1;//переменная для добавления после последнего уровня
int list=0;//Количество листьев
struct tree
{
int chislo;
tree* left;
tree* right;
};
tree* Push(int chto)//Добавление элемента
{
tree* Elem = new tree;
Elem->chislo = chto;
dobavlenno++;//говорим что добавлен элемент на уровень
int j=1;
for (int i = 1; i < uroven; i++)
j *= 2;
if (dobavlenno == j) { dobavlenno = 0; uroven++; }//кол-во добавлений = кол-ву элементов по расчету по переход на след уровень
Elem->left = NULL;
Elem->right = NULL;
return Elem;
}
void print_Tree(tree* p, int level)//вывод дерева
{
if (p)//Если дерево есть то выводим
{
print_Tree(p->left, level + 1);
for (int i = 0; i< level; i++) printf( " ");
printf("%d\n",p->chislo);
print_Tree(p->right, level + 1);
}
}
void Dobavit(int chto,int N1,int N2,tree* derevo)//поиск место для добавления
{
z++;
int G = N2-(N2-N1)/2-0.0001;//поиск середины с округлением ВНИЗ
if ((N1 == dobavlenno + 1) && (z==uroven)) { derevo->left = Push(chto); return; };
if ((N2 == dobavlenno + 1) && (z == uroven)) { derevo->right = Push(chto); return; };
if (((dobavlenno + 1) < G+1) || ((dobavlenno + 1) == G)) { Dobavit(chto, N1, G, derevo->left); }
else { Dobavit(chto, G+1, N2, derevo->right); };
return;
}
void listik(tree* derevo)//Подсчет количества листьев в дереве
{
if (derevo != NULL)
{
listik(derevo->left);
listik(derevo->right);
if (derevo->right == NULL && derevo->left == NULL) list++;
}
}
void obh1(tree* derevo)//Прямой обход
{
if (derevo != NULL)
{
printf("%d ", derevo->chislo);
obh1(derevo->left);
obh1(derevo->right);
}
}
void obh2(tree* derevo)//Симетричный обход
{
if (derevo != NULL)
{
obh2(derevo->left);
printf("%d ", derevo->chislo);
obh2(derevo->right);
}
}
void obh3(tree* derevo)//Обратный обход
{
if (derevo != NULL)
{
obh3(derevo->left);
obh3(derevo->right);
printf("%d ", derevo->chislo);
}
}
int main()
{
int chto=0;
tree* derevo=NULL;
printf("Programma derevo\nVvedite pervi koren dereva\n");
if (scanf("%d", &chto) != 1) {printf("Vvedeno ne chislo\n"); return 0; };
dobavlenno = 0;
uroven = 1;
derevo = Push(chto);
char ch1=' ';
int N2=1;
while (ch1 != 'e')//Вывод меню для работы с деревом
{
fflush(stdin);
printf("Chto hotite?\n d-dovit element\n v-vivod\n o-obhod\n p-podschet listev\n e-vihod\n");
ch1=getchar();
switch (ch1){
case 'd':
fflush(stdin);
printf("Vvedite chislo: ");
if (scanf("%d", &chto) != 1) { printf("Vvedeno ne chislo\n"); break; };
for (int i = 1; i < uroven; i++)
N2 *= 2;
Dobavit(chto, 1, N2, derevo);
N2 = 1;
z = 1;
break;
case 'v':
print_Tree(derevo,0);
break;
case 'o':
printf("Pramoi obhod:\n");
obh1(derevo);
printf("\nSimmetichn obhod:\n");
obh2(derevo);
printf("\nObratni obhod:\n");
obh3(derevo);
printf("\n");
break;
case 'p':
list = 0;
listik(derevo);
printf("Kolichestvo listev = %d\n", list);
list = 0;
break;
}
}
return 0;
}