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

Question

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

其中 A 是任何排序列表:

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

在中序遍历中，我会得到 1 3 4 6 7 8 10 13 14。这是有序的，符合我写的等式，并且是一棵二叉树。我遇到的问题是编写(和理解)递归，这将使我能够保持以前的值(value)。我想到达 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 时，无需检查。

希望对您有所帮助。