Pythonでn-aryツリーのルートを見つけるプログラム

配列内のn-aryツリーのノードが与えられたとします。ツリーを再構築して、ツリーのルートノードを見つけて返す必要があります。返されたノードから、ツリー全体をプレオーダー表記で表示する必要があります。

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

その場合、出力は次のようになります

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

ツリーのルートを使用して、ツリーのプレオーダートラバーサルを表示します。したがって、出力はツリーのプレオーダートラバーサルです。

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

• indegree：=整数値を含む新しいマップ

• ツリー内のノードごとに、実行します

  • ノードの子ポインタ内の子ごとに、次のようにします

    • indegree [子の値]：=indegree[子の値]+1

• ツリー内のノードごとに、実行します

  • indegree [ノードの値]が0と同じ場合、

    • リターンノード

• nullを返す

例（Python）

理解を深めるために、次の実装を見てみましょう-

import collections
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(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 == 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])
tree = [node2, node1, node5, node3, node6, node4]

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

入力

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]

出力

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