我想在 python 中实现一个包含元素、左右子节点和父节点的二叉搜索树。
class BSTNode:
""" An internal node for a BST . """
def __init__(self, item):
""" Initialise a BSTNode on creation, with value==item. """
self._element = item
self._leftchild = None
self._rightchild = None
self._parent = None
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
node._leftchild.__str__()
s = str(node._element)
s+= ' '
elif node._rightchild:
node._rightchild.__str__()
s += str(node._element)
else:
return s
else:
return ''
def add(self, item):
node = self
if node:
if item <node._element :
if node._leftchild is None:
node._leftchild = BSTNode(item)
node._leftchild._parent = node
else:
node._leftchild.add(item)
elif item > node._element:
if node._rightchild is None:
node._rightchild = BSTNode(item)
node._rightchild._parent = node
else:
node._rightchild.add(item)
tree = BSTNode(3);
tree.add(7);
print(tree.__str__());
我写了这个程序,但是当我运行它时,它没有输出,但它应该输出 3 7(顺序是中序遍历)。有谁知道我做错了什么?
请您参考如下方法:
您的__str__ 方法不正确。具体来说,您调用左右 child 的 __str__() 但不对结果做任何事情。另请注意,一个节点可以有两个 左右子节点(if...elif 将只检查一个)。如果您点击了您的 if 或 elif block 之一,您也不会不返回 s。
您可以将其简化为:
def __str__(self):
node = self
if node != None:
s = str(node._element)
if node._leftchild:
s = node._leftchild.__str__() + s
if node._rightchild:
s += ' ' + node._rightchild.__str__()
return s
return ''
