Я пытаюсь преобразовать дерево в порядок списка. Вот код, который у меня есть.
#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.
Любая помощь приветствуется. Спасибо.
Вам нужно немного изменить логику, так как вы не возвращаете никакого значения. Изменяя оператор 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 сделано! Готово!