สมมติว่าเราได้รับต้นไม้ n-ary ซึ่งรากได้รับ 'ราก' แก่เรา เราต้องทำสำเนาของต้นไม้ไบนารี n-ary แบบเต็ม และทำการสั่งซื้อล่วงหน้าของต้นไม้ทั้งสอง ต้องเก็บทรีที่คัดลอกโดยใช้โหนดรูทอื่น โครงสร้างโหนดของต้นไม้แสดงไว้ด้านล่าง -
Node: value : <integer> children : <array>
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น
[14, 27, 32, 42, 56, 65]
การแสดงลำดับล่วงหน้าของแผนผังอินพุตและแผนผังเอาต์พุตจะเหมือนกับการสร้างสำเนาแผนผังที่ถูกต้อง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้ารูทไม่ว่าง
-
คืนค่ารูท
-
-
head :=โหนดใหม่ที่มีค่ารูท
-
q :=deque ใหม่ที่มีองค์ประกอบ root และ head
-
ในขณะที่ q ไม่ว่างให้ทำ
-
node :=เปิดองค์ประกอบแรกจาก q
-
โคลน :=ป๊อปองค์ประกอบแรกจาก q
-
สำหรับแต่ละ chld ใน node.children ให้ทำ
-
new_n :=โหนดใหม่ที่มีค่า chld
-
ต่อท้าย new_n กับลูกของโคลน
-
ใส่ chld และ new_n ต่อท้าย q
-
-
-
กลับหัว
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
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
ผลลัพธ์
[14, 27, 32, 42, 56, 65]
