C 구현의 다중 경로 트리 검색 알고리즘

Question

typedef struct dt { 
    .....; 
} Data; 

typedef struct nd { 
    int id; 
    Data *data; 
    struct tm *_parent; 
    struct tm *_child[7]; 
} Node; 


Node* findNode(int id, Node *tree) { 
    Node *p = tree; 
    if (id == p->_id) 
     return p; 
    for (int i = 0; i < 7; i++) { 
     if (id == p->_child[i]->_id) { 
      p = p->_child[i]; 
      break; 
     } else if(p->_child[i] != NULL) { 
      findNode(id, p->_child[i]); 
     } 
    } 

    return p; 
} 

모든 노드가 0-7 개의 자식으로 구성된 다중 경로 트리가 있습니다. 어린이는 특별한 순서없이 추가되거나 제거 될 수 있습니다. 나는 주어진 ID가 트리를 검색하고 특정 노드에 대한 포인터를 반환하는 검색 알고리즘을 작성하려고합니다. 나는 행운을 빌지 않고 위와 같이 재귀 적으로 시도했다. 이 알고리즘을 재귀 적으로 구축 할 수 있습니까? 아니면 스택을 사용해야합니까?

Answer 1

최종 조건에는 몇 가지 문제가 있습니다. 루프가 id를 찾지 못하면 반환 값을 통해 탐지 할 수 있어야합니다. 이 경우 NULL로 만드는 것이 현명 할 것입니다. 이는 두 가지 변경을 통해 수행 할 수 있습니다. p를 설정하고 break를 수행하는 대신 직접 리턴하십시오 (그 f}은 ID가 발견되지 않으면 for 루프를 완료하고 끝에서 return p를 NULL로 리턴하도록 변경하십시오).

다음 재귀 호출을 할 때 반환 값을 확인해야합니다. NULL 인 경우 계속하십시오. 그렇지 않으면 반환하십시오.

그리고 앞의 대답은 하위 ID에 대한 검사가 더 잘 제거 될 수 있다는 점에서 정확합니다. 특히 NULL을 확인해야하기 때문에 필요합니다.

Answer 2

이 알고리즘을 재귀 적으로 구축 할 수 있습니까?

예, 재귀를 사용하여이를 수행 할 수 있습니다.

올바른 길을 가고 있습니다. 코드는 수정의 몇 가지가 필요합니다 : 그것은 재귀 호출 어쨌든 무엇을 할 것 인 복제 (그리고 아이가 NULL입니다 어떠했는지를 확인하는 데 실패)로

는

1. if (id == p->_child[i]->_id)...의 첫 번째 부분은 완전히 중복됩니다.
2. 함수가 자신을 재귀 적으로 호출하면 반환 값이 무시됩니다. 당신은 그 반환 값으로 무엇을해야 할지를 알아야합니다.