Дерево двоичного поиска Python: упражнение 5 с решением
Напишите программу на Python для преобразования заданных элементов массива в сбалансированное по высоте двоичное дерево поиска (BST).
Примечание. Сортировка по выбору улучшает пузырьковую сортировку, выполняя только один обмен для каждого прохода по списку.
Пример решения :
Код Python:
class TreeNode (object): def __init __ (self, x): self.val = x self.left = None self.right = Nonedef array_to_bst (array_nums): если не array_nums: return None mid_num = len (array_nums)//2 node = TreeNode (array_nums [mid_num]) node.left = array_to_bst (array_nums [: mid_num ]) node.right = array_to_bst (array_nums [mid_num + 1:]) return nodedef preOrder (node): if not node: return print (node.val) preOrder (node.left) preOrder (node.right) array_nums = [1 , 2,3,4,5,6,7] print ("Исходный массив:") print (array_nums) result = array_to_bst (array_nums) print (" nArray to BST с балансировкой по высоте:") print (preOrder (result) )e>Пример вывода:
Исходный массив: [1, 2, 3, 4, 5, 6, 7] Массив со сбалансированной высотой BST: 4213657NoneБлок-схема:
Редактор кода Python:
