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

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

0 голосов
/ 26 октября 2011

В настоящее время мне трудно вставить узел в двоичное дерево с помощью рекурсии.Я останавливался на этой проблеме уже несколько дней и думал, что пришло время искать ответы!

Класс узла (.h): 

#ifndef STUDENT_MACROGUARD
#define STUDENT_MACROGUARD

#include <cstdlib>
#include <string>

namespace student_class
{
    class student
    {
        public:
            // Constructors / Destructors;

            student(const float entry = 0, std::string name = "", 
                        student* left_ptr = NULL, student* right_ptr = NULL);
            ~student(void){};

            // Mutating member functions;

            void set_grade(const float entry);
            void set_name(std::string entry);

            void set_left(student* node_ptr);
            void set_right(student* node_ptr);

            // Non mutating member functions;

            float grade(void);
            std::string name(void);

            student* left(void);
            student* right(void);

            // Const member functions;

            const student* left(void) const;
            const student* right(void) const;

    private:
            std::string student_name;
            float grade_field;
            student* left_ptr;
            student* right_ptr;
    };
}

#endif

Класс BSTree для реализацииструктура данных двоичного дерева (.h): 

#ifndef BTTree_MACROGUARD
#define BTTree_MACROGUARD

#include <cstdlib>
#include <string>
#include <iostream>
#include "student.h"

using namespace student_class;

namespace BTTree_class
{
class BTTree
{
    public:
            // Constructors / Destructors; 

            BTTree(student* node_ptr = NULL);
            ~BTTree(void);

            // Mutating member functions;

            void insert(student* node_ptr = NULL, const float grade = 0, std::string name = "");
            void remove(student* node_ptr);

            // Non mutating member functions;

            student* grade_search(const float entry);
            student* name_search(const std::string entry);
            student* root(void);
            void print_tree(student* node_ptr);

            // Const member functions;

            const student* grade_search(const float entry) const;
            const student* name_search(const float entry) const;
            const student* root(void) const;

    private:
            student* root_ptr;
    };
}

#endif

Реализация функции вставки члена, которую я использую для вставки узлов в дерево: 

    void BTTree::insert(student* node_ptr, const float grade, std::string name)
{
    if(root_ptr == NULL)
    {
        root_ptr = new student(grade, name);
        return;
    }

    if(node_ptr == NULL)
    {
        node_ptr = new student(grade, name);
        return;
    }
    else if(node_ptr->grade() > grade)
    {
        insert(node_ptr->left(), grade, name);
    }
    else
    {
        insert(node_ptr->right(), grade, name);
    }
}

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

Любая помощь будет фантастической, спасибо.

1 Ответ

3 голосов
/ 26 октября 2011

Проблема здесь: 

if(node_ptr == NULL)
{
    node_ptr = new student(grade, name);
    return;
}

node_ptr является локальной переменной, потому что вы передаете ее по значению. Таким образом, назначение теряется при выходе из функции.

Чтобы это исправить - пройдите по ссылке: 

void BTTree::insert(student* &node_ptr, const float grade, std::string name)

Это потребует изменений, конечно: 

        student* & left(void);
        student* & right(void);
...