Создайте n-арное дерево в python с пользователем, дающим ребра

Question

Я хочу создать дерево с заданными пользователем ребрами (в формате uv) и значениями.Узлы могут иметь любое количество дочерних элементов.Например, если заданные значения 3 узлов равны 2 3 4, а ребра заданы как 1-2 и 2-3, дерево будет равно 2 3 4. Также необязательно, что u

Я пробовал код, но он не может создать дерево, как показано ниже, но узел может иметь любое количество дочерних элементов

2
 3
  4
   5

Ниже приведен код

class Node : 

# Utility function to create a new tree node 
def __init__(self ,key): 
    self.key = key 
    self.child = []



# Prints the n-ary tree level wise 
def printNodeLevelWise(root): 
if root is None: 
    return

# create a queue and enqueue root to it 
queue = [] 
queue.append(root) 

# Do level order traversal. Two loops are used 
# to make sure that different levels are printed 
# in different lines 
while(len(queue) >0): 

    n = len(queue) 
    while(n > 0) : 

        # Dequeue an item from queue and print it 
        p = queue[0] 
        queue.pop(0) 
        print p.key, 

        # Enqueue all children of the dequeued item 
        for index, value in enumerate(p.child): 
            queue.append(value) 

        n -= 1
    print "" # Seperator between levels 


# test case
t = raw_input()
t=int(t)
while(t > 0):
# number of nodes
n = raw_input()
n=int(n)
# array to keep node value
a = []
nums = raw_input().split()
for i in nums: a.append(int(i))
n = n -1
root = Node(a[0])
i = 1
for j in range(0, n):
    u, v = raw_input().split()
    u=int(u)
    v=int(v)
    if(u == 1):
        root.child.append(Node(a[i]))
    else:
        root.child[u-2].child.append(Node(a[i]))
    i=i+1
t=t-1
printNodeLevelWise(root)

Я знаю, что коррекция должна быть сделана на root.child[u-2].child.append(Node(a[i])) Я ожидаю, что выход будет

2
 3
  4
   5

для этого случая, но я получаю

Traceback (most recent call last):
File "/home/25cd3bbcc1b79793984caf14f50e7550.py", line 52, in <module>
root.child[u-2].child.append(Node(a[i]))
 IndexError: list index out of range

, поэтому я неполучить представление, как это исправить.Пожалуйста, предоставьте мне правильный код

Answer 1

Допустим, пользователь задал список ребер как

ребра = [[3,2], [3,4], [4,5]]

root = 2

Во-первых, мы должны преобразовать список ребер в правильный словарь , который укажет древовидную структуру заданных ребер. Ниже приведен код, который я нашел на StackOverflow .

def createDict(edges, root):
    graph ={}
    for x,y in es:
        graph.setdefault(x,set()).add(y)
        graph.setdefault(y,set()).add(x)
    tree, stack = {}, [s]
    while stack:
        parent = stack.pop()
        children = graph[parent] - tree.keys()
        tree[parent] = list(children)
        stack.extend(children)
    for i in tree.keys():
        if tree[i] == []:    #if the node is leaf node, give it a 0 val
           tree[i].append(0)   
    return tree

Вывод будет: дерево = {2: [3], 3: [4], 4: [5], 5: [0]}

Теперь мы превратим его в древовидную структуру, используя класс Node . Этот код написан мной.

class Node:
     def __init__(self, val):
         self.val = val
         self.children = []  

def createNode(tree, root,b=None, stack=None):
    if stack is None:
        stack = []           #stack to store children values
        root = Node(root)    #root node is created
        b=root               #it is stored in b variable 
    x = root.val             # root.val = 2 for the first time
   if len(tree[x])>0 :       # check if there are children of the node exists or not
      for i in range(len(tree[x])):   #iterate through each child
          y = Node(tree[x][i])        #create Node for every child
          root.children.append(y)     #append the child_node to its parent_node
          stack.append(y)             #store that child_node in stack
          if y.val ==0:     #if the child_node_val = 0 that is the parent = leaf_node 
             stack.pop()    #pop the 0 value from the stack
      if len(stack):        #iterate through each child in stack
          if len(stack)>=2:      #if the stack length >2, pop from bottom-to-top
              p=stack.pop(0)     #store the popped val in p variable
          else:
              p = stack.pop()    #pop the node top_to_bottom
      createNode(tree, p,b,stack)   # pass p to the function as parent_node 
return b                            # return the main root pointer

В этом коде b - это просто переменная, которая будет указывать на корневой узел, чтобы мы могли перебирать его по уровням и распечатывать.

Для печати на уровне уровня:

def printLevel(node):
    if node is None:
        return
    queue = []
    queue.append(node)
    while(len(queue)>0):
         n =len(queue)
         while(n>0):
             p = queue[0]
             queue.pop(0)
             if p.val !=0:           #for avoiding the printing of '0'
                print(p.val, end='  ')
                for ind, value in enumerate(p.children):
                      queue.append(value)
             n -= 1
         print(" ")

Вывод:

       2
       3
       4
       5  #each level is getting printed

Я не знаю сейчас, как распечатать его наклонным способом): Все еще работаю над этим

Ну, я не профессионал в Python, просто новичок. Исправления и модификации приветствуются.