пытаюсь преобразовать дерево в список в С++

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

 #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.

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


person Joe Li    schedule 02.05.2014    source источник
comment
Требуется ли, чтобы вы реализовали свой собственный список вместо использования, например. std::list?   -  person Some programmer dude    schedule 02.05.2014
comment
У Node есть left и right дочерние элементы. Откуда вы взяли next?   -  person Rakib    schedule 02.05.2014
comment
это требование, чтобы я не мог использовать список из стандартной библиотеки   -  person Joe Li    schedule 02.05.2014
comment
какой узел вы имеете в виду. Все объекты узла имеют только левый и правый. Тот, у кого следующий, - это объект LNode   -  person Joe Li    schedule 02.05.2014
comment
LNode используется для списка. Узел используется для дерева — все узлы дерева.   -  person Joe Li    schedule 02.05.2014
comment
Пробовали ли вы создать маленькое дерево, а затем построчно выполнять код в отладчике?   -  person Some programmer dude    schedule 02.05.2014


Ответы (1)


Вам нужно немного изменить логику, так как вы не возвращаете никакого значения. Изменяя оператор 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 );
    }
}
Inorder traversal:   -21 -2 -2 3 3 10 35 85 100 
Converting to a list ... -21 -2 -2 3 3 10 35 85 100  done!
Done!
person Rich    schedule 05.05.2014