为二叉树实现 DFS 和 BFS

Question

我正在尝试使用深度优先遍历和广度优先遍历来遍历二叉树，但我运行遇到了麻烦。我的节点和树实现似乎没问题，我只是不确定如何正确地按深度和广度遍历树。

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

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

    def getRoot(self):
        return self.root

    def add(self, val):
        if(self.root == None):
            self.root = Node(val)
        else:
            self._add(val, self.root)

    def _add(self, val, node):
        if(val < node.v):
            if(node.l != None):
                self._add(val, node.l)
            else:
                node.l = Node(val)
        else:
            if(node.r != None):
                self._add(val, node.r)
            else:
                node.r = Node(val)

    def find(self, val):
        if(self.root != None):
            return self._find(val, self.root)
        else:
            return None

    def _find(self, val, node):
        if(val == node.v):
            return node
        elif(val < node.v and node.l != None):
            self._find(val, node.l)
        elif(val > node.v and node.r != None):
            self._find(val, node.r)

    def printTree(self):
        if(self.root != None):
            self._printTree(self.root)

    def _printTree(self, node):
        if(node != None):
            self._printTree(node.l)
            print(str(node.v) + ' ')
            self._printTree(node.r)

    # This doesn't work - graph is not subscriptable
    def dfs(self, graph, start):
        visited, stack = set(), [start]
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                visited.add(vertex)
                stack.extend(graph[vertex] - visited)
        return visited

     # Haven't tried BFS.  Would use a queue, but unsure of the details.

Answer 1

如果是一棵树，visited可以是一个列表，因为树是非循环的，所以不需要检查你之前是否访问过一个节点，更重要的是，你想维护你的遍历顺序。

def dfs(self, tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]
    while stack:
        node = stack.pop()
        visited.append(node)
        stack.extend(filter(None, [node.r, node.l]))  
        # append right first, so left will be popped first
    return visited

Answer 2

您的 DFS 实现略有不正确。如所写，您实际上模仿了队列，而不是堆栈。

您当前的代码对于广度优先搜索实际上工作得相当好。它强制在其子节点之前评估节点的兄弟节点：

def bfs(self, graph, start):
    visited, queue = set(), [start]
    while queue:
        vertex = queue.pop()
        if vertex not in visited:
            visited.add(vertex)
            # new nodes are added to end of queue
            queue.extend(graph[vertex] - visited)
    return visited

DFS的逻辑要求栈的行为是这样的：当一个新节点到来时，你需要将它添加到列表的left，而不是对。这样，您可以强制遍历节点的后代在节点的兄弟姐妹之前。

def dfs(self, graph, start): visited, stack = set(), [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) # new nodes are added to the start of stack stack = graph[vertex] - visited + stack return visited

其他问题

除此之外，您面临的具体问题是您没有指定 graph 是什么 。

如果 graph 是一个不支持查找的对象，那么您可以实现使用 [=42= 中的 __getitem__() 方法]定义。

通常，人们乐于使用字典来实现这一点。像 {Node: [<list of node's children], ... } 这样的东西就足够了。

为二叉树实现 DFS 和 BFS

Implementing DFS and BFS for binary tree

python

tree

depth-first-search

breadth-first-search

其他问题