순서가 지정된 이진 검색 트리에 삽입

Question

알파벳순으로 정렬 된 이진 트리에 항목을 삽입하는 C++ 함수를 만드는 데 문제가 있습니다.

삽입 기능은 다음과 같이 작동합니다. 사용자가 번호를 입력하라는 메시지가 나타납니다. 이 숫자는 입력 할 책의 수를 나타냅니다. 그런 다음 책의 제목과 URL (구조체로 정의 됨)이 입력되고 책은 제목의 첫 글자를 기반으로 사전 순으로 트리에 삽입됩니다.

나는 제목과 URL이 문자의 배열 인이 같은 책, 정의했습니다 :

struct bookNode { 
    char title[30]; 
    char url[40]; 
    char key; 
    bookNode *left; 
    bookNode *right; 
} book; 

을 그리고 이것은 내가 삽입 기능을 위해 지금까지 무엇을 가지고 :

void insertBook() { 
    struct bookNode *p, *q; 
    int i, n; 
    char key; 
    cout << "Enter the number of books you want to add" << endl; 
    cin >> n; 
    for(i=0;i<n;i++) { 
     p = (struct bookNode *)malloc(sizeof(struct bookNode)); 
     if(p==0) 
      cout << "Out of Memory" << endl; 
     cout << "Enter the title of the book" << endl; 
     cin.getline(book.title, 30); 
     key = book.title[0]; 
     cout << "Enter the url of the book" << endl; 
     cin.getline(book.url, 40); 
     p->key;      //I'm not sure if these next 3 lines are right 
     p->left=0; 
     p->right=0; 
     ... 
    } 
} 

나는 나무의 뿌리에 어떤 종류의 포인터를 선언해야한다고 생각하지만, 어디에 넣어야할지 모르겠습니다. 또한이 insert 함수를 호출하여 실제로 책을 삽입 할 위치를 찾는 별도의 "검색"함수를 작성해야하지만이 삽입 함수를 끝내기위한 도움을 찾고 있습니다.

Answer 1

트리를 가로 지르는 것은 재귀가 매우 잘하는 것 중 하나입니다.

내가 수행 할 작업은 하위 트리와 값을 삽입하여 하위 트리의 적절한 위치에 해당 값을 삽입하는 재귀 함수를 작성하는 것입니다.

Answer 2

bookNode* closest = search(p); //find closest node to where p goes 
    if (p->key < closest->key) //if p goes to the left 
    closest->left = p; //put it on the left 
    else //otherwise 
    closest->right = p; //put it on the right 


bookNode* search(bookNode* findme) { 
    //The search should traverse the tree 
    //and return a pointer to the "bottom" bookNode 
    //that is closest in value to p->title 
} 

은 또한 당신이 당신의 insert 기능 어디서나 book를 참조하고 싶지 않아, 당신은 그렇지 않으면 당신은 book에서 매 시간이었다 무엇이든지 삭제하고 새 bookNode을, p->title 및 p->url로 읽고 싶어.

---------- 참고 ---------------
나는 매우 char*를 사용하여, 대신 std::string를 사용하지 않는 것이 좋습니다

struct bookNode { 
    std::string title; //unlimited space 
    //other members 
} book; 

int main() { 
    std::string name = "Fred"; //easy to make 
    std::getline(cin, name); //read in entire title, no matter how long 
    if (name < "Fred") //easy to compare entire strings 
     std::cout << name; //easy to use 
} //deletes itself automagically