이진 탐색 트리의 전체 높이

Question

이진 검색 트리를 만드는 중이고 각 노드의 높이를 기록하고 합계하는 함수를 만들고 싶습니다. 재귀를 사용하려고합니다.

어려운 점은 각 노드에 높이를 지정하고 돌아가서 합산하는 것입니다. 한 번에 높이를 지정하고 기록 할 수 없다면? 미리 감사드립니다.

편집 : 미래에 이것을 보게 될 사람을 위해 나를 위해 일한 것을 보여주는 최종 코드. 도움을 주셔서 감사합니다.

BST.h 

    int totalheight(node); 
    int getHeight(node); 

    class BST { 
    Node root; 
    public: 
     BST { root = NULL; } 
     int totalheight() 
     { return ::totalheight(root); 
    }; 


BST.cpp 

int totalHeight(BSTNode* node) 
{ 
    if (node == NULL) 
     return -1; 

    int leftHeight = getheight(node->left); 
    int rightHeight = getheight(node->right); 
    int totalheight = 1 + leftHeight + rightHeight; // +1 to count the root 

    return totalheight; 
} 

int getheight(BSTNode* node) 
{ 
    if (node == NULL) 
     return 0; 

     return 1 + max(getheight(node->left), getheight(node->right)); 
} 

main.cpp 

    int main() { 
     BST tree; // and various inserts 

     tree.totalheight(); 
    } // main 

Answer 1

한 가지 문제는 여기에 있습니다 :

int myheight = max(leftheight, rightheight); 

그것은해야한다 :

int myheight = max(leftheight, rightheight) + 1; 

당신이 높이 노드에 대한 계정를 위해 하나가 필요합니다. 또한 표시된 코드에서 findHeight은 getHeight이어야합니다.

int getheight(BSTNode* node) 
{ 
    if (node == null) 
     return 0; 
    else 
     return 1 + max(getHeight(node->left), getHeight(node->right)); 
} // getheight