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

Question

我一直在尝试创建一个以递归方式获取二叉树高度的函数.

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

Answer 1

在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());
}