Python 中二叉搜索树的广度优先搜索
Breadth First Search on a Binary Search Tree in Python
我一直致力于构建不同的数据类型并对其应用各种排序算法。我目前正在对二叉搜索树进行 breadth-first 搜索。我的代码与您在网上随处可见的代码几乎相同,但它始终将我的值打印两次,我现在感到困惑。任何指导将不胜感激。
# Remove (dequeue) function for Queue class
def remove(self, current=''):
if current == '':
current = self.tail
# start looping/recurring to find the front of the queue
if current.next:
if current.next.next:
current = current.next
return self.remove(current)
# side note - I'm doubting the usefulness of recursion here
else:
n = current.next.value
current.next = None
self.size -= 1
return n
elif current == self.tail:
if current.value:
n = current.value
current = None
self.size -= 1
# print("Queue is now empty - returning final number")
return n
else:
return "Queue is already empty."
else:
raise ValueError("mind boggling error...") #never raised
# Add (enqueue) function for my queue:
def add(self,value):
n = Node(value) # create the new node we're adding
n.next = self.tail # point the new node to link to the old tail
self.tail = n # now have the tail point to the new node
self.size += 1
# Breadth First Search function for the Binary Search Tree
def bfs(self):
"""
This is currently VERY inefficient from a memory
standpoint, as it adds a subtree for EACH node...right?
or is it just the names/addresses of the objects being stored in
each node, and each node is still only in the same memory location?
"""
queue = Queue()
queue.add(self)
while queue.size > 0:
current = queue.remove()
print(current.value)
if current.left_child:
queue.add(current.left_child)
if current.right_child:
queue.add(current.right_child)
# how I typically test:
bst = BinarySearchTree(50)
for i in range(1,10):
bst.insert_node(i*4)
bst.bfs()
示例输出:
25
25
4个
28
4个
28
8个
32
8个
32
12
36
12
36
16
16
20
20
24
看到它自己打印根节点两次,然后 children 节点成对打印两次,一个接一个,这表明它在按正确顺序级别进行的意义上工作水平,但它同时打印左和右 child,直到没有,正如可以看到的那样,到最后它开始打印两次 back-to-back 而不是成对打印,并且它在打印 24 之前被切断第二次。
我还应该声明我对在我的队列函数中使用 python 列表没有兴趣。本练习的重点是手动构建我的数据结构 w/o 帮助使用 pre-built 超出 ints/strings 的数据结构。
完整文件可在我的 GitHub https://github.com/GhostlyMowgli/data_structures_plus
上找到
再次强调,如有任何帮助,我们将不胜感激。
您的问题出在您的 queue.remove
功能上,下面是修复代码,在违规行 (219)
上带有标记
def remove(self, current=''):
if current == '':
current = self.tail
if current.next:
if current.next.next:
current = current.next
return self.remove(current) # recursive - keep going to front
else:
n = current.next.value
current.next = None
self.size -= 1
return n
elif current == self.tail:
# now I'm wondering if this is even smart
# shouldn't I be checking if current is a None type?!?!
if current.value:
n = current.value
self.tail = None # HERE!!!! NOT current = None
self.size -= 1
# print("Queue is now empty - returning final number")
return n
else:
return "Queue is already empty."
else:
raise ValueError("mind boggling coding error...")
我一直致力于构建不同的数据类型并对其应用各种排序算法。我目前正在对二叉搜索树进行 breadth-first 搜索。我的代码与您在网上随处可见的代码几乎相同,但它始终将我的值打印两次,我现在感到困惑。任何指导将不胜感激。
# Remove (dequeue) function for Queue class
def remove(self, current=''):
if current == '':
current = self.tail
# start looping/recurring to find the front of the queue
if current.next:
if current.next.next:
current = current.next
return self.remove(current)
# side note - I'm doubting the usefulness of recursion here
else:
n = current.next.value
current.next = None
self.size -= 1
return n
elif current == self.tail:
if current.value:
n = current.value
current = None
self.size -= 1
# print("Queue is now empty - returning final number")
return n
else:
return "Queue is already empty."
else:
raise ValueError("mind boggling error...") #never raised
# Add (enqueue) function for my queue:
def add(self,value):
n = Node(value) # create the new node we're adding
n.next = self.tail # point the new node to link to the old tail
self.tail = n # now have the tail point to the new node
self.size += 1
# Breadth First Search function for the Binary Search Tree
def bfs(self):
"""
This is currently VERY inefficient from a memory
standpoint, as it adds a subtree for EACH node...right?
or is it just the names/addresses of the objects being stored in
each node, and each node is still only in the same memory location?
"""
queue = Queue()
queue.add(self)
while queue.size > 0:
current = queue.remove()
print(current.value)
if current.left_child:
queue.add(current.left_child)
if current.right_child:
queue.add(current.right_child)
# how I typically test:
bst = BinarySearchTree(50)
for i in range(1,10):
bst.insert_node(i*4)
bst.bfs()
示例输出: 25 25 4个 28 4个 28 8个 32 8个 32 12 36 12 36 16 16 20 20 24
看到它自己打印根节点两次,然后 children 节点成对打印两次,一个接一个,这表明它在按正确顺序级别进行的意义上工作水平,但它同时打印左和右 child,直到没有,正如可以看到的那样,到最后它开始打印两次 back-to-back 而不是成对打印,并且它在打印 24 之前被切断第二次。
我还应该声明我对在我的队列函数中使用 python 列表没有兴趣。本练习的重点是手动构建我的数据结构 w/o 帮助使用 pre-built 超出 ints/strings 的数据结构。
完整文件可在我的 GitHub https://github.com/GhostlyMowgli/data_structures_plus
上找到再次强调,如有任何帮助,我们将不胜感激。
您的问题出在您的 queue.remove
功能上,下面是修复代码,在违规行 (219)
def remove(self, current=''):
if current == '':
current = self.tail
if current.next:
if current.next.next:
current = current.next
return self.remove(current) # recursive - keep going to front
else:
n = current.next.value
current.next = None
self.size -= 1
return n
elif current == self.tail:
# now I'm wondering if this is even smart
# shouldn't I be checking if current is a None type?!?!
if current.value:
n = current.value
self.tail = None # HERE!!!! NOT current = None
self.size -= 1
# print("Queue is now empty - returning final number")
return n
else:
return "Queue is already empty."
else:
raise ValueError("mind boggling coding error...")