Деревья. Как выполнить некоторые действия с бинарным деревом?

Question

[DenKG]

У меня задание на самостоятельную работу. Построить бинарное дерево и выполнить с ним некоторые операции. Но вот не знаю, как это сделать. Дерево я построил, оно заполняется, выполняются обходы. С этим всё хорошо. Но вот есть 4 пункта, которые я никак не могу реализовать:
итератор для доступа к элементам дерева с операциями:
• установка на корень дерева,
• проверка конца дерева,
• доступ к данным текущего элемента дерева,
• переход к следующему по значению ключа элементу дерева,
• переход к предыдущему по значению ключа элементу дерева,
Как их выполнить? Или хотя бы дайте ссылку, где читать

Comments

[Денис Загаевский]

Что непонятно-то?
Просто итератор, который обходит дерево. Не "за раз", а по требованию. Раз обходы уже есть, то такой итератор написать не должно составить труда.

[DenKG]

Денис Загаевский: ну я, к сожалению, не могу это сделать :(

[Толстый Лорри]

А в чем проблема? Обходы у вас делаются, т.е. алгоритм есть. Для 1-3 нужно просто высунуть наружу итератор (указатель на узел, обернутый в класс с нужными операциями). В нем определить операции получения одного из следующих узлов и родительского.

[DenKG]

Толстый Лорри: а вы не могли бы мне помочь? :)

[Денис Загаевский]

DenKG: А обходы точно есть? Вы их сами написали? какого рода помощь нужна?

[Толстый Лорри]

DenKG: как только смогу понять, в чем у вас проблема. Покажите код что ли...

[DenKG]

Толстый Лорри: ну я, если честно, даже не очень понимаю, какой код вам дать, ибо я в целом не понимаю, как выполнить это задание. Вот код заполнения:

if (root != 0) {
		if (item > root->item)
		{
			root->right = insert(root->right, item);
			return root;
		}
		else
		{
			root->left = insert(root->left, item);
			return root;
		}
	}
	else {
		Tree *root = new Tree;
		root->item = item;
		root->left = NULL;
		root->right = NULL;
		return root;
	}

Обход сверху-вниз:

for (int i = level; i >= 0; i--)
		cout << root->item;
		preorder(root->left, level + 1);
		preorder(root->right, level + 1);

А вот как выполнить эти 5 заданий, я не понимаю :(

Answer 1

[AtomKrieg]

Или хотя бы дайте ссылку, где читать

Это std::map::iterator

Answer 2

[private_tm]

1)установка на корень дерева- корень это самый верхний елемент. Т.е. текущий елемент надо установить на самый верхний елемент.

Я раньше тоже не везжал. Но потом понял прост прочитай про структуру обычных деревя(двоичные к примеру).
Т.е. каждый елемент имеет два поделемента. + индексы как к ним обращаться и значения которыи там храняться.
Как кокретно ты реализуешь особо не важно. Это больше теоритичиская задача.

И так вобщем это струтура данных как обычный масив. Только индексы грубо говоря по хитрей и обход.