Main.java - CB100 - Notas, resueltos y tps de la materia Algoritmos y Estructuras de Datos

Line numbers
   1 import java.util.LinkedList;
   2 import java.util.Queue;
   3 
   4 class BinaryTree {
   5     class Node {
   6         int value;
   7         Node left, right;
   8 
   9         Node(int val) {
  10             this.value = val;
  11             this.left = this.right = null;
  12         }
  13 
  14         int getValue() {
  15             return this.value;
  16         }
  17     }
  18 
  19     private Node root;
  20 
  21     // Inserta un nuevo nodo por niveles (usando BFS)
  22     void insert(int value) {
  23         Node newNode = new Node(value);
  24 
  25         if (this.root == null) {
  26             this.root = newNode;
  27             return;
  28         }
  29 
  30         Queue<Node> queue = new LinkedList<>();
  31         queue.add(root);
  32 
  33         while (queue.isEmpty() == false) {
  34             Node current = queue.poll();
  35 
  36             if (current.left == null) {
  37                 current.left = newNode;
  38                 return;
  39             } else {
  40                 queue.add(current.left);
  41             }
  42 
  43             if (current.right == null) {
  44                 current.right = newNode;
  45                 return;
  46             } else {
  47                 queue.add(current.right);
  48             }
  49         }
  50     }
  51 
  52     private int max(int a, int b) {
  53         return a >= b ? a : b;
  54     }
  55 
  56     int altura() {
  57         return altura(this.root);
  58     }
  59 
  60     private int altura(Node node) {
  61         if (node == null)
  62             return 0;
  63         return 1 + max(altura(node.left), altura(node.right));
  64     }
  65 
  66     private int factBalanceo() {
  67         return factBalanceo(this.root);
  68     }
  69 
  70     private int factBalanceo(Node node) {
  71         if(node == null) {
  72             return 0;
  73         }
  74 
  75         return altura(node.left) - altura(node.right);
  76     }
  77 
  78     int cantNodosDesbalanceados() {
  79         return this.cantNodosDesbalanceados(this.root);
  80     }
  81 
  82     private int cantNodosDesbalanceados(Node node) {
  83         if(node == null) {
  84             return 0;
  85         }
  86 
  87         int cantidad = 0;
  88         if(Math.abs(factBalanceo(node)) > 1) {
  89             cantidad++;
  90         }
  91 
  92         cantidad += cantNodosDesbalanceados(node.left);
  93         cantidad += cantNodosDesbalanceados(node.right);
  94 
  95         return cantidad;
  96     }
  97 
  98     int cantNodosConValorPar() {
  99         return this.cantNodosConValorPar(this.root);
 100     }
 101 
 102     private int cantNodosConValorPar(Node node) {
 103         if(node == null) {
 104             return 0;
 105         }
 106 
 107         int cantidad = 0;
 108 
 109         cantidad += cantNodosConValorPar(node.left);
 110         cantidad += cantNodosConValorPar(node.right);
 111 
 112         if((node.getValue() % 2) == 0) {
 113             cantidad++;
 114         }
 115 
 116         return cantidad;
 117     }
 118 
 119     int cantNodosUltNivel() {
 120         return cantNodosUltNivel(this.root);
 121     }
 122 
 123     private boolean esHoja(Node node) {
 124         if(node == null) {
 125             return false;
 126         }
 127         return ((node.left == null) && (node.right == null));
 128     }
 129 
 130     private int cantNodosUltNivel(Node node) {
 131         if(node == null) {
 132             return 0;
 133         }
 134 
 135         int cant = 0;
 136 
 137         if(esHoja(node)) {
 138             cant++;
 139         }
 140         cant += cantNodosUltNivel(node.left);
 141         cant += cantNodosUltNivel(node.right);
 142         return cant;
 143     }
 144 
 145     int cantNodos() {
 146         return cantNodos(this.root);
 147     }
 148 
 149     private int cantNodos(Node node) {
 150         if(node == null) {
 151             return 0;
 152         }
 153         int cant = 0;
 154         cant += cantNodos(node.left);
 155         return 1 + cantNodos(node.left) + cantNodos(node.right);
 156     }
 157 
 158 
 159     int cantDeNodosEnNivel(int n) {
 160         return cantDeNodosEnNivel(this.root, n);
 161     }
 162 
 163     private int cantDeNodosEnNivel(Node node, int n) {
 164         if (node == null) return 0;
 165 
 166         if (n == 1) {
 167             return 1;
 168         } else {
 169             return cantDeNodosEnNivel(node.left, n-1) +
 170                    cantDeNodosEnNivel(node.right, n-1);
 171         }
 172     }
 173 
 174     int cantNodosInternos() {
 175         return this.cantNodosInternos(this.root.left) + this.cantNodosInternos(this.root.right);
 176     }
 177 
 178     private int cantNodosInternos(Node node) {
 179         if((node == null) || ((node.left == null) && (node.right == null))) {
 180             return 0;
 181         }
 182 
 183         return 1 + cantNodosInternos(node.left) + cantNodosInternos(node.right);
 184     }
 185 
 186     int cantNodosCon2Hijos() {
 187         return cantNodosCon2Hijos(this.root);
 188     }
 189 
 190     // devuelve la cantidad de hijos (directos) de un nodo
 191     private int cantHijos(Node node) {
 192         if (node == null) {
 193             return 0;
 194         }
 195 
 196         int res = 0;
 197         if(node.left != null) {
 198             res++;
 199         }
 200 
 201         if(node.right != null) {
 202             res++;
 203         }
 204 
 205         return res;
 206     }
 207 
 208     private int cantNodosCon2Hijos(Node node) {
 209         if(node == null) {
 210             return 0;
 211         }
 212 
 213         int contador = 0;
 214 
 215         if(cantHijos(node) == 2) {
 216             contador++;
 217         }
 218         contador += cantNodosCon2Hijos(node.left);
 219         contador += cantNodosCon2Hijos(node.right);
 220 
 221         return contador;
 222     }
 223 
 224     // recorrido inorden (IRD) para mostrar el árbol
 225     void inorder(Node node) {
 226         if (node == null)
 227             return;
 228         inorder(node.left);
 229         System.out.print(node.value + " ");
 230         inorder(node.right);
 231     }
 232 
 233     // recorrido preorden (RID)
 234     void preorder(Node node) {
 235         if (node == null)
 236             return;
 237         System.out.print(node.value + " ");
 238         preorder(node.left);
 239         preorder(node.right);
 240     }
 241 
 242     void levelOrder(Node node) {
 243         if(node == null) {
 244             return;
 245         }
 246 
 247         Queue<Node> queue = new LinkedList<>();
 248         System.out.print("[");
 249         queue.add(root);
 250 
 251         while (!queue.isEmpty()) {
 252             Node current = queue.poll();
 253             System.out.print(current.value);
 254 
 255             if (current.left != null) {
 256                 queue.add(current.left);
 257             }
 258 
 259             if (current.right != null) {
 260                 queue.add(current.right);
 261             }
 262 
 263             if(!queue.isEmpty()) {
 264                 System.out.print(", ");
 265             }
 266         }
 267         System.out.print("]\n");
 268     }
 269 
 270     void printLevelOrder() {
 271         levelOrder(this.root);
 272     }
 273 
 274     void printInOrder() {
 275         inorder(this.root);
 276         System.out.println();
 277     }
 278 
 279     void printPreOrder() {
 280         preorder(this.root);
 281         System.out.println();
 282     }
 283 }
 284 
 285 public class Main {
 286     public static void main(String[] args) {
 287         BinaryTree b = new BinaryTree();
 288 
 289         b.insert(10);
 290         b.insert(20);  //            _10_
 291         b.insert(30);  //           /    \
 292         b.insert(40);  //          20    30
 293         b.insert(50);  //         / \    / \
 294         b.insert(60);  //       40  50  60  70
 295         b.insert(70);
 296 
 297         b.printLevelOrder();
 298 
 299         // System.out.println(b.altura());
 300         // System.out.println(b.cantDeNodosEnNivel(3));
 301         // System.out.println(b.cantNodosInternos());
 302         // System.out.println(b.cantNodosConValorPar());
 303         System.out.println(b.cantNodosUltNivel());
 304         System.out.println(b.cantNodosCon2Hijos());
 305     }
 306 }