Aula Prática #10 - Árvores Binárias

Exercício 1) Compreender Árvores Binárias

1. Uma primeira árvore binária.
   Uma maneira de descrever uma árvore é usar uma das seguintes representações:
   • preorder: raíz, seguida da representação prenorder da subárvore esquerda, seguida da representação preorder da subárvore direita.
   • inorder: representação inorder da subárvore esquerda, seguida da raíz, seguida da representação inorder da subárvore direita.
   • postorder: representação postorder da subárvore esquerda, seguida da representação postorder da subárvore direita, seguida da raíz.
   • em largura: nós por ordem crescente de profundidade (de cima para baixo) e no mesmo nível da esquerda para a direita

   Considere a árvore binária da figura seguinte:

   
   

   Nas 4 representações anteriores, a árvore da figura seria descrita do seguinte modo:

   • preorder: 5 1 8 6 7 2
   • inorder: 8 1 6 5 2 7
   • postorder: 8 6 1 2 7 5
   • em largura: 5 1 7 8 6 2
2. Percebendo as várias ordens de visita aos nós Para garantir que percebeu, procure agora escrever no seu caderno as 4 representações como descritas para a seguinte árvore (preorder, inorder, postorder, em largura):

   
   
   Mostrar/Esconder Solução

   • preorder: 6 8 4 3 5 1 7
   • inorder: 8 4 6 1 5 3 7
   • postorder: 4 8 1 5 7 3 6
   • em largura: 6 8 3 4 5 7 1

Exercício 2) Implementação de Árvores Binárias

