在二叉搜索树中插入节点时堆栈溢出

Question

我是 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");
}

感谢您的帮助。

Answer 1

在你的 insert()

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)，导致栈溢出，正确的操作是make current node移动到 root.left，然后递归调用 insert(value)。

而且你根本不需要节点 class，树 class 可以做所有的事情。

再次强调，这里不是帮助您调试的好地方，您需要自己学习如何调试:-)。

在二叉搜索树中插入节点时堆栈溢出

Stack Overflow when inserting a node in a Binary Search Tree

c++

binary-tree

binary-search-tree

data-structures