无法找到 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。
我正在使用 GNU GCC 编译器 Code::Blocks IDE 它在那里工作，
但是当我在 Programiz c++ 在线编译器上运行相同的代码时，它显示 分段错误 所以也许我做错了什么。
问候

Answer 1

马上，这个代码：

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

有问题。

root 是一个未初始化的指针，将该未初始化的指针传递给 insert 将调用未定义的行为。

可能的解决方法是：

node* root = nullptr;

Answer 2

您的代码返回 4，因为您计算的是从根向下的最长路径上的节点的数量，而不是 边的数量。例如，请注意，您正在考虑 one-node 树的高度为 1，而通常认为它的高度为 0。

有一个简单的解决方法，那就是改变你的基本情况。看起来很奇怪，惯例是将空树视为高度为 -1。适当地改变你的基本情况并观察会发生什么。你能解释为什么这样做吗？

（另外，正如另一个答案所指出的，您的代码使用未初始化的指针，它可以从字面上破坏时空结构并将我们所有人传送到无限危险的维度。将该指针初始化为 nullptr 应该解决这个问题。专业提示：运行您在 valgrind 下的代码可以在 real-time 中看到这些错误！）

无法找到 BST 的高度

Unable to find height of BST

c++

segmentation-fault

binary-search-tree