Chương trình tìm gốc của cây n-ary trong Python

Giả sử ta được cho các nút của một cây n-ary trong một mảng. Ta phải tìm và trả về nút gốc của cây bằng cách tái cấu trúc nó. Cây đầy đủ phải được hiển thị từ nút trả về theo thứ tự preorder.

Ví dụ với cây như hình, kết quả preorder traversal là [14, 27, 32, 42, 56, 65].

Giải thuật

1. indegree := new map (đếm số cạnh vào của mỗi nút)
2. Với mỗi node trong cây:
   • Với mỗi child trong node.children:
     • indegree[child.val]++
3. Với mỗi node trong cây:
   • Nếu indegree[node.val] == 0: trả về node (đây là gốc)
4. Trả về null

Ví dụ (Python)

import collections

class Node:
    def __init__(self, value, child=None) -> None:
        self.val = value
        self.children = []
        if child is not None:
            for value in child:
                self.children.append(value)

def solve(tree):
    indegree = collections.defaultdict(int)
    for node in tree:
        for child in node.children:
            indegree[child.val] += 1
    for node in tree:
        if indegree[node.val] == 0:
            return node
    return None

def treeprint(node, tree):
    if node is None:
        tree.append("None")
        return tree
    if tree is None:
        tree = []
    tree.append(node.val)
    for child in node.children:
        treeprint(child, tree)
    return tree

# Xây dựng cây
node6 = Node(65)
node5 = Node(56)
node4 = Node(42, [node5, node6])
node3 = Node(32)
node2 = Node(27)
node1 = Node(14, [node2, node3, node4])
tree = [node2, node1, node5, node3, node6, node4]

root = solve(tree)
print(treeprint(root, None))

Input

node6 = Node(65) node5 = Node(56) node4 = Node(42, [node5, node6]) node3 = Node(32) node2 = Node(27) node1 = Node(14, [node2, node3, node4]) tree = [node2, node1, node5, node3, node6, node4]

Output

[14, 27, 32, 42, 56, 65]