Chương trình sao chép cây n-ary trong Python

Giả sử ta có một cây n-ary với gốc root. Ta phải tạo bản sao của toàn bộ cây và thực hiện preorder traversal của cả hai cây. Cây sao chép được lưu trữ bằng nút gốc khác. Cấu trúc nút:

Node:
    value: 
    children: 

Kết quả preorder của cây gốc và cây sao chép sẽ giống nhau.

Giải thuật

1. Nếu root rỗng: trả về root
2. head := Node(root.val)
3. q := deque([(root, head)])
4. While q không rỗng:
   • node, cloned := q.popleft()
   • Với mỗi chld trong node.children:
     • new_n := Node(chld.val)
     • Thêm new_n vào cloned.children
     • Thêm (chld, new_n) vào q
5. Trả về head

Ví dụ (Python)

from queue import deque

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(root):
    if not root:
        return root
    head = Node(root.val)
    q = deque([(root, head)])
    while q:
        node, cloned = q.popleft()
        for chld in node.children:
            new_n = Node(chld.val)
            cloned.children.append(new_n)
            q.append((chld, new_n))
    return head

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])
root = node1

copynode = solve(root)
print(treeprint(copynode, 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]) root = node1

Output

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