c++ - 无法找到 BST 的高度

Question

使用递归我试图找到树的高度，但输出似乎错误。有什么错误吗？

#include <iostream>

struct node{
    int data;
    node* left, *right;
};

node* getNode(int item){
    node* new_node = new node;
    new_node->data = item;
    new_node->left = new_node->right = nullptr;
    return new_node;
}

node* insert(node* root, int item){
    if(root == nullptr){
        root = getNode(item);
    }
    else if(item < root->data){
        root->left = insert(root->left, item);
    }
    else if(item > root->data){
        root->right = insert(root->right, item);
    }
    return root;
}

int height(node* root){
    if(root == nullptr){
        return 0;
    }
    else{
        return 1+std::max(height(root->left), height(root->right));
    }
}

int main()
{
    node* root;
    root = insert(root, 40);
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 80);
    root = insert(root, 30);
    root = insert(root, 1);
    std::cout << "\nheight of Tree: " << height(root);

    return 0;
}

树的高度应该为 3（如果我没记错的话），但它显示为 4。
我正在使用带有 Code::Blocks IDE 的 GNU GCC 编译器，它在那里工作，
但是当我在 Programiz c++ 在线编译器上运行相同的代码时，它显示分段错误所以也许我做错了什么。
问候

标签： c++segmentation-faultbinary-search-tree

Answer 1

Right away, this code:

int main()
{
    node* root;  // <-- uninitialized
    root = insert(root, 40); // <-- Using an uninitialized pointer
    //...
}

is faulty.

The root is an uninitialized pointer, and passing that uninitialized pointer to insert will invoke undefined behavior.

The probable fix is to simply do:

node* root = nullptr;