Introdução
Neste laboratório, aprenderemos como implementar uma Árvore de Busca Binária (Binary Search Tree) em Java. Uma Árvore de Busca Binária é uma estrutura de dados de árvore binária na qual o valor de cada nó é maior ou igual aos valores em sua subárvore esquerda e menor ou igual aos valores em sua subárvore direita.
Criando a Classe BSTNode
Primeiramente, vamos criar uma classe Java que representa o nó de uma árvore de busca binária e chamá-la de BSTNode. Um nó em uma árvore de busca binária deve ter um valor e dois nós filhos - um à sua esquerda e outro à sua direita.
class BSTNode {
int value;
BSTNode leftChild;
BSTNode rightChild;
BSTNode(int val) {
this.value = val;
this.leftChild = null;
this.rightChild = null;
}
}
Inserindo Elementos na Árvore de Busca Binária
Para inserir elementos na árvore de busca binária, seguimos o seguinte algoritmo:
- Se o novo valor for menor que o valor do nó atual, então recursivamente vá para o filho esquerdo.
- Se o novo valor for maior que o valor do nó atual, então recursivamente vá para o seu filho direito.
- Se o nó atual for nulo, então adicione o novo valor nesta posição.
public static BSTNode insert(int value, BSTNode current) {
if (current == null) {
BSTNode newNode = new BSTNode(value);
return newNode;
} else {
if (value < current.value)
current.leftChild = insert(value, current.leftChild);
else
current.rightChild = insert(value, current.rightChild);
}
return current;
}
Para testar este método, crie a árvore de busca binária e insira alguns elementos:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Print out the tree to verify the insertion
System.out.println("Traversal after insertion: ");
inorderTraversal(root);
}
// Function to traverse the tree inorder
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}
Saída:
Traversal after insertion:
5 7 9 12 20 21
Buscando um Elemento na Árvore de Busca Binária
Para buscar um elemento na árvore de busca binária, seguimos o seguinte algoritmo:
- Se o valor do nó atual corresponder ao valor que estamos tentando encontrar, então retorne verdadeiro (true).
- Se o valor do nó atual for maior que o valor que estamos tentando encontrar, então recursivamente vá para o filho esquerdo.
- Se o valor do nó atual for menor que o valor que estamos tentando encontrar, então recursivamente vá para o filho direito.
- Se o nó atual for nulo, então retorne falso (false).
public static boolean search(int key, BSTNode current) {
if (current == null)
return false;
if (current.value == key)
return true;
else {
if (key < current.value)
return search(key, current.leftChild);
else
return search(key, current.rightChild);
}
}
Para testar este método, busque por alguns elementos:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Search for elements
System.out.println(search(7, root));
System.out.println(search(9, root));
System.out.println(search(17, root));
}
Saída:
true
true
false
Removendo um Elemento de uma Árvore de Busca Binária
Excluir um elemento de uma árvore de busca binária é um pouco mais complexo do que os passos anteriores, pois precisamos lidar com diferentes casos dependendo do tipo de nó:
- Se o nó não tiver filhos (um nó folha), simplesmente remova-o.
- Se o nó tiver apenas um filho, substitua-o por seu único filho.
- Se o nó tiver dois filhos, substitua-o pelo valor mínimo da subárvore direita ou pelo valor máximo da subárvore esquerda.
public static BSTNode delete(int value, BSTNode current) {
if (current == null)
return current;
if (value < current.value)
current.leftChild = delete(value, current.leftChild);
else if (value > current.value)
current.rightChild = delete(value, current.rightChild);
else if (value == current.value) {
if (current.leftChild != null && current.rightChild != null) {
int min = current.rightChild.value;
BSTNode temp = current.rightChild;
while (temp.leftChild != null) {
min = temp.leftChild.value;
temp = temp.leftChild;
}
current.value = min;
current.rightChild = delete(min, current.rightChild);
} else if (current.leftChild == null)
return current.rightChild;
else if (current.rightChild == null)
return current.leftChild;
}
return current;
}
Para testar este método, exclua alguns nós e imprima a árvore:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// Delete some nodes
root = delete(12, root);
root = delete(20, root);
root = delete(9, root);
// Print the tree to verify the deletion
System.out.println("Traversal after deletion: ");
inorderTraversal(root);
}
Saída:
Traversal after deletion:
5 7 21
Percorrendo a Árvore de Busca Binária
Podemos percorrer uma árvore de busca binária de diferentes maneiras:
- Inorder Traversal (Esquerda-Raiz-Direita)
- Preorder Traversal (Raiz-Esquerda-Direita)
- Postorder Traversal (Esquerda-Direita-Raiz)
- Level-order Traversal (BFS)
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}
public static void preorderTraversal(BSTNode current) {
if (current == null)
return;
System.out.print(current.value + " ");
preorderTraversal(current.leftChild);
preorderTraversal(current.rightChild);
}
public static void postorderTraversal(BSTNode current) {
if (current == null)
return;
postorderTraversal(current.leftChild);
postorderTraversal(current.rightChild);
System.out.print(current.value + " ");
}
public static void levelOrderTraversal(BSTNode root) {
Queue<BSTNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
BSTNode temp = queue.poll();
System.out.print(temp.value + " ");
if (temp.leftChild != null)
queue.add(temp.leftChild);
if (temp.rightChild != null)
queue.add(temp.rightChild);
}
}
Para testar esses métodos, imprima a árvore usando cada técnica de travessia:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
System.out.print("Inorder Traversal: ");
inorderTraversal(root);
System.out.print("\nPreorder Traversal: ");
preorderTraversal(root);
System.out.print("\nPostorder Traversal: ");
postorderTraversal(root);
System.out.print("\nLevel-order Traversal: ");
levelOrderTraversal(root);
}
Saída:
Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21
Resumo
Neste laboratório, aprendemos como criar, inserir elementos, pesquisar um elemento, excluir um elemento e percorrer uma Árvore de Busca Binária em Java.
Primeiramente, criamos a classe BSTNode, que representa um nó na árvore de busca binária. Em seguida, implementamos as funcionalidades de inserção, pesquisa e exclusão usando algoritmos específicos para árvores de busca binária. Finalmente, aprendemos como percorrer a árvore de busca binária usando diferentes técnicas de travessia, como inorder, preorder, postorder e level-order traversal.
Com esses conceitos, você deve ser capaz de implementar árvores de busca binária em seus próprios programas Java.
