Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária…

Questão

Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária de filhos (representação n-ária), converta-a em uma árvore binária usando a técnica 'filho-esquerdo / irmão-direito' (left-child right-sibling).

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Precondição: cada nó tem 'children' (lista possivelmente vazia). Pós-condição: cada nó terá ponteiros 'left' e 'right' correspondentes a filho-esquerdo e irmão-direito. Pseudocódigo (retorna referência ao nó convertido): function ConvertToLeftChildRightSibling(node): if node == null: return null // converte todos os filhos recursivamente convertedChildren = [] for c in node.children: convertedChildren.append(ConvertToLeftChildRightSibling(c)) // vincula o primeiro filho como left if length(convertedChildren) == 0: node.left = null else: node.left = convertedChildren[0] // vincula irmãos pela ponte 'right' curr = node.left i = 1 while i < length(convertedChildren): curr.right = convertedChildren[i] curr = curr.right i = i + 1 // o ponteiro right do próprio nó permanece para o irmão no nível superior // se não houver irmão, será null (tratado pelos chamadores) node.right = node.right // mantém valor do contexto de chamada // opcional: liberar/ignorar node.children se não mais necessário return node Observações: a técnica define left = primeiro filho e right = próximo irmão. O algoritmo percorre a árvore n-ária recursivamente, converte cada subárvore de filho e liga os irmãos em cadeia usando o ponteiro right.

Explicação

O algoritmo utiliza uma abordagem recursiva para converter cada nó da árvore n-ária em uma estrutura binária, onde o primeiro filho se torna o filho esquerdo e os irmãos são encadeados como filhos direitos. A lógica de vinculação garante que todos os filhos e irmãos sejam corretamente conectados, mantendo a hierarquia original da árvore. A implementação também cuida de casos em que um nó não possui filhos, assegurando que a conversão ocorra de maneira completa e eficiente.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma…
• Projete um algoritmo em pseudocódigo que, dada uma árvore de decisão codificada como nós com condição e referências a…
• Considere uma árvore binária. Em linguagem corrente ou pseudocódigo, descreva a ordem de visita do percurso pré-ordem…
• Projete um algoritmo em pseudocódigo que receba uma lista de strings binárias (dados) e construa uma trie (árvore de…
• Para percorrer recursivamente uma árvore binária em um algoritmo e processar cada nó antes de seus filhos, qual percurso…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.