74

二分探索木の高さを見つけるためにこの方法を作り直すのを手伝ってくれる人がいるかどうか疑問に思っていました。これまでのところ、私のコードは次のようになります。しかし、私が得ている答えは実際の高さよりも 1 大きいです。しかし、return ステートメントから +1 を削除すると、実際の高さよりも 1 小さくなります。これらの BST。どんな助けでも大歓迎です。

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}
4

26 に答える 26

142

問題は基本ケースにあります。

「ツリーの高さは、ルートからツリーの最も深いノードまでのパスの長さです。ノード (ルート) のみを持つ (ルート化された) ツリーの高さはゼロです。」-ウィキペディア

ノードがない場合は、0 ではなく -1 を返します。これは、最後に 1 を追加しているためです。

したがって、ノードがない場合は、+1 をキャンセルする -1 を返します。

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}
于 2010-04-08T05:26:01.487 に答える
38

二分探索木の高さは に等しいnumber of layers - 1。

http://en.wikipedia.org/wiki/Binary_treeの図を参照してください。

あなたの再帰は良いので、ルートレベルで 1 を引くだけです。

また、null ノードを処理することで、関数を少しクリーンアップできることにも注意してください。

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}
于 2010-04-08T05:08:46.390 に答える
11

私の意見では、コードを少し単純化することでメリットが得られます。子ポインターが nullの場合に再帰を終了しようとするのではなく、現在のポインターが nullの場合にのみ終了します。これにより、コードの記述が非常に簡単になります。擬似コードでは、次のようになります。

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);
于 2010-04-08T05:06:20.590 に答える
4

それを表現するための簡潔でうまくいけば正しい方法は次のとおりです。

  private int findHeight(TreeNode<T> aNode){
    if(aNode == null || (aNode.left == null && aNode.right == null))
      return 0;
    return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
  }

現在のノードが null の場合、ツリーはありません。両方の子が存在する場合、レイヤーは 1 つになり、高さが 0 になります。これは、高さの定義 (Stephen が言及) をレイヤー数 - 1 として使用します。

于 2010-04-08T04:51:06.660 に答える
4

これはテストされていませんが、かなり明らかに正しいです:

private int findHeight(Treenode<T> aNode) {
  if (aNode.left == null && aNode.right == null) {
    return 0; // was 1; apparently a node with no children has a height of 0.
  } else if (aNode.left == null) {
    return 1 + findHeight(aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight(aNode.left);
  } else {
    return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
  }
}

多くの場合、コードが 1 つずれている理由を理解するよりも、コードを単純化する方が簡単です。このコードは理解しやすいです。考えられる 4 つのケースは、明らかに正しい方法で明確に処理されます。

  • 左右のツリーが両方とも null の場合は、0 を返します。これは、定義により単一のノードの高さが 0 であるためです。 (以前は 1 でした)
  • 左または右のツリーのいずれか (両方ではない!) が null の場合、null 以外のツリーの高さに 1 を加えた値を返し、現在のノードの追加された高さを考慮します。
  • どちらのツリーも null でない場合は、背の高いサブツリーの高さに現在のノードの 1 を加えた値を返します。
于 2010-04-08T05:15:53.350 に答える
3 
    public void HeightRecursive()
    {
        Console.WriteLine( HeightHelper(root) ); 
    }

    private int HeightHelper(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));           
        }
    }

C# コード。これら 2 つのメソッドを BST クラスに含めます。木の高さを計算するには2つの方法が必要です。HeightHelper で計算し、HeightRecursive で main() に出力します。

于 2011-12-05T11:50:42.040 に答える
2

上記の高さの定義は正しくありません。それが深さの定義です。

「ツリー内のノードMの深さは、ツリーのルートからMまでのパスの長さです。ツリーの高さは、ツリー内の最も深いノードの深さよりも 1 つ大きくなります。深さdのすべてのノードは、ツリーのレベルdにあります。ルートはレベル 0 の唯一のノードであり、その深さは 0 です。」

引用: 「データ構造とアルゴリズム分析の実践的な紹介」第 3.2 版 (Java バージョン) Clifford A. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061

于 2013-05-09T01:31:16.080 に答える
1 
 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }
于 2016-11-23T19:14:46.847 に答える
1

この質問には2つの異なる意味があると思います...

  1. 高さは、最長の枝のノード数です:-

    int calcHeight(node* root){ if(root==NULL) return 0; int l=calcHeight(root->left); int r=calcHeight(root->right); if(l>r) return l+1; else return r+1; }

  2. 高さは、ツリー自体のノードの総数です。

    int calcSize(node* root){ if(root==NULL) return 0; return(calcSize(root->left)+1+calcSize(root->right)); }

于 2014-02-25T16:14:30.933 に答える
0

これを読んでいる他の人のために!!!!

HEIGHT は、ルート ノードからリーフ ノードまでの最長パスのノード数として定義されます。したがって、ルート ノードのみを持つツリーの高さは 0 ではなく 1 です。

特定のノードの LEVEL は、ルートからの距離 + 1 です。したがって、ルートはレベル 1 にあり、その子ノードはレベル 2 にあり、以下同様です。

(情報の提供は Data Structures: Abstraction and Design Using Java, 2nd Edition, by Elliot B. Koffman & Paul AT Wolfgang) - 私が現在コロンバス州立大学で受講しているデータ構造コースで使用されている本。

于 2013-11-11T22:32:21.933 に答える