c++ - 二叉树插入法导致栈溢出

Question

问题

我对我在 C++ 中的插入方法有一些疑问，它会导致堆栈溢出。

在 Windows 上使用 g++ 编译

g++ -Wall -O2 Tree.cpp -o 树

输出

0 [未知 (0x2B70)] 树 10496 cygwin_exception::open_stackdumpfile:将堆栈跟踪转储到 Tree.exe.stackdump

代码

# include < iostream >

using namespace std;

struct Node{

    int val;
    Node *left, *right;

};

Node* Insert(Node *node, int val)
{

    if(node == NULL)
    {
        node = new Node;
        node->val = val;
        node->right = node->left = NULL;
    }   

if(node->val > val)
    node->left = Insert(node->left, val);
else
    node->right = Insert(node->right, val);

return node;

}

int main()
{

Node *root = NULL; // New tree

root = Insert(root, 5);
root = Insert(root, 19);
root = Insert(root, 1);
root = Insert(root, 32);
return 0;
}

Answer 1

当递归到达 NULL 时，您必须停止递归。

试试这个:

Node* Insert(Node *node, int val)
{

    if(node == NULL)
    {
        node = new Node;
        node->val = val;
        node->right = node->left = NULL;
    }

    else if(node->val > val) // add "else" here
        node->left = Insert(node->left, val);
    else
        node->right = Insert(node->right, val);

    return node;

}