二进制搜索树输出

Question

我无法输出二叉搜索树。我必须构建树，然后将树中的所有双精度元素按顺序放入一个向量中，然后按顺序输出该向量。我遇到的问题是将其导入矢量并输出它。当我刚刚输出树时，一切都按原样运行。该向量应该被排序，并且std :: vector * sort（）应该返回一个指向向量的指针。我遇到的问题是我遇到了分段错误，我不知道为什么。任何意见，将不胜感激。这是我的代码：

#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 
       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; 
} 

Answer 1

这里有几个问题。

首先，您从不定义set指向的矢量。

例如：

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

是一家集指针到std::vector<double>。当你第一次声明它的时候，它只是一个栈上的一个未定义的值，它指向一个未定义的地方。因此，当您在下一行BOOL上解除引用时，由于您正在访问操作系统分配给您的进程的允许内存之外的内存，因此会出现分段错误。

其次，除非你必须使用指针std::vector为你的家庭作业，绕过在order()一个参考向量，并从sort()返回载体的拷贝...这将让您的生活很容易，也可以避免代码的用户泄漏内存，许多人在您从sort()返回给他们的指针上不呼叫delete。

第三，您已将order()定义为递归函数...因此您无法在函数的每次迭代中定义您的向量，并在其中放置一个值，否则您将创建一个新向量为每个函数调用。所以，你需要确定你的载体在实际sort()方法，然后将向量作为参考传递给您的order()方法如下所示：

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

    return set; 
} 

最后，您将需要重新定义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; 
}