Python 中二叉搜索树的广度优先搜索

Question

我一直致力于构建不同的数据类型并对其应用各种排序算法。我目前正在对二叉搜索树进行 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

上找到

再次强调，如有任何帮助，我们将不胜感激。

Answer 1

您的问题出在您的 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...")

Python 中二叉搜索树的广度优先搜索

Breadth First Search on a Binary Search Tree in Python

python

queue

binary-search-tree

breadth-first-search