当二叉搜索树中存在值时,实例变量返回 None
Instance variable returning None when value is present in Binary search tree
我正在重新彻底学习我的数据结构,我必须实现二叉搜索树。我有一个带有相关字段的节点 class 和一个实现树的树 class。我有两种方法 - insert
和 get
insert 按预期工作,但是 get
方法 returns None 在访问除根以外的任何节点的值时。
使用 pycharm 的调试器遍历代码显示已到达特定节点,但返回的值仍为 None。
这是节点class
class Node:
def __init__(self, key, value):
self.right = None
self.left = None
self.key = key
self.value = value
这是整个 BinarySearchTree class
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def insert(self, key, value):
self.size += 1
if self.root is None:
self.root = Node(key, value)
else:
self.insert_with_node(self.root, key, value)
def insert_with_node(self, node, key, value):
if node.left is None and node.right is None:
if node.key > key:
node.left = Node(key, value)
else:
node.right = Node(key, value)
else:
if node.key > key:
if node.left is not None:
self.insert_with_node(node.left, key, value)
else:
node.left = Node(key, value)
else:
if node.right is not None:
self.insert_with_node(node.right, key, value)
else:
node.right = Node(key, value)
def get(self, key):
if self.root.key == key:
return self.root.value
else:
return self.get_with_node(self.root, key)
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
self.get_with_node(node.right, key)
编辑:添加测试代码和控制台输出:
def main():
t = BinarySearchTree()
t.insert(1, "g")
t.insert(5, "qa")
t.insert(3, "ac")
t.insert(6, "cva")
t.insert(12, "as")
t.printTree(t.root)
print(t.get(3))
输出:
C:\Python34\python.exe C:/Users/home/PycharmProjects/DSandA/BinarySearchTree.py
1 : g
3 : ac
5 : qa
6 : cva
12 : as
None
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
self.get_with_node(node.right, key)
当一个函数递归调用自身时,如果你想要返回任何东西,你仍然需要使用return
语句。
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
return self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
return self.get_with_node(node.right, key)
我正在重新彻底学习我的数据结构,我必须实现二叉搜索树。我有一个带有相关字段的节点 class 和一个实现树的树 class。我有两种方法 - insert
和 get
insert 按预期工作,但是 get
方法 returns None 在访问除根以外的任何节点的值时。
使用 pycharm 的调试器遍历代码显示已到达特定节点,但返回的值仍为 None。
这是节点class
class Node:
def __init__(self, key, value):
self.right = None
self.left = None
self.key = key
self.value = value
这是整个 BinarySearchTree class
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def insert(self, key, value):
self.size += 1
if self.root is None:
self.root = Node(key, value)
else:
self.insert_with_node(self.root, key, value)
def insert_with_node(self, node, key, value):
if node.left is None and node.right is None:
if node.key > key:
node.left = Node(key, value)
else:
node.right = Node(key, value)
else:
if node.key > key:
if node.left is not None:
self.insert_with_node(node.left, key, value)
else:
node.left = Node(key, value)
else:
if node.right is not None:
self.insert_with_node(node.right, key, value)
else:
node.right = Node(key, value)
def get(self, key):
if self.root.key == key:
return self.root.value
else:
return self.get_with_node(self.root, key)
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
self.get_with_node(node.right, key)
编辑:添加测试代码和控制台输出:
def main():
t = BinarySearchTree()
t.insert(1, "g")
t.insert(5, "qa")
t.insert(3, "ac")
t.insert(6, "cva")
t.insert(12, "as")
t.printTree(t.root)
print(t.get(3))
输出:
C:\Python34\python.exe C:/Users/home/PycharmProjects/DSandA/BinarySearchTree.py
1 : g
3 : ac
5 : qa
6 : cva
12 : as
None
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
self.get_with_node(node.right, key)
当一个函数递归调用自身时,如果你想要返回任何东西,你仍然需要使用return
语句。
def get_with_node(self, node, key):
if node.key > key:
if node.left.key == key:
return node.left.value
else:
return self.get_with_node(node.left, key)
else:
if node.right.key == key:
return node.right.value
else:
return self.get_with_node(node.right, key)