遍历二叉搜索树C++

Question

我正在编写一个编程任务并编写一堆函数来实现二叉搜索树,并给出了一些函数.我以为我理解了递归,但是如果你愿意,我会一直挂断转换方向.

这是赋值的函数:

static void deleteAll(BSTNode<Data>* n) {
  if (0 == n) return;
  deleteAll(n->left);
  deleteAll(n->right);
  delete n;
}

要删除一棵非常短的树,

    root
   /    \
lefty  righty

我打电话deleteAll(root).n != 0所以现在我打电话deleteAll(lefty).n != 0所以我打电话deleteAll(lefty->left).当然没有左节点.当我添加lefty节点时,我的构造函数将left,right和parent指针初始化为0,所以现在n == 0.所以我退出了这个功能,永远不会删除.我怎么去deleteAll(n->right)？

正如我所说,提供此功能所以我不应该改变它.我想也许我不得不打电话deleteAll(b.begin())或者b.end()从左边或最右边的节点开始,但是每当我在脑海里经历它时,我都会打n == 0.

请帮我理解.

Answer 1

想象一下箭头指向正在执行的当前行.当我们打电话时deleteAll(root),首先检查是否root为0:

--> if (0 == root) return;
    deleteAll(root->left);
    deleteAll(root->right);
    delete root;

因为root != 0,我们随后致电deleteAll(root->left):

    if (0 == root) return;
--> deleteAll(root->left); /*
    |-1-> if (0 == lefty) return;
    |-2-> deleteAll(lefty->left);
    |-3-> deleteAll(lefty->right);
    |-4-> delete lefty; */
    deleteAll(root->right);
    delete root;
  }

现在,箭头会移回至函数的顶部,并开始做的一样lefty,通过我的评论在1-4行运行(在第2行,同样的扩张将再次直到空节点被发现发生).但重要的是它会记住函数调用之前的位置,以便以后可以恢复.所以deleteAll(root->left)会去做它做的事情并最终回归.然后原始呼叫继续:

    if (0 == root) return;
    deleteAll(root->left);
--> deleteAll(root->right);
    delete root;

现在也删除了正确的节点.这种情况发生在递归的每一步.请记住,return只返回当前函数,而不是整个递归链.