#include <iostream>
#include <stdio.h>
#include <cstdint>
std::uintptr_t i;
using namespace std;

struct Node {
	int data;
	Node* left;
	Node* right;
	Node* parent;
	Node*v, *cur;

};
Node* root = 0;
Node* getfreeNode(int value, Node *parent) {// построение нового узла
	Node *tmp = new Node;
	tmp->left = tmp->right = NULL;
	tmp->data = value;
	tmp->parent = parent;
	return tmp;

}
Node create(Node *root, int key)
{
	// Выделение памяти под корень дерева
	Node *tmp = new Node;
	// Присваивание значения ключу
	tmp->data = key;
	// Присваивание указателю на родителя значения NULL
	tmp->parent = NULL;
	// Присваивание указателю на левое и правое поддерево значения NULL
	tmp->left = tmp->right = NULL;
	root = tmp;
	return *root;
}
void insert(Node **root, int value) {
	Node *tmp = NULL;
	if (*root == NULL) {
		*root = getfreeNode(value, NULL);
		return;
	}
	tmp = *root;
	while (tmp) {
		if (value > tmp->data) {
			if (tmp->right) {
				tmp = tmp->right;
				continue;

			}
			else {
				tmp->right = getfreeNode(value, tmp);
				return;
			}
		}
		else if (value < tmp->data) {
			if (tmp->left) {
				tmp = tmp->left;
				continue;
			}
			else {
				tmp->left = getfreeNode(value, tmp);
				return;
			}
		}
		else {
			return;
		}
	}
}
void find1(Node **root, int d) {
	Node *cur = new Node;
	cur = *root;
	Node *v = new Node;
	v = NULL;
	while (cur != NULL) {
		if (cur->data > d) {
			v = cur;
			cur = cur->left;
		}
		else
			cur = cur->right;
	}
	cout << "Следующий элемент за данным: " << v->data << endl;
}

void find2(Node **root, int d) {
	Node *cur = new Node;
	Node *v = new Node;
	cur = *root;
	v = NULL;
	while (cur != NULL) {
		if (cur->data < d) {
			v = cur;
			cur = cur->right;
		}
		else
			cur = cur->left;
	}
	cout << "Предыдущий элемент: " << v->data << endl;

}


void Vyvod(Node **w, int l) {
	int i;
	if (*w != NULL) {
		Vyvod(&((**w).right), l + 1);
		for (i = 1; i <= l; i++) cout << " ";
		cout << (**w).data << endl;
		Vyvod(&((**w).left), l + 1);
	}
}



int main() {
	setlocale(LC_ALL, "Russian");
	int mas[] = {10, 3, 4, 8, 9, 11, 1, 12, 13, 14, 15, 16,  2, 5, 7, 6 };
	for (int i = 0; i < 16; i++)
		insert(&root, mas[i]); // заполнение корня числами
	create(root, 10); // создание корня дерева
	Vyvod(&root, 1); // вывод всего дерева
	int n;
	cout << "Введите элемент из дерева" << endl;
	cin >> n;
	find1(&root,n); // поиск соседей
	find2(&root, n);
	system("pause");
	return 0;

}