1. Código de implementação de Árvores Binárias.
   

   Nó da árvore (BTNode.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // No de uma arvore binaria "normal"
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class BTNode<T> {
      private T value;         // Valor guardado no no
      private BTNode<T> left;  // Filho esquerdo
      private BTNode<T> right; // Filho direito
   
      // Construtor
      BTNode(T v, BTNode<T> l, BTNode<T> r) {
         value = v;
         left = l;
         right = r;
      }
   
      // Getters e Setters
      public T getValue() {return value;}
      public BTNode<T> getLeft() {return left;}
      public BTNode<T> getRight() {return right;}
      public void setValue(T v) {value = v;}
      public void setLeft(BTNode<T> l) {left = l;}
      public void setRight(BTNode<T> r) {right = r;}   
   }
   

   ---

   Árvore binária (BTree.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Arvore binaria "normal"
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   public class BTree<T> {   
      private BTNode<T> root; // raiz da arvore
   
      // Construtor
      BTree() {
         root = null;
      }
   
      // Getter e Setter para a raiz
      public BTNode<T> getRoot() {return root;}
      public void setRoot(BTNode<T> r) {root = r;}
   
      // Verificar se arvore esta vazia
      public boolean isEmpty() {
         return root == null;
      }
   
      // --------------------------------------------------------
   
      // Numero de nos da arvore   
      public int numberNodes() {
         return numberNodes(root);
      }
   
      private int numberNodes(BTNode<T> n) {
         if (n == null) return 0;
         return 1 + numberNodes(n.getLeft()) + numberNodes(n.getRight());
      }
   
      // --------------------------------------------------------
   
      // Altura da arvore
      public int depth() {
         return depth(root);
      }
   
      private int depth(BTNode<T> n) {
         if (n == null) return -1;
         return 1 + Math.max(depth(n.getLeft()), depth(n.getRight()));
      }
   
      // --------------------------------------------------------
      
      // O elemento value esta contido na arvore?
      public boolean contains(T value) {
         return contains(root, value);
      }
   
      private boolean contains(BTNode<T> n, T value) {
         if (n==null) return false;
         if (n.getValue().equals(value)) return true;
         return contains(n.getLeft(), value) || contains(n.getRight(), value);
      }
   
      // --------------------------------------------------------
   
      // Imprimir arvore em PreOrder
      public void printPreOrder() {
         System.out.print("PreOrder:");
         printPreOrder(root);
         System.out.println();
      }
   
      private void printPreOrder(BTNode<T> n) {
         if (n==null) return;
         System.out.print(" " + n.getValue() );
         printPreOrder(n.getLeft());
         printPreOrder(n.getRight());
      }
   
      // --------------------------------------------------------
      
      // Imprimir arvore em InOrder
      public void printInOrder() {
         System.out.print("InOrder:");
         printInOrder(root);
         System.out.println();
      }
   
      private void printInOrder(BTNode<T> n) {
         if (n==null) return;
         printInOrder(n.getLeft());
         System.out.print(" " + n.getValue());
         printInOrder(n.getRight());
      }
   
      // --------------------------------------------------------
   
      // Imprimir arvore em PostOrder
      public void printPostOrder() {
         System.out.print("PostOrder:");
         printPostOrder(root);
         System.out.println();
      }
   
      private void printPostOrder(BTNode<T> n) {
         if (n==null) return;
         printPostOrder(n.getLeft());
         printPostOrder(n.getRight());
         System.out.print(" " + n.getValue());
      }
   
      // --------------------------------------------------------
   
      // Imprimir arvore numa visita em largura (usando TAD Fila)
      public void printBFS() {
         System.out.print("BFS:");
         
         MyQueue<BTNode<T>> q = new LinkedListQueue<BTNode<T>>();
         q.enqueue(root);
         while (!q.isEmpty()) {
            BTNode<T> cur = q.dequeue();
            if (cur != null) {
               System.out.print(" " + cur.getValue());
               q.enqueue(cur.getLeft());
               q.enqueue(cur.getRight());
            }
         }
         System.out.println();
      }
   
      // --------------------------------------------------------
      
      // Imprimir arvore numa visita em profundidade (usando TAD Pilha)
      public void printDFS() {
         System.out.print("DFS:");
         
         MyStack<BTNode<T>> q = new LinkedListStack<BTNode<T>>();
         q.push(root);
         while (!q.isEmpty()) {
            BTNode<T> cur = q.pop();
            if (cur != null) {
               System.out.print(" " + cur.getValue());
               q.push(cur.getLeft());
               q.push(cur.getRight());
            }
         }
         System.out.println();
      }
   
   }
   

   ---

   Exemplo de teste das árvores binárias (TestBTree.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Exemplo de utilizacao da uma arvore binaria
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   import java.util.Scanner;
   
   public class TestBTree {
      public static void main(String[] args) {
         // Ler arvore de inteiros em preorder
         Scanner in = new Scanner(System.in);
         BTree<Integer> t = LibBTree.readIntTree(in);
   
         // Escrever resultado de chamada a alguns metodos
         System.out.println("numberNodes = " + t.numberNodes());
         System.out.println("depth = " + t.depth());
         System.out.println("contains(2) = " + t.contains(2));
         System.out.println("contains(3) = " + t.contains(3));
   
         // Escrever nos da arvore seguindo varias ordens possiveis
         t.printPreOrder();      
         t.printInOrder();
         t.printPostOrder();
         t.printBFS();
         t.printDFS();
      }
   }
   

   ---

   Classe Utilitária (LibBTree.java)

   // -----------------------------------------------------------
   // Estruturas de Dados 2023/2024 (CC1007) - DCC/FCUP
   // https://www.dcc.fc.up.pt/~miguel-areias/teaching/2324/ed/
   // -----------------------------------------------------------
   // Classe utilitaria com metodo para ler uma arvore em preorder
   // Ex: 5 1 8 N N 6 N N 7 2 N N N
   // (Pedro Ribeiro @ DCC-FCUP)
   // -----------------------------------------------------------
   
   import java.util.Scanner;
   
   public class LibBTree {
      public static BTree<Integer> readIntTree(Scanner in) {
         BTree<Integer> t = new BTree<Integer>();
         t.setRoot(readIntNode(in));
         return t;
      }
      
      private static BTNode<Integer> readIntNode(Scanner in) {
         String s = in.next();
         if (s.equals("N")) return null;
         Integer value = Integer.parseInt(s);
         BTNode<Integer> left = readIntNode(in);
         BTNode<Integer> right = readIntNode(in);
         return new BTNode<Integer>(value, left, right);
      }
   }
   

2. Um primeiro teste.
   Crie um ficheiro input.txt contendo a seguinte linha: 5 1 8 N N 6 N N 7 2 N N N. Esta é a representação preorder da árvore binária da figura seguinte (onde N representa explicitamente um nó nulo).

   
   (as duas representações da imagems referem-se à mesma árvore)

   Agora execute a classe de teste das árvores dando como input o ficheiro que criou:

   $ java TestBTree < input.txt

   Procure acompanhar cada uma das linhas de código de TestBTree.java e perceber qual é o seu objetivo. Espreite também Para os métodos numberNodes, depth e contains.

3. Um segundo teste.
   Crie um ficheiro input2.txt contendo a descrição preorder da árvore binária de 7 nós descrita na figura da pergunta 1.2. Execute novamente TestBTree, agora com este novo input, e verifique se os resultados são os esperados.

Exercício 3) Vários exercícios de árvores

1. Contando o número de folhas.
   O método numberNodes conta o número de nós. Resolva o problema [ED204] Contando folhas (também disponível no Mooshak).
   

   Mostrar/Esconder Dicas

   • O número de folhas de uma árvore é igual ao número de folhas da subárvore esquerda mais o número de folhas da subárvore direita
   • Um caso base é quando o nó é uma folha... nesse caso devemos devolver 1
   • Outro caso base é quando a árvore é nula... nessa caso devemos devolver 0

   Como este é o primeiro exercício de árvores aqui fica uma possível solução já em código Java:

   Mostrar/Esconder Possível Solução

       // [ED204] Contando Folhas
       // Pedro Ribeiro (DCC/FCUP)
         
       public int numberLeafs() {
   	return numberLeafs(root);
       }
       private int numberLeafs(BTNode<T> n) {
   	if (n==null) return 0;
   	if (n.getLeft()==null && n.getRight()==null) return 1;
   	return numberLeafs(n.getLeft()) + numberLeafs(n.getRight()); 	
       }
   

2. Verificando se uma árvore é "estritamente binária".
   Resolva o problema [ED205] Árvores estritamente binárias (também disponível no Mooshak).

   Mostrar/Esconder Dicas

   • Uma árvore é estritamente binária se ambas as suas subárvores (esquerda e direita) foram estritamente binárias.
   • Em cada nó, deve verificar se este é válido, ou seja, se é folha ou se tem dois filhos:
   • Se não for válido é só devolver... false!
   • Se for válido, ainda falta verificar se ambas as sub-árvores esquerda e direita são também estritamente binárias.
3. Caminhos numa árvore
   Resolva o problema [ED206] Percorrendo caminhos (também disponível no Mooshak).

   Mostrar/Esconder Dicas

   • Olhar para a primeira letra permite decidir se devemos ir para a esquerda ou para a direita. Qual o método da classe String para ver um caracter numa dada posição?
   • Depois de avançar, falta processar o resto do caminho (tudo excepto a primeira letra). Consegue ver um método da classe String que lhe permite obter todos os caracteres excepto o primeiro?
4. Número de nós a uma dada profundidade
   Resolva o problema [ED207] Nós profundos (também disponível no Mooshak).

Exercícios extra para consolidação de conhecimentos

Aqui ficam mais alguns problemas envolvendo árvores:

1. [ED211] Contando os números pares (também disponível no Mooshak).
   

   Mostrar/Esconder Dicas

   • Este problema é muito semelhante a contar o número de nós
   • Ao invés de contar todos, conte apenas aqueles que são divisíveis por 2 (utilize o operador %, que devolve o resto da divisão inteira)
2. [ED212] Soma de todos os níveis (também disponível no Mooshak).
   

   Mostrar/Esconder Dicas

   • Comece por criar um array com tamanho igual à altura + 1 (note que já tem disponível um método para ver a altura)
   • Faça um método auxiliar para contar a soma apenas de um dado nível
   • Faça um ciclo para passar por todos os níveis, chamando para cada um o método auxiliar que criou anteriorment e colocando o resultado na posição respectiva do array.
3. [ED213] Caminho de maior soma (também disponível no Mooshak).
   

Baseado em material didático de Pedro Ribeiro (DCC-FCUP)