0

これは、12年生の二分木の割り当てからの質問です。BTreeクラスが木の高さを返すメソッドが必要です。ツリーにノードが1つある場合、高さは0だと思いますが、それについてはよくわかりません。今日は先生に聞いてみます。

しかしとにかく、これが私のコードです。何が問題なのかわかりません。

public int height(){
    if(root == null){
        return -1;
    }
    return height(root, 0, 0);
}
public int height(BNode branch, int depth, int ans){
    if(depth>ans){
        ans=depth;
    }
    if(branch.getLeft()!=null){
        depth+=1;
        return height(branch.getLeft(), depth, ans);
    }
    else if(branch.getRight()!=null){
        depth+=1;
        return height(branch.getRight(), depth, ans);
    }
    return ans;
}

これはテストクラスです：

    BTree bTree = new BTree();
    bTree.add(50);
    bTree.add(60);
    bTree.add(40);
    bTree.add(35);
    bTree.add(55);
    bTree.add(45);
    bTree.add(51);
    bTree.display();
    System.out.println(bTree.height());

この木は高さが3であるはずですが、戻ってきます：35 40 45 50 51 55 60 2

助けていただければ幸いです、ありがとう。

4

2 に答える 2

2

右ノードよりも左ノードを優先します。ノードの高さは次のようになります。

MAX(height(left), height(right)) + 1

しかし、代わりにあなたは代わりに効果的に言っています：

if (left)
   return height(left) + 1
else if (right) 
   return height(right) + 1

したがって、ノードの左脚が短く右脚が長い場合、間違った答えが返されます。

于 2013-03-25T05:21:57.977 に答える
0

ただのヒント。いくつかの計算を行うためにツリーをトラバースするときは、両方のサブツリーを再帰的に処理する必要があります。

したがって、null以外の特定のツリーノードの高さは次のようになります。 

max( (  height of left sub tree) , (height of right  sub tree)) + 1

他の回答で述べられているように、トラバーサルは正しくありません。

ノードがnullの場合、その高さは0です。

同様に、null以外のノードのサイズは、sizeof（left）+ sizeof（right）+1などになります。

于 2013-03-25T05:27:49.883 に答える