이진 검색 트리에서 값을 제거

주어진 키가 연결된 이진 검색 트리에서 항목을 제거하는 함수를 작성했습니다. 지금까지 나는 내 코드이 있습니다이진 검색 트리에서 값을 제거

template <typename Item, typename Key = Item> 
bool BSTree<Item,Key>::remove(const Key& key) { 
    bool removed = false; 
    Node* ptr = root; 
    if(ptr == NULL) 
     return removed; 
    while(key != ptr) { 
     if(ptr == NULL) 
      return removed; 
     else if(key > ptr) 
      ptr = ptr->right(); 
     else 
      ptr = ptr->left(); 
    } 
    removed = true; 
    Item max = max(ptr); 
    ptr->data() = max; 
    Node* prev = ptr; 
    while (ptr != NULL) { 
     prev = ptr; 
     ptr = ptr->right(); 
    } 
    delete ptr; 
    if (prev->left() != NULL) 
     prev = copy(prev->left()); 
    delete prev; 
    return removed; 
}

복사 그냥 재귀 적 접근법을 사용하여 나무의 끝 부분에 특정 노드에서 모든 값을 전송합니다 이미 작성한 다른 기능입니다. 나는이 함수가 작동해야한다고 생각하지만, 나는 완전히 확신 할 수 없으며 그것에 대한 피드백을 얻기를 희망했다.

또한 함수의 마지막 세 줄에 문제가 있습니다. 각각의 경우 "if", "delete"및 "return"에 밑줄이 그어져 있으며 "Error : declaration expected"오류가 표시됩니다. 나는 이것으로 무슨 일이 일어나고 있는지 전혀 모르며, 정말로 피드백을 고맙게 여길 것입니다!

출처

2012-12-05 Brandon Bosso

"while (key! = ptr)"에 같은 유형이 있습니까? –

예. 함수를 키로 템플리트함으로써 올바른 연산자가 이미 구현되었으므로 노드에 대해 주어진 키를 확인할 수 있습니다. –

나는 당신이 연산자를 오버로드하는 것을 본다! = 키와 노드를 비교한다 * –

IMHO, 나는 두 가지를 보았습니다.

는 BST 제거의 경우, 적어도 당신이 일에 비해 다음 작은 노드를 제거 할 찾아야한다, 당신의 "복사"이외의 더 나은 이식 방법이 필요합니다.
ptr-> data() = max; 귀하의 "data()"메서드는 Item의 멤버에 대한 참조를 반환합니다. 잘못이 아니라 이상하게 느껴집니다.
두 개의 "삭제"문장이 있지만 하나의 항목 만 삭제할 예정이 아닙니까? 이 섹션에서는
: 당신은 멋진 없습니다하는 NULL을 삭제하도록하면서 종료 후
```
while (ptr != NULL) { 

    prev = ptr; 
    ptr = ptr->right(); 
} 
delete ptr; 
```
, PTR의 값은 NULL입니다.

출처

2012-12-05 02:43:00

이진 검색 트리에서 값을 제거

답변

관련 문제