Question

Даю 100 баллов Массив из 100 элементов, построить бинарное дерево, без использования функции мин и макс на python

Answer 1

Ответ:

Python:

# Класс узла

class Node:

# Конструктор класса

def __init__(self, value):

# Значение узла

self.value = value

# Левый потомок

self.left = None

# Правый потомок

self.right = None

# Функция для вставки узла в дерево

def insert(node, value):

# Если узел не существует, создаем новый

if node is None:

return Node(value)

# Если значение узла больше или равно вставляемому значению, вставляем узел в левого потомка

if node.value >= value:

node.left = insert(node.left, value)

# Иначе вставляем узел в правого потомка

else:

node.right = insert(node.right, value)

return node

# Функция для создания двоичного дерева

def build_binary_tree(arr):

# Корень дерева

root = None

# Перебираем все элементы массива

for value in arr:

# Добавляем элементы в дерево

root = insert(root, value)

return root

# Массив элементов

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 100]

# Создаем дерево

tree = build_binary_tree(array)

Answer 2

class Node:

   def __init__(self, data):

       self.data = data

       self.left = None

       self.right = None

class BinaryTree:

   def __init__(self, data):

       self.root = Node(data)

   

   def insert(self, data):

       if self.root is None:

           self.root = Node(data)

       else:

           self._insert(data, self.root)

   

   def _insert(self, data, node):

       if node is None:

           return Node(data)

       if data < node.data:

           node.left = self._insert(data, node.left)

       else:

           node.right = self._insert(data, node.right)

       return node

Можно добавить элементы в дерево, вызывая Insert:

tree = BinaryTree(50)

tree.insert(30)

tree.insert(20)

tree.insert(40)

tree.insert(70)

tree.insert(60)

tree.insert(80)

Answer 3

Чтобы построить бинарное дерево из массива из 100 элементов без использования функций min и max в Python, вам потребуется написать свои собственные функции для поиска минимального и максимального элементов.

Вот пример кода, который реализует это:

pythonCopy code
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def construct_binary_tree(arr):
    if not arr:
        return None

    # Находим индекс максимального элемента в массиве
    max_index = find_max_index(arr)

    # Создаем корневой узел с максимальным элементом
    root = Node(arr[max_index])

    # Рекурсивно строим левое поддерево из элементов до максимального элемента
    root.left = construct_binary_tree(arr[:max_index])

    # Рекурсивно строим правое поддерево из элементов после максимального элемента
    root.right = construct_binary_tree(arr[max_index + 1:])

    return root

def find_max_index(arr):
    max_index = 0
    for i in range(1, len(arr)):
        if arr[i] > arr[max_index]:
            max_index = i
    return max_index

# Пример использования
arr = [i for i in range(100)]
root = construct_binary_tree(arr)

В этом примере мы используем класс Node для представления узлов бинарного дерева. Функция construct_binary_tree рекурсивно строит дерево, разделяя массив на левую и правую части относительно максимального элемента и строя поддеревья для каждой части.

Функция find_max_index ищет индекс максимального элемента в массиве, используя обычный цикл.

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