用Python实现树形结构的递归算法

2023-04-11 00:00:00 算法 结构 递归

假设我们有一个树形结构的数据，每个节点包含一个唯一的ID和一个父节点ID，我们需要将这些数据转化为树形结构的形式，并实现递归算法。

首先，我们可以定义一个节点类来表示每个节点：

class Node:
    def __init__(self, id, parent_id, value):
        self.id = id
        self.parent_id = parent_id
        self.value = value
        self.children = []

其中，id和parent_id表示节点的唯一ID和父节点ID，value表示节点的值，children表示节点的子节点列表。

接下来，我们使用一个列表来存储所有节点数据，并编写一个函数来将这些数据转化为树形结构：

def build_tree(nodes):
    # 存储节点ID和节点对象的映射关系
    mapping = {node.id: Node(node.id, node.parent_id, node.value) for node in nodes}

    # 添加子节点
    for node in mapping.values():
        if node.parent_id in mapping:
            mapping[node.parent_id].children.append(node)

    # 找出树的根节点
    roots = [node for node in mapping.values() if not node.parent_id]

    # 如果有多个根节点，将它们合并为一个虚拟节点
    if len(roots) > 1:
        root = Node(None, None, None)
        root.children = roots
        return root
    elif roots:
        return roots[0]
    else:
        return None

这个函数接受一个节点列表作为参数，将节点数据转化为树形结构。首先，我们使用一个字典来存储节点ID和节点对象的映射关系。然后，遍历节点列表，为每个节点添加子节点，最后找出根节点并返回。

最后，我们可以编写一个递归算法来遍历整颗树，例如打印所有节点的值：

def traverse(node):
    print(node.value)
    for child in node.children:
        traverse(child)

完整代码如下所示：

class Node:
    def __init__(self, id, parent_id, value):
        self.id = id
        self.parent_id = parent_id
        self.value = value
        self.children = []

def build_tree(nodes):
    # 存储节点ID和节点对象的映射关系
    mapping = {node.id: Node(node.id, node.parent_id, node.value) for node in nodes}

    # 添加子节点
    for node in mapping.values():
        if node.parent_id in mapping:
            mapping[node.parent_id].children.append(node)

    # 找出树的根节点
    roots = [node for node in mapping.values() if not node.parent_id]

    # 如果有多个根节点，将它们合并为一个虚拟节点
    if len(roots) > 1:
        root = Node(None, None, None)
        root.children = roots
        return root
    elif roots:
        return roots[0]
    else:
        return None

def traverse(node):
    print(node.value)
    for child in node.children:
        traverse(child)

nodes = [
    {'id': 1, 'parent_id': None, 'value': 'a'},
    {'id': 2, 'parent_id': 1, 'value': 'b'},
    {'id': 3, 'parent_id': 1, 'value': 'c'},
    {'id': 4, 'parent_id': 2, 'value': 'd'},
    {'id': 5, 'parent_id': 4, 'value': 'e'},
    {'id': 6, 'parent_id': 2, 'value': 'f'},
    {'id': 7, 'parent_id': 3, 'value': 'g'},
]

tree = build_tree(nodes)
traverse(tree)

相关文章