Инициализировать дерево по порядку?
Я использую список инициализаторов и помощника для создания дерева по порядку. например {1,2,3,4,5,6,7}, если я напечатаю дерево в порядке обхода, это также даст 1,2,3,4,5,6,7.
tree::tree(const initializer_list<int>& I) {
const int* p1 = I.begin();
root = nullptr;
IL_helper(I, p1, root);
}
void tree::IL_helper(const initializer_list<int>& I, const int*& p1, node* & p2) {
if (p1 == I.end()) {
return;
}
p2 = new node(*p1);
++p1;
IL_helper(I, p1, p2->Lchild);
IL_helper(I, p1, p2->Rchild);
}
как сформировать дерево с неупорядоченным обходом с рекурсией. В моем коде я понимаю, что у него будет только Lchild. дерево t{1,2,3,4,5,6,7} ; cout << t.inOrderT (t.root); вывод: 1,2,3,4,5,6,7
Ответы 1
p2 = new node(*p1);
перезаписывает p2, но его тип — просто node*, так что это присваивание не влияет ни на что вне функции. Просто измените параметр на node* &p2.
Кроме того, я вижу вторую проблему - в вашем примере нет разделения входного списка пополам - поэтому узлы дерева, которое вы построите, всегда будут иметь только набор Lchild. Потому что в рекурсивной цепочке IL_helper(I, p1, p2->Lchild); весь список будет использован, и для вызова Rchild ничего не останется. Технически это не ошибка, если это предполагаемое поведение (например, после этого дерево может быть перебалансировано), но так ли это?
Рекурсия и деревья плохо сочетаются. Основная причина рекурсии — сохранить некоторую «память» путем кодирования важного состояния в стеке вызовов, а не в пользовательских переменных состояния. Но это именно то, что вам нужно изменить, чтобы решить эту проблему. Таким образом, рекурсия просто не будет вашим решением. В основном вы должны заполнить все листья одной глубины одновременно....
Рекурсия и деревья очень хорошо сочетаются друг с другом — просто измените алгоритм так, чтобы он сначала читал всю последовательность, разделяя ее как нижняя половина — средняя точка — верхняя половина. А затем сохраните среднюю точку для родителя и отдайте первую половину Lребенку, а вторую половину Rребенку, а затем применяйте это рекурсивно, пока у вас не останется ничего, что можно было бы дать детям.
да после смены p2 я понимаю что у меня только Lchild. Есть ли способ исправить это?