C에서 트리 트리의 높이를 찾는 방법

Question

트라이 트리의 높이를 찾기 위해 알고리즘을 작성하는 데 문제가 있습니다. 나는 아이디어를 시작하는 법이나 어떻게 할 수 있을지 모른다. 죄송합니다, 이것이 '멍청한 놈'이라는 질문이긴하지만, 나는 꽤 새로운 시도이고 이것은 내 과제에 대해 빠진 유일한 부분입니다. 'A는 하나의 아이 인 경우는, [0], 그리고 경우는'B '가 아닌이 chidren의 트리는가있을 것입니다, 그래서 기본적으로

typedef struct RegTrie * ImplTrie; 
typedef struct RegTrie { 
    Boolean IsItAWord; /* true if it is a word, false if it is not a word */ 
    ImplTrie children[ALPHABETsize]; 
} RegTrie; 

: 어쨌든 여기

는 트라이 트리의 구조 자식 인 children [1]은 NULL이됩니다. 보시다시피 문자는 링크 색인에 의해 암시 적으로 정의되며, 과거 노드의 문자가 현재 노드까지 단어를 구성하면 'Boolean IsItAWord'가 true가됩니다.

내게이 빛을 줄 수 있겠 니? 내가 아는 유일한 것은 높이가 가장 긴 단어의 길이 + 1로 정의 될 수 있다는 것입니다. 그러나 어떻게 해야할지 모르겠습니다. 난 단지 해결책을 원한다. 그래서이 트라이의 높이를 찾는 어떤 방법도 크게 감사 할 것이다.

감사합니다.

Answer 1

ImplTrie을 사용하는 재귀 함수로 수행 할 수 있으며 int을 반환합니다.

기본 케이스는 ImplTrie이 NULL인지 확인합니다.이 경우 함수는 0을 반환합니다.

그렇지 않으면 함수는 children을 통해 루프를 진행하고, 자신을 호출하고, 최대 값을 선택하고, 최대 값 +1을 반환합니다.

int height(ImplTrie t) { 
    if (!t) return 0; 
    int res = 0; 
    for (int i = 0 ; i != ALPHABETsize ; i++) { 
     int h = height(t->children[i]); 
     if (h > res) { 
      res = h; 
     } 
    } 
    return res + 1; 
}