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

Question

Задан массив А = [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 = {data} root = {self.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 = {data} root = {self.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;
и так далее
Как это можно исправить?

Answer 1

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

Алгоритм:

Начиная с текущего узла идём влево, добавляя новые узлы в левую ветку до тех пор, пока не встретим 0. Это означает конец данной ветки, записываем 0 в поле left текущего (последнего) узла.
Так как поле 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())

Output

[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]

БЛОГ НА HUSL

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

Ответы (1 шт):