<p>我创建了一个BST,现在我想找到BST的高度。</p>
<p>下面是我构造<strong>BST的代码</p>
<pre><code>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
</code></pre>
<p>我有一个数字列表(<code>[2,4,6,3,190,1,56 and so on]</code>),通过它构造这个BST。</p>
<p>现在我想找到创建的BST的高度。我该怎么做?</p>
<p><strong>编辑</strong></p>
<p>根据我所提供的解决方案:</p>
<pre><code>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))
</code></pre>
<p>也不管用。它会弹出一个错误,说<code>BST instance has no attribute 'left'</code></p>