laba18

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include "ctime"
#include "math.h"
#include <tchar.h>
#include <cstring>
#include "stdlib.h"
#include <string>
#include "conio.h"
#include <fstream>

using namespace std;

struct Node { //структура бинарного дерева
	int value; //поле данных
	Node* left; //указатель на левый потомок
	Node* right; //указатель на правый

};



Node* BTree = NULL; //с

void print(Node* MyTree) {
	if (MyTree != NULL) //обращение к информационному полю узла
	{
		cout << MyTree->value << " ";
		print(MyTree->left);
		print(MyTree->right);
	}
}

//&MyTree, TreeElement



void AddNode(Node** MyTree, Node* TreeElement) //рекурсивная функция создания/добавления вершины дерева
{
	int p = 0;
	int q = 0;
	Node* current;
	int A, B;
	A = TreeElement->value;
	current = *MyTree; //вспомогательный указатель на указатель дерева
	if (current == NULL)
		*MyTree = TreeElement; //если узла нет, создаем узел
	else {
		B = current->value;
		while (A) {
			if (A % 10 % 2 == 0) p += A % 10;
			A /= 10;
		}
		while (B) {
			if (B % 10 % 2 == 0) q += B % 10;
			B /= 10;
		}
		//если значение текущего узла поддерева меньше значения узла дерева,
		if (p < q) {         //то зависываем значение узла в левое поддерево
			AddNode(&current->left, TreeElement);
		}
		else {
			AddNode(&current->right, TreeElement);
		} //иначе зависываем значение узла в правое поддерево
	}
}
void PrintTree(Node* tree, int space)
{
	const int COUNT = 5;
	if (tree != NULL)
	{
		space += COUNT;
		PrintTree(tree->right, space);
		for (int i = COUNT; i < space; i++)
			printf("%c", ' ');
		printf_s("%d\n", tree->value);
		PrintTree(tree->left, space);
	}
}
void randomic(int* a, int n)
{
	int t;
	puts("generated list");
	for (int i = 0; i < n; i++)
	{
		t = rand() % 100 + 2452;
		a[i] = t;
		printf_s("%d   ", t);
	}
	printf_s("\n");
}

void Del1(Node** r, Node** q) // вспомогательная функция для удаления вершины
{
	Node* s;
	if ((*r)->right == NULL)
	{
		(*q)->value = (*r)->value;
		*q = *r;
		s = *r;
		*r = (*r)->left;
		delete s;
	}
	else Del1(&((*r)->right), q);
}


void Del_Node(Node** MyTree, int k) // удаление вершины из дерева
{
	Node* current, * q;
	current = *MyTree;
	if (*MyTree == NULL)
		cout << endl << "Элемент с таким значением не найден" << endl;
	else
		if (k < (current)->value)
			Del_Node(&current->left, k); //если вершина является листом
		else
			if (k > (current)->value)
				Del_Node(&current->right, k);
			else {
				q = *MyTree;
				if (q->right == NULL) {
					*MyTree = q->left;
					delete q;
				} //если вершина имеет одну дочернюю вершину
				else
					if (q->left == NULL) {
						*MyTree = q->right; delete q;
					} //если у вершины две дочерних вершины
					else Del1(&q->left, &q);

			}
}



void* Poisk(Node* MyTree)
{
	if (MyTree == NULL)
		return NULL;
	else
		if (MyTree->value % 3 == 0)
		{
			cout << MyTree->value << " ";
			Del_Node(&MyTree, MyTree->value);

		}
	Poisk(MyTree->left);
	Poisk(MyTree->right);


}

void Del_Mem(Node** MyTree) // очистка памяти
{
	Node* current;
	current = *MyTree;
	if (*MyTree != NULL) {
		Del_Mem(&(*MyTree)->left);
		Del_Mem(&(*MyTree)->right);
		delete* MyTree;
	}
}
Node* add(int value)  //Инициализация
{
	Node* TreeElement = new Node; //выделение памяти под узел дерева
	TreeElement->value = value; //запись значения в узел дерева
	TreeElement->left = NULL; //задание пустого левого поддерева
	TreeElement->right = NULL; //задание пустого правого поддерева
	return TreeElement;
}
Node* insert(Node* MyTree, int key)  //Функция добавления узлов в бинарное дерево поиска (BST)
{
	if (MyTree == NULL)
		return add(key);
	if (key < MyTree->value)
		MyTree->left = insert(MyTree->left, key);
	else if (key > MyTree->value)
		MyTree->right = insert(MyTree->right, key);
	return MyTree;
}

int main()
{
	int x;
	int p=0;
	setlocale(0, "rus");
	srand(time(0));
	int n;
	cout << "Введите кол-во элементов дерева ";
	cin >> n;
	int* a = new int[n];
	Node* MyTree = NULL; //указатель, тип которого соответсвует узлу дерева, в   начале создается пустое дерево
	Node* TreeElement;
	int next_number; //вводимые значения узлов дерева

	randomic(a, n);
	for (int i = 0; i < n; i++)
	{
		next_number = a[i];
		TreeElement = new Node; //выделение памяти под узел дерева
		TreeElement->value = next_number; //запись значения в узел дерева
		TreeElement->left = NULL; //задание пустого левого поддерева
		TreeElement->right = NULL; //задание пустого правого поддерева
		AddNode(&MyTree, TreeElement); // добавление узла TreeElement в дерево MyTree
	}

	int temp;
	cout << "Полученное бинарное дерево:" << endl;
	PrintTree(MyTree, 0);
	//cout << endl << "Элементы, которые делятся на 3 " << endl;
	for (int i = 0; i <= n; i++)
	{
		temp = a[i];
		while (a[i]) {

			if (a[i] % 10 % 2 != 0) p = 1 ;
			a[i] /= 10;
		}

		if (p!=1)
		{
			Del_Node(&MyTree, temp);
		}
	}
	cout << endl << "Бинарное дерево после выполнения задания :" << endl;
	print(MyTree);
	cout << endl << "Если вы хотите добавить элементы, то нажмите 1 или программа завершится" << endl;
	cin >> x;
	if (x == 1)
	{
		cout << "Сколько элементов вы хотите задать?" << endl;
		cin >> n;
		cout << "Задайте элементы" << endl;
		for (int i = 0; i < n; i++)
		{
			cin >> x;
			if (i == 0) MyTree = insert(MyTree, x);
			else insert(MyTree, x);

		}


	}
	cout << endl;
	PrintTree(MyTree,0);
}