Бинарное дерево только массивов

Построить бинарное дерево из родительского массива

Дан целочисленный массив, представляющий двоичное дерево, такое, что отношение родитель-потомок определяется как (A[i], i) для каждого индекса i в массиве A , построить из него бинарное дерево. Значение корневого узла равно i если -1 присутствует в индексе i в массиве. Можно предположить, что входные данные, предоставленные программе, действительны.

• -1 присутствует в индексе 0, что означает, что корень бинарного дерева является узлом 0.
• 0 присутствует в индексах 1 и 2, что означает, что левый и правый потомки узла 0 — это 1 и 2.
• 1 присутствует в индексе 3, что означает, что левый или правый дочерний элемент узла 1 равен 3.
• 2 присутствует в индексах 4 и 5, что означает, что левый и правый потомки узла 2 — это 4 и 5.
• 4 присутствует в индексах 6 и 7, что означает, что левый и правый потомки узла 4 — это 6 и 7.

Соответствующее бинарное дерево:

Решение простое и эффективное – создайте n новые узлы дерева, каждый из которых имеет значения от 0 до n-1 , куда n — это размер массива, и сохранить их на карте или в массиве для быстрого поиска. Затем пройдите по данному родительскому массиву и постройте дерево, установив отношение родитель-потомок, определенное (A[i], i) для каждого индекса i в массиве A . Поскольку из одного входа можно сформировать несколько бинарных деревьев, решение должно построить любое из них. Решение всегда будет устанавливать левый дочерний узел для узла перед установкой его правого дочернего элемента.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Источник

13 Вопрос. Реализация деревьев с помощью массива.

В статической памяти дерево можно представить массивом, для которого определено понятие пустого элемента:

Рис.2. двоичное дерево представленное в виде массива

Вершины двоичного дерева располагаются в массиве следующим образом (см. рис.2.): если k – индекс вершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1); корень дерева находится в элементе с индексом 0 (при индексации в массиве от 1 до N индексы потомков k-ой вершины: 2k и 2k + 1, корень имеет индекс 1).

В динамической памяти дерево представляется иерархическим списком. Задать элемент двоичного дерева можно как элемент списка с тремя полями: два ссылочных поля, содержащие указатели на его левое ( L ) и правое ( R ) поддеревья, и информационное поле ( E ):

Определение типа элемента бинарного динамического дерева:

Здесь type – тип информационного поля (если информационное поле имеет сложную структуру, то type может быть типом — указатель на объект, содержащий значение элемента дерева).

Чтобы определить дерево как единую структуру, надо задать указатель на корень дерева:

Рис.3. Двоичное динамическое дерево

На рис.3 представлено двоичное динамическое дерево d в соответствии с определением типа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочное поле со значением равным пустому указателю (NULL).

14 Вопрос. Алгоритмы обходов бинарного дерева.

Обход дерева – это способ методичного исследования его узлов, при котором каждый узел проходится точно один раз. Полное прохождение динамического дерева дает линейную расстановку его узлов.

Возможны два способа прохождения бинарного дерева (если дерево не пусто):

• в глубину;
• в ширину.

Алгоритмы обхода в глубину Существует несколько способов обхода в глубину:

1. Прямой порядок (см. рис.4.а):
   1. попасть в корень;
   2. пройти в прямом порядке левое поддерево;
   3. пройти в прямом порядке правое поддерево.
2. Обратный порядок(см. рис.4.б):
   1. пройти в обратном порядке левое поддерево;
   2. пройти в обратном порядке правое поддерево;
   3. попасть в корень.
3. Симметричный порядок(см. рис.4.в):
   1. пройти в симметричном порядке левое поддерево;
   2. попасть в корень;
   3. пройти в симметричном порядке правое поддерево.

Рис.4. Способы обхода дерева в глубину Алгоритмы обхода в ширину Узлы дерева посещаются слева направо, уровень за уровнем вниз от корня (линейная расстановка узлов дерева, представленна на рис.5). Рис.5. Порядок обхода дерева в ширину

15 Вопрос. Добавление элемента в двоичное дерево.

