Если это не лаба, которую нужно было сдать вчера, то стоит начать с чего-то более простого (в противном случае вам к фрилансерам). Возможно что-то из этого вы уже делали, но из вашего вопроса кажется, что вы не знаете с чего начать. Задание сложное для начинающего, будьте готовы потратить на него несколько дней из новогодних праздников.
Структуры. Ключевое слово struct. Именно они будут элементами. Прочитайте про них.
Структуры данных на указателях. Дерево -- сложная структура. Начните с односвязного списка. Примеров куча в сети. Тут вам не обойтись без функций. А еще лучше написать класс LinkedList.
Итераторы. Когда написан список, попробуйте разобраться с итераторами. Написать итератор для списка не сложно, но тут уже нужно иметь минимальные представления о классах, методах, перегрузке операторов.
Если сложно, то можно обойтись без них, задача не сильно пострадает.
Деревья. После того как написан список, разобраться с деревьями будет проще. Забейте на "элемент данных void*", пусть у вас это будет то же что и в любом понравившемся примере из интернета. Тем более, в C++ стараются избегать void*.
Обход дерева. Итераторы предполагают, что вы сможете перебирать элементы дерева в некотором порядке. В основном используют 2 подхода: обход в глубину и обход в ширину. Первый несколько проще реализовывать с помощью рекурсии. Для второго может потребоваться структура данных очередь, которую будет полезно написать на основе односвязного списка.
Дерево поиска. Вас просят сделать так, чтобы меньшие элементы были ближе к корню дерева. Есть структура данных "куча"(обычно бинарная куча) , которая это обеспечивает. Но на практике чаще используют деревья поиска, которые тоже это гарантируют. Это достаточно непростая тема, к ней можно вернуться как закончите с остальным.
