Как изменить этот древовидный код для повторения упорядоченным способом? - PullRequest
Новая
       13

Как изменить этот древовидный код для повторения упорядоченным способом?

0 голосов
/ 25 апреля 2011

Этот фрагмент кода перебирает дерево объектов TreeNode, где у каждого объекта могут быть дочерние элементы (из ответа на этот вопрос: Альтернатива рекурсии для огромных древовидных структур для iPhone? ). 

-(void)iterateOverTree:(TreeNode *)node
{
    NSMutableArray * elements = [NSMutableArray array];
    [elements addObject:node];

    while([elements count])
    {
        TreeNode * current = [elements objectAtIndex:0];
        [self doStuffWithNode:current];
        for(TreeNode * child in current.children)
        {
            [elements addObject:child];
        }

        [elements removeObjectAtIndex:0];
    }
}

Проблема в том, что этот код не проходит по дереву упорядоченным образом.

т.е. У меня есть это: А владеет B, J B владеет C владеет D владеет E J владеет K владеет L владеет M (примечание: «владеет» означает «имеет ребенка». У A есть два ребенка, а у остальных - один или нет)

Вот как обходится дерево: A, B, J, C, K, D, L, ...

Но я хочу: A, B, C, D, E, J, K, L, M, ...

упорядоченным образом, как это происходит с рекурсией.

Как я могу изменить это так, чтобы оно проходило по упорядоченному дереву, как в примере выше?

1 Ответ

1 голос
/ 25 апреля 2011

Вы хотите поиск в глубину .В настоящее время вы выполняете поиск в ширину .

Я не знаю Objective-C, но похоже, что вы используете NSMutableArray в качестве очереди .Используйте его в качестве стека для нерекурсивного поиска в глубину.

...