0

Имеется такой код двоичного дерева. При использовании его для сортировки сначала 1000, затем 3000, 5000, 5000 и 9000 элементов в какой-то момент (это случается примерно при каждом десятом запуске) выбрасывается исключение о переполнение стека. Конкретнее,

Unhandled exception at 0x0097A1A9 in Lab1.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x00602F94).

Это происходит всегда при освобождении памяти при удалении std::shared_ptr или в функциях декремента счетчика объектов shared_ptr. Что с этим можно сделать, чтобы не было переполнения?

#include <iostream>
#include <vector>
#include <memory>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;

// class representing a binary tree
class BinaryTree
{
protected:
    // binary tree node
    struct BinaryTreeNode
    {
        shared_ptr<BinaryTreeNode> left, right; // left and right subtrees
        int key{ 0 }; // key(node value)
    };

    shared_ptr<BinaryTreeNode> m_root; // root of a binary tree

    // recursive procedure of inserting a key
    // cur_node — the current node compared to the inserted node
    // node_to_insert — inserted node
    void insert_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const shared_ptr<BinaryTreeNode>& node_to_insert)
    {
        assert(cur_node != nullptr);
        // comparison
        bool insertIsLess = node_to_insert->key < cur_node->key;
        if (insertIsLess)
        {
            // inserting into left subtree
            if (cur_node->left == nullptr)
                cur_node->left = node_to_insert;// if current node has no left subtree
            else
                insert_recursive(cur_node->left, node_to_insert);// if current node has left subtree 
        }
        else
        {
            // inserting into right subtree
            if (cur_node->right == nullptr)
                cur_node->right = node_to_insert;// if current node has no right subtree
            else
                insert_recursive(cur_node->right, node_to_insert);// if current node has right subtree 
        }
    }

public:

    // procedure of inserting a new node with value = key
    void insert(int key)
    {
        shared_ptr<BinaryTreeNode> node_to_insert(new BinaryTreeNode);// creating a new node
        node_to_insert->key = key;//setting the value to created node

        if (m_root == nullptr)// if tree has no node
            m_root = node_to_insert;
        else
            insert_recursive(m_root, node_to_insert);
    }

    typedef function<void(int key)> Visitor;// type alias of function

protected:
    // recursive tree traversal procedure
    // cur_node - currently visited node
    void visit_recursive(const shared_ptr<BinaryTreeNode>& cur_node, const Visitor& visitor)
    {
        assert(cur_node != nullptr);// checking if invalid node was passed

        // visited left subtree
        if (cur_node->left != nullptr)
            visit_recursive(cur_node->left, visitor);

        // visited current element
        visitor(cur_node->key);

        // visited right subtree
        if (cur_node->right != nullptr)
            visit_recursive(cur_node->right, visitor);
    }

public:

    // procedure of applying to nodes passed function
    void visit(const Visitor& visitor)
    {
        if (m_root == nullptr)// if tree has no node
            return;
        visit_recursive(m_root, visitor);
    }
};

1 ответ 1

1

Написать деструктор для BinaryTree, который удалял бы каждый узел вручную, без рекурсии, в обычном цикле.

Чтобы обходить дерево без рекурсии потребуется "стек" - список, созданный в куче (std::vector, например), указателей на узлы.

Примерно так: (писал на коленке, не запускал)

struct Elem
{
    std::shared_ptr<BinaryTreeNode> *target = nullptr;
    int phase = 0;
};

std::vector<Elem> stack;
stack.emplace_back().target = &m_root;

while (!stack.empty())
{
    if (stack.back().phase == 0)
    {
        stack.back().phase = 1;
        if (auto &target = (*stack.back().target)->left)
            stack.push_back(&target);
    }
    else if (stack.back().phase == 1)
    {
        stack.back().phase = 2;
        if (auto &target = (*stack.back().target)->right)
            stack.push_back(&target);
    }
    else
    {
        *stack.back().target = nullptr;
        stack.pop_back();
    }

}
1
  • Хотя оп не предоставил минимальный воспроизводимый пример, мне сдается, что проблема прежде всего из-за несбалансированности дерева. Ну и неуместное использование shared_ptr и рекурсии тоже играет роль. А для обхода без рекурсии можно держать указатель на родителя. Хотя для сбалансированного дерева это бы не потребовалось. 23 мар 2021 в 21:42

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.