Переполнение стека при вставке узла в дерево двоичного поиска - PullRequest
Новая
       38

Переполнение стека при вставке узла в дерево двоичного поиска

0 голосов
/ 06 июля 2019

Я новичок в программировании на C ++, но пытаюсь создать дерево двоичного поиска.

Программа, похоже, прекрасно компилируется, но выдает ошибку: 

 Unhandled exception at 0x009229B7 in Lab001_CS3.exe: 0xC00000FD: Stack 
 overflow (parameters: 0x00000001, 0x00AD2FBC).

когда я пытаюсь запустить его. Ошибка возникает в этой строке кода: 

void insert(int value) {
   ...
}

Я не уверен, что я делаю неправильно, и я никогда не получал эту ошибку раньше.

Вот код: 

#include <iostream>

using namespace std;

//create a node struct
struct node {

    //member variables
    int key;
    node* left;
    node* right;

    //default constructor
    node() {
        key = 0;
        left = NULL;
        right = NULL;
        cout << "a new node is created" << endl;
    }

    //constructor so can create a node in one line
    node(int k) {
        key = k;
        left = NULL;
        right = NULL;
        cout << "a new node is created" << endl;
    }


};

class Tree {
public:
    //root node
    node root;

    //default constructor 
    Tree() {
        root.key = 0;
        root.left = NULL;
        root.right = NULL;


    }

    //constructor to create the root node
    Tree(int data) {

        //set the data to the key
        //set the right and left pointers to null
        root.key = data;
        root.left = NULL;
        root.right = NULL;
    }

    //print the root node
    void printRootNode() {
        cout << "Root Node - Key: " << root.key << endl;
    }

    //insert functions
    void insert(int value) {

        /* If the newNode's key is less than the root key, traverse left 
    */
    if (value < root.key) {

        /* if the left node is NULL */
        if (root.left == NULL) {
            root.left = new node(value);
            cout << "assigned left" << endl;
        }
        else {

            /* if the left node is important */
            insert(value);
            cout << "recurse" << endl;
        }

    }

    if (value > root.key) {

        /* if the right node is NULL */
        if (root.right == NULL) {
            root.right = new node(value);
            cout << "assigned right" << endl;
        }
        else {
            /* if the right node is important */
            insert(value);
            cout << "recurse" << endl;
        }
    }
}


};

//print inorder
void inorder(node* rt) {
//base
if (rt == NULL) {
    return;
}

inorder(rt->left);
cout << " " << rt->key << endl;
inorder(rt->right);
}

int main() {

//create a tree for a root node
Tree t(16);
t.printRootNode();

//create  newNode
node n1(20);
node n2(31);

//insert the new nodes
t.insert(20);
t.insert(31);

//keep the window from closing
system("pause");
}

Спасибо за любую помощь.

1 Ответ

1 голос
/ 06 июля 2019

В вашей вставке () 

if (value < root.key) {

        /* if the left node is NULL */
        if (root.left == NULL) {
            root.left = new node(value);
            cout << "assigned left" << endl;
        }
        else {

            /* if the left node is important */
            insert(value);
            cout << "recurse" << endl;
        }

    }

давайте возьмем этот фрагмент кода в качестве примера, если root.left! = NULL, код введет блок else и рекурсивно вызовет insert (value) навсегда, что вызываетпереполнение стека, правильная операция - переместить текущий узел в root.left, а затем рекурсивно вызвать insert (value).

также вам не нужен класс узла вообще, класс дерева может сделать все.

Опять же, здесь не место для отладки, вам нужно научиться делать это самостоятельно: -).

...