Binary Search Tree Output

I am having trouble outputting a binary search tree. I have to build the tree, and then place all the doubles from the tree in order into a vector, and then output that vector in order. The problem I am having is getting it into the vector and outputting it. When I just output the tree, everything works as it is supposed to. The vector is supposed to get sorted and the std::vector* sort() is supposed to return a pointer to a vector. The problem I am having is that I get a segmentation fault, and I don't know why. Any advice would be appreciated. Here is my code:

#include <vector>

struct ordered_set {
private:
    class node {
    public:
        double val;
        node* left;
        node* right;

        node(double v, node* l, node* r): val(v), left(l), right(r) { }
    };

    node* root;
    int size;

public:
    ordered_set();
    void insert(double x);
    std::vector<double>* sort();
    std::vector<double>* order(node*);
};

#include <vector>
#include <iostream>

#include "ordered_set.hpp"

ordered_set::ordered_set()
{
    root = 0;
    size = 0;
}

void ordered_set::insert(double x)
{
    node* data = new node(x, 0, 0);
    node* parent;
    parent = 0;

    if(root == 0)
        root = data;
    else
    {
        node* curr = root;
        while (curr)
        {
            parent = curr;
            if(data->val > curr->val)
                curr = curr->right;
            else
 开发者_如何学C               curr = curr->left;
        }
        if(data->val < parent->val)
            parent->left = data;
        else
            parent->right = data;
    }
    ++size;
}

std::vector<double>* ordered_set::sort()
{
    node* ndptr = root;
    return order(ndptr);
}

std::vector<double>* ordered_set::order(node* top)
{
    node* curr = top;
    std::vector<double>* set;
    std::vector<double>::iterator it = set->begin();

    if(curr != 0)
    {
        order(curr->left);
        set->insert(it, curr->val);
        ++it;
        order(curr->right);
    }
    else return set;
}

There are a couple problems here.

First, you never define the vector that set is pointing to.

For instance:

std::vector<double>* set;
std::vector<double>::iterator it = set->begin();

Set is a pointer to a std::vector<double>. When you first declare it, it's just a memory value on the stack with some undefined value and it's pointing to some undefined place. Therefore when you dereference it on the next line, BOOM, you get a segmentation fault since you're accessing memory outside the allowed memory the OS has allotted to your process.

Secondly, unless you must use a pointer to a std::vector for you homework assignment, pass around a reference to the vector in order(), and return a copy of the vector from sort() ... it will make your life a lot easier as well as avoid memory leaks from the user of your code who many not call delete on the pointer you return to them from sort().

Third, you've defined order() as a recursive function ... so you can't define your vector in each iteration of the function and place a value in it, otherwise you're going to be creating a new vector for every function call. So you need to define your vector in the actual sort() method, and then pass the vector as a reference to your order() method like the following:

std::vector<double> ordered_set::sort()
{
    node* ndptr = root;
    std::vector<double> set;
    order(ndptr, set);

    return set;
}

Lastly, you will need to re-define order() so that does an in-order recursive traversal of your tree (compared to a pre-order or post-order traversal). This means that it will recursively go to the left-most child first and end with the right-most child of the tree, processing each node in-order:

void ordered_set::order(node* top, std::vector<double>& set)
{
    node* curr = top;

    if(curr == 0)
    {
        return;
    }

    //go to the left-most child
    order(curr->left, set);

    //at this point we've now processed all children to the 
    //left of this node ... so we can now process this node itself
    set.push_back(curr->val);

    //now process all children to the right of this node
    order(curr->right, set);

    return;
}