我创建了一个BST,现在我想找到BST的高度。
下面是我构造BST的代码
class Node:
'''represents a new node in the BST'''
def __init__(self,key):
self.key=key
self.disconnect()
def disconnect(self):
self.left=None;
self.right=None;
self.parent=None;
def __str__(self):
return 'node with kay %s'%self.key
class BST:
def __init__(self):
self.root=None
def insert(self,t):
'''inserts a new element into the tree'''
if self.root is None:
self.root = Node(t)
else:
self._do_insert(self.root,t)
def _do_insert(self,parent,t):
if t > parent.key:
if parent.left is None:
parent.left = Node(t)
else:
self._do_insert(parent.left,t)
elif t < parent.key:
if parent.right is None:
parent.right = Node(t)
else:
self._do_insert(parent.right,t)
else:
# raise a KeyError or something appropriate?
pass
我有一个数字列表([2,4,6,3,190,1,56 and so on]
),通过它构造这个BST。
现在我想找到创建的BST的高度。我该怎么做?
编辑
根据我所提供的解决方案:
def create_bst(values):
'''Creates a BST and returns the BST created object'''
BSTobj = BST()
for i in values:
BSTobj.insert(i)
return BSTobj
def height_of_BST(bst):
'''Returns the height of the BST created'''
if bst == None: return 0
else: return 1 + max(height_of_BST(bst.left), height_of_BST(bst.right))
print height_of_BST(create_bst(unique_values))
也不管用。它会弹出一个错误,说BST instance has no attribute 'left'
非空二叉搜索树的高度是其最高子树高度的1+,如果没有子树,则仅为1。这直接转化为递归算法。在伪代码中:
类中的BST实际上存储在BST.root而不是BST中。您需要修改代码以查看BST.root而不是BST
尝试:
这定义了一个helper函数,它执行实际的工作,但允许您只调用BST对象的height。将来,您可能只想拥有一个
Node
类,因为您的BST类基本上只是root
值的包装器。可以使用has attr检查对象是否具有attr,如果没有,则转到树的末尾
相关问题 更多 >
编程相关推荐