插入到一個有序的二叉搜索樹

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