istomina_sofia

питон лаба3

Dec 20th, 2022 (edited)
1,157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.03 KB | None | 0 0
  1. class node:
  2.     def __init__(self, data=None, left=None, right=None):
  3.         self.data = data
  4.         self.left = left
  5.         self.right = right
  6.  
  7.     def __str__(self):
  8.         return 'Node ['+str(self.data)+']'
  9.  
  10.  
  11. class Tree:
  12.     def __init__(self, root=None):
  13.         self.root = root
  14.  
  15.     def add_node(self, _data, _node):
  16.         if self.root is None:
  17.             self.root = _data
  18.         elif _node.data < _data:
  19.             if _node.left is None:
  20.                 _node.left = node(_data)
  21.             else:
  22.                 self.add_node(_data, _node.left)
  23.         else:
  24.             if _node.right is None:
  25.                 _node.right = node(_data)
  26.             else:
  27.                 self.add_node(_data, _node.right)
  28.  
  29.     def mirror_tree(self, _node):
  30.         if _node.left and _node.right:
  31.             _node.left, _node.right = _node.right, _node.left
  32.             self.mirror_tree(_node.right)
  33.             self.mirror_tree(_node.left)
  34.         else:
  35.             if _node.left is None and _node.right:
  36.                 return self.mirror_tree(_node.right)
  37.             if _node.right is None and _node.left:
  38.                 return self.mirror_tree(_node.left)
  39.  
  40.     def mirror_to(self, tree):
  41.         self.mirror_tree(self.root)
  42.         if self.root is None and tree.root \
  43.                 or self.root and tree.root is None:
  44.             return False
  45.         if self.root is None and tree.root is None:
  46.             return True
  47.         return self.sub_mirror_to(tree, self.root, tree.root)
  48.  
  49.     def sub_mirror_to(self, tree, node1, node2):
  50.         if node1.left and node2.left:
  51.             self.sub_mirror_to(tree, node1.left, node2.left)
  52.         elif node1.left and node2.left is None \
  53.                 or node1.left is None and node2.left:
  54.             return False
  55.         elif node1.right and node2.right:
  56.             self.sub_mirror_to(tree, node1.right, node2.right)
  57.         elif node1.right and node2.right is None \
  58.                 or node1.right is None and node2.right:
  59.             return False
  60.         if node1.data == self.root.data:
  61.             return True
  62.  
  63. if __name__ == '__main__':
  64.  
  65.     a1 = list(map(int, input("Введите элементы 1 бинарного дерева: ").split()))
  66.     a1_root = int(input("Введите корневой элемент 1 дерева: "))
  67.     a1.pop(a1.index(a1_root))
  68.     a2 = list(map(int, input("Введите элементы 2 бинарного дерева: ").split()))
  69.     a2_root = int(input("Введите корневой элемент 2 дерева: "))
  70.     a2.pop(a2.index(a2_root))
  71.  
  72.     a1_root_node = node(a1_root)
  73.     tree1 = Tree(a1_root_node)
  74.     a2_root_node = node(a2_root)
  75.     tree2 = Tree(a2_root_node)
  76.  
  77.     for a in a1:
  78.         tree1.add_node(a, tree1.root)
  79.     for a in a2:
  80.         tree2.add_node(a, tree2.root)
  81.  
  82.     print()
  83.  
  84.     if tree1.mirror_to(tree2):
  85.         print("Деревья зеркально подобны")
  86.     else:
  87.         print("Деревья не являются зеркально подобны")
  88.  
Advertisement
Add Comment
Please, Sign In to add comment