Как сделать сравнение двух бинарных деревьев без рекурсии на языке Python?

Question

Нужно написать функцию, которая в параметрах принимает два корневых узла бинарного дерева, а на выходе возвращает True, если бинарные деревья равны и False, если они не равны. Функция должна быть БЕЗ РЕКУРСИЙ. Прошу помогите, пожалуйста, искал на просторах интернета, не смог найти НЕ рекурсивный способ.

Answer 1

Предлагаю преобразовать дерево в список, содержащий пары ("путь_до_узла", "значение"), и потом уже сравнивать списки обычным способом.

Существует довольно простой алгоритм обхода дерева "по левой стенке" используя стек:

Создаём пустой стек
Инициализируем текущий узел узлом, который находится в корне дерева
Добавляем текущий узел в стек и устанавливаем текущий узел на его левый подузел до тех пор пока не достигнем конца левой ветки (т.е. текущий узел будет равен None)
Если текущий узел равен None и стек не пустой, то

а. Извлекаем узел из стека

б. Обрабатываем его как нам надо (в вашем случае запоминаем его в списке) и устанавливаем текущий узел на его правый подузел

в. Возвращаемся на шаг №3
Если текущий узел равен None и стек пуст - то всё дерево обработано

Ну и код:

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

def tree_to_list(tree_root):
    current_node = tree_root
    stack = []
    path  = ""
    resulted_list = []
     
    while True:
        # идём по левой стороне дерева до конца
        if current_node != None:
            # сохраняем промежуточный узел и путь до него в стеке
            stack.append((path, current_node))
            current_node = current_node.left
            # обновляем путь до узла (идём влево 'L')
            path += 'L'
        # постепенно возвращаемся по стеку и идём вправо
        # чтобы затем опять пойти по левой стороне до конца
        elif stack:
            path, current_node = stack.pop()
            # запоминаем значение, которое хранит узел, и путь до него 
            # в результируещий список, т.к. мы его полностью обработали
            # (сходили влево и теперь идём вправо)
            resulted_list.append((path, current_node.value))
            current_node = current_node.right
            # не забываем трекать путь до узла (идём вправо 'R')
            path += "R"
        else:
            # обошли всё дерево, т.к. не обработанных узлов 
            # больше не осталось и стек тоже пуст
            break

    return resulted_list

def are_trees_equal(tree_root1, tree_root2):
    return tree_to_list(tree_root1) == tree_to_list(tree_root2)

#======================================================================
# тесты
tree1 = Node("root")
tree1.left                  = Node("L")
tree1.right                 = Node("R")
tree1.left.left             = Node("L-L")
tree1.left.left.right       = Node("L-L-R")
tree1.left.right            = Node("L-R")
tree1.left.right.left       = Node("L-R-L")
tree1.right.left            = Node("R-L")
tree1.right.left.left       = Node("R-L-L")

from copy import deepcopy

tree2 = deepcopy(tree1)
tree3 = deepcopy(tree1)
tree3.left.right.value = "another_value"
tree4 = deepcopy(tree1)
tree4.left.left = None

lst1 = tree_to_list(tree1)
lst2 = tree_to_list(tree2)
lst3 = tree_to_list(tree3)
lst4 = tree_to_list(tree4)
print("tree1 в виде list =", lst1)
print("tree2 в виде list =", lst2)
print("tree3 в виде list =", lst3)
print("tree4 в виде list =", lst4)

print("tree1 и tree2 -", "эквивалентны" if are_trees_equal(tree1, tree2) else "не эквивалентны")
print("tree1 и tree3 -", "эквивалентны" if are_trees_equal(tree1, tree3) else "не эквивалентны")
print("tree1 и tree4 -", "эквивалентны" if are_trees_equal(tree1, tree4) else "не эквивалентны")

Ну и результат:

D:\Programming\Python>python cmp_trees.py
tree1 в виде list = [('LL', 'L-L'), ('LLR', 'L-L-R'), ('L', 'L'), ('LRL', 'L-R-L'), ('LR', 'L-R'), ('', 'root'), ('RLL', 'R-L-L'), ('RL', 'R-L'), ('R', 'R')]
tree2 в виде list = [('LL', 'L-L'), ('LLR', 'L-L-R'), ('L', 'L'), ('LRL', 'L-R-L'), ('LR', 'L-R'), ('', 'root'), ('RLL', 'R-L-L'), ('RL', 'R-L'), ('R', 'R')]
tree3 в виде list = [('LL', 'L-L'), ('LLR', 'L-L-R'), ('L', 'L'), ('LRL', 'L-R-L'), ('LR', 'another_value'), ('', 'root'), ('RLL', 'R-L-L'), ('RL', 'R-L'), ('R', 'R')]
tree4 в виде list = [('L', 'L'), ('LRL', 'L-R-L'), ('LR', 'L-R'), ('', 'root'), ('RLL', 'R-L-L'), ('RL', 'R-L'), ('R', 'R')]
tree1 и tree2 - эквивалентны
tree1 и tree3 - не эквивалентны
tree1 и tree4 - не эквивалентны

БЛОГ НА HUSL

Как сделать сравнение двух бинарных деревьев без рекурсии на языке Python?

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