Вставьте Node рекурсивно в BTree с использованием C ++ - PullRequest
Новая
       25

Вставьте Node рекурсивно в BTree с использованием C ++

0 голосов
/ 22 октября 2019

Создание класса шаблона для рекурсивной вставки данных в BTree. Код дает ошибку сегментации, я включил функции получения и установки в заголовочный файл, не уверен, где он идет не так, пожалуйста, помогите подсказать, если я уберу проверку на Node->right==NULL, тогда код работает нормально, но в этомЯ не могу добавить рекурсию. 

       template <class S>
        class STree
        {
            public:
              // Constructors
                    STree()                         
                    {root = NULL; size=0;}
                    STree(S part)                       
                    {root = new BTNode<S>(part); size=0;}

             // Destructor
                  ~STree(){};
            void insert(S part)
            {
                if (root == NULL)
                {
                    root = new BTNode<S>(part);
                    cout<< "\n from root " << root->get_data();
                }
                else
                {add(root,part);}
                size++;
            }   

            void add(BTNode<S>* node, S part)
            {
                S part2 = node->get_data();
                cout << "part "<< part;
                cout<< "part2 "<< node->get_data();
                if( part == part2)
                    {node->set_data(part);}
                else if (part > part2)
                {
                    if (node->get_right()== NULL)   //if I remove this check the segmentation error goes away
                    {node->set_right(new BTNode<S>(part)); cout<< "from right "<< node->right->get_data();}
                    else
                    {add(node->get_right(),part);}  //If I remove the if statement above the recursion won't work
                }
                else
                {
                    if (node->get_left()==NULL)
                    { node->set_left(new BTNode<S>(part));}
                    else
                    {add(node->get_left(),part);}
                }
            }
            private:
                BTNode<S>* root;
                BTNode<S>* current;
                int size;
        };
        #endif

        int main()
        {
            STree<int> trees;
            trees.insert(10);
            trees.insert(20);
            trees.insert(30);
            trees.insert(40);

            return 0;
        }

1 Ответ

0 голосов
/ 22 октября 2019

BS part2 = node->get_data() будет обращаться к nullptr каждый раз, когда вы вставляете. При реализации рекурсии всегда сначала позаботьтесь о базовом сценарии. 

void add(BTNode<BS>* node, BS part)
{
    if (part < node->get_data() && node->get_left() == nullptr)
        node->set_left(new BTNode<BS>(part));
    else if (part > node->get_data() && node->get_right() == nullptr)
        node->set_right(new BTNode<BS>(part));

    if (node->get_data() == part)
        return;
    else
    {
        if (part < node->get_data())
            add(node->get_left(), part);
        else
            add(node->get_right(), part);
    }
}
...