#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <windows.h>
int lvl=0;//количество уровней
int added=0;//сколько элементов уже добавленно на этом уровне
int z = 1;//переменная для добавления после последнего уровня
int count=0;//Количество элементов в левом поддереве
struct tree
{
int koren;
tree* left;
tree* right;
};
tree* NewTree(int info)//Добавление элемента
{
tree* Elem = new tree;
Elem->koren = info;
added++;//говорим что добавлен элемент на уровень
int j=1;
for (int i = 1; i < lvl; i++)
j *= 2;
if (added == j) { added = 0; lvl++; }//кол-во добавлений = кол-ву элементов по расчету по переход на след уровень
Elem->left = NULL;
Elem->right = NULL;
return Elem;
}
void print_Tree(tree* p, int lvl)//вывод дерева
{
if (p)//Если дерево есть то выводим
{
print_Tree(p->right, lvl + 1);
for (int i = 0; i< lvl; i++) printf( " ");
printf("%d\n",p->koren);
print_Tree(p->left, lvl + 1);
}
}
void Dobavit(int info,int N1,int N2,tree* derevo)//поиск места для добавления
{
z++;
int G = N2-(N2-N1)/2-0.0001;//поиск середины с округлением ВНИЗ
if ((N1 == added + 1) && (z==lvl)) { derevo->left = NewTree(info); return; };
if ((N2 == added + 1) && (z == lvl)) { derevo->right = NewTree(info); return; };
if (((added + 1) < G+1) || ((added + 1) == G)) { Dobavit(info, N1, G, derevo->left); }
else { Dobavit(info, G+1, N2, derevo->right); };
return;
}
void Resh(tree* derevo)//Определение для каждой вершины числа вершин в левом поддереве
{
if (derevo != NULL)
{
Resh(derevo->left);
Resh(derevo->right);
count++;
}
}
void straight(tree* derevo)//Прямой обход
{
if (derevo != NULL)
{
printf("%d ", derevo->koren);
straight(derevo->left);
straight(derevo->right);
}
}
void symetric(tree* derevo)//Симетричный обход
{
if (derevo != NULL)
{
symetric(derevo->left);
printf("%d ", derevo->koren);
symetric(derevo->right);
}
}
void reverse(tree* derevo)//Обратный обход
{
if (derevo != NULL)
{
reverse(derevo->left);
reverse(derevo->right);
printf("%d ", derevo->koren);
}
}
tree* del_tree(tree *derevo, int val) //удалить элемент из дерева
{
if (NULL == derevo) return NULL;
if (derevo->koren == val) {
if (NULL == derevo->left && NULL == derevo->right) { // если лист
free(derevo);
return NULL;
}
if (NULL == derevo->right && derevo->left != NULL) {
tree *temp = derevo->left;
free(derevo);
return temp;
}
if (NULL == derevo->left && derevo->right != NULL) {
tree *temp = derevo->right;
free(derevo);
return temp;
}
derevo->left = del_tree(derevo->left, derevo->koren);
return derevo;
}
// поиск нужного элемента
if (val < derevo->koren) {
derevo->left = del_tree(derevo->left, val);
return derevo;
}
if (val > derevo->koren) {
derevo->right = del_tree(derevo->right, val);
return derevo;
}
return derevo;
}
int main()
{
int info=0;//значение текущего элемента
tree* derevo=NULL;
printf("LR#4. Derevo. Var13.\nVvedite koren dereva: ");
if (scanf("%d", &info) != 1) {
printf("Vvedeno ne koren. Nevernii symbol.\n");
return 0;
}
added = 0; //кол-во добавленных элементов
lvl = 1; //текущий уровень дерева
derevo = NewTree(info); //создаем новое дерево с введенным корнем
char ch1=' ';//переменная для ввода кода операции
int N2=1;//количество заполненных уровней
int n;
while (ch1 != 'e')//Вывод меню для работы с деревом
{
fflush(stdin);
printf("_____________________________________________");
printf("\nVvedite opperatiy: \n d-dobavit elementi\n v-vivod dereva\n o-obhod\n r-Vipolnenie zadania. Kol-vo vershin v levom poddereve. \n u - Udalit derevo\n e-EXIT\n");
ch1=getchar();
switch (ch1){
case 'd'://добавить элементы
fflush(stdin);
printf("Vvedite colichestvo: ");
if (scanf("%d", &n) != 1)
{
printf("Vvedeno ne chislo\n");
break;
}
printf("Vvedite elementi(razdelitel - enter):\n");
for (int i = 0; i < n; i++)
{
if (scanf("%d", &info) != 1)
{
printf("Vvedeno ne chislo\n");
break;
}
for (int i = 1; i < lvl; i++)
N2 *= 2;
Dobavit(info, 1, N2, derevo);
N2 = 1;
z = 1;
}
break;
case 'v':
print_Tree(derevo,0);
break;
case 'o':
printf("\nKLR: ");
straight(derevo);
printf("\nLKR: ");
symetric(derevo);
printf("\nLRK: ");
reverse(derevo);
printf("\n");
break;
case 'r':
count = 0;
Resh(derevo->left);
printf("Kolichestvo vershin v levom poddereve = %d\n", count);
count = 0;
break;
case 'u':
printf("\n Vvedite udal element: ");
int t;
if (scanf("%d", &t) != 1)
{
printf("Vvedeno ne chislo\n");
break;
}
fflush(stdin);
derevo = del_tree(derevo, t);
break;
}
}
return 0;
}