Обход двоичного дерева на основе вектора

У меня есть двоичное дерево на основе векторов, и мне нужно применить функцию к каждому значению в дереве, используя различные методы обхода. Предварительный обход было очень легко реализовать с помощью рекурсивной функции, но у меня возникли проблемы с тем, чтобы сделать то же самое с обходами без порядка и после порядка. Если бы кто-нибудь мог помочь, это было бы здорово!

Некоторая дополнительная информация, которую я должен был включить: я использую вектор узлов, каждый узел содержит логическую переменную, указывающую, заполнен ли этот узел, и переменную шаблонных данных. Каждый узел хранится с индексом «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".


c++ vector traversal binary-tree preorder
person Brandon Bosso    schedule 26.11.2012    source источник
comment
Не могли бы вы опубликовать код обхода, который вам удалось получить правильно? Это поможет нам лучше понять, как вы складывали дерево в векторе.   -  person Sergey Kalinichenko    schedule 26.11.2012
comment
Является ли векторное представление максимально заполненным слева направо определением? (т.е. дети [i] находятся в [2i + 1] и [2i + 2]?   -  person WhozCraig    schedule 26.11.2012
comment
пройти предварительный заказ было легко ... но у меня [возникли проблемы] с предварительным заказом ... обходом? Возможно, вы не сказали того, что хотели сказать.   -  person Robᵩ    schedule 26.11.2012
comment
Я добавил код и дополнительные сведения о векторе в редактирование вопроса. Я также хотел сказать inorder и postorder, а не preorder и postorder.   -  person Brandon Bosso    schedule 26.11.2012

Ответы (2)


arrow_upward
2
arrow_downward

Предполагая, что ваше дерево представляет собой максимально заполненное левое доминирующее представление, тогда любая заданная точка в вашем массиве в позиции 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]);
}
person WhozCraig    schedule 26.11.2012
comment
ваша функция постзаказчика неверна, она должна быть postorder(ar, 2*i+1, visit);, postorder(ar, 2*i+2, visit);, а затем visit(ar[i]); - person hinafu; 26.11.2012

arrow_upward
3
arrow_downward

предзаказ:

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)

почтовый заказ:

f(go to the left)
f(go to the right)
do something with the value
person hinafu    schedule 26.11.2012