Вставка в упорядоченное дерево двоичного поиска - PullRequest
Новая
       13

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

0 голосов
/ 15 марта 2012

У меня проблемы с созданием функции 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;
        ...
    }
}

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

Ответы [ 2 ]

0 голосов
/ 15 марта 2012 
  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
0 голосов
/ 15 марта 2012

обход дерева - это одна из тех вещей, в которых рекурсия очень хороша.

Я бы написал рекурсивную функцию, которая принимает поддерево и значение для вставки, и вставляет это значение в нужное место в поддереве.

...