Подразделы

Другие разделы

Дата и время

19/03/2024 09:58:32

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

print2329. (деревья) Поиск по ключу в частично-упорядоченном бинарном дереве

print(деревья) Поиск по ключу в частично-упорядоченном бинарном дереве

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Структура "узел", операция вставки, печати определена в коде.
"Вставка" работает таким образом, что сохраняется структура частично-упорядоченного бинарного дерева.
Требуется реализовать поиск по значению в дереве
Используйте следующий шаблон программы:
#include <iostream>



using namespace std;

void search(int);

struct NODE {	// Структура "Узел" для элементов дерева

	int elem;	// данные
	NODE *left;		// левое поддерево
	NODE *right;	// правое поддерево
	NODE(int el) { left = right = NULL; elem = el; }
};

NODE *root;	// глобальный корень дерева

void push(int el) { // вставка нового элемента в дерево

	if (!root) {
		root = new NODE(el);
		return;
	}

	NODE *buf;
	buf = root;

	while (true) {
		if (buf->elem >= el) {
			if (!buf->left) {
				buf->left = new NODE(el);
				return;
			}
			buf = buf->left;
		}
		else {
			if (!buf->right) {
				buf->right = new NODE(el);
				return;
			}
			buf = buf->right;
		}
	}
}

void search(int key) {
	// ЭТУ ФУНКЦИЮ НУЖНО НАПИСАТЬ
}

void print(NODE* cur) {	// печать, симметричный обход
	if (cur->left) {
		print(cur->left);
	}
	cout << cur->elem << endl;
	if (cur->right) {
		print(cur->right);
	}
}

int main() {
	// для отладки:
	// вывод дерева print(node) где node - указатель на корень дерева
	// поместить элемент в дерево push(element) прим. - элемент поместится в нужное место.
	// шаблон предназначен для отправки на проверку, для отладки можете самостоятельно
	// помещать свои элементы напр. push(5); push(20); push(50) и т.д. и работать со своими элементами
	
	// Само дерево объявлено глобально в коде
	int N;	// кол-во элементов
	cin >> N;
	for (int i = 0; i < N; i++) {	// ввод элементов в дерево
		int a;
		cin >> a;
		push(a);
	}
	cin >> N;	// искомый элемент
	search(N);	// поиск с выводом
	return 0;
}


Ввод
N+2 числа, первое – количество вводимых элементов N, далее N элементов дерева, затем значение искомого элемента.
Вывод
Строка в виде Element "X" is found.

Пример ввода

5 2 4 6 8 10 6

Пример вывода

Element "6" is found.

loading