順序付きバイナリ検索ツリーに挿入

Question

アルファベット順にソートされたバイナリツリーに項目を挿入するC++関数を作成するのに問題があります。

insert関数は次のように動作するはずです。ユーザーは番号を入力するよう求められます。この数字は、入力する書籍の数を示します。次に、書籍のタイトルと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

ツリーを横断することは、再帰が非常に優れていることの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にあったものは何でもあなたが新しいbookNodeを作るひとつひとつの時間を消去している、あなたはp->titleとp->urlに読みたい、どこでもあなたのinsert機能でbookを参照する必要はありません。

----------注意事項---------------
I非常に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