在中序遍历中，如何从一个递归到下一个递归保存一个元素？

Question

我正在验证 BST。如果要按顺序遍历树，它将按排序顺序输出值。此外，如果将前一个元素与当前元素进行比较，则可以验证它是否排序：

其中 A 是任何排序列表：

我不想按顺序遍历值并将它们存储到数组中以验证（O(n) space 复杂度），而是想保留前一个元素并在下一个递归时检查它。例如：

在中序遍历中，我会得到 1 3 4 6 7 8 10 13 14。这是有序的，符合我写的等式，并且是一棵二叉树。我遇到的问题是编写（和理解）递归，这将使我能够保持以前的价值。我想到达 1（基本情况）并将它保持到下一个元素，即 3。我确认 3 大于 1，然后 3 成为前一个，我将它保持到下一个元素。下一个元素是 4，我确认 4 大于 3，然后我保持 4 直到下一个元素......等等。

这是我的代码：

void InOrder(Root* root)
{
    Root* previous;

    if (root == NULL)
        return;

    else
    {
        previous = root;

        InOrder(root->left);
        cout << root->data << " " << previous->data << endl;
        InOrder(root->right);
    }
}

很明显这段代码只是做了一个中序遍历。我已经四处搜索和阅读，但找不到任何明确的内容。如何存储从一个递归周期到下一个递归周期的值？

Answer 1

这是一种方法：

bool InOrder(Root* root, int *min, int *max)
{
  return root == NULL ||
         (InOrder(root->left, min, &root->data) &&
          (min == NULL || *min < root->data) &&
          (max == NULL || root->data < *max) &&
          InOrder(root->right, &root->data, max));
}

bool InOrder(Root *root)
{
  InOrder(root, NULL, NULL);
}

基本上，您传递两个额外的参数并检查当前值是否在范围（最小值、最大值）内。在左递归中，你改变你的最大值，在右递归中——你的最小值。

我正在传递指针，因此当它为 NULL 时，无需检查。

希望对您有所帮助。

Answer 2

这里我们通过引用传递一个名为 prev 的变量。我已经使用 climits 头文件中的 INT_MIN 初始化了 prev，或者您可以使用小于所有 BST 值的值对其进行初始化。

void InOrder(struct node* root, int& prev)
{
    if (root == NULL)
        return ;

    else
    {
        InOrder(root->left,prev);
        if(prev<root->data)
        {
            prev = root->data;
            //printf("prev is %d\n",prev);
        }
        cout << root->data << endl;
        InOrder(root->right,prev);
    }
}

您可以从这里相应地更改您的代码。
您也可以查看下面的 link
希望你明白了。

在中序遍历中，如何从一个递归到下一个递归保存一个元素？

How do you hold an element from one recurse until the next recurse in an in-order traversal?

c++

sorting

algorithm

recursion

binary-search-tree