1

我有兴趣找到给定范围内的所有整数BST。我想知道如果 BST 是用节点创建的，我将如何做这件事，因此我必须使用单链表。返回的链表中项目的顺序无关紧要。

例如考虑如下所示的树，

在此处输入图像描述

范围为 [6, 13]，则列表应包括 6->7->8->10->13 或 13->10->8->7->6。正如我所说，返回列表中的顺序无关紧要。

此外，运行时约束是 O(n)，其中 n 是树中的节点数。

提前致谢！

4

2 回答 2

1

您只需使用 2 个堆栈就可以做到这一点......

让我们从 2 个堆栈开始，1 个是简单的待办事项堆栈（例如包含您应该访问的节点），另一个是带有结果的堆栈。

从根节点开始，如果节点在范围内，则将其推入结果堆栈，并将两个子节点都推入待办事项堆栈。如果超出范围，可能会发生 2 种情况：1.) 它小于我们范围内的最小值 -> 将它的右孩子推入 todo 堆栈 2.) 它大于我们范围内的最大值 -> pus 它是 todo 上的左孩子堆

好的，让我们将其创建为一些有用的算法：

List<BSTNode*> FindAllInRange(BSTNode* root, int low, int high)
{
    Stack<BSTNode*> todo;              //< Todo stack
    Stack<BSTNode*> results;           //< Results stack

    // Start with root node
    todo.push(root);

    // While we have nodes to process
    while(todo.size() > 0)
    {
        // Get top node, and pop it from stack
        BSTNode* curr = todo.top();
        todo.pop();

        // If its value is less than the lowest value in range
        if(curr->value < low)
        {
            // Push right children if exists (as it may be higher than lowest value in range)
            if(node->right)
                todo.push(node->right);
        }
        // If its value is greater than the highest value in range
        else if(curr->value > high)
        {
            // Push left children if exists (as it may be lower than highest value in range)
            if(node->left)
                todo.push(node->left);
        }
        // Otherwise (we're in range)
        else
        {
            // Push current node to results stack
            results.push(curr);

            // If right node exists, push it on todo stack
            if(node->right)
                todo.push(node->right);

            // If left node exists, push it on todo stack
            if(node->left)
                todo.push(node->left);
        }
    }

    // Now you just have to convert the stack to list (and possibly sort it, reverse sort it, ...)
    return results.ConvertToList();
}

请注意，这只是类似 C++ 语言的伪代码。

于 2013-04-16T01:57:58.443 回答
1

如果你有 BST 的基本知识，你应该知道从树中检索一组排序的元素实际上非常简单。如果你熟悉LVR/RVL遍历你可以跳到“答案”。

循环遍历树：

遍历树通常被描述为三个字母的组合LVR。L离开了。R是正确的。V访问的意思。

这描述了您在遍历树时遵循的模式。L表示如果存在，您将树向下提升到左节点。R对。V表示对当前节点的一些操作，如打印。它使用重复！这很重要。

现在。如何获得排序集。LVR当访问意味着打印或推送时，这很简单。

示例 - 完整的演练：

 (8) You start in root. `L` - go left. 
  (3) You are in (3). You go `LVR` for this node again - recurrence. `L`
    (1) You are in (1). Now *again* `LVR`.
    However there is no left node so we go to `V` - visit/print 1. Now `R` - no right node. End. By recurrence we go back to 3.
  (3) - We're done with `L`. We do `V`. Print 3.
  (3) - `R`.
    (6) You are in (6) - `LVR` again. 'L'
      (4) You are in (4) - `L` does not exists. Print 4. `R` does not exist. Back one level.
    (6) - `V`. Print 6.
    (6) - `R`.
      You are in (7) - `L` does not exists. Print 7. `R` does not exist. Back one level.
    (6) - `LVR` Done. Back one level.
  (3) - `LVR` Done. Back one level.
(8) - `R`.
  (10) You are in 10. `L` Does not exist.
  (10) `V`. Print 10.
  (10) `R`.
    (14) You are in 14.
    (14) `L`.
      (13) You are in 13. `L` does not exists. Print 14. `R` does not exist. Back one level.
    (14) `V`. Print 14.
    (14) `R`. Does not exist. Back one level.
  (10) Done with `R`. Back one level.
(8) Done with `R`. Back one level.
Haha we were on root node so we are done.

如果你会跟随打印。事实证明，您按从低到高的顺序打印了整套。RVL模式会做类似的事情，但是由于您首先向右走，因此您将首先访问最右边的节点，因此顺序将是降序的。由于没有魔法并且您只访问每个节点一次，因此时间复杂度为O(n).

答案：

简单的方法。做一个正常的LVR遍历。但仅在符合范围的情况下打印数字。稍微困难但更好的平均和极端情况。找到起始节点。然后开始遍历并在每次访问时仅与上限进行比较，并在节点数据超过上限时停止。

当然，您可以使用堆栈或其他东西（如列表）代替打印，以按排序顺序存储元素。

于 2013-04-16T09:24:58.157 回答