пытаясь преобразовать дерево в список в переполнении стека

Я пытаюсь преобразовать дерево в порядок списка. Вот код, который у меня есть.

 #include <iostream>
using std::cout;
using std::endl;
using std::ostream;

class Tree{
public:
Tree(): root(nullptr), list(nullptr){
}
~Tree(){
delete_postorder( root); root = nullptr;
delete list;             list = nullptr;
}
void add(int d){
if (root==nullptr)
root = new Node(d);
else
add_inorder(root, d);
}
friend ostream& operator <<( ostream& o, Tree& t){
o << "Inorder traversal:   ";
t.print_inorder(o, t.root);
o << endl;
return o;
}
void convert_to_list( ostream& o ){
o << "Converting to a list ... ";
delete list; list = nullptr;
list = list_inorder( root );
/*
* Print list
*/
for (LNode* p = list; p != nullptr; p=p->next)
o << p->data << " ";
o << " done!" << endl;
}
private:
class Node{
public:
Node(int d): data(d), left(nullptr), right(nullptr) {
}
~Node() {
delete left;  left = nullptr;
delete right; right = nullptr;
}
int data;
Node* left;
Node* right;
};
Node* root;

void add_inorder(Node* t, int d){
if (d <= t->data)
if (t->left == nullptr)
t->left = new Node(d);
else add_inorder(t->left, d);
else
if (t->right == nullptr)
t->right = new Node(d);
else add_inorder(t->right, d);
}

void print_inorder( ostream& o, Node*t ){
if (t==nullptr)
return;
print_inorder(o, t->left);
o << t->data << " ";
print_inorder(o, t->right);
}
void delete_postorder(Node* t){
if (t== nullptr)
return;
delete_postorder( t->left );
t->left = nullptr;
delete_postorder( t->right );
t->right = nullptr;
delete t; t=nullptr;
}
class LNode{
public:
int data;
LNode* next;
LNode(int d): data(d), next(nullptr){
}
~LNode(){
delete next; next = nullptr;
}
void append(int d){
LNode* p = this;
for (; p->next != nullptr; p=p->next)
;
p->next = new LNode( d );
}
};

LNode* list;
LNode* list_inorder(Node* t){
if (t==nullptr)
return nullptr;
LNode* left = list_inorder( t-> left );
LNode* right = list_inorder( t->right );
if (left == nullptr)
return right;
if (right == nullptr)
return left;
/*
* Find last node in "left" and append right to it.
*/
LNode* p = left;
for (; p->next != nullptr; p=p->next) ;
p->next = right;
return left;
}

/*    void list_inorder(Node* t){
if (t==nullptr)
return;
list_inorder( t-> left );
if (list==nullptr)
list = new LNode( t->data );
else
list->append(t->data);
list_inorder( t->right );
}
*/
};int main(){
Tree t;
int data[] = { -2, 3, 10, -21, 35, 3, 85, -2, 100};

for (int i=0; i<9; i++)
t.add( data[i] );p

cout << t << endl;

t.convert_to_list( cout );

cout << "Done!";
}

Прокомментированный list_inorder — рекурсивный способ преобразовать дерево в порядке в список, и это работает. Другой метод list_inorder (без комментариев) — это тот, над которым я работаю. По какой-то причине другой list_inorder не работает. Я пытаюсь вернуть указатель, указывающий на первый узел в преобразованном списке. Итак, я могу запустить список и распечатать элементы в методе convert_to_list.

Любая помощь приветствуется. Спасибо.

0

Решение

Вам нужно немного изменить логику, так как вы не возвращаете никакого значения. Изменяя оператор if, как показано ниже, это позволяет рекурсивным вызовам правильно завершаться. (Кроме того, измените способ вызова в функции преобразования list_inorder( root );)


void list_inorder(Node* t){
if (t!=nullptr)
{
list_inorder( t->left );
if (list == nullptr)
list = new LNode( t->data );
else
list->append(t->data);
list_inorder( t->right );
}
}
Обход заказа: -21 -2 -2 3 3 10 35 85 100
Преобразование в список ... -21 -2 -2 3 3 10 35 85 100 сделано!
Готово!
0

Другие решения


По вопросам рекламы [email protected]