我即将完成一个项目，该项目要求我们创建一个利用二叉树结构的字典类。然而，我卡在了如何实现一个打印出树中所有元素的方法上，因为我对二叉树没有太多经验，所以编码时相当困惑。
我正在尝试解决的方法是一个keys方法，它将遍历整个树并返回所有键的列表。我认识的某个人暗示我应该创建一个私有的辅助函数，递归遍历树并跟踪所有键。我想创建他所说的内容，但我不知道如何编写代码。有人能帮我编写出这个方法吗？如果能解决这个问题，我的项目基本上就完成了。
以下是我到目前为止的代码。[Key:Value]对是元组。我已经编写了它，并从教科书示例中得到了一些帮助，构建了你在这里看到的所有内容:
我正在尝试解决的方法是一个keys方法，它将遍历整个树并返回所有键的列表。我认识的某个人暗示我应该创建一个私有的辅助函数，递归遍历树并跟踪所有键。我想创建他所说的内容，但我不知道如何编写代码。有人能帮我编写出这个方法吗？如果能解决这个问题，我的项目基本上就完成了。
以下是我到目前为止的代码。[Key:Value]对是元组。我已经编写了它，并从教科书示例中得到了一些帮助，构建了你在这里看到的所有内容:
class DictWithTree:
def __init__(self):
self._element = None
self._left = None
self._right = None
self._size = 0
def isempty(self):
if self._element == None:
return True
return False
def __len__(self):
return self._size
def __contains__(self,key):
path = self._tracePath(key)
return path[-1]._size > 0
def _tracePath(self,key): # taken from the textbook example and modified
if len(self) == 0 or key == self._element[0]:
return [self]
elif len(key) < len(self._element[0]):
return [self] + self._left._tracePath(key)
else:
return [self] + self._right._tracePath(key)
def __getitem__(self,key):
if len(self) == 0:
raise KeyError(key)
elif key == self._element[0]:
return self._element[1]
elif key < self._element[0]:
return self._left[key]
elif key > self._element[0]:
return self._right[key]
else:
raise KeyError(key)
def __setitem__(self,key,value):
path = self._tracePath(key)
endOfPath = path[-1]
if endOfPath._element != None:
if endOfPath._element[0] == key:
endOfPath._element = key,value
if endOfPath._size == 0: # a new element
for location in path:
location._size += 1
endOfPath._element = key,value
endOfPath._left = DictWithTree()
endOfPath._right = DictWithTree()
def clear(self):
self._element = None
self._left = None
self._right = None
self._size = 0
def pop(self,key):
value = self[key]
self._remove(key)
return value
def popitem(self): # returns the 'last' item in the dictionary,
if self.isempty(): # (i.e. the largest key in the dictionary)
return KeyError("There are no keys in the dictionary")
elif self._right._element == None:
return self._element
else:
return self._right.popitem()
def _remove(self,key):
path = self._tracePath(key)
endOfPath = path[-1]
if endOfPath._size > 0:
for location in path:
location._size -= 1
if len(endOfPath._left) == 0:
endOfPath._promoteChild(endOfPath._right)
elif len(endOfPath._right) == 0:
endOfPath._promoteChild(endOfPath._left)
else:
endOfPath._element = endOfPath._left.pop()
def _promoteChild(self,child):
self._element = child._element
self._left = child._left
self._right = child._right