311 Program 5 Loops Drawing a Tree
Print N-ary tree graphically
Given an N-ary tree, the task is to print the N-ary tree graphically.
Graphical Representation of Tree: A representation of tree in which the root is printed in a line and the children nodes are printed in subsequent lines with some amount of indentation.
Examples:
Input: 0 / | \ / | \ 1 2 3 / \ / | \ 4 5 6 7 8 | 9 Output: 0 +--- 1 | +--- 4 | +--- 5 +--- 2 +--- 3 +--- 6 +--- 7 | +--- 9 +--- 8
Approach: The idea is to traverse the N-ary Tree using DFS Traversal to traverse the nodes and explore its children nodes until all the nodes are visited and then similarly, traverse the sibling nodes.
The step-by-step algorithm for the above approach is described below –
- Initialize a variable to store the current depth of the node, for the root node the depth is 0.
- Declare a boolean array to store the current exploring depths and initially mark all of them to False.
- If the current node is a root node that is the depth of the node is 0, then simply print the data of the node.
- Otherwise, Iterate over a loop from 1 to the current depth of node and print, '|' and three spaces for each of the exploring depth and for non-exploring depth print three spaces only.
- Print the current value of the node and move the output pointer to the next line.
- If the current node is the last node of that depth then mark that depth as non-exploring.
- Similarly, explore all the child nodes with the recursive call.
Below is the implementation of the above approach:
C++
#include <iostream>
#include <list>
#include <vector>
using namespace std;
struct tnode {
int n;
list<tnode*> root;
tnode( int data)
: n(data)
{
}
};
void printNTree(tnode* x,
vector< bool > flag,
int depth = 0, bool isLast = false )
{
if (x == NULL)
return ;
for ( int i = 1; i < depth; ++i) {
if (flag[i] == true ) {
cout << "| "
<< " "
<< " "
<< " " ;
}
else {
cout << " "
<< " "
<< " "
<< " " ;
}
}
if (depth == 0)
cout << x->n << '\n' ;
else if (isLast) {
cout << "+--- " << x->n << '\n' ;
flag[depth] = false ;
}
else {
cout << "+--- " << x->n << '\n' ;
}
int it = 0;
for ( auto i = x->root.begin();
i != x->root.end(); ++i, ++it)
printNTree(*i, flag, depth + 1,
it == (x->root.size()) - 1);
flag[depth] = true ;
}
void formAndPrintTree(){
int nv = 10;
tnode r(0), n1(1), n2(2),
n3(3), n4(4), n5(5),
n6(6), n7(7), n8(8), n9(9);
vector< bool > flag(nv, true );
r.root.push_back(&n1);
n1.root.push_back(&n4);
n1.root.push_back(&n5);
r.root.push_back(&n2);
r.root.push_back(&n3);
n3.root.push_back(&n6);
n3.root.push_back(&n7);
n7.root.push_back(&n9);
n3.root.push_back(&n8);
printNTree(&r, flag);
}
int main( int argc, char const * argv[])
{
formAndPrintTree();
return 0;
}
Java
import java.util.*;
class GFG{
static class tnode {
int n;
Vector<tnode> root = new Vector<>();
tnode( int data)
{
this .n = data;
}
};
static void printNTree(tnode x,
boolean [] flag,
int depth, boolean isLast )
{
if (x == null )
return ;
for ( int i = 1 ; i < depth; ++i) {
if (flag[i] == true ) {
System.out.print( "| "
+ " "
+ " "
+ " " );
}
else {
System.out.print( " "
+ " "
+ " "
+ " " );
}
}
if (depth == 0 )
System.out.println(x.n);
else if (isLast) {
System.out.print( "+--- " + x.n + '\n' );
flag[depth] = false ;
}
else {
System.out.print( "+--- " + x.n + '\n' );
}
int it = 0 ;
for (tnode i : x.root) {
++it;
printNTree(i, flag, depth + 1 ,
it == (x.root.size()) - 1 );
}
flag[depth] = true ;
}
static void formAndPrintTree(){
int nv = 10 ;
tnode r = new tnode( 0 );
tnode n1 = new tnode( 1 );
tnode n2 = new tnode( 2 );
tnode n3 = new tnode( 3 );
tnode n4 = new tnode( 4 );
tnode n5 = new tnode( 5 );
tnode n6 = new tnode( 6 );
tnode n7 = new tnode( 7 );
tnode n8 = new tnode( 8 );
tnode n9 = new tnode( 9 );
boolean [] flag = new boolean [nv];
Arrays.fill(flag, true );
r.root.add(n1);
n1.root.add(n4);
n1.root.add(n5);
r.root.add(n2);
r.root.add(n3);
n3.root.add(n6);
n3.root.add(n7);
n7.root.add(n9);
n3.root.add(n8);
printNTree(r, flag, 0 , false );
}
public static void main(String[] args)
{
formAndPrintTree();
}
}
Python3
class tnode:
def __init__( self , data):
self .n = data
self .root = []
def printNTree(x,flag,depth,isLast):
if x = = None :
return
for i in range ( 1 , depth):
if flag[i]:
print ( "| " ," ", " ", " ", end = " ")
else :
print ( " " , " ", " ", " ", end = " ")
if depth = = 0 :
print (x.n)
elif isLast:
print ( "+---" , x.n)
flag[depth] = False
else :
print ( "+---" , x.n)
it = 0
for i in x.root:
it + = 1
printNTree(i, flag, depth + 1 , it = = ( len (x.root) - 1 ))
flag[depth] = True
def formAndPrintTree():
nv = 10
r = tnode( 0 )
n1 = tnode( 1 )
n2 = tnode( 2 )
n3 = tnode( 3 )
n4 = tnode( 4 )
n5 = tnode( 5 )
n6 = tnode( 6 )
n7 = tnode( 7 )
n8 = tnode( 8 )
n9 = tnode( 9 )
flag = [ True ] * (nv)
r.root.append(n1)
n1.root.append(n4)
n1.root.append(n5)
r.root.append(n2)
r.root.append(n3)
n3.root.append(n6)
n3.root.append(n7)
n7.root.append(n9)
n3.root.append(n8)
printNTree(r, flag, 0 , False )
formAndPrintTree();
C#
using System;
using System.Collections.Generic;
class GFG
{
public class tnode
{
public
int n;
public
List<tnode> root = new List<tnode>();
public
tnode( int data)
{
this .n = data;
}
};
static void printNTree(tnode x,
bool [] flag,
int depth, bool isLast )
{
if (x == null )
return ;
for ( int i = 1; i < depth; ++i)
{
if (flag[i] == true )
{
Console.Write( "| "
+ " "
+ " "
+ " " );
}
else
{
Console.Write( " "
+ " "
+ " "
+ " " );
}
}
if (depth == 0)
Console.WriteLine(x.n);
else if (isLast)
{
Console.Write( "+--- " + x.n + '\n' );
flag[depth] = false ;
}
else
{
Console.Write( "+--- " + x.n + '\n' );
}
int it = 0;
foreach (tnode i in x.root)
{
++it;
printNTree(i, flag, depth + 1,
it == (x.root.Count) - 1);
}
flag[depth] = true ;
}
static void formAndPrintTree()
{
int nv = 10;
tnode r = new tnode(0);
tnode n1 = new tnode(1);
tnode n2 = new tnode(2);
tnode n3 = new tnode(3);
tnode n4 = new tnode(4);
tnode n5 = new tnode(5);
tnode n6 = new tnode(6);
tnode n7 = new tnode(7);
tnode n8 = new tnode(8);
tnode n9 = new tnode(9);
bool [] flag = new bool [nv];
for ( int i = 0; i < nv; i++)
flag[i] = true ;
r.root.Add(n1);
n1.root.Add(n4);
n1.root.Add(n5);
r.root.Add(n2);
r.root.Add(n3);
n3.root.Add(n6);
n3.root.Add(n7);
n7.root.Add(n9);
n3.root.Add(n8);
printNTree(r, flag, 0, false );
}
public static void Main(String[] args)
{
formAndPrintTree();
}
}
Javascript
<script>
class tnode
{
constructor(data)
{
this .n = data;
this .root=[];
}
}
function printNTree(x,flag,depth,isLast)
{
if (x == null )
return ;
for (let i = 1; i < depth; ++i) {
if (flag[i] == true ) {
document.write( "| "
+ " "
+ " "
+ " " );
}
else {
document.write( " "
+ " "
+ " "
+ " " );
}
}
if (depth == 0)
document.write(x.n+ "<br>" );
else if (isLast) {
document.write( "+--- " + x.n + '<br>' );
flag[depth] = false ;
}
else {
document.write( "+--- " + x.n + '<br>' );
}
let it = 0;
for (let i of x.root.values()) {
++it;
printNTree(i, flag, depth + 1,
it == (x.root.length) - 1);
}
flag[depth] = true ;
}
function formAndPrintTree()
{
nv = 10;
let r = new tnode(0);
let n1 = new tnode(1);
let n2 = new tnode(2);
let n3 = new tnode(3);
let n4 = new tnode(4);
let n5 = new tnode(5);
let n6 = new tnode(6);
let n7 = new tnode(7);
let n8 = new tnode(8);
let n9 = new tnode(9);
let flag = new Array(nv);
for (let i=0;i<nv;i++)
{
flag[i]= true ;
}
r.root.push(n1);
n1.root.push(n4);
n1.root.push(n5);
r.root.push(n2);
r.root.push(n3);
n3.root.push(n6);
n3.root.push(n7);
n7.root.push(n9);
n3.root.push(n8);
printNTree(r, flag, 0, false );
}
formAndPrintTree();
</script>
Output
0 +--- 1 | +--- 4 | +--- 5 +--- 2 +--- 3 +--- 6 +--- 7 | +--- 9 +--- 8
Performance Analysis:
- Time Complexity: In the above-given approach, there is a recursive call to explore all the vertices which takes O(V) time. Therefore, the time complexity for this approach will be O(V).
- Auxiliary Space Complexity: In the above-given approach, there is extra space used to store the exploring depths. Therefore, the auxiliary space complexity for the above approach will be O(V)
whitakertagathe93.blogspot.com
Source: https://www.geeksforgeeks.org/print-n-ary-tree-graphically/
0 Response to "311 Program 5 Loops Drawing a Tree"
Post a Comment