c++ - 使用递归的 BST 中序遍历

Question

我使用了搜索功能，虽然我找到了一些类似的主题，但没有找到完全涵盖我的问题的主题。

我正在尝试使用递归和中序遍历来查找 BST，因此我想跟踪元素的位置。

我有以下代码，但它没有按照我的意愿执行。遍历是对的，但是位置不对。

void startProces(int x)
{
void inOrder(x,*n,*Position)
}

void inOrder(int x, Node *n, int *Position)
{
    int counter = *Position;
    counter++;
    Position = &counter;
}

这是一项家庭作业，所以请避免给我一个直接的解决方案。另外，请避免给我一个涉及在我被锁定时必须重写函数参数的建议。我将不胜感激了解为什么我的位置值没有正确增加。我知道一旦找到值，我的函数目前不会执行任何操作。一旦我弄清楚了这个问题，我就打算实现它。

说明:我有一个插入函数，这里没有显示。如果我插入节点 (15,5,3,12,10,13,6,7,16,20,18,23) 我得到中序遍历 (3,5,6,7,10,12, 13、15、16、18、20、23)。我希望它对应于 (1,2,3,4,5,6,7,8,9,10,11,12)。最后，当我运行类似 startProcess(10) 的程序时，我希望 inOrder 打印 5。

Answer 1

您的代码在堆栈上复制一个变量并传递该变量的地址。因此，对于每个子节点，该值将始终是父节点的值加一，而不是之前遍历的节点的值加一。

具体来说，这一行复制了它...

int counter = *Position;

变量Position是一个指针，其中counter是一个局部变量。指针指向您使用 & 给它的地址。每次您调用 inOrder 时，它都会创建一个新的 counter 变量，该变量的作用域为该函数调用。

所以，这条线...

Position = &counter;

在上述函数调用中设置指向counter 实例的指针。您需要做的就是将指针传递给一个特定的实例而不是拷贝。