Генерация всех листьев из дерева - PullRequest
Новая
       25

Генерация всех листьев из дерева

0 голосов
/ 08 февраля 2019

Я пытаюсь сделать простой скрипт исследования дерева, который печатает все листья.Однако то, что я вижу напечатанным, не то, что я ожидаю.

В этом игрушечном примере каждый узел представляет строку и имеет 4 дочерних элементов, при этом добавляется A, B, C или D к родительской строке. 

E.g for max_depth = 2:

                        ""
     A            B            C            D
AA AB AC AD  BA BB BC BD  CA CB CC CD  DA DB DC DD

Мой код: 

void explore_tree(string sequence, int depth, int max_depth) {
    if (depth == max_depth) {
        cout << sequence << endl;
        return;
    }
    explore_tree(sequence.append("A"), depth+1, max_depth);
    explore_tree(sequence.append("B"), depth+1, max_depth);
    explore_tree(sequence.append("C"), depth+1, max_depth);
    explore_tree(sequence.append("D"), depth+1, max_depth);
}

explore_tree("", 0, 2);

Обычно, когда я достигаю max_depth, я печатаю последовательность.В противном случае я делаю рекурсию, добавляя A, B, C или D к текущей последовательности

. Я бы ожидал увидеть список листьев, но вместо этого я увидел бы несколько вещей, объединенных: 

AA
AAB
AABC
AABCD
ABA
ABAB
ABABC
ABABCD
ABCA
ABCAB
ABCABC
ABCABCD
ABCDA
ABCDAB
ABCDABC
ABCDABCD

AmЯ что-то пропустил?Я не могу понять, почему это не приводит к ожидаемому результату.

...