Dada una array que contiene el recorrido previo al pedido del árbol k-ario completo, construya el árbol k-ario completo e imprima su recorrido posterior al pedido. Un árbol k-ario completo es un árbol en el que cada Node tiene 0 o k hijos.
Ejemplos:
Input : preorder[] = {1, 2, 5, 6, 7,
3, 8, 9, 10, 4}
k = 3
Output : Postorder traversal of constructed
full k-ary tree is: 5 6 7 2 8 9 10
3 4 1
Tree formed is: 1
/ | \
2 3 4
/|\ /|\
5 6 7 8 9 10
Input : preorder[] = {1, 2, 5, 6, 7, 3, 4}
k = 3
Output : Postorder traversal of constructed
full k-ary tree is: 5 6 7 2 4 3 1
Tree formed is: 1
/ | \
2 3 4
/|\
5 6 7
Hemos discutido este problema para el árbol binario en la publicación a continuación.
Construya un árbol especial a partir de un recorrido preorden dado
En esta publicación, se discute la solución para un árbol k-ario.
En Preorder transversal , se procesa el primer Node raíz y luego el subárbol izquierdo y el subárbol derecho. Debido a esto, para construir un árbol k-ario completo, solo necesitamos seguir creando los Nodes sin preocuparnos por los Nodes construidos previamente. Podemos usar esto para construir el árbol recursivamente.
Los siguientes son los pasos para resolver el problema:
- Encuentra la altura del árbol.
- Atraviese la array de preorden y agregue recursivamente cada Node
Implementación:
C++
// C++ program to build full k-ary tree from
// its preorder traversal and to print the
// postorder traversal of the tree.
#include <bits/stdc++.h>
using namespace std;
// Structure of a node of an n-ary tree
struct Node {
int key;
vector<Node*> child;
};
// Utility function to create a new tree
// node with k children
Node* newNode(int value)
{
Node* nNode = new Node;
nNode->key = value;
return nNode;
}
// Function to build full k-ary tree
Node* BuildKaryTree(int A[], int n, int k, int h, int& ind)
{
// For null tree
if (n <= 0)
return NULL;
Node* nNode = newNode(A[ind]);
if (nNode == NULL) {
cout << "Memory error" << endl;
return NULL;
}
// For adding k children to a node
for (int i = 0; i < k; i++) {
// Check if ind is in range of array
// Check if height of the tree is greater than 1
if (ind < n - 1 && h > 1) {
ind++;
// Recursively add each child
nNode->child.push_back(BuildKaryTree(A, n, k, h - 1, ind));
} else {
nNode->child.push_back(NULL);
}
}
return nNode;
}
// Function to find the height of the tree
Node* BuildKaryTree(int* A, int n, int k, int ind)
{
int height = (int)ceil(log((double)n * (k - 1) + 1)
/ log((double)k));
return BuildKaryTree(A, n, k, height, ind);
}
// Function to print postorder traversal of the tree
void postord(Node* root, int k)
{
if (root == NULL)
return;
for (int i = 0; i < k; i++)
postord(root->child[i], k);
cout << root->key << " ";
}
// Driver program to implement full k-ary tree
int main()
{
int ind = 0;
int k = 3, n = 10;
int preorder[] = { 1, 2, 5, 6, 7, 3, 8, 9, 10, 4 };
Node* root = BuildKaryTree(preorder, n, k, ind);
cout << "Postorder traversal of constructed"
" full k-ary tree is: ";
postord(root, k);
cout << endl;
return 0;
}
Java
// Java program to build full k-ary tree from
// its preorder traversal and to print the
// postorder traversal of the tree.
import java.util.*;
class GFG
{
// Structure of a node of an n-ary tree
static class Node
{
int key;
Vector<Node> child;
};
// Utility function to create a new tree
// node with k children
static Node newNode(int value)
{
Node nNode = new Node();
nNode.key = value;
nNode.child= new Vector<Node>();
return nNode;
}
static int ind;
// Function to build full k-ary tree
static Node BuildKaryTree(int A[], int n,
int k, int h)
{
// For null tree
if (n <= 0)
return null;
Node nNode = newNode(A[ind]);
if (nNode == null)
{
System.out.println("Memory error" );
return null;
}
// For adding k children to a node
for (int i = 0; i < k; i++)
{
// Check if ind is in range of array
// Check if height of the tree is greater than 1
if (ind < n - 1 && h > 1)
{
ind++;
// Recursively add each child
nNode.child.add(BuildKaryTree(A, n, k, h - 1));
}
else
{
nNode.child.add(null);
}
}
return nNode;
}
// Function to find the height of the tree
static Node BuildKaryTree_1(int[] A, int n, int k, int in)
{
int height = (int)Math.ceil(Math.log((double)n * (k - 1) + 1) /
Math.log((double)k));
ind = in;
return BuildKaryTree(A, n, k, height);
}
// Function to print postorder traversal of the tree
static void postord(Node root, int k)
{
if (root == null)
return;
for (int i = 0; i < k; i++)
postord(root.child.get(i), k);
System.out.print(root.key + " ");
}
// Driver Code
public static void main(String args[])
{
int ind = 0;
int k = 3, n = 10;
int preorder[] = { 1, 2, 5, 6, 7, 3, 8, 9, 10, 4 };
Node root = BuildKaryTree_1(preorder, n, k, ind);
System.out.println("Postorder traversal of " +
"constructed full k-ary tree is: ");
postord(root, k);
System.out.println();
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to build full k-ary tree
# from its preorder traversal and to print the
# postorder traversal of the tree.
from math import ceil, log
# Utility function to create a new
# tree node with k children
class newNode:
def __init__(self, value):
self.key = value
self.child = []
# Function to build full k-ary tree
def BuildkaryTree(A, n, k, h, ind):
# For None tree
if (n <= 0):
return None
nNode = newNode(A[ind[0]])
if (nNode == None):
print("Memory error")
return None
# For adding k children to a node
for i in range(k):
# Check if ind is in range of array
# Check if height of the tree is
# greater than 1
if (ind[0] < n - 1 and h > 1):
ind[0] += 1
# Recursively add each child
nNode.child.append(BuildkaryTree(A, n, k,
h - 1, ind))
else:
nNode.child.append(None)
return nNode
# Function to find the height of the tree
def BuildKaryTree(A, n, k, ind):
height = int(ceil(log(float(n) * (k - 1) + 1) /
log(float(k))))
return BuildkaryTree(A, n, k, height, ind)
# Function to print postorder traversal
# of the tree
def postord(root, k):
if (root == None):
return
for i in range(k):
postord(root.child[i], k)
print(root.key, end = " ")
# Driver Code
if __name__ == '__main__':
ind = [0]
k = 3
n = 10
preorder = [ 1, 2, 5, 6, 7, 3, 8, 9, 10, 4]
root = BuildKaryTree(preorder, n, k, ind)
print("Postorder traversal of constructed",
"full k-ary tree is: ")
postord(root, k)
# This code is contributed by pranchalK
C#
// C# program to build full k-ary tree from
// its preorder traversal and to print the
// postorder traversal of the tree.
using System;
using System.Collections.Generic;
class GFG
{
// Structure of a node of an n-ary tree
class Node
{
public int key;
public List<Node> child;
};
// Utility function to create a new tree
// node with k children
static Node newNode(int value)
{
Node nNode = new Node();
nNode.key = value;
nNode.child= new List<Node>();
return nNode;
}
static int ind;
// Function to build full k-ary tree
static Node BuildKaryTree(int []A, int n,
int k, int h)
{
// For null tree
if (n <= 0)
return null;
Node nNode = newNode(A[ind]);
if (nNode == null)
{
Console.WriteLine("Memory error" );
return null;
}
// For adding k children to a node
for (int i = 0; i < k; i++)
{
// Check if ind is in range of array
// Check if height of the tree is greater than 1
if (ind < n - 1 && h > 1)
{
ind++;
// Recursively add each child
nNode.child.Add(BuildKaryTree(A, n, k, h - 1));
}
else
{
nNode.child.Add(null);
}
}
return nNode;
}
// Function to find the height of the tree
static Node BuildKaryTree_1(int[] A, int n, int k, int iN)
{
int height = (int)Math.Ceiling(Math.Log((double)n * (k - 1) + 1) /
Math.Log((double)k));
ind = iN;
return BuildKaryTree(A, n, k, height);
}
// Function to print postorder traversal of the tree
static void postord(Node root, int k)
{
if (root == null)
return;
for (int i = 0; i < k; i++)
postord(root.child[i], k);
Console.Write(root.key + " ");
}
// Driver Code
public static void Main(String []args)
{
int ind = 0;
int k = 3, n = 10;
int []preorder = { 1, 2, 5, 6, 7, 3, 8, 9, 10, 4 };
Node root = BuildKaryTree_1(preorder, n, k, ind);
Console.WriteLine("Postorder traversal of " +
"constructed full k-ary tree is: ");
postord(root, k);
Console.WriteLine();
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to build full k-ary tree from
// its preorder traversal and to print the
// postorder traversal of the tree.
class Node
{
constructor(key) {
this.child = [];
this.key = key;
}
}
// Utility function to create a new tree
// node with k children
function newNode(value)
{
let nNode = new Node(value);
return nNode;
}
let ind;
// Function to build full k-ary tree
function BuildKaryTree(A, n, k, h)
{
// For null tree
if (n <= 0)
return null;
let nNode = newNode(A[ind]);
if (nNode == null)
{
document.write("Memory error" );
return null;
}
// For adding k children to a node
for (let i = 0; i < k; i++)
{
// Check if ind is in range of array
// Check if height of the tree is greater than 1
if (ind < n - 1 && h > 1)
{
ind++;
// Recursively add each child
nNode.child.push(BuildKaryTree(A, n, k, h - 1));
}
else
{
nNode.child.push(null);
}
}
return nNode;
}
// Function to find the height of the tree
function BuildKaryTree_1(A, n, k, In)
{
let height = Math.ceil(Math.log(n * (k - 1) + 1) / Math.log(k));
ind = In;
return BuildKaryTree(A, n, k, height);
}
// Function to print postorder traversal of the tree
function postord(root, k)
{
if (root == null)
return;
for (let i = 0; i < k; i++)
postord(root.child[i], k);
document.write(root.key + " ");
}
ind = 0;
let k = 3, n = 10;
let preorder = [ 1, 2, 5, 6, 7, 3, 8, 9, 10, 4 ];
let root = BuildKaryTree_1(preorder, n, k, ind);
document.write("Postorder traversal of " +
"constructed full k-ary" + "</br>" + "tree is: ");
postord(root, k);
document.write("</br>");
</script>
Producción
Postorder traversal of constructed full k-ary tree is: 5 6 7 2 8 9 10 3 4 1
Este artículo es una contribución de Prakriti Gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA