c++ - 二叉树的示例实现不适用于大量值

Question

我最近尝试实现一个二叉树，它似乎适用于少于 1000 个值，但在那之后最终它给我堆栈溢出错误

#include<iostream>
#include<math.h>

using namespace std;
struct Node{
    long long int val;
    Node *left;
    Node *right;
};
struct BinaryTree{
    Node *head  = (Node*) malloc(sizeof(Node));
    bool headSet = false;
    Node* findLast(Node *asgn,int val){
        if (val > asgn->val){
            if (asgn->right != NULL)
                asgn  = findLast(asgn->right, val);
            else
                return asgn;
        }
        else{
            if (asgn->left != NULL)
                asgn = findLast(asgn->left, val);
            else
                return asgn;
        }
        return asgn;
    }
    void insert(long long int vals){
        if (headSet){
            Node *asgn = (Node*) malloc(sizeof(Node));
            asgn = findLast(head,vals);
            Node *fix = (Node*)malloc(sizeof(Node));
            fix->val = vals;
            fix->left = NULL;
            fix->right = NULL;
            if (vals > asgn->val){
                asgn->right = fix;
                asgn->left = NULL;
            }
            else{
                asgn->right = NULL;
                asgn->left = fix;
            }
        }
        else{
            head->val = vals;
            head->right = NULL;
            head->left = NULL;
            headSet = true;
        }
    }
};
int main(){
    BinaryTree a;
    for (long long int i = 0; i < 100;i++)
    a.insert(i);

    return 0;
}

例如:- 如果我改变

for (long long int i = 0; i < 100;i++)
    a.insert(i);

到

for (long long int i = 0; i < 10000;i++)
    a.insert(i);

它给我错误。我似乎无法理解为什么会发生这种情况，堆栈在哪里溢出？

Answer 1

您的堆栈溢出来自您的 findLast 方法，一旦二叉树变得太大，递归就会变得太多并在某一点溢出调用堆栈。您应该通过将有关搜索的信息存储在某种结构中并动态分配它来将其转换为非递归方法，这样您的堆栈就不会填满。

P.S 在 C++ 中使用 new 而不是 malloc 和 delete 来清除分配的内存，你目前正在泄漏内存。