다 방향 트리의 높이 찾기

Question

다 방향 트리의 높이를 어떻게 알 수 있습니까? 나는 이진 트리의 높이를 발견하고 싶었다면, 나는 이런 식으로 뭔가를 할 수 :

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

하지만 내가 다자간 트리 유사한 재귀 적 방법을 적용 할 수 있는지 모르겠습니다.

Answer 1

'(현재) 루트 노드의 하위 노드 중 하나에서 시작하여 하위 트리의 최대 높이가 1'이 아닌가요?

이진 트리는 자식 노드가 왼쪽 자식과 오른쪽 자식으로 알려져있는 다중 경로 트리의 특별한 경우에 불과합니다. 루트 노드 포인터가 널인 경우 결과는 0입니다.

Answer 2

null 이외 경우 :

• 1

Answer 3

를 추가

최대

걸릴 아이들의 각각의 높이를 찾을 일반적인 경우는 다음과 같습니다

int height(node *root) 
{ 
    if (root == NULL) 
     return 0; 
    else { 
     // pseudo code 
     int max = 0; 
     for each child { 
      int height = height(child); 
      if (height > max) max = height; 
     } 
     return max + 1; 
    } 
} 

Answer 4

이것은 하위 노드가 저장된. 초에 그들이 벡터에 저장되어 있다고 가정합니다. 다음을 사용하여 높이를 계산할 수 있습니다. 이 (거의 아무것도) 가치가 무엇인지에 대한

int height(node* root) { 
    if (!root) { 
    return 0; 
    } 
    int max = 0; 
    for (vector<node*>::const_iterator it = root->children.begin(); 
     it != root->children.end(); 
     it++) { 
    int cur = height(*it); 
    if (cur > max) { 
     max = cur; 
    } 
    } 
    return max+1; 
} 

Answer 5

이 문제는 SML처럼 순수 함수형 언어에 아름답게 렌더링이 작동하지 않습니다

fun height Node(children) = (foldl max -1 (map height children)) + 1