Блог

Я пытаюсь придумать алгоритм, чтобы построить бинарное дерево поиска с использованием элементов из еще бинарное дерево поиска, но с ограничением, что эти элементы должны быть больше или равны, чем некоторые дано целое число, назовем его x .

Я думал, что рекурсивный подход (используя в порядок обхода):

 binary_tree (bst tree, int x) {
  if (tree is empty)
    return empty;
  if (tree->element>=x)
    insert tree->element in a new BST;
  else ????
}
  

Я понятия не имею, что последний рекурсивный вызов будет, очевидно, я не могу писать с двумя возвращает такой:

 else
  return (tree->left, x)
  return (tree->right, x)
  

И я не могу думать ни о чем другом, извините, если это глупый вопрос! Я только начинаю с рекурсией и это действительно сбивает с толку.

Давайте подумаем о том, что мы делаем здесь. Мы хотим построить дерево из существующего двоичного дерева поиска. Потому что дерево является по британскому летнему времени мы получить некоторую полезную информацию.

Для любого узла V , если V <= x потом поддерево, которое указывает V -> left , будет иметь узлы все меньше x . Так что нам больше не нужно смотреть в правое поддерево. Однако если мы попали в узел, который больше или равно x надо продолжать рекурсию. Позволяет довести это все вместе в псевдо код

 newBST(root):
    if root is null 
        return 
    if root.val >= x
        addNewNode(root.val)
        newBST(root.right)
        newBST(root.left)
    else:
        newBST(root.right)
  

Это немного сложно, чтобы сделать это рекурсивно, потому что нет 1-1 соответствие между поддеревьев в дереве у вас есть и поддеревьев в дереве требуется.

Самый простой способ сделать это, чтобы скопировать значения >= X в список в порядке, а затем построить дерево из списка рекурсивно.