二進制搜索樹輸出

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