Обход на основе векторного двоичного дерева
У меня есть векторное двоичное дерево, и мне нужно применить функцию к каждому значению в дереве, используя различные методы обхода. Обход предзаказа было очень легко реализовать с помощью рекурсивной функции, но у меня возникли проблемы с тем же путем обхода по порядку и по порядку. Если бы кто-нибудь мог помочь, это было бы здорово!
Некоторая дополнительная информация, которую я должен был включить:
Я использую вектор узлов, каждый из которых содержит логическую переменную, указывающую, заполнен ли этот узел, и переменную данных с шаблонами. Каждый узел хранится с индексом «i», в то время как его левый дочерний элемент имеет индекс «2i + 1», а правый дочерний элемент — «2i + 2».
Чтобы применить предварительный обход к списку, я сначала обработал данные, хранящиеся в индексе 0, а затем вызвал эту рекурсивную функцию.
template <typename Item, typename Key>
template <typename Function>
void BST<Item,Key>::preTraverse(int n, Function f) {
if(tree[n].occupied == false) return;
else {
f(tree[n].data);
preTraverse(2*i+1,f);
preTraverse(2*i+2,f);
}
}
дважды начиная с индексов 1 & 2 как мой параметр «n».
Решение
Предполагая, что ваше дерево является максимально заполненным лево-доминантным представлением, тогда любая заданная точка в вашем массиве в позиции i будет иметь детей на должностях 2*i+1 а также 2*i+2, Тривиальная прогулка:
Node Children
===== ===========
ar[0]: ar[1], ar[2]
ar[1]: ar[3], ar[4]
ar[2]: ar[5], ar[6]
ar[3]: ar[7], ar[8]
ar[4]: ar[9], ar[10] etc...
Учитывая это определение, предварительный заказ, почтовый заказ и порядок могут быть выполнены с помощью простой переадресации индекса и некоторых проверок вашего «занятого» флага. Следующие шаблоны принимают тип T является структурным типом, который имеет «занятый» член.
template<typename T>
void preorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
visit(ar[i]);
preorder(ar, 2*i+1, count, visit);
preorder(ar, 2*(i+1), count, visit);
}
template<typename T>
void inorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
inorder(ar, 2*i+1, count, visit);
visit(ar[i]);
inorder(ar, 2*(i+1), count, visit);
}
template<typename T>
void postorder(const T ar[], size_t i, size_t count, void (&visit)(const T&))
{
if (i>=count || !ar[i].occupied)
return;
postorder(ar, 2*i+1, count, visit);
postorder(ar, 2*(i+1), count, visit);
visit(ar[i]);
}
Другие решения
Предварительный заказ:
do something with the value
f(go to the left)
f(go to the right)
с целью:
f(go to the left)
do something with the value
f(go to the right)
postorder:
f(go to the left)
f(go to the right)
do something with the value