питон-Реализовать и проверить следующий метод BST

Question

Реализовать и проверить следующий метод BST

Я работаю с этим кодом, чтобы реализовать двоичный класс дерева узлов и двоичный класс дерева, чтобы проверить, являются ли два BSTs идентичны. Метод рекурсивный и требует вспомогательной функции.

Это то, что у меня есть до сих пор, мне трудно писать основную программу. Может кто-то, пожалуйста, помогите мне.

def is_identical(self, rs): 

    identical = self._is_identical_aux(self._root, rs._root) 
    return identical 

def _is_identical_aux(self, node1, node2): 

    result = True 
    if node1._value != node2._value: 
     result = False 
    if node1._left is not None and node2._left is not None and result == True: 
     result = self._is_identical_aux(node1._left, node2._left) 
    if node1.right is not None and node2._right is not None and result == True: 
     result = self._is_identical_aux(node1._right, node2._right) 
    return result 

Answer 1

Ваш код выглядит неправильно. Пожалуйста, попробуйте следующий код.

def _is_identical_aux(self, node1, node2): 
    if node1 is None and node2 is None: 
     return True 
    if node1 is not None and node2 is not None: 
     return ((node1._value == node2._value) and 
       _is_identical_aux(node1.left, node2.left) and 
       _is_identical_aux(node1.right, node2.right)) 
    return False 

Вот тест:

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

def _is_identical_aux(node1, node2): 
    if node1 is None and node2 is None: 
     return True 
    if node1 is not None and node2 is not None: 
     return ((node1._value == node2._value) and 
       _is_identical_aux(node1.left, node2.left) and 
       _is_identical_aux(node1.right, node2.right)) 
    return False 

root1 = Node(7) 
root1.left = Node(3) 
root1.right = Node(2) 
root1.left.left = Node(123) 
root1.left.right = Node(231) 
root1.right.left = Node(9) 
root1.right.right = Node(5) 

root2 = Node(7) 
root2.left = Node(3) 
root2.right = Node(2) 
root2.left.left = Node(123) 
root2.left.right = Node(231) 
root2.right.left = Node(9) 
root2.right.right = Node(5) 

root3 = Node(7) 
root3.left = Node(3) 
root3.right = Node(2) 

if _is_identical_aux(root1, root2): 
    print "Both trees are identical" 
else: 
    print "Trees are not identical" 

if _is_identical_aux(root1, root3): 
    print "Both trees are identical" 
else: 
    print "Trees are not identical" 

Результаты:

Both trees are identical 
Trees are not identical