Graph Traversal usando DFS es una forma obvia de atravesar un árbol con recursividad. A continuación se muestra un algoritmo para atravesar un árbol binario usando DFS.
requisitos previos
- Gráfico transversal usando DFS
- Conceptos básicos de Java (Lista de arrays)
- Conceptos básicos de recursividad
Algoritmo
- Inicialice el Node actual como Node raíz y el padre como -1.
- Atraviese el árbol binario como en la forma general de DFS y siga aumentando el nivel del Node a medida que nos alejamos del Node raíz.
- Mientras recorremos, verificamos si el nivel del Node actual del árbol binario es par y luego agregamos la suma par ; de lo contrario, agregamos la suma impar .
- Finalmente, imprima la diferencia absoluta de la suma par y la suma impar .
Ejemplo
Java
import java.util.*;
public class GFG {
// global variable declaration
static ArrayList<ArrayList<Integer> > arr;
static int val[];
static int sum_odd = 0, sum_even = 0;
// traverses the binary-tree/tree having parameters u,
// par, level which denotes current node, current's
// parent node, current level of the tree.
static void dfs(int u, int par, int level)
{
// according to level adding the node
if (level % 2 == 0)
sum_even += val[u];
else
sum_odd += val[u];
// exploring the child of the particular node u (2
// in case of binary tree).
for (int v : arr.get(u)) {
if (v != par) {
// recursively calling the current child
// node to become parent of the next dfs
// call.
dfs(v, u, level + 1);
}
}
}
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
int n = 5;
val = new int[] { 0, 2, 10, 5, 3, 2 };
// declaration of the ArrayList size
arr = new ArrayList<>();
// initialization of each array element as ArrayList
// class
for (int i = 0; i <= n; i++)
arr.add(new ArrayList<>());
arr.get(1).add(2);
arr.get(2).add(1);
arr.get(1).add(4);
arr.get(4).add(1);
arr.get(2).add(5);
arr.get(5).add(2);
arr.get(3).add(4);
arr.get(4).add(3);
// 1(2)
// / \
// 2(10) 4(3)
// / /
// 5(2) 3(5)
// initial call of recurssion
dfs(1, -1, 0);
System.out.println(
"Absolute difference of sum of odd and even nodes of a binary tree "
+ Math.abs(sum_odd - sum_even));
}
}
Producción
Absolute difference of sum of odd and even nodes of a binary tree 4
Complejidad temporal: O(V + E) donde V son los vértices y E son las aristas.