这是我第一次编码二进制搜索树。
我从网上大量参考,并尝试了一些代码。
想知道
为什么当我尝试将其输出时,这两个代码无法正常工作并给我同样的错误
def height(self,node):
if node is None:
return 0
else:
return max(height(node.left), height(node.right)) + 1
def depth(self, count=0):
if self.root is None:
return count
return max(depth(self.root.left, count+1),
depth(self.root.right, count+1))
两者都有相同的错误说明
"global name height is not define"
"global name depth is not define"
我不知道为什么,因为我在调用相同的函数
完整的代码:
class BST:
root=None
def put(self, key, val):
self.root = self.put2(self.root, key, val)
def put2(self, node, key, val):
if node is None:
#key is not in tree, create node and return node to parent
return Node(key, val)
if key < node.key:
# key is in left subtree
node.left = self.put2(node.left, key, val)
elif key > node.key:
# key is in right subtree
node.right = self.put2(node.right, key, val)
else:
node.val = val
# node.count = 1 + self.size2(node.left) + self.size2(node.right)
return node
# draw the graph
def drawTree(self, filename):
# create an empty undirected graph
G=pgv.AGraph('graph myGraph {}')
# create queue for breadth first search
q = deque([self.root])
# breadth first search traversal of the tree
while len(q) <> 0:
node = q.popleft()
G.add_node(node, label=node.key+":"+str(node.val))
if node.left is not None:
# draw the left node and edge
G.add_node(node.left, label=node.left.key+":"+str(node.left.val))
G.add_edge(node, node.left)
q.append(node.left)
if node.right is not None:
# draw the right node and edge
G.add_node(node.right, label=node.right.key+":"+str(node.right.val))
G.add_edge(node, node.right)
q.append(node.right)
# render graph into PNG file
G.draw(filename,prog='dot')
os.startfile(filename)
def createTree(self):
self.put("F",6)
self.put("D",4)
self.put("C",3)
self.put("B",2)
self.put("A",1)
self.put("E",5)
self.put("I",9)
self.put("G",7)
self.put("H",8)
self.put("J",10)
def height(self,node):
if node is None:
return 0
else:
return max(height(node.left), height(node.right)) + 1
def depth(self, count=0):
if self.root is None:
return count
return max(depth(self.root.left, count+1),
depth(self.root.right, count+1))
class Node:
left = None
right = None
key = 0
val = 0
def __init__(self, key, val):
self.key = key
self.val = val
bst = BST()
bst.createTree()
bst.drawTree("demo.png")
print bst.get("B")
##print bst.size("D")
##print bst.size("F")
print bst.depth("B")
最佳答案
Python不会自动将代码范围限制到本地类:
return max(self.height(node.left), self.height(node.right)) + 1
和
return max(self.depth(self.root.left, count+1),
self.depth(self.root.right, count+1))