バイナリツリーの挿入方法によってスタックオーバーフローが発生する

Question

問題が発生しました。

C++での挿入方法に疑問があります。スタックオーバーフローが発生します。ダンプスタックトレース：G ++のWindows上

グラム++ -Wall -O2 -o Tree.cppツリー

出力

0 [不明（0x2B70）]ツリー10496 cygwin_exception :: open_stackdumpfileでコンパイル

コード

# 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

YをTree.exe.stackdumpしますそれが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; 

} 

Answer 2

The problem in your function is, you are trying to access null memory. 
Please check my comments here 

/* You are checking for node == null, which is correct. */ 
if(node == NULL) 
    { 
     node = new Node; 
     node->val = val; 
     node->right = node->left = NULL; 
    } 


    /* Consider what will happen when node is null, you are still trying to access null memory. You need to put else if here to avoid control to fall into this condition if node is null. */ 
    if(node->val > val) // add "else" here 
     node->left = Insert(node->left, val); 
    else 
     node->right = Insert(node->right, val);