c++ - 使用 C++ 在 BTree 中递归插入节点

Question

创建一个模板类以递归方式在 BTree 中插入数据。代码给出了分段错误，我在头文件中包含了getter和setter函数，不确定哪里出错了，请帮忙提出建议，如果我删除了检查Node->right==NULL，那么代码可以正常工作，但在那种情况下我是无法添加递归。

       template <class S>
        class STree
        {
            public:
              // Constructors
                    STree()                         
                    {root = NULL; size=0;}
                    STree(S part)                       
                    {root = new BTNode<S>(part); size=0;}

             // Destructor
                  ~STree(){};
            void insert(S part)
            {
                if (root == NULL)
                {
                    root = new BTNode<S>(part);
                    cout<< "\n from root " << root->get_data();
                }
                else
                {add(root,part);}
                size++;
            }   

            void add(BTNode<S>* node, S part)
            {
                S part2 = node->get_data();
                cout << "part "<< part;
                cout<< "part2 "<< node->get_data();
                if( part == part2)
                    {node->set_data(part);}
                else if (part > part2)
                {
                    if (node->get_right()== NULL)   //if I remove this check the segmentation error goes away
                    {node->set_right(new BTNode<S>(part)); cout<< "from right "<< node->right->get_data();}
                    else
                    {add(node->get_right(),part);}  //If I remove the if statement above the recursion won't work
                }
                else
                {
                    if (node->get_left()==NULL)
                    { node->set_left(new BTNode<S>(part));}
                    else
                    {add(node->get_left(),part);}
                }
            }
            private:
                BTNode<S>* root;
                BTNode<S>* current;
                int size;
        };
        #endif

        int main()
        {
            STree<int> trees;
            trees.insert(10);
            trees.insert(20);
            trees.insert(30);
            trees.insert(40);

            return 0;
        }

标签： c++insertb-tree

Answer 1

BS part2 = node->get_data()nullptr每次插入时都会访问。实现递归时，请始终首先处理基本情况。

void add(BTNode<BS>* node, BS part)
{
    if (part < node->get_data() && node->get_left() == nullptr)
        node->set_left(new BTNode<BS>(part));
    else if (part > node->get_data() && node->get_right() == nullptr)
        node->set_right(new BTNode<BS>(part));

    if (node->get_data() == part)
        return;
    else
    {
        if (part < node->get_data())
            add(node->get_left(), part);
        else
            add(node->get_right(), part);
    }
}