Implementation of Tree Data Structure:
C++
// C++ program to demonstrate some of the above
// terminologies
#include
using namespace std;
// Function to add an edge between vertices x and y
void addEdge(int x, int y, vector >& adj)
{
adj[x].push_back(y);
adj[y].push_back(x);
}
// Function to print the parent of each node
void printParents(int node, vector >& adj,
int parent)
{
// current node is Root, thus, has no parent
if (parent == 0)
cout << node << "->Root" << endl;
else
cout << node << "->" << parent << endl;
// Using DFS
for (auto cur : adj[node])
if (cur != parent)
printParents(cur, adj, node);
}
// Function to print the children of each node
void printChildren(int Root, vector >& adj)
{
// Queue for the BFS
queue q;
// pushing the root
q.push(Root);
// visit array to keep track of nodes that have been
// visited
int vis[adj.size()] = { 0 };
// BFS
while (!q.empty()) {
int node = q.front();
q.pop();
vis[node] = 1;
cout << node << "-> ";
for (auto cur : adj[node])
if (vis[cur] == 0) {
cout << cur << " ";
q.push(cur);
}
cout << endl;
}
}
// Function to print the leaf nodes
void printLeafNodes(int Root, vector >& adj)
{
// Leaf nodes have only one edge and are not the root
for (int i = 1; i < adj.size(); i++)
if (adj[i].size() == 1 && i != Root)
cout << i << " ";
cout << endl;
}
// Function to print the degrees of each node
void printDegrees(int Root, vector >& adj)
{
for (int i = 1; i < adj.size(); i++) {
cout << i << ": ";
// Root has no parent, thus, its degree is equal to
// the edges it is connected to
if (i == Root)
cout << adj[i].size() << endl;
else
cout << adj[i].size() - 1 << endl;
}
}
// Driver code
int main()
{
// Number of nodes
int N = 7, Root = 1;
// Adjacency list to store the tree
vector > adj(N + 1, vector());
// Creating the tree
addEdge(1, 2, adj);
addEdge(1, 3, adj);
addEdge(1, 4, adj);
addEdge(2, 5, adj);
addEdge(2, 6, adj);
addEdge(4, 7, adj);
// Printing the parents of each node
cout << "The parents of each node are:" << endl;
printParents(Root, adj, 0);
// Printing the children of each node
cout << "The children of each node are:" << endl;
printChildren(Root, adj);
// Printing the leaf nodes in the tree
cout << "The leaf nodes of the tree are:" << endl;
printLeafNodes(Root, adj);
// Printing the degrees of each node
cout << "The degrees of each node are:" << endl;
printDegrees(Root, adj);
return 0;
}
Java
// java code for above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to print the parent of each node
public static void
printParents(int node, Vector > adj,
int parent)
{
// current node is Root, thus, has no parent
if (parent == 0)
System.out.println(node + "->Root");
else
System.out.println(node + "->" + parent);
// Using DFS
for (int i = 0; i < adj.get(node).size(); i++)
if (adj.get(node).get(i) != parent)
printParents(adj.get(node).get(i), adj,
node);
}
// Function to print the children of each node
public static void
printChildren(int Root, Vector > adj)
{
// Queue for the BFS
Queue q = new LinkedList<>();
// pushing the root
q.add(Root);
// visit array to keep track of nodes that have been
// visited
int vis[] = new int[adj.size()];
Arrays.fill(vis, 0);
// BFS
while (q.size() != 0) {
int node = q.peek();
q.remove();
vis[node] = 1;
System.out.print(node + "-> ");
for (int i = 0; i < adj.get(node).size(); i++) {
if (vis[adj.get(node).get(i)] == 0) {
System.out.print(adj.get(node).get(i)
+ " ");
q.add(adj.get(node).get(i));
}
}
System.out.println();
}
}
// Function to print the leaf nodes
public static void
printLeafNodes(int Root, Vector > adj)
{
// Leaf nodes have only one edge and are not the
// root
for (int i = 1; i < adj.size(); i++)
if (adj.get(i).size() == 1 && i != Root)
System.out.print(i + " ");
System.out.println();
}
// Function to print the degrees of each node
public static void
printDegrees(int Root, Vector > adj)
{
for (int i = 1; i < adj.size(); i++) {
System.out.print(i + ": ");
// Root has no parent, thus, its degree is
// equal to the edges it is connected to
if (i == Root)
System.out.println(adj.get(i).size());
else
System.out.println(adj.get(i).size() - 1);
}
}
// Driver code
public static void main(String[] args)
{
// Number of nodes
int N = 7, Root = 1;
// Adjacency list to store the tree
Vector > adj
= new Vector >();
for (int i = 0; i < N + 1; i++) {
adj.add(new Vector());
}
// Creating the tree
adj.get(1).add(2);
adj.get(2).add(1);
adj.get(1).add(3);
adj.get(3).add(1);
adj.get(1).add(4);
adj.get(4).add(1);
adj.get(2).add(5);
adj.get(5).add(2);
adj.get(2).add(6);
adj.get(6).add(2);
adj.get(4).add(7);
adj.get(7).add(4);
// Printing the parents of each node
System.out.println("The parents of each node are:");
printParents(Root, adj, 0);
// Printing the children of each node
System.out.println(
"The children of each node are:");
printChildren(Root, adj);
// Printing the leaf nodes in the tree
System.out.println(
"The leaf nodes of the tree are:");
printLeafNodes(Root, adj);
// Printing the degrees of each node
System.out.println("The degrees of each node are:");
printDegrees(Root, adj);
}
}
// This code is contributed by rj13to.
Python
from collections import deque
# Function to add an edge between vertices x and y
def addEdge(x, y, adj):
adj[x].append(y)
adj[y].append(x)
# Function to print the parent of each node
def printParents(node, adj, parent):
# current node is Root, thus, has no parent
if parent == 0:
print("{}->Root".format(node))
else:
print("{}->{}".format(node, parent))
# Using DFS
for cur in adj[node]:
if cur != parent:
printParents(cur, adj, node)
# Function to print the children of each node
def printChildren(Root, adj):
# Queue for the BFS
q = deque()
# pushing the root
q.append(Root)
# visit array to keep track of nodes that have been
# visited
vis = [0] * len(adj)
# BFS
while q:
node = q.popleft()
vis[node] = 1
print("{}->".format(node)),
for cur in adj[node]:
if vis[cur] == 0:
print(cur),
q.append(cur)
print()
# Function to print the leaf nodes
def printLeafNodes(Root, adj):
# Leaf nodes have only one edge and are not the root
for i in range(1, len(adj)):
if len(adj[i]) == 1 and i != Root:
print(i),
# Function to print the degrees of each node
def printDegrees(Root, adj):
for i in range(1, len(adj)):
print(i, ":"),
# Root has no parent, thus, its degree is equal to
# the edges it is connected to
if i == Root:
print(len(adj[i]))
else:
print(len(adj[i]) - 1)
# Driver code
N = 7
Root = 1
# Adjacency list to store the tree
adj = [[] for _ in range(N + 1)]
# Creating the tree
addEdge(1, 2, adj)
addEdge(1, 3, adj)
addEdge(1, 4, adj)
addEdge(2, 5, adj)
addEdge(2, 6, adj)
addEdge(4, 7, adj)
# Printing the parents of each node
print("The parents of each node are:")
printParents(Root, adj, 0)
# Printing the children of each node
print("The children of each node are:")
printChildren(Root, adj)
# Printing the leaf nodes in the tree
print("The leaf nodes of the tree are:")
printLeafNodes(Root, adj)
# Printing the degrees of each node
print("The degrees of each node are:")
printDegrees(Root, adj)
C#
using System;
using System.Collections.Generic;
class Program
{
static void PrintParents(int node, List> adj, int parent)
{
if (parent == 0)
{
Console.WriteLine($"{node} -> Root");
}
else
{
Console.WriteLine($"{node} -> {parent}");
}
foreach (int cur in adj[node])
{
if (cur != parent)
{
PrintParents(cur, adj, node);
}
}
}
static void PrintChildren(int Root, List> adj)
{
Queue q = new Queue();
q.Enqueue(Root);
bool[] vis = new bool[adj.Count];
while (q.Count > 0)
{
int node = q.Dequeue();
vis[node] = true;
Console.Write($"{node} -> ");
foreach (int cur in adj[node])
{
if (!vis[cur])
{
Console.Write($"{cur} ");
q.Enqueue(cur);
}
}
Console.WriteLine();
}
}
static void PrintLeafNodes(int Root, List> adj)
{
for (int i = 0; i < adj.Count; i++)
{
if (adj[i].Count == 1 && i != Root)
{
Console.Write($"{i} ");
}
}
Console.WriteLine();
}
static void PrintDegrees(int Root, List> adj)
{
for (int i = 1; i < adj.Count; i++)
{
Console.Write($"{i}: ");
if (i == Root)
{
Console.WriteLine(adj[i].Count);
}
else
{
Console.WriteLine(adj[i].Count - 1);
}
}
}
static void Main(string[] args)
{
int N = 7;
int Root = 1;
List> adj = new List>();
for (int i = 0; i <= N; i++)
{
adj.Add(new List());
}
adj[1].AddRange(new int[] { 2, 3, 4 });
adj[2].AddRange(new int[] { 1, 5, 6 });
adj[4].Add(7);
Console.WriteLine("The parents of each node are:");
PrintParents(Root, adj, 0);
Console.WriteLine("The children of each node are:");
PrintChildren(Root, adj);
Console.WriteLine("The leaf nodes of the tree are:");
PrintLeafNodes(Root, adj);
Console.WriteLine("The degrees of each node are:");
PrintDegrees(Root, adj);
}
}
JavaScript
// Number of nodes
let N = 7, Root = 1;
// Adjacency list to store the tree
let adj = new Array(N + 1).fill(null).map(() => []);
// Creating the tree
addEdge(1, 2, adj);
addEdge(1, 3, adj);
addEdge(1, 4, adj);
addEdge(2, 5, adj);
addEdge(2, 6, adj);
addEdge(4, 7, adj);
// Function to add an edge between vertices x and y
function addEdge(x, y, arr) {
arr[x].push(y);
arr[y].push(x);
}
// Function to print the parent of each node
function printParents(node, arr, parent)
{
// current node is Root, thus, has no parent
if (parent == 0)
console.log(`${node}->Root`);
else
console.log(`${node}->${parent}`);
// Using DFS
for (let cur of arr[node])
if (cur != parent)
printParents(cur, arr, node);
}
// Function to print the children of each node
function printChildren(Root, arr)
{
// Queue for the BFS
let q = [];
// pushing the root
q.push(Root);
// visit array to keep track of nodes that have been
// visited
let vis = new Array(arr.length).fill(0);
// BFS
while (q.length > 0) {
let node = q.shift();
vis[node] = 1;
console.log(`${node}-> `);
for (let cur of arr[node])
if (vis[cur] == 0) {
console.log(cur + " ");
q.push(cur);
}
console.log("\n");
}
}
// Function to print the leaf nodes
function printLeafNodes(Root, arr)
{
// Leaf nodes have only one edge and are not the root
for (let i = 1; i < arr.length; i++)
if (arr[i].length == 1 && i != Root)
console.log(i + " ");
console.log("\n");
}
// Function to print the degrees of each node
function printDegrees(Root, arr) {
for (let i = 1; i < arr.length; i++) {
console.log(`${i}: `);
// Root has no parent, thus, its degree is equal to
// the edges it is connected to
if (i == Root)
console.log(arr[i].length + "\n");
else
console.log(arr[i].length - 1 + "\n");
}
}
// Driver code
// Printing the parents of each node
console.log("The parents of each node are:");
printParents(Root, adj, 0);
// Printing the children of each node
console.log("The children of each node are:");
printChildren(Root, adj);
// Printing the leaf nodes in the tree
console.log("The leaf nodes of the tree are:");
printLeafNodes(Root, adj);
// Printing the degrees of each node
console.log("The degrees of each node are:");
printDegrees(Root, adj);
// This code is contributed by ruchikabaslas....
Contact Us