在 Python 中实现 Stack 的 BFS 二叉树

Question

我正在寻找使用堆栈（不是队列！）在 Python 中实现二叉树的 BFS（广度优先搜索）。

class Stack:
    def __init__(self):
        self.data = []
        
    def Empty(self):
        return self.data == []

    def Push(self, x):
        self.data.append(x)

    def Pop(self):
        return self.data.pop()

    def Peek(self):
        return self.data[len(self.data)-1]

    def Size(self):
        return len(self.data)


class Node:
    def __init__(self, data, left, right):
        self.data = data
        self.l_node = left
        self.r_node = right


class Tree:
    def __init__(self):
        self.root= None

    def bfs_stack(self, node):
        pass


t = Tree()
t.root = Node("1")
t.root.l_node = Node("2")
t.root.l_node.l_node = Node("4")
t.root.l_node.r_node = Node("5")
t.root.l_node.r_node.l_node = Node("8")
t.root.r_node = Node("3")
t.root.r_node.l_node = Node("6")
t.root.r_node.r_node = Node("7")
t.root.r_node.r_node.l_node = Node("9")
t.root.r_node.r_node.l_node.l_node = Node("11")
t.root.r_node.r_node.r_node = Node("10")

我创建了 Stack() class 来使用。我试图结合递归和堆栈推送，但我没有想法。

Queue 实现非常简单，但 Stack() 实现对我来说很重要。

Answer 1

从算法上讲，BFS 与队列操作相关联，而 DFS 与堆栈操作相关联。

如果你只有堆栈，你可以用两个堆栈形成类似队列的东西。

堆栈执行 FILO（先进后出）顺序，而队列执行 FIFO（先进先出）。

如果你把三个数字 1,2,3 叠在一起，然后把它们拉出来，你会得到 3,2,1。

如果你对队列做同样的事情，它们会以 1,2,3 的形式出现。

现在假设我们将 1,2,3 放入堆栈 A，将它们拉出为 3,2,1，然后将它们放入堆栈 B。将它们从堆栈 B 中取出将得到它们 1,2,3 ，这意味着通过两个堆栈类似于通过队列。

现在，如果您拥有整个序列并一次输入所有内容，然后将其全部取出，那么这个论点本身就有效。但是对于BFS/DFSsearches这不是真的，你输入了一些东西，然后在你输入更多之前把它们取出来。

如果堆栈 B 完全为空，您仍然可以通过仅将内容从堆栈 A 移动到堆栈 B 来使 BFS 工作，然后将整个堆栈 A 转移到 B。B 为空可确保放入的内容在堆栈 A 中收集的东西之前，所有进入堆栈 B 的东西都被处理。将 A 的整体放入 B 确保与中心节点距离相同的所有节点在任何给定时间都保持在同一堆栈（A 或 B）中。每次从堆栈 A 到 B 的内容传输都代表在距起始节点特定距离处完成 BFS 级别的处理，并且内层保证在外层之前处理，这就是 BFS。

stack_a = Stack()
stack_b = Stack()

stack_b.Push(t.root)
while len(stack_a)+len(stack_b)>0:
    if len(stack_b) >0:
        current_node = stack_b.Pop()
    else:
        while len(stack_a)> 0:
            stack_b.Push(stack_a.Pop())
        current_node = stack_b.Pop()
    process(current_node) # this gets called on nodes in BFS order
    for neighbor in [current_node.l_node, current_node.r_node]:
        stack_a.Push(neighbor)
        #can generalize this to non-binary graphs by iterating through all unvisited neighbors
        #for cyclical graphs, must track processed nodes to ensure nodes don't get processed more than once

在 Python 中实现 Stack 的 BFS 二叉树

BFS binary tree that implements Stack in Python

python

stack

binary-tree

breadth-first-search

tree-traversal