使用递归的 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 实例。您需要做的就是将指针传递给一个特定的实例而不是副本。

使用递归的 BST 中序遍历

BST In-Order Traversal Using Recursion

c++

recursion

binary-search-tree