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

Пользователь

от roxanne.hauck , в категории: Python , 7 месяцев назад

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

Facebook Vk Ok Twitter LinkedIn Telegram Whatsapp

1 ответ

Пользователь

от jedidiah.brown , 7 месяцев назад

@roxanne.hauck 

Для сравнения двух бинарных деревьев без использования рекурсии на языке Python можно использовать алгоритм обхода дерева в ширину или алгоритм обхода дерева в глубину с использованием стека.


Ниже приведен пример алгоритма обхода дерева в ширину:

  1. Создайте две пустые очереди, одну для первого дерева и другую для второго дерева.
  2. Вставьте корневые узлы обоих деревьев в соответствующие очереди.
  3. Пока обе очереди не станут пустыми, повторяйте следующие шаги: Извлеките текущий узел из каждой очереди. Сравните значения текущих узлов. Если они не равны, верните False. Если значения текущих узлов равны, вставьте их левых и правых дочерних узлов (если они существуют) в соответствующие очереди.
  4. Если оба дерева пройдены и все значения узлов совпадают, верните True.


Ниже приведена реализация данного алгоритма на языке Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque

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

def compare_trees(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False

    queue1 = deque([root1])
    queue2 = deque([root2])

    while queue1 and queue2:
        curr1 = queue1.popleft()
        curr2 = queue2.popleft()

        if curr1.val != curr2.val:
            return False

        if curr1.left and curr2.left:
            queue1.append(curr1.left)
            queue2.append(curr2.left)
        elif curr1.left or curr2.left:
            return False

        if curr1.right and curr2.right:
            queue1.append(curr1.right)
            queue2.append(curr2.right)
        elif curr1.right or curr2.right:
            return False

    return not queue1 and not queue2


Пример использования:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Создание двух бинарных деревьев
root1 = TreeNode(1)
root1.left = TreeNode(2)
root1.right = TreeNode(3)

root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.right = TreeNode(3)

# Сравнение деревьев
result = compare_trees(root1, root2)
print(result)  # Вывод: True


В этом примере оба дерева содержат одинаковую структуру и значения узлов, поэтому функция compare_trees возвращает True.