2

二分探索木の高さを計算する方法を探していましたが、研究の結果、次の実装にたどり着きました。私はまだそれが機能する理由を理解しようとしていますが、なぜ機能しないのかもわかりません。これが私の身長関数です。

int BinaryTreeNode::height() const {
    int lefth = left->height();
    int righth = right->height();
    if(lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

これがノードのクラス定義です

class BinaryTreeNode {
  public:
    Data * nodeData;
    BinaryTreeNode * left;
    BinaryTreeNode * right;

実行しようとすると、プログラムがロックアップしてクラッシュします。明らかな何かが欠けていますか？

編集:なぜこれがうまくいかないのですか?

int BinaryTreeNode::height() const {
    int l = 0;
    if (left != NULL) {
        left->height();
    }
    int r = 0;
    if (right != NULL) {
        right->height();
    }
    if (l > r) {
        return l + 1;
    }
    else {
        return r + 1;
    }
}
4

3 に答える 3

2

問題は、関数が子ポインターが であるかどうかをチェックしないことです。そのNULLため、無効なポインターを逆参照する以外に、基本ケースを見逃す再帰関数があります。

このバージョンを試してください:

int BinaryTreeNode::height() const 
{
    int lefth = 0;
    if (left != NULL) { lefth = left->height(); }

    int righth = 0;
    if (righth != NULL) { righth = right->height(); }

    if (lefth > righth) { return lefth + 1; } 
    else { return righth + 1; }
}
于 2013-03-30T21:26:14.443 に答える
0

私も同じ問題に直面していましたが、あなたのコードの問題は、あなたの関数で再帰を2回使用していて、左端と右端に行きますが、親の1つの右の子の可能性をチェックしていないことです左のサブツリーのノードには独自の子があるため、ツリーの最後のリーフ ノードに移動していません。お役に立てれば

于 2017-01-03T03:13:32.743 に答える