Python Object не имеет ошибки атрибута

Question

class EmptyMap(): 
    """ 
    EmptyMap has no slots 
    """ 
    __slots__ =() 

class NonEmptyMap(): 
    """ 
    Has slots of left, key, value, and right. 
    """ 
    __slots__ = ('left', 'key', 'value', 'right') 

def mkEmptyMap(): 
    """ 
    Is a function that takes no arguments and returns an instance of EmptyMap 
    """ 
    return EmptyMap() 

def mkNonEmptyMap(left, key, value, right): 
    """ 
    Is a function that takes a map, a key, a value, and another map, 
    and returns an instance of NonEmptyMap. This function merely initializes the slots; 
    it is possible to use this function to create trees that are not binary search trees. 
    """ 
    nonEmptyMap = NonEmptyMap() 
    nonEmptyMap.left = left 
    nonEmptyMap.key = key 
    nonEmptyMap.value = value 
    nonEmptyMap.right = right 
    return nonEmptyMap 

def mapInsert(key, value, node): 
    """ 
    Is a function that takes a key, a value, and a map, and returns an instance 
    of NonEmptyMap. Further, the map that is returned is a binary search tree based 
    on the keys. The function inserts the key-value pair into the correct position in the 
    map. The map returned need not be balanced. Before coding, review the binary 
    search tree definition and the structurally recursive design pattern, and determine 
    what the function should look like for maps. If the key already exists, the new value 
    should replace the old value. 
    """ 
    if isinstance(node, EmptyMap): 
     return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap()) 
    else: 
     if key > node.key: 
      node.right = mapInsert(key, value, node.right) 
      return node.right 
     elif key < node.key: 
      node.left = mapInsert(key, value, node.left) 
      return node.left 
     elif key == node.key: 
      node.value = value 
      return mapInsert(key, value, node) 
     else: 
      raise TypeError("Bad Tree Map") 

def mapToString(node): 
    """ 
    Is a function that takes a map, and returns a string that represents the 
    map. Before coding, review the structurally recursive design pattern, and determine 
    how to adapt it for maps. An EmptyMap is represented as ’ ’. For an instance of 
    NonEmptyMap, the left sub-tree appears on the left, and the right sub-tree appears 
    on the right. 
    """ 
    if isinstance(node, EmptyMap): 
     return '_' 
    elif isinstance(node, NonEmptyMap): 
     return '(' + mapToString(node.left) + ',' + str(node.key) + '->' + str(node.value) + ',' + mapToString(node.right)+ ')' 
    else: 
     raise TypeError("Not a Binary Tree") 

def mapSearch(key, node): 
    """ 
    Is a function that takes a key and a map, and returns the value associated 
    with the key or None if the key is not there. Before coding, review the binary search 
    tree definition and the structurally recursive design pattern, and determine how it 
    should look for maps. 
    """ 
    if isinstance(node, EmptyMap): 
     return 'None' 
    elif isinstance(node, NonEmptyMap): 
     if key == node.key: 
      return str(node.value) 
     elif key < node.key: 
      return mapSearch(key, node.left) 
     elif key > node.key: 
      return mapSearch(key, node.right) 
    else: 
     raise TypeError("Not a Binary Tree") 

def main(): 
    smallMap = mapInsert(\ 
     'one',\ 
     1,\ 
     mapInsert(\ 
      'two',\ 
      2,\ 
      mapInsert(\ 
       'three',\ 
       3,\ 
       mkEmptyMap()))) 

    print(smallMap.key) 
    print(smallMap.left.key) 
    print(smallMap.right.key) 

main() 

Когда я запускаю программу, у меня есть синтаксис, который я понятия не имею, что я делаю неправильно. Я уверен, что у emptymap есть объект, который находится в функции mkNonEmptyMap. Это моя домашняя проблема.

Карта - это структура данных, которая связывает значения с ключами. Можно найти конкретный ключ для определения связанного с ним значения. Например, значение 3 может быть связано с ключом «три».

one 
Traceback (most recent call last): 
    File "/Users/USER/Desktop/test.py", line 113, in <module> 
    main() 
    File "/Users/USER/Desktop/test.py", line 110, in main 
    print(smallMap.left.key) 
AttributeError: 'EmptyMap' object has no attribute 'key' 

Answer 1

Если вы посмотрите на то, что в smallMap, его left и right оба EmptyMap s. Итак, конечно smallMap.left.key не собирается работать - EmptyMap s не имеет key s.

Итак, почему это неправильно? Ну, давайте разложим это выражение монстра на шаги и посмотрим, где он пойдет не так:

>>> empty = mkEmptyMap() 
>>> mapToString(empty) 
'_' 
>>> three = mapInsert('three', 3, mkEmptyMap()) 
>>> mapToString(three) 
'(_,three->3,_)' 
>>> two = mapInsert('two', 2, three) 
>>> mapToString(two) 
(_,two->2,_) 

Есть проблема. Объект two не имеет ни левого, ни правого. Как насчет three?

>>> mapToString(three) 
(_,three->3,(_,two->2,_)) 

ОК, так что у нас есть действующий сбалансированное дерево, но это не в two объекта, возвращенного mapInsert, это в three объект, который вы передаваемым в mapInsert (что ваша первоначальная программа даже не сохраняя ссылка).

Итак, почему это происходит? Это верно? Это зависит от вашего дизайна. Если вы хотите изменить ваши аргументы как это, это вполне разумно сделать (хотя я подозреваю, что это не то, чего действительно хотел ваш учитель, - любой, кто пытается заставить вас написать ML на Python, похоже, что это, вероятно, потребует использования не мутирующих алгоритмов ...). Но тогда вам нужно всегда возвращать корневой узел. Ваша функция явно пытается вернуть вновь созданный узел, является ли он корнем или нет. Итак, просто исправьте это:

if key > node.key: 
     node.right = mapInsert(key, value, node.right) 
     return node # not node.right 

А также для двух других случаев. (Я не уверен, почему вы пытались называть себя рекурсивно в случае с ==.)

Если вы это сделаете, код больше не будет иметь ошибки.

Это не похоже на правильное балансирование дерева, но это следующая проблема для вас.