bst에서 최소 깊이 리프 노드 찾기

Question

최소 깊이를 갖는 리프 노드를 가져와야합니다. 나는 각 노드에 추가 정보를 저장하지 않고 그것을 수행하는 좋은 방법을 생각할 수 없다. 제안 해 주셔서 대단히 감사합니다.

Answer 1

무차별 방정식은 발견 된 첫 번째 잎에서 끝나는 너비 우선 검색이며 반복적으로 반복적으로 구현하는 것이 더 쉬울 것입니다.

예를 들어 my answer to "Breadth First Vs Depth First"의 의사 코드를 보면 while 루프에 다른 조건을 추가하기 만하면됩니다.

BTW - 잎이 최소 깊이로 도착합니다. 깊이가 두 개 이상있을 수 있습니다. 최소 깊이 잎의 전체 세트를 얻는 것은 조금 더 어렵습니다. 나는 iterative deepening strategy와 함께가는 것 같아요.

---

해당 노드가 어떤 레벨인지 알아내는 중입니다.

세 가지 선택 :

먼저 노드와 그것을위한 나무 아래 검색을 찾습니다. 그것은 낭비이지만, 두 번째 검색은 레벨만큼 노드를 방문해야하므로 실제로는 빠릅니다.

이동 중에도 계속 추적 할 수 있습니다. 세 개의 카운터 levelCounter, thisLevelCounter 및 nextLevelCounter을 사용합니다. 때마다 당신은 더 많은 새로운 노드에 당신은 thisLevelCounter을 감소하고, 제로 안타 때 그렇게

levelCounter++ 
thisLevelCounter = nextLevelCounter 
nextLevelCounter = 0 

당신이 검색 목록에 자식 노드를 추가 할 때마다, nextLevelCounter를 증가 할 수준을 아래로 이동했습니다. 때마다 당신이 nextLevelCounter

마지막으로 새 자식 노드의 증가를 저장, 반복 심화 전략은 당신에게 무료로 성공 수준을 (반복 ... 그것을 발견하는) 제공하고 약간 더 높은 승수 (비록 성능의 동일한 순서가)를 폭 넓은 첫 번째 검색으로 사용합니다.

다음

Answer 2

코드 버전 (내가 어떤 에러 체크를 놓치지 않았다 희망) :

void min_leaf(node_t *t, int *min, int lev, node_t **n) { 
    if (!t) { 
      return; 
    } 

    if (lev > *min) { 
      printf("Back from %d at lev %d, min: %d already found\n", 
          t->key, 
          lev, 
          *min); 
      return; 
    } 

    if (!t->left && !t->right) { 
      if (*min > lev) { 
        *min = lev; 
        *n = t; 
      } 
    } else { 
      min_leaf(t->left, min, lev+1, n); 
      min_leaf(t->right, min, lev+1, n); 
    } 
} 

void bst_print_min_leaf(bst_t* bst) { 
    int min = 10000; /* Replace it with some really large number */ 
    node_t *minn = NULL; 

    min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */ 
    if (minn) printf("min leaf is at depth: %d: (%p:%d)\n", min, minn, minn->key); 
}