我正在尝试从二叉搜索树中删除一个节点。 虽然这个函数可以正常工作,但为什么我们需要设置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;
}
您正在将left或right设置为调用该分支上的deletenode函数的结果,而不是设置为函数本身。
递归的意思是:“如果我的树有一个左分支和一个右分支,并且要删除的项在左分支中,那么就制作一个新的树,它有相同的右分支,但是从左分支中删除要删除的项的结果作为它的左分支。”