二叉搜索树递归插入

发布于 2024-12-12 03:37:12 字数 2923 浏览 0 评论 0原文

我目前在使用递归将节点插入二叉树时遇到困难。我已经思考这个问题几天了,我想是时候来寻找答案了!

节点类 (.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);
    }
}

我不明白为什么此插入不起作用。代码看起来完美无缺,这让我摸不着头脑。我编写了一个使用迭代的替代插入函数,但递归是必须的。

任何帮助都会很棒,谢谢。

I'm currently having difficulty inserting a node into a binary tree using recursion. I've been dwelling on this problem for a few days now and thought it was time I came looking for answers!

Node class (.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 class to implement the Binary Tree data structure (.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

The insert member function implementation I'm using to insert nodes into the tree:

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

I don't understand why this insertion isn't working. The code looks flawless and it's left me scratching my head. I've written an alternate insertion function which uses iteration, but recursion is a must.

Any help would be fantastic, thank you.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

給妳壹絲溫柔 2024-12-19 03:37:12

问题就在这里:

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);

The problem is here:

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

node_ptr is a local variable, because you pass it by value. Thus, the assignment is lost when you exit the function.

To fix it - pass by reference:

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

That will require these changes, of course:

        student* & left(void);
        student* & right(void);
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文