Для заданного бинарного дерева поиска выведите все комбинации входных данных, образующие один и тот же BST.

Эта проблема сложнее, чем кажется на первый взгляд.

Рассмотрим дерево из вашего первого примера:

  2
1   3

Как вы сказали, есть два возможных порядка ввода: 2,1,3 и 2,3,1. Правило такое: корень, потом дети в любом порядке.

Но это слишком просто. Чтобы увидеть всю сложность проблемы, вы должны расширить ее на другой уровень. Таким образом, ваш второй пример:

      5 
   3     7
2    4  6   8

Обычно существует два способа построения этого дерева: сначала в ширину или в глубину. Чтобы сделать это в ширину, вы неоднократно применяете правило «сначала корень, затем потомки в любом порядке». Таким образом:

5,3,7,2,4,6,8
5,3,7,2,4,8,6
5,3,7,2,6,4,8
...
5,7,3,8,6,4,2

На каждом уровне есть (2 ^ k)! перестановок, где k — уровень. Таким образом, имеется 1 перестановка в корне, две перестановки на втором уровне (k == 1), 24 перестановки на следующем уровне и т. д.

Но выполнение этой широты в первую очередь не будет генерировать все возможные допустимые входные данные. Например, 5,3,2,4,7,6,8 вполне допустимо. Чтобы получить все допустимые входные данные, вы также должны включить построение в глубину. И тут все становится как-то интересно.

Вы можете сгенерировать предварительный обход дерева: 5,3,2,4,7,6,8 или обратный предварительный обход: 5,7,6,8,3,2,4. Здесь действует правило root, а затем обход дочерних элементов в глубину в любом порядке.

Но это не покрывает странный случай 5,3,2,7,8,4,6, который просто пропускает, но гарантирует, что родительский узел будет предоставлен перед любым из его дочерних элементов.

У меня нет полного решения, но я могу дать вам начало алгоритма. Рассмотрим случай случайной генерации действительной входной последовательности. Вы можете сделать это с помощью цикла:

nodes_array = create an array of nodes that can be selected
output_array = array of selected nodes

add root to nodes_array
while nodes_array is not empty
    temp = randomly select node from nodes_array, and remove it
    if temp.left != null
        add temp.left to nodes_array
    if temp.right != null
        add temp.right to nodes_array
    append temp to output_array
end while

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

Таким образом, проблема генерирования всех допустимых комбинаций становится проблемой изменения шага случайного выбора таким образом, чтобы на каждом уровне он генерировал все возможные перестановки nodes_array. Генерация перестановок - решаемая задача. Однако применение этого рекурсивно требует некоторого размышления.

Вот простой алгоритм, использующий поиск с возвратом в Python. Он предполагает реализацию бинарного дерева поиска с операцией insert. Каждый узел имеет значение node.value и, возможно, дочерние узлы node.left и node.right.

def get_children(node):
    children = []
    if node.left is not None:
        children.append(node.left)
    if node.right is not None:
        children.append(node.right)
    return children

def print_permutations(possibilities, string):
    if len(possibilities) == 0:
        print(string)
        return

    for i in range(len(possibilities)):
        node = possibilities[i]
        del possibilities[i]
        new_possibilities = get_children(node) + possibilities
        print_permutations(new_possibilities, string + " " + str(node.value))
        possibilities.insert(i, node)

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

Вы можете назвать это так:

b = BinarySearchTree()
b.insert(5)
b.insert(3)
b.insert(7)
b.insert(2)
b.insert(4)
b.insert(6)
b.insert(8)

print_permutations(get_children(b.root), str(b.root.value))

И он выведет:

5 3 2 4 7 6 8
5 3 2 4 7 8 6
5 3 2 7 6 8 4
5 3 2 7 6 4 8
5 3 2 7 8 6 4
...

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

Обратите внимание: другая допустимая последовательность: root› правый дочерний элемент› левый дочерний элемент также может быть напечатана. Для простоты я привожу здесь код для первого типа действительной последовательности.

Вот мой код:

class Node: 
  
    # Constructor to create a new node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None

root = Node(20) 
root.left = Node(8) 
root.right = Node(22) 
root.left.left = Node(4) 
root.left.right = Node(12) 
root.left.right.left = Node(10) 
root.left.right.right = Node(14)

Суть проблемы:

def printNodes(root):
    
    if root == None:
        return False
    else:
        print(root.data)
        printNodes(root.left)
        printNodes(root.right)

Выход:

printNodes(root)

20
8
4
12
10
14
22

Ответ @deleterOfWorlds работает, но он использует список, для вставки и удаления которого требуется линейное время. Вот мое решение Python с большим количеством объяснений.

Мы строим каждый массив слева направо, выбирая для каждой позиции один узел из набора возможных вариантов для этой позиции. Добавляем значение узла в путь, а дочерние элементы узла (если они есть) в список возможностей, затем рекурсивно продолжаем. Когда нет других вариантов, у нас есть один массив кандидатов. Чтобы сгенерировать остальные массивы, мы откатываемся до тех пор, пока не сможем сделать другой выбор и снова рекурсивно.

Суть в том, чтобы использовать подходящую структуру данных для хранения возможностей. Список работает, но узел должен быть возвращен в предыдущую позицию при откате (порядок имеет значение, так как мы добавили дочерние элементы узла, которые необходимо посетить ПОСЛЕ узла). Вставка и удаление из списка занимает линейное время. Набор не работает, так как он не поддерживает порядок. Диктовка работает лучше всего, так как словарь Python запоминает порядок вставки, и все операции выполняются в постоянное время.

def bst_seq(root: TreeNode) -> list[list[int]]:
    def _loop(choices: MutableMapping[TreeNode, bool], path: list[int], result: list[list[int]]) -> None:
        if not choices:
            result.append([*path])
        else:
            # Take a snapshot of the keys to avoid concurrent modification exception
            for choice in list(choices.keys()):
                del choices[choice]
                children = list(filter(None, [choice.left, choice.right]))
                for child in children:
                    choices[child] = False
                path.append(choice.val)
                _loop(choices, path, result)
                path.pop()
                choices[choice] = False
                for child in children:
                    del choices[child]

    result = []
    _loop({root: False}, [], result)
    return result