实现二叉树的深度优先搜索和广度优先搜索

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.

- 123

---

这里有一个提示。对于BFS，队列是最合适的数据结构，而对于DFS，你可以使用栈。 - Neel

@Neel OP知道DFS/BFS的实现-他们已经编写了相应的代码作为一种方法。具体问题是，他们似乎正在尝试使他们的图表可下标化。 - Akshat Mahajan

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

- user2390182

---

这是一个非常好的侧记，很可能也是正确的答案！ - user1767754

Answer 2

你的深度优先搜索实现略有问题。按照现在的写法，你实际上模拟了一个 队列 而不是一个栈。

你目前的代码实际上对于广度优先搜索相当有效。它强制节点的兄弟节点在其子节点之前被评估：

你目前的代码实际上对于广度优先搜索相当有效。它强制节点的兄弟节点在其子节点之前被评估：

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

深度优先搜索算法的逻辑要求栈的行为方式应如下：当一个新节点到来时，需要将其添加到列表的左侧而不是右侧。这样可以强制在遍历节点的兄弟节点之前，先遍历该节点的后代节点。

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是一个不支持查找的对象，那么可以在类定义中使用__getitem__()方法进行实现。

通常，人们会满足于使用字典来实现这一点。类似{Node: [<list of node's children], ... }应该足够了。

- Akshat Mahajan