#algorithm #recursion #binary-search-tree
#алгоритм #рекурсия #двоичный поиск-дерево
Вопрос:
Я пытаюсь придумать алгоритм, чтобы построить бинарное дерево поиска с использованием элементов из еще бинарное дерево поиска, но с ограничением, что эти элементы должны быть больше или равны, чем некоторые дано целое число, назовем его 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)
И я не могу думать ни о чем другом, извините, если это глупый вопрос! Я только начинаю с рекурсией и это действительно сбивает с толку.
Ответ №1:
Давайте подумаем о том, что мы делаем здесь. Мы хотим построить дерево из существующего двоичного дерева поиска. Потому что дерево является по британскому летнему времени мы получить некоторую полезную информацию.
Для любого узла 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)
Ответ №2:
Это немного сложно, чтобы сделать это рекурсивно, потому что нет 1-1 соответствие между поддеревьев в дереве у вас есть и поддеревьев в дереве требуется.
Самый простой способ сделать это, чтобы скопировать значения >= X в список в порядке, а затем построить дерево из списка рекурсивно.