为了计算二叉树height(left)+height(right)+1的高度,将不存在的节点的高度定义为-1。因此,如果left或right为null,则该公式将有效而无需明确指定这些情况。
我在C ++中实现了这个想法,并确保如果,成员函数将不会访问成员变量this == nullptr。我的实现成功并且有效(至少在我的Linux机器上)。
我想找出这种方法可能带来的实际弊端,以及该标准是否规定了任何其他方面。所以,这就是我的问题。
#include <algorithm>
#include <iostream>
struct Node {
// default values of the child nodes are NULL
Node *left = nullptr;
Node *right = nullptr;
// store some value
int v;
int get_height() const __attribute__ ((optimize(0))) {
if (this == nullptr)
return -1;
return std::max(left->get_height(), right->get_height()) + 1;
}
};
int main() {
Node node1, node2, node3, node4;
node2.left = &node1;
node2.right = &node3;
node3.right = &node4;
std::cout << node2.get_height() << std::endl;
return 0;
}
Run Code Online (Sandbox Code Playgroud)
编辑:如果启用优化,则代码将失败,并出现分段错误。可以通过附加__attribute__ ((optimize(0)))功能来解决问题。
this == nullptr 在任何方面都没有副作用的意义上讲,“安全”是“安全的”。
this == nullptr是没用在这个意义上,在具有明确的行为的任何程序,这是从来没有true。因此,允许优化器假装您原来编写了以下代码:
if (false)
return -1;
return std::max(left->get_height(), right->get_height()) + 1;
Run Code Online (Sandbox Code Playgroud)
与写相同:
return std::max(left->get_height(), right->get_height()) + 1;
Run Code Online (Sandbox Code Playgroud)
不安全的是通过空指针(或其他任何不指向具有有效生存期的对象的指针)调用成员函数。尽管人们可能会凭直觉认为这样做,但这项检查并不能防止这种情况的发生。示例程序的行为是不确定的。
该函数的明确定义的示例:
int get_height() const {
int lh = left ? left->get_height() : -1;
int rh = right ? right->get_height() : -1;
return std::max(lh, rh) + 1;
}
Run Code Online (Sandbox Code Playgroud)
非成员函数在避免重复时可能有用。
PS一个好的编译器会警告您潜在的错误:
警告:'this'指针在定义良好的C ++代码中不能为null;可以假设比较结果始终为假[-Wtautologic-undefined-compare]
Run Code Online (Sandbox Code Playgroud)if (this == nullptr) ^~~~ ~~~~~~~