我创建了一个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.这直接转换为递归算法.在伪代码中:
def height(bst): if isempty(bst): return 0 else: return 1 + max(height(bst.left), height(bst.right))