c++ - 递归获取二叉搜索树的高度

<分区>

我一直在尝试制作一个函数以递归方式获取二叉树的高度。

int BSNode::getHeight() const //Returns the height of the tree.
{
    if (this->_left == nullptr && this->_right == nullptr)
    {
        return 0;
    }
    else
    {
        return std::max(this->_left->getHeight(), this->_right->getHeight()) + 1;
    }
}

我调试了我的代码，由于某种原因，我在“if condition”行遇到了访问冲突错误。我不明白为什么我仍然收到此错误。我想它的发生是因为我的左边或右边之一为空，但我看不到其他方法。这是我向树中插入节点的函数:

void BSNode::insert(string value) //Inserts node to the tree.
{
    if (value > this->_data)
    {
        if (this->_right != NULL)
        {
            this->_right->insert(value);
        }
        else
        {
            this->_right = new BSNode(value);
        }
    }
    else if (value < this->_data)
    {
        if (this->_left != NULL)
        {
            this->_left->insert(value);
        }
        else
        {
            this->_left = new BSNode(value);
        }
    }
}

这是我构建的类:

class BSNode
{
    private:
        string _data;
        BSNode* _left;
        BSNode* _right;
}

最佳答案

此 if 语句中条件的否定

if (this->_left == nullptr && this->_right == nullptr)

是

else if ( not ( this->_left == nullptr && this->_right == nullptr) )

这又等同于

else if ( this->_left != nullptr || this->_right != nullptr )

但是在函数中忽略了 this->_left 或 this->_right 可以等于 nullptr 的事实。

    return std::max(this->_left->getHeight(), this->_right->getHeight()) + 1;

也不清楚为什么高度有符号类型 int 而不是一些无符号类型，例如 size_t。

我假设树的头部总是不等于nullptr。否则，您应该将该函数重写为具有一个参数的静态成员函数:指向头节点的指针。

函数如下所示

size_t BSNode::getHeight() const //Returns the height of the tree.
{
        return  1 + std::max(
                this->_left  == nullptr ? 0 : this->_left->getHeight(), 
                this->_right == nullptr ? 0 : this->_right->getHeight());
}

关于c++ - 递归获取二叉搜索树的高度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47441009/

上一篇：C++ - map 包含太多元素

下一篇：c++ - 如何将 PWSTR 转换为 QString 以显示在列表框中

相关文章：

c++ - 从左和右对数组求和时平衡数组索引

python - 无需递归访问嵌套列表和字典中的所有元素

parsing - 左递归语法中先发现后跟随的混淆

java - 二叉搜索树遍历方法，依次为toString

c++ - C++中的二叉树中序遍历

c++ - 如果我的 CPU 负载表明不是这样，我应该启动多个线程吗？

c++ - C++ 类对象的最佳容器

C++:reinterpret_cast 是这些场景中的最佳选择吗？

c++ - 为什么要这样调用宏？

javascript - 尾递归和斐波那契