提问者:小点点

二叉搜索树中的递归堆栈


我正在尝试从二叉搜索树中删除一个节点。 虽然这个函数可以正常工作,但为什么我们需要设置node->m_left或node->m_right来返回deletenode函数本身的值呢? 很难理解此递归结构。
当前仅对叶节点执行此操作

Node<T>*  deletenode(T key){
         return deletenode(key,this->root);
        }
        Node<T>*  deletenode(T key,Node<T>* node){
            Node<T>* temp;
         if(node==nullptr){
             return node;
         }
         if(key<node->m_data){
             node->m_left=deletenode(key,node->m_left);
         }
         if(key>node->m_data){
             node->m_right=deletenode(key,node->m_right);
         }
          
         

         return temp;
        }
        
        

共1个答案

匿名用户

您正在将left或right设置为调用该分支上的deletenode函数的结果,而不是设置为函数本身。

递归的意思是:“如果我的树有一个左分支和一个右分支,并且要删除的项在左分支中,那么就制作一个新的树,它有相同的右分支,但是从左分支中删除要删除的项的结果作为它的左分支。”