1

3つの要素{1、2、3}のBSTがあります。その構造は次のようになります

  2
 / \
1   3

次に、以下に定義するBSTHeight（）を使用して各ノードの高さを計算しようとしましたが、「2」の高さの計算に問題があります。「1」と「3」の高さは次のように定義されているため、この値は1であると想定されます。 0.私の問題は、「2」の2つの子の高さを直接使用する場合（以下で強調表示されているパート2を参照）、その高さは常に0であるということです。ただし、2つの一時整数変数を使用する場合、その値は正しいです（以下で強調表示されているパート1を参照）。機能面では、2つのアプローチの違いはわかりませんでした。誰かが理由を説明するのを手伝ってもらえますか？

void BSTHeight(bst_node *p_node)
{
    if (!p_node) 
        return;

    if (!p_node->p_lchild && !p_node->p_rchild) {
        p_node->height = 0;
    } else if (p_node->p_lchild && p_node->p_rchild) {
        BSTHeight(p_node->p_lchild);
        BSTHeight(p_node->p_rchild);
#if 0   // part 1
        int lchild_height = p_node->p_lchild->height;
        int rchild_height = p_node->p_rchild->height;
        p_node->height = 1 + ((lchild_height > rchild_height) ? lchild_height : rchild_height);
#else   // part 2
        p_node->height = 1 + ((p_node->p_lchild->height) > (p_node->p_rchild->height)) ? (p_node->p_lchild->height) : (p_node->p_rchild->height);
#endif
    } else if (!p_node->p_lchild) {
        BSTHeight(p_node->p_rchild);
        p_node->height = 1 + p_node->p_rchild->height;
    } else {
        BSTHeight(p_node->p_lchild);
        p_node->height = 1 + p_node->p_lchild->height;
    }
}
4

1 に答える 1

1

問題は、演算子の優先順位にあります。加算は三項演算子よりも強く結合するため、三項演算子（？:)を角かっこで囲む必要があります。

以下は修正されたバージョンです。使用したブラケットはすべて不要であり、削除したことに注意してください。代わりに、必要なペアのみを追加しました。

1 + (p_node->p_lchild->height > p_node->p_rchild->height ?
     p_node->p_lchild->height : p_node->p_rchild->height);

代わりにstd::max（from ）を使用するのがさらに良いでしょう：<algorithm>

1 + std::max(p_node->p_lchild->height, p_node->p_rchild->height)
于 2013-01-22T20:29:23.743 に答える