Нужно написать функцию, которая в параметрах принимает два корневых узла бинарного дерева, а на выходе возвращает True, если бинарные деревья равны и False, если они не равны. Функция должна быть БЕЗ РЕКУРСИЙ. Прошу помогите, пожалуйста, искал на просторах интернета, не смог найти НЕ рекурсивный способ.
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 - не эквивалентны
-
Значения узлов, конечно, могут быть любыми. Просто для наглядности использовались строки эквивалентные расположению узла.– GrAnd9 мая 2021 в 12:33
-
Интересное, решение, я по итогу пришёл к тому же выводу, что сравню какие-нибудь списки, а именно, я просто нашёл нерекурсивный алгоритм печати дерева, и вместо print, делал append значения узла в результирующий список, по итогу потом просто сравнивал два списка. Но всё равно спасибо большое. 11 мая 2021 в 15:43
-
@kiri11-mi1 Заметте, что сохранять только значения в узлах - не достаточно для сравнения. Потому как два дерева могут иметь разную структуру и при этом хранить в себе абсолютно те же значения. Простейший пример: дерево, у которого ветка только влево, и дерево, у которого ветка только вправо. Но такие дереевья считаются не эквивалентными, хотя распечатка сдержимого обойх деревьев по этому алгоритму может дать одно и то же. Поэтому я, кроме самих значений, сохраняю ещё и путь до узла.– GrAnd11 мая 2021 в 16:37
class Node: def __init__(self, value): self.left = None self.right = None self.value = value