二叉树插入法导致栈溢出

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;

}

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);

二叉树插入法导致栈溢出

Binary tree insertion method causes stack overflow

c++

tree

struct

问题

在 Windows

输出

代码