使用广度优先搜索查找节点路径

Question

我有一棵二叉树，我想实现广度优先搜索算法来搜索树中的一个节点。我设法做了某种树，我想为 BFS 创建一个函数，它打印出到选定节点的路径。如何实现这样的功能？

class Node: 

# A utility function to create a new node 
def __init__(self, key): 
    self.data = key  
    self.left = None
    self.right = None

root = Node('A') 
root.left = Node('B') 
root.left.left = Node('D')
root.left.right = Node('E')
root.left.left.left = Node('G')
root.left.left.right = Node('H') 
root.left.right.right = Node('K')
root.left.right.left = Node('I')
root.left.right.left.left = Node('K')

Answer 1

您可以使用队列执行标准 BFS，但将该节点的路径添加为队列中状态的一部分。

from collections import deque

class Node: 
    def __init__(self, key): 
        self.data = key  
        self.left = None
        self.right = None

def path_from_to(root, target):
    queue = deque([(root, [root.data])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        if node.left:
            queue.append((node.left, path + [node.left.data]))
        if node.right:
            queue.append((node.right, path + [node.right.data]))

if __name__ == "__main__":
    root = Node('A')
    root.left = Node('B') 
    root.left.left = Node('D')
    root.left.right = Node('E')
    root.left.left.left = Node('G')
    root.left.left.right = Node('H') 
    root.left.right.right = Node('K')
    root.left.right.left = Node('I')
    target = Node('K')
    root.left.right.left.left = target
    print(path_from_to(root, target))

输出：

['A', 'B', 'E', 'I', 'K']

因为它是一棵树，我们不需要保留以前访问过的节点的列表。

请注意，DFS 通常更适合在树中搜索。

Answer 2

或者，您可以使用需要更多处理但内存更少（比队列）的方法：

节点 class 本身可以提供迭代器，这些迭代器将以自上而下或自下而上的广度优先顺序遍历节点。

class Node:
    
    def __init__(self, value): 
        self.value = value  
        self.left  = None
        self.right = None
        
    @property
    def maxLevel(self):
        return max(self.left.maxLevel+1  if self.left  else 0,
                   self.right.maxLevel+1 if self.right else 0)

    def topDown(self):
        for depth in range(self.maxLevel+1):
            for node in self.nodesAtLevel(depth): yield node

    def bottomUp(self):
        for depth in range(self.maxLevel,-1,-1):
            for node in self.nodesAtLevel(depth): yield node
            
    def nodesAtLevel(self,depth,level=0):        
        if level == depth:
            yield self  # output node when at requested depth
            return 
        for subNode in (self.left,self.right): # reach deeper
            if not subNode: continue
            for node in subNode.nodesAtLevel(depth,level+1):
                yield node

输出：

root           = Node('A') # level 0
B = root.left  = Node('B') # level 1
D = B.left     = Node('D') # level 2
E = B.right    = Node('E') # level 2
G = D.left     = Node('G') # level 3
H = D.right    = Node('H') # level 3 
K = root.right = Node('K') # level 1
I = K.left     = Node('I') # level 2

for node in root.topDown(): print(node.value)

# A B K D E I G H

for node in root.bottomUp(): print(node.value)

# G H D E I B K A

您还可以进一步扩展 class 以添加其他类型的遍历迭代器：

    def leftToRight(self):
        if self.left:
            for node in self.left.leftToRight(): yield node
        yield self
        if self.right:
            for node in self.right.leftToRight(): yield node

    def rightToLeft(self):
        if self.right:
            for node in self.right.rightToLeft(): yield node
        yield self
        if self.left:
            for node in self.left.rightToLeft(): yield node

要使用广度优先搜索实现路径功能，您应该使用自下而上的功能并在找到父项时附加它们（因为父项将按此顺序出现在子项之后）：

    def BFPath(self,node):
        path = [node]
        for parent in self.bottomUp():
            if path[-1] in [parent.left,parent.right]:
                path.append(parent)
        return path[::-1]

使用示例：

print([n.value for n in root.BFPath(H)])

# ['A', 'B', 'D', 'H']

使用广度优先搜索查找节点路径

Finding path to node using Breadth First Search

python

algorithm

binary-tree