0

我正在尝试将树转换为列表中的顺序。这是我到目前为止的代码。

 #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 方法中打印出元素。

任何帮助表示赞赏。谢谢你。

4

1 回答 1

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 完成!
完毕!
于 2014-05-05T05:07:42.880 回答