VB .NET - Árvore Binária (Binary Tree)

  Neste artigo vou apresentar os conceitos sobre árvore e árvore binária no cenário de Tecnologia da Informação com implementação feita pela linguagem VB .NET.

Vamos começar com a conceituação de árvore binária recorrendo a Wikipédia:

Na ciência da computação, uma árvore binária é uma estrutura de dados em árvore em que cada nó tem no máximo dois filhos, que são referidos como o nó filho esquerdo e nó filho direito.
(https://en.wikipedia.org/wiki/Binary_tree)

ou

Uma árvore binária é uma estrutura de dados caracterizada por:

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária. (https://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria)

Vamos ser um pouco mais detalhista iniciando pela definição de árvore no contexto da TI.

O que é uma árvore ?

Uma árvore é formada por um conjunto finito T de elementos denominados vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados em m>=1 conjuntos distintos não vazios, as subárvores de r, sendo cada um destes conjuntos por sua vez uma árvore. 

Lembrando que os conjuntos das subárvores tem de ser disjuntos.

Na figura abaixo temos uma árvore com nove nós onde A é o nó raiz a direita e uma estrutura à esquerda que não é uma árvore:

Árvore com 9 nós sendo o nó A o nó raiz Estrutura que não é uma árvore

O que é uma árvore binária ?

Em uma árvore binária cada nó tem no máximo duas subárvores, e quando há somente uma presente é necessário distinguir entre subárvore esquerda e direita.

Árvores binárias podem ser vistas em diversas situações do cotidiano. Por exemplo, um torneio de futebol eliminatório, como a Copa do Brasil, em que a cada etapa os times são agrupados dois a dois e sempre são eliminados metade dos times é uma árvore binária. 

Formalmente uma árvore binária pode ser definida como um conjunto finito de nós, que é vazio, ou consiste de um nó raiz e dois conjuntos disjuntos de nós, a subárvore esquerda e a subárvore direita.

Para concluir a teoria podemos ter os seguintes tipos de árvore binária:

1- Uma árvore estritamente binária é uma árvore binária em que cada nó tem 0 ou 2 filhos.

2- Uma árvore binária cheia é uma árvore em que se um nó tem alguma subárvore vazia então ele está no último nível.

3- Uma árvore completa é aquela em que se n é um nó com algumas de subárvores vazias, então n se localiza no penúltimo ou no último nível. Portanto, toda árvore cheia é completa e estritamente binária.

Aplicação prática de utilização de árvore binária

Problema : Suponhamos que precisamos descobrir números duplicados em uma lista não ordenada de números.

Solução:

Podemos usar uma árvore binária para manter os números.

- O primeiro número lido é colocado na raiz da árvore.
- Cada novo número lido é comparado com o elemento raiz, caso seja igual é uma duplicata e voltamos a ler outro número.
- Se é menor repetimos o processo com a árvore da direita e se maior com a árvore da esquerda.
- Este processo continua até que uma duplicata é encontrada ou uma árvore vazia é achada. Neste caso, o número é inserido na posição devida na árvore.

Considere que os números : 7 8 2 5 8 3 5 10 4

Neste caso seria construída a árvore binária da figura abaixo:

Agora vamos sujar as mãos criando uma implementação para uma busca em uma árvore binária usando a linguagem VB .NET.

Recursos Usados

Criando o projeto no VS 2015 Community

Abra o VS 2015 Community clique em New Project;

Selecione a linguagem VB .NET e o template Console Application informando o nome ArvoreBinaria_VBNET;

Definindo a classe Node

No menu Project clique em Add Class e informe o nome Node.vb inserindo o código abaixo nesta classe:

Public Class Node
    Public iData As Integer
    Public Left As Node
    Public Right As Node
    Public Sub ExibirNode()
        Console.Write(iData & " ")
    End Sub
End Class

Definindo a classe BinarySearchTree

Nesta classe vamos criar os seguintes métodos :

Cada uma dessas abordagens é muito útil e tem suas próprias aplicações. Neste artigo vamos considerar percorrer a ordem usando a travessia naOrdem.

Este é um processo recursivo como explicado a seguir:

ublic Class BinarySearchTree
    Public root As Node
    Public Sub New()
        root = Nothing
    End Sub
    Public Sub Inserir(ByVal i As Integer)
        Dim novoNode As New Node()
        novoNode.iData = i
        If (root Is Nothing) Then
            root = novoNode
            Console.WriteLine("Criado o Nó raiz : " & i)
        Else
            Dim atual As Node = root
            Dim parent As Node
            While (True)
                parent = atual
                If (i < atual.iData) Then
                    atual = atual.Left
                    If (atual Is Nothing) Then
                        parent.Left = novoNode
                        Exit While
                    End If
                Else
                    atual = atual.Right
                    If (atual Is Nothing) Then
                        parent.Right = novoNode
                        Exit While
                    End If
                End If
            End While
            Console.WriteLine("Adicionado na árvore: " & i)
        End If
    End Sub
    Public Sub naOrdem(ByVal ARaiz As Node)
        If (Not (ARaiz Is Nothing)) Then
            naOrdem(ARaiz.Left)
            ARaiz.ExibirNode()
            naOrdem(ARaiz.Right)
        End If
    End Sub
    Public Sub preOrdem(ByVal ARaiz As Node)
        If (Not (ARaiz Is Nothing)) Then
            ARaiz.ExibirNode()
            preOrdem(ARaiz.Left)
            preOrdem(ARaiz.Right)
        End If
    End Sub
    Public Sub posOrdem(ByVal ARaiz As Node)
        If (Not (ARaiz Is Nothing)) Then
            posOrdem(ARaiz.Left)
            posOrdem(ARaiz.Right)
            ARaiz.ExibirNode()
        End If
    End Sub
End Class

Para testar a nossa implementação vamos definir o código abaixo no módulo Module1:

Module Module1
    Sub Main()
        Dim numeros As New BinarySearchTree()
        numeros.Inserir(23)
        numeros.Inserir(45)
        numeros.Inserir(16)
        numeros.Inserir(37)
        numeros.Inserir(3)
        numeros.Inserir(99)
        numeros.Inserir(22)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando naOrdem : ")
        numeros.naOrdem(numeros.root)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando preOrdem : ")
        numeros.preOrdem(numeros.root)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando posOrdem : ")
        numeros.posOrdem(numeros.root)
        Console.ReadKey()
    End Sub
End Module

Executando o projeto iremos obter o seguinte resultado:

Podemos também implementar a busca pelo elemento de valor mínimo e de valor máximo na classe BinarySearchTree ´:

 Public Function LocalizaMin() As Integer
        Dim current As Node = root
        While (Not (current.Left Is Nothing))
            current = current.Left
        End While
        Return current.iData
    End Function

    Public Function LocalizaMax() As Integer
        Dim current As Node = root
        While (Not (current.Right Is Nothing))
            current = current.Right
        End While
        Return current.iData
    End Function

Testando os novos métodos podemos alterar o código do módulo Module1 conforme abaixo:

Module Module1
    Sub Main()
        Dim numeros As New BinarySearchTree()
        numeros.Inserir(23)
        numeros.Inserir(45)
        numeros.Inserir(16)
        numeros.Inserir(37)
        numeros.Inserir(3)
        numeros.Inserir(99)
        numeros.Inserir(22)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando naOrdem : ")
        numeros.naOrdem(numeros.root)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando preOrdem : ")
        numeros.preOrdem(numeros.root)
        Console.WriteLine("")
        Console.WriteLine("Atravessando a árvore usando posOrdem : ")
        numeros.posOrdem(numeros.root)
        Console.WriteLine(" ")
        Console.WriteLine("Elemento com valor Mínimo " & numeros.LocalizaMin())
        Console.WriteLine(" ")
        Console.WriteLine("Elemento com valor Máximo " & numeros.LocalizaMax())
        Console.ReadKey()
    End Sub
End Module

Executando o projeto iremos obter:

Pegue o projeto completo aqui :   ArvoreBinaria_VBNET.zip

Jesus Cristo é o mesmo, ontem, e hoje, e eternamente.
Hebreus 13:8

Veja os Destaques e novidades do SUPER DVD Visual Basic (sempre atualizado) : clique e confira !

Quer migrar para o VB .NET ?

Quer aprender C# ??

Quer aprender os conceitos da Programação Orientada a objetos ?

Quer aprender o gerar relatórios com o ReportViewer no VS 2013 ?

Quer aprender a criar aplicações Web Dinâmicas usando a ASP .NET MVC 5 ?

  Gostou ?   Compartilhe no Facebook   Compartilhe no Twitter

Referências:

José Carlos Macoratti