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 はキー「three」に関連付けることができます。
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'