按BST顺序返回较小的值
按BST顺序返回较小的值
提问于 2021-03-14 03:11:44
我正在尝试实现这个方法，BST的" smaller“，它按顺序返回树中小于给定项的值。
class BinarySearchTree:
def __init__(self, root: Optional[Any]) -> None:
if root is None:
self._root = None
self._left = None
self._right = None
else:
self._root = root
self._left = BinarySearchTree(None)
self._right = BinarySearchTree(None)
def is_empty(self) -> bool:
return self._root is None
def smaller(self, item: Any) -> List:
if self.is_empty():
return []
else:
return self._left.items() + [self._root] + self._right.items()到目前为止，" smaller“方法将按顺序返回树中的所有值，但我不确定如何检查这些值是否小于给定的项，以及如何仅返回列表中的值。
回答 1
Stack Overflow用户
发布于 2021-03-14 15:26:24
让我们为in-order-tree-walk方法编写伪代码，该方法按排序(按顺序)打印BST的键。
in-order-tree-walk(T, x)
if (T != NULL)
in-order-tree-walk(T.left, x)
print T's key
in-order-tree-walk(T.right, x)smaller方法具有与in-order-tree-walk完全相同的结构，除了它的附加条件，这使得它可以打印更小的键。smaller方法的伪代码如下所示
smaller(T, x)
if (T != NULL)
smaller(T.left, x)
if (T's key is less than x)
print T's key
smaller(T.right, x)我们说完了。smaller方法现在已完成。现在让我们看看您的实际实现。
您的代码按排序顺序打印BST的所有键，这取决于您实现它的方式。您在以下部分遇到了问题：
def smaller(self, item: Any) -> List:
if self.is_empty():
return []
else:
return self._left.items() + [self._root] + self._right.items()在return self._left.items() + [self._root] + self._right.items()中，您不会检查[self.root]是否小于item's value。你必须检查这一点，因为你限制了打印树的键，但在实现中你没有检查它。由于我不精通Python，所以我不能完成这一部分，但我认为您已经根据上面的解释了解了代码的问题所在。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/66617544
复制相关文章
相似问题
腾讯云开发者
