이진 트리의 잎을 찾는 방법은 무엇입니까?

검색 기능이있는 이진 트리를 작성했습니다. 이 함수는 검색 할 값을 나타내는 인자 x를 취해서 발견되면 잎인지 아닌지를 결정합니다. 값을 찾을 수 없으면 검색 함수는 false를 반환합니다.이진 트리의 잎을 찾는 방법은 무엇입니까?

다음은 내가 seg 결함을 제공하며 1에서 100까지의 모든 값에 대해 잘못된 반환 값을 제공합니다. 이진 트리는 100 개의 값으로 초기화됩니다. 검색 기능에서

bool search(Node<T>* &currentNode, const T& x) const 
{ 
    //~ cout << "CURRENT NODE DATA: " << currentNode->data << " : "; 


    /* FUNCTION: Searches for variable that is passed in X and checks if this value is a leaf or not */ 

    //Left Subtree Search 
    if (x < currentNode->data) 
    { 

    if ((leaf(currentNode)) == true) 
     { 
      return true; 
     } 
    else 
    { 
    search(currentNode->left, x); 

    } 

    } 


//Right Subtree Search 
else if (x >= currentNode->data) 
{ 

    //If node in right subtree is a node check 
    if ((leaf(currentNode)) == true) 
    { 
     return true; 
    } 

    else 
    { 
    search(currentNode->right, x); 
    } 

} 




//Return false if the node is not a leaf 
return false; 

} //END OF SEARCH FUNCTION 



void remove(Node<T>* &currentNode, const T& x) 
{ 

} 

bool leaf(Node<T>* currentNode) const 
{ 
    if (currentNode != nullptr) 
    { 
    return ((currentNode->left == nullptr && currentNode->right == nullptr) ? true : false);   
    } 
    else 
    { 
     return true; 
    } 
}

출처

2014-03-31 Scholar

어떤 줄에서 세그 폴트가 발생합니까? 또한 이진 트리가 정렬되어 있다고 가정합니다 (즉, 각 노드는 왼쪽보다 크거나 작거나 같음). 함수가 정렬 된 이진 트리를 받습니까? – CurlyCorvus

요소를 값순으로 내림차순으로 삽입합니다. – Scholar

나는 [self balancing tree] (https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)를 의미했습니다. 어느 쪽이든, x가 잎이 아닌 노드에 있으면 잎 노드에 대해서만 참을 반환 할 수 있기 때문에 함수는 그것을 찾지 못한다. 이것은 완전한 대답은 아니지만 'if (x == currentNode-> data)가 true를 반환하는 함수의 일부분을 가져야합니다.'(값 x를 검색하므로) seg 오류를 일으키고 코드를 덤프하는 대신 알고리즘을 묻습니다. – CurlyCorvus

또한, leaf 함수는 true를 반환합니다. 존재하지 않는 잎을 가리키는 포인터에 대해 원하는 동작입니까?

출처

2014-03-31 01:05:41

leaf 함수는 왼쪽 및 오른쪽 자식이 모두 null 포인터 인 경우 true를 반환합니다. Tenary 연산자를 사용하여 true 또는 false를 반환했습니다. 아마 뭔가 표현에 문제가 있으며 결코 사실을 반환하지 않을 수 있습니까? – Scholar

@Revoo 내가 보는 방법은'search' 함수에 두 개의 기본 케이스가 있어야한다는 것입니다. 그렇지 않으면 문제가있을 것입니다. 둘 다 이미 코멘트와 답변 사이에 언급되었습니다. 코드를 업데이트하고 테스트 한 다음 질문 세부 정보를 업데이트하면 나머지는 검토하고 도움이 될 것입니다. –

, 당신은 그들이 먼저 ... 그럼 당신은 널 (null) 확인하지 않고 여전히 데이터 요소를 참조 해제하려고 nullptr 있다면 보지 않고 자식 노드에 의지. currentNode가 해결 search에서 nullptr에 대한 검사를 가정 nullptr 때

출처

2014-03-31 01:01:47 mah

이진 트리의 잎을 찾는 방법은 무엇입니까?

답변

관련 문제