Python中的树形图搜索算法

class Node(object):
    """定义一个节点类，表示树形图的节点"""

    def __init__(self, data):
        self.data = data  # 数据
        self.children = []  # 孩子节点


class Tree(object):
    """定义一个树形图"""

    def __init__(self, root):
        self.root = root  # 根节点

    def add_node(self, parent_node, child_node):
        """添加一个节点"""
        parent_node.children.append(child_node)

    def bfs(self, target):
        """广度优先搜索"""
        queue = [self.root]  # 用队列存储待遍历节点
        while queue:
            node = queue.pop(0)  # 取出队列中的第一个节点
            if node.data == target:  # 如果目标值是当前节点，则返回该节点
                return node
            else:
                queue += node.children  # 将当前节点的孩子节点加入队列

        return None  # 如果没有找到目标值，则返回None

    def dfs(self, target):
        """深度优先搜索"""
        stack = [self.root]  # 用栈存储待遍历节点
        visited = []  # 用来存储已经遍历过的节点
        while stack:
            node = stack.pop()  # 取出栈顶节点
            if node.data == target:  # 如果目标值是当前节点，则返回该节点
                return node
            elif node not in visited:  # 如果当前节点未被访问过
                visited.append(node)  # 将当前节点添加到已访问列表
                stack += node.children  # 将当前节点的孩子节点加入栈

        return None  # 如果没有找到目标值，则返回None


# 构建一个树形图
root_node = Node('p')
tree = Tree(root_node)

node1 = Node('i')
node2 = Node('d')
node3 = Node('a')
node4 = Node('n')
tree.add_node(root_node, node1)
tree.add_node(root_node, node2)
tree.add_node(node1, node3)
tree.add_node(node1, node4)

# 深度优先搜索
node = tree.dfs('n')
if node:
    print("在树形图中找到了目标节点:", node.data)
else:
    print("在树形图中未找到目标节点。")

# 广度优先搜索
node = tree.bfs('i')
if node:
    print("在树形图中找到了目标节点:", node.data)
else:
    print("在树形图中未找到目标节点。")

在树形图中找到了目标节点: n
在树形图中找到了目标节点: i