BST高さのアルゴリズムは

Question

class node 
{ 
    private float data; 
    private node left; 
    private node right; 

    public int TreeHeight(int depth) 
    {  
     root vL = left;//access to left data 
     root vR = right; 

     return depthOfTheTree; 
    } 
} 

ツリーはそのように見えます。 このメソッドは、左右のノードにのみアクセスできます。パラメータとしての変数の深さは、メソッド自体（ツリーのルートを数える）にすでに値1が付いています。 私は再帰呼び出しメソッドを試しましたが、結果は期待に近いものではありませんでした。 私の前のコードは以下のコードに似ています。

definitionにより

public int TreeHeight(int depth) 
{ 
    if (left != null && right == null) 
     return left.TreeHeight(depth); 
    else if (left == null && right != null) 
     return right.TreeHeight(depth); 
    else 
     return left.TreeHeight(depth) + right.TreeHeight(depth); 
} 

Answer 1

：

ノードの高さは、そのノードとリーフの間最長パス上のエッジの数です。したがって

height(node) = 
{ 
    0, when node == null 
    1 + max(height(node.left), height(node.right)), when node != null 
} 

再帰的方法はdepthパラメータを必要とせず、次のようであってもよい：

public int TreeHeight() 
{ 
    return 1 + Math.Max(
     left != null ? left.TreeHeight() : 0, 
     right != null ? right.TreeHeight() : 0 
    ); 
} 

と

は、BSTの場合には（擬似コード）として再帰的に表すことができます。 C＃6 null conditional operatorでは、その実装は次のように簡単です：

return 1 + Math.Max(left?.TreeHeight() ?? 0, right?.TreeHeight() ?? 0);