BST 삽입 기능에 대한 도움말

Question

안녕하세요, BST 작성을 시도하고 있지만 많은 오류가 발생했으며 어떻게 처리해야할지 압도 당하고 있습니다. 너희들은 한 번 들여다보고있는 것을 지적 해 줄 수 있니? 교사는 아무 것도 설명하는 데 전혀 도움이되지 않았습니다. .H 파일

class Tree 
{ 
public: 
    bool insert(int k, string s); 

private: 
    struct Node 
    { 
     int key; 
     string data; 
     Node *left; 
     Node *right; 
    }; 
    Node* root; 
    bool insert(Node *& root, int k, string s); 
}; 

.cpp 파일 우선

bool Tree::insert(int k, string s) 
{ 
    return insert(root, k, s); 
} 
bool Tree::insert (Node *& root, int k, string s) 
{ 
    if (root == NULL){ 
     root = new Node; 
     root->key = k; 
     root->data = s; 
     root->left = NULL; 
     root->right = NULL; 
    } 
    else if (root == k) 
     return false; 
    else if (root->key < k) 
     insert (root ->left, k); 
    else 
     insert (root -> right, k); 
} 

Answer 1

테스트하지 않은 코드가 많은 것으로 보입니다. 한 번에 하나씩 기능을 작동시켜야합니다.

또한 중복 된 작업의 인스턴스가 하나 이상 표시됩니다. preOrder과 postOrder 메서드는 동일한 알고리즘에 약간의 변형이 있어야하지만, 하나는 루프 기반이고 다른 하나는 함수 재귀에 의해 작동합니다.

이 소스 파일을 제쳐 놓고 새 프로젝트를 만들고 한 번에 하나의 기능을 복사하여 붙여 넣으십시오. 다음 기능으로 이동하기 전에 철저히 테스트하십시오. 이미 기존 코드에 숨겨진 기능에 도달하면 이전 코드에서 복사하여 붙여 넣기하지 말고 기존 테스트 코드를 활용하십시오.

편집

제대로 작동하는 것처럼 보입니다. 당신이 그들을 원한다면 여기에 몇 가지 문체 비판이 있습니다 : v).

1. Node 구조체에는 고유 한 생성자가 있어야합니다. 무효 상태에 빠질 수있는 것을 보장하는 생성자를 항상 제공하십시오.
2. 마찬가지로 Tree을 새로 만들 때 무언가를 root에서 NULL으로 설정해야합니다.
3. root 인수의 값을 변경하는 것이 좋지 않은 스타일입니다. 언뜻보기에는 left이고 right은 NULL 값을받지 못합니다. 개인적으로 여기서 포인터 대 포인터를 선호하지만 일부는 대신 구현에 동의 할 수 있습니다.

Answer 2

에서

헤더는, 당신은 당신의 코드의 끝 부분에 누락 된 브래킷이있다.

Answer 3

실제 구현을 고려하지 않으면 인터페이스 관련 함정이 많이 있습니다. 다음은 그 중 일부입니다 :

• 헤더 파일에 include guard가 누락되었습니다.
• 포함 된 헤더 파일의 전역 범위에서 "namespace std"를 사용하는 것은 허용되지만 매우 나쁜 스타일입니다.
• Tree::findKey 메서드는 문자열을 상수가 아닌 참조로 받아들입니다. 이유는 무엇입니까?
• Tree::insert은 값으로 문자열을 받아들입니다. 불필요한 복사가 필요합니까?
• preOrder 및 levelOrder은 함수에 대한 포인터를 필요로합니다. 클래스 메소드를 호출하거나 추가 인수를 전달하려면 어떻게해야합니까? 나는 당신이 술어를 가지고 더 잘 나가라고 말하고 싶습니다. boost::function.(클래스 내에 데이터) 상태를 수정하지 않는 상수 (const 수정)을 출시하지 않는
• 방법. 예 : isEmpty() 방법입니다.
• makeCopy 방법은 exception-safe 없습니다.
• 부호있는 정수 대신 size_t 사용됩니다.

는 도움이되기를 바랍니다.

Answer 4

첫 번째 BST 작성이 어려울 수 있습니다 ... Potatoswatter에 대한 조언을 듣고 먼저 다른 곳으로 이동하기 전에 VERY SOLID 삽입 기능이 있는지 확인해야합니다. 그래서 당신은 함수에 대한 선언을 포함하여 BST의 클래스를 만들 수 있지만 그 정의에 단지 예를 들어, 그들에게 빈 기능을합니다 헤더 파일에서

을 : 당신에

class BST 
{ 
    public: 
     BST(); 
     bool insert(int k, const string& s); 
     bool findKey(int k, string& s); 
     int maxKey(); 

     /* ... the rest of your class ...*/ 
}; 

합니다. CPP 파일 :이 방법 이제

#include "BST.h" 

BST::BST() 
{ 
    /*initialize anything required for your insert function to work*/ 
} 

//pass in a const reference for your string argument, 
//or else you could end up doing a lot 
//of extra processing creating a new copy of your string on the stack for 
//each insertion call 
bool BST::insert(int k, const string& s) 
{ 
    /* write your insertion algorithm implementation */ 
} 

//make the rest of your function definitions that don't 
//apply to insertion empty so you can compile and test your insertion algorithm 
//without adding more cruft 
bool BST::findKey(int k, string& s) {} 

int BST::maxKey() {} 

/* continue process for the rest of the class */ 

, 당신은 제대로 등, 충돌없이 트리에 노드를 삽입하고 있는지를 확인하기 위해 테스트 할 수 있습니다, 그 작업이 완료되면, 당신은 당신이 찾을 수 있는지 확인하기 위해 테스트 할 수 있습니다 삽입 한 노드 그 후에는 삭제, 반복 등을 처리하는 나머지 함수에 대한 정의를 완성 할 수 있습니다. 그러나 각 단계에 대해 필요하지 않은 함수에 대한 정의를 비워두면 솔루션 없이도 솔루션을 올바르게 빌드 할 수 있습니다. 컴파일러 오류 및 기타 비 관련 항목의 혼란으로 실제 작업 인터페이스를 구축하지 못하게합니다. 즉, 문제가없는 노드가 제대로 삽입되지 않은 트리에서 노드를 찾거나 삭제할 수 없으므로이 단계에서 꼬리를 쫓는 것을 원하지 않습니다. 첫발을 내디뎠다. 또한 노드 삽입과 같은 후속 단계를 구현할 때 삽입 문제가 여전히 있음을 발견 할 수 있습니다 ... 삽입 및 노드 찾기에 대한 전체 정의 만 구현 한 경우 이러한 두 가지 기능 만 사용할 수 있습니다. 고치기에 대해 걱정해야 할 것입니다.

그래서 기본적인 부분으로 (찾기, 삽입, 삭제 한 다음 다른 모든 것들을)를 분해, 당신은 작업이 Aaaaand 오류가 있습니다