Pythonでn-aryツリーのコピーを作成するプログラム

ルートが「ルート」に与えられているn-aryツリーが提供されたとします。完全なn-aryバイナリツリーのコピーを作成し、両方のツリーのプレオーダートラバーサルを実行する必要があります。コピーしたツリーは、別のルートノードを使用して保存する必要があります。ツリーのノード構造を以下に示します-

Node:
   value : <integer>
   children : <array>

したがって、入力が次のような場合

、出力は

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

入力ツリーと出力ツリーのプレオーダー表現は、ツリーの正確なコピーが作成されたものと同じになります。

これを解決するには、次の手順に従います-

• ルートが空でない場合は、

  • ルートを返す

• head：=rootの値を持つ新しいノード

• q：=要素rootとheadを含む新しい両端キュー

• qが空でない間、実行します

  • node：=qから最初の要素をポップします

  • cloned：=qから最初の要素をポップ

  • node.childrenのchldごとに、実行します

    • new_n：=chldの値を含む新しいノード

    • クローンの子にnew_nを追加します

    • qの最後にchldとnew_nを挿入します

• リターンヘッド

例（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]