c++ - 二叉树递归插入错误

Question

我有这种方法可以在二叉树中添加一个节点，在示例中，我首先添加了 4，它可以正常工作，然后当我添加 10 时，我得到了这个：

它首先检测top != NULL哪个是正确的，因为有 4 个，然后用top->droitein 参数（即top->right）调用方法。当它没有检测top为 NULL 并跳过时，它就变成了您在屏幕截图中看到的内容。正如您所看到的，变量为 NULL。

我究竟做错了什么？

Answer 1

通过查看其余的调试信息，我们可以看到新节点的左右指针是0xcdcdcdcd，据我所知，这是 Visual Studio 中调试构建的未启动指针的标准值。

您的错误不是初始化新节点的指针。这是正在发生的事情：

开头top是NULL，然后插入nbr为 4 的节点。新顶部是一个nbr为 4 的节点，但两个指针基本上指向垃圾。

当您尝试插入 10 时，它将正确地将 10 与 4 进行比较，并尝试在 4 的右子树中插入 10。此右子树未初始化，因此出现错误。

解决它的一种方法是使您的代码如下所示：

static void insertion(Noeud *&top, Noeud *newNoeud) {
   if (top == NULL) {
       top = newNoeud;
       top->droite = NULL;
       top->gauche = NULL;
   } else if (newNoeud->nbr < top->nbr)
       insertion(top->gauche, newNoeud);
   else
       insertion(top->droite, newNoeud);
}

这是一个完整的例子：http: //ideone.com/5TDD49