为二叉树实现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 stack:
        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的逻辑要求堆栈具有如下行为：当出现新节点时，您需要将其添加到列表的左侧，而不是右侧。这样，您可以在遍历节点的同级之前强制遍历节点的后代。

def dfs(self, graph, start):
    visited, stack = set(), [start]
    while queue:
        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是不支持查找的对象，则可以使用类定义中的方法来实现__getitem__()。

通常，人们很满足于使用字典来实现这一目标。诸如此类的东西{Node: [<list of node's children], ... }应该绰绰有余。