Включение элемента в дерево. Операция заключается в добавлении листа (исключая сбалансированное дерево – включение элемента в сбалансированное дерево приводит, как правило, к его перестройке) в какое-то поддерево, если такого элемента нет в исходном дереве. При включении нового элемента в дерево поиска лист добавляется в то поддерево, в котором не нарушается отношение порядка; В двоичном дереве каждая вершина имеет не более двух потомков, обозначенных как левый ( left) и правый ( right). Кроме того, на данные, хранимые в вершинах дерева, вводится следующее правило упорядочения: значения вершин левого поддерева всегда меньше, а значения вершин правого поддерева — больше значения в текущей вершине. struct btree < int val; btree *left,*right; >; Свойства двоичного дерева позволяют применить в нем алгоритм поиска, аналогичный двоичному поиску в массиве. Каждое сравнение искомого значения и значения в вершине позволяет выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений. Эти алгоритмы являются линейно рекурсивными или циклическими.

Источник

Построить бинарное дерево из массива

Задан массив А = [1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0], где первый элемент — корень. Один ноль после элемента массива означает отсутствие наследника. Два нуля после элемента говорят о том, что он — лист. В итоге должно получится такое дерево: Вот мой код на Python, но проблема в том, что я не знаю что делать, когда элемент массива равен 0, поэтому в результате получаю неправильное дерево.

class Node: # Constructor to create a new node def __init__(self, data): self.root = data self.left = None self.right = None def put(self, data): if self.root: if data > self.root: if self.left is None: if data: self.left = Node(data) print(f"left = root = ") else: self.left = None else: self.left.put(data) if data < self.root: if self.right is None: if data: self.right = Node(data) print(f"right = root = ") else: self.right = None else: self.right.put(data) elif data: self.root = data if __name__ == '__main__': arr = [1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0] root = Node(arr[0]) for i in arr: root.put(arr) 

Получается что, right = 7 root = 10, хотя должно быть root = 4;
right = 2 root = 4, а должно быть root = 1;
и так далее
Как это можно исправить?

1 ответ 1

Ваше решение не разбирал, сделал по своему.

1. Начиная с текущего узла идём влево, добавляя новые узлы в левую ветку до тех пор, пока не встретим 0 . Это означает конец данной ветки, записываем 0 в поле left текущего (последнего) узла.
2. Так как поле left текущего узла уже закрыто, следующее значение можно поставить только в поле right . 2.1. Если значение == 0 , то заканчиваем и правую ветку. Пример: Так как поля left и right узла 6 использованы, возвращаемся в родительский узел 4 и продолжаем наполнение дерева с него. Переход на пункт 2. Если родительского узла нет, значит, достигли корня и добавлять больше некуда, можно вывести сообщение. 2.2. Если значение != 0 , то создаём новый узел и записываем его в поле right текущего узла. Переход на пункт 1.Пример:

class Node: def __init__(self, value): self.value = value self.left = None self.right = None self.parent = None class Tree: def __init__(self): self.root = None self.cur_node = None def add(self, value): if not self.root: self.root = Node(value) self.cur_node = self.root return if self.cur_node.left is None: if value != 0: next_node = Node(value) self.cur_node.left = next_node next_node.parent = self.cur_node self.cur_node = next_node else: self.cur_node.left = value elif self.cur_node.right is None: if value != 0: next_node = Node(value) self.cur_node.right = next_node next_node.parent = self.cur_node self.cur_node = next_node else: self.cur_node.right = value else: # Если оба дочерних узла заполнены (левый и правый), поднимаемся на уровень выше # и запускаем функцию add() ещё раз, с родителем в качестве cur_node if self.cur_node.parent: self.cur_node = self.cur_node.parent self.add(value) else: # Только один узел в дереве не имеет родителя - root # Значит, все узлы заняты, добавлять некуда print("Can't add") ### Два варианта формирования результата. ### С генераторами короче, с обычной рекурсией понятнее. #################### # Вариант 1: рекурсия с использованием генераторов # Возвращаемое значение - generator def as_generator(self, node): if node == 0: yield 0 else: yield node.value yield from self.as_generator(node.left) yield from self.as_generator(node.right) # Вариант 2: обычная рекурсия # Возвращаемое значение - list def as_list(self): lst = [] # dfs - deep first search (поиск в глубину) def dfs(node): if node == 0: lst.append(0) return lst.append(node.value) dfs(node.left) dfs(node.right) dfs(self.root) return lst lst = [1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0] tree = Tree() for item in lst: tree.add(item) # Печатаем дерево двумя вариантами print(list(tree.as_generator(tree.root))) print(tree.as_list()) 

[1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0] [1, 4, 6, 10, 0, 0, 0, 7, 0, 8, 0, 0, 2, 5, 0, 0, 3, 9, 0, 0, 0] 

Источник