이진 검색 트리에서 범위 쿼리

범위 쿼리 (예 : [x, y]의 모든 키)에서 키 벡터를 반환하는 템플릿을 기반으로 몇 가지 코드를 작성해야합니다. 나를 감싸, 나는 재귀에도 상당히 새로운 편이다.이진 검색 트리에서 범위 쿼리

template <typename Key, typename Value> 
vector<<BSTNode<Key, Value>*> range_query(BSTNode<Key, Value>* root,Key key1,Key key2) { 

vector<BSTNode<Key, Value>*> found; 
if(key1 > key2) return found; 

while(root != NULL){ 
    range_query(root->left,key1,key2); 
    range_query(root->right,key1,key2); 
    if(root->key >= key1 && root->key <= key2) found.push_back(root); 
}

벡터 내에서 순서가 중요하지 않다고 가정하기 때문에 벡터에서 트래버스하고 키를 저장하는 올바른 방법일까요? 또한 재귀가 끝나면 완성 된 벡터를 어떻게 반환합니까? 함수 내부 매개 변수 (벡터 참조) 및 업데이트에

출처

2012-12-05 Lakeside

이진 검색 트리입니다. 범위의 키는 무엇을 의미합니까? 이것은 key1과 key2 아래의 모든 노드를 반환하는 것을 의미합니까? 또한 구조가 어떻게 배열되는지 공유하십시오. 키가 무작위로 배열되어 있거나 어떤 순서로 배열되어 있습니다. –

이진 검색 트리입니다. 아이디어는 트리를 탐색하고 지정된 제약 조건 사이에있는 모든 키 (또는 노드 값)를 포함하는 벡터를 반환하는 것입니다. x는 key1 <= x <= key2 인 [key1, key2]의 요소입니다. 나무는 무작위로 그려져 있고, 왼쪽에는 뿌리가 있고 왼쪽에있는 아이는 적고 오른쪽 아이는 더 커지고 있습니다. – Lakeside

패스 :

template <typename Key, typename Value> 
void range_query(BSTNode<Key, Value>* root, Key key1, Key key2, vector<<BSTNode<Key, Value>*>& found) 
{ 
    if (!root) return; 
    if(key1 > key2) return; 

    range_query(root->left,key1,key2,found); 
    range_query(root->right,key1,key2,found); 

    if(root->key >= key1 && root->key <= key2) 
     found.push_back(root); 
    } 
}

난 당신의 코드를 약간 수정했습니다.

출처

2012-12-05 02:06:22

아, 나는 모든 재귀 호출을 통해 벡터를 다시 인스턴스화하고 있다는 것을 깨닫지 못했습니다. 나는 매개 변수를 수정하지 않고 그것을 할 수 있는지를 물었다. 그 주위에 어쨌든 있습니까? – Lakeside

@ 레이크 사이드 : 정적 또는 글로벌하게 만드십시오! 그게 중요합니까? –

필자는 그렇게 생각하지 않는다. 함수 외부에 변수를 배치하는 것은 용납 될 수 없을 것이다. 반복을 사용하는 방법을 잘 모르겠다. 재귀는 훨씬 더 깨끗해 보인다. 데이터를 유지하는 방법을 재귀 적으로 살펴 보겠습니다. – Lakeside

이진 검색 트리에서 범위 쿼리

답변

관련 문제