Python. Двоичное дерево

Question

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

class TreeNode:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None


    def insert(self, key):
        if self.key == None:
            self.key = key
        elif self.left == None:
            self.left = TreeNode(key)
        elif self.right == None:
            self.right = TreeNode(key)
        else:
            if type(self.left.left) != 'TreeNode':
                node = self.left
                node.left = TreeNode()
                node.left.insert(key)



tree = TreeNode()
tree.insert(9)
tree.insert(17)
tree.insert(4)
tree.insert(3)
tree.insert(6)
print(tree.key)
print(tree.left.key)
print(tree.right.key)
print(tree.left.left.key)
print(tree.left.left.left.key)

Answer 1

Вот вариант на рекурсии.
Сначала, сравнив добавляемое значение с текущим, надо решить куда идти - налево или направо. Ну а потом, если там None, то добавляем новый узел. Иначе проваливаемся вглубь (вызываем insert у дочернего элемента) и там всё повторяется сначала. Вроде ничего сложного.

class TreeNode:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None

    def __str__(self):
        return f"TreeNode({self.key})"

    def insert(self, key):
        if self.key is None:
            self.key = key
            return
        
        if key < self.key:
            if self.left is None:
                self.left = TreeNode(key)
            else:
                self.left.insert(key)
        elif key > self.key:
            if self.right is None:
                self.right = TreeNode(key)
            else:
                self.right.insert(key)
        else:
            raise ValueError(f"Key {key} already exists")
    
    def print_hierarchy(self, dir="root", level=0):
        print(f"[{dir}] #{level} = {self.key} | left = {self.left} | right = {self.right}")
        if self.left  is not None: self.left.print_hierarchy("left", level+1)
        if self.right is not None: self.right.print_hierarchy("right", level+1)


tree = TreeNode()
tree.insert(9)
tree.insert(17)
tree.insert(4)
tree.insert(3)
tree.insert(6)
tree.print_hierarchy()
tree.insert(3) # exception

[root] #0 = 9 | left = TreeNode(4) | right = TreeNode(17)
[left] #1 = 4 | left = TreeNode(3) | right = TreeNode(6)
[left] #2 = 3 | left = None | right = None
[right] #2 = 6 | left = None | right = None
[right] #1 = 17 | left = None | right = None
ValueError: Key 3 already exists

Или вариант добавления без рекурсии, простым проходом по дереву в цикле.

    def insert(self, key):
        if self.key is None:
            self.key = key
            return
        
        current = self
        while True:
            if key < current.key:
                if current.left is None:
                    current.left = TreeNode(key)
                    break
                current = current.left
            elif key > current.key:
                if current.right is None:
                    current.right = TreeNode(key)
                    break
                current = current.right
            else:
                raise ValueError(f"Key {key} already exists")

БЛОГ НА HUSL

Python. Двоичное дерево

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