Вставка в упорядоченное двоичное дерево поиска

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; 
     ... 
    } 
} 

Я думаю, что мне, возможно, придется объявить какой-то указатель на корень дерева, но я не уверен, куда его поместить. И я также понимаю, что мне нужно будет написать отдельную функцию «поиска», которую я вызову в этой функции вставки, чтобы найти, где фактически вставить книгу, но я просто ищу помощь для завершения этой функции вставки.

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 
} 

Также вы не хотите, чтобы обратиться к book где-нибудь в вашей insert функции, вы хотите читать в p->title и p->url, в противном случае вы стираете все, что было в book каждый раз, когда вы делаете новый bookNode.

---------- ПРИМЕЧАНИЯ ---------------
Я настоятельно рекомендую не использовать 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