c++ - 二叉搜索树输出

Question

我在输出二叉搜索树时遇到问题。我必须构建树，然后将树中的所有 double 按顺序放入一个 vector 中，然后按顺序输出该 vector 。我遇到的问题是将其放入 vector 并输出。当我刚刚输出树时，一切都按预期进行。应该对 vector 进行排序，并且 std::vector* sort() 应该返回指向 vector 的指针。我遇到的问题是出现段错误，我不知道为什么。任何意见，将不胜感激。这是我的代码:

#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 的 vector 指向。

例如:

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

Set 是一个指向 std::vector<double> 的指针 .当你第一次声明它时，它只是堆栈上的一个内存值，带有一些未定义的值，它指向一些未定义的地方。因此，当您在下一行取消引用它时，BOOM，您会遇到段错误，因为您正在访问操作系统分配给您的进程的允许内存之外的内存。

其次，除非您必须使用指向 std::vector 的指针对于你的家庭作业，传递对 order() 中 vector 的引用，并返回来自 sort() 的 vector 拷贝...这将使您的生活更轻松，并避免许多不调用 delete 的代码用户造成内存泄漏在你从 sort() 返回给他们的指针上.

第三，你定义了order()作为递归函数......所以你不能在函数的每次迭代中定义你的 vector 并在其中放置一个值，否则你将为每个函数调用创建一个新 vector 。所以你需要在实际 sort() 中定义你的 vector 方法，然后将 vector 作为对 order() 的引用传递方法如下:

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

    return set;
}

最后，您需要重新定义 order()这样就可以对树进行有序递归遍历(与先序或后序遍历相比)。这意味着它将首先递归到最左边的 child ，然后以树的最右边的 child 结束，按顺序处理每个节点:

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