Giả sử, chúng ta đã được cung cấp một cây n-ary có gốc được cấp cho chúng ta 'root'. Chúng ta phải tạo một bản sao của cây nhị phân n-ary đầy đủ và thực hiện duyệt đặt hàng trước của cả hai cây. Cây đã sao chép phải được lưu trữ bằng một nút gốc khác. Cấu trúc nút của cây được đưa ra dưới đây -
Node: value : <integer> children : <array>
Vì vậy, nếu đầu vào giống như
, thì đầu ra sẽ là
[14, 27, 32, 42, 56, 65]
Biểu diễn đặt hàng trước của cây đầu vào và cây đầu ra sẽ giống như một bản sao chính xác của cây đã được tạo.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu gốc không trống, thì
-
trả về thư mục gốc
-
-
head:=một nút mới có giá trị là gốc
-
q:=a new deque chứa phần tử gốc và đầu
-
trong khi q không trống, thực hiện
-
node:=bật phần tử đầu tiên từ q
-
nhân bản:=bật phần tử đầu tiên từ q
-
đối với mỗi chld trong node.children, thực hiện
-
new_n:=một nút mới chứa giá trị của chld
-
thêm new_n vào con của nhân bản
-
chèn chld và new_n vào cuối q
-
-
-
quay trở lại đầu
Ví dụ (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from queue import deque
class Node:
def __init__(self, value, child = None) -> None:
self.val = value
self.children = []
if child != 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 == None:
tree.append("None")
return tree
if tree == None:
tree = []
tree.append(node.val)
for child in node.children:
treeprint(child, tree)
return tree
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)) Đầu vào
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
Đầu ra
[14, 27, 32, 42, 56, 65]