Você está aqui: JavaScript ::: Estruturas de Dados ::: Árvore Binária e Árvore Binária de Busca

Estruturas de dados em JavaScript - Como pesquisar um nó em uma árvore binária de busca usando um método recursivo em JavaScript

Quantidade de visualizações: 57 vezes
Nesta dica mostrarei um exemplo completo de como pesquisar um valor em uma árvore binária de busca em JavaScript. Note que o exemplo usa apenas valores numéricos, mas você não terá dificuldades para modificar a classe Nó para os dados que você precisar.

Vamos começar com a classe No, ou seja, a classe que representa os nós da árvore binária e que contém o valor numérico e também as referências para os nós esquerdo e direito.

Código para No.js:

// implementação da classe No
class No{
  // construtor do nó
  constructor(valor){
    this.valor = valor; // valor do nó  
    this.esquerdo = null; // filho esquerdo
    this.direito = null; // filho direito
  }
} 

Agora que já temos a classe No devidamente colocada em um arquivo .js separado, vamos criar a classe ArvoreBinariaBusca. Veja:

Código para ArvoreBinariaBusca.js:

// implementação da classe ArvoreBinariaBusca
class ArvoreBinariaBusca{
  raiz = null; // referência para a raiz da árvore

  // método usado para inserir um novo nó na árvore
  // retorna true se o nó for inserido com sucesso e false
  // se o elemento
  // não puder ser inserido (no caso de já existir um 
  // elemento igual)
  inserir(valor){
   // a árvore ainda está vazia?
   if(this.raiz == null){
     // vamos criar o primeiro nó e definí-lo como 
     // a raiz da árvore
     this.raiz = new No(valor); // cria um novo nó 
   }
   else{
     // localiza o nó pai do novo nó
     var pai = null;
     var noAtual = this.raiz; // começa a busca pela raiz
 
     // enquanto o nó atual for diferente de null
     while(noAtual != null){
       // o valor sendo inserido é menor que o nó atual?
       if(valor < noAtual.valor) {
         pai = noAtual;
         // vamos inserir do lado esquerdo
         noAtual = noAtual.esquerdo;
       }
       // o valor sendo inserido é maior que o nó atual
       else if(valor > noAtual.valor){
         pai = noAtual;
         // vamos inserir do lado direito
         noAtual = noAtual.direito;
       }
       else{
         // um nó com este valor foi encontrado 
         return false;
       } 
     }
 
     // cria o novo nó e o adiciona como filho do nó pai
     if(valor < pai.valor){
       pai.esquerdo = new No(valor);
     }
     else{
       pai.direito = new No(valor);
     }
   }
 
   // retorna true para indicar que o novo nó foi inserido
   return true;
  }

  // método que permite pesquisar na árvore 
  // binária de busca
  pesquisar(valor){
    // chama a versão recursiva do método
    return this.pesquisarRec(this.raiz, valor);
  }

  // outra versão do método pesquisar que possui dois 
  // parâmetros (esta é a versão recursiva do método)
  pesquisarRec(noAtual, valor){
    // o valor pesquisado não foi encontrado. Vamos
    // retornar null
    if(noAtual == null){
      return null;
    } 
 
    // o valor pesquisado foi encontrado?
    if(valor == noAtual.valor){
      return noAtual; // retorna o nó atual 
    }

    // ainda não encontramos...vamos disparar uma nova 
    // chamada para a sub-árvore da esquerda
    else if(valor < noAtual.valor){
      return this.pesquisarRec(noAtual.esquerdo, valor);
    }

    // ainda não encontramos...vamos disparar uma nova 
    // chamada para a sub-árvore da direita
    else{
      return this.pesquisarRec(noAtual.direito, valor);
    }
  }
}
// fim classe Arvore

E finalmente o código para a página HTML que contém uma função JavaScript que permite testar a árvore binária de busca:

<html>
<head>
  <title>Árvore Binária de Busca em JavaScript</title>
</head>
 
<body onload="testarArvore()">

<script type="text/javascript">
  function testarArvore(){
    // vamos criar um novo objeto da classe ArvoreBinariaBusca
    arvore = new ArvoreBinariaBusca();
  
    // vamos inserir 5 valores na árvore
    arvore.inserir(8);
    arvore.inserir(43);
    arvore.inserir(2);
    arvore.inserir(18);
    arvore.inserir(71);
  
    var valorPesquisa = 18;
    // obtém um objeto da classe NoArvore a partir do 
    // método pesquisar() da classe ArvoreBinariaBusca
    var res = arvore.pesquisar(valorPesquisa);
    // o valor foi encontrado?
    if(res != null){
      document.writeln("O valor foi encontrado na árvore");
    }
    else{
      document.writeln("O valor não foi encontrado na árvore");  
    }
  }
</script>

<!-- faz o import das classes No e ArvoreBinariaBusca //-->
<script src="No.js"></script>
<script src="ArvoreBinariaBusca.js"></script>

</body>
</html>



JavaScript ::: Fundamentos da Linguagem ::: Estruturas de Controle

JavaScript para iniciantes - Como usar o laço do-while da linguagem JavaScript

Quantidade de visualizações: 6671 vezes
O laço do..while (também chamado de loop ou laço repita enquanto) da linguagem JavaScript é usado quando queremos repetir uma instrução ou um grupo de instruções ENQUANTO uma condição for satisfeita. Veja sua sintáxe:

do{
  // uma instrução ou grupo de instruções
}while(condição);

A condição pode ser qualquer expressão que resulte em um valor boolean (true ou false). Note também que, diferente do laço while (enquanto) o teste condicional do laço do-while é feito DEPOIS de cada iteração (repetição) do laço. Isso faz com que este laço seja executado no mínimo uma vez.

Veja um trecho de código no qual usamos o laço do..while para contar de 0 até 10:

<html>
<head>
<title>Estudos JavaScript</title>
</head>
<body>

<script type="text/javascript">
  var i = 0;
  
  do{
    document.write(i + "<br>");
    i++;
  }while(i <= 10);  
</script>

</body>
</html>

Ao executarmos este código teremos o seguinte resultado:

0
1
2
3
4
5
6
7
8
9
10

Veja que declaramos uma variável de controle i e a inicializamos com o valor 0. No corpo do laço nós exibimos o valor da variável de controle e a incrementamos em 1. Em seguida nós verificamos se seu valor é menor ou igual a 10. Como esta condição é satisfeita, o laço é executado pela segunda vez. Dessa forma o ciclo continua até que o valor da variável de controle seja maior que 10, o que faz com que o laço cesse sua repetição.

Veja agora como modificar o laço do-while anterior para exibir os números de 10 até 0:

<html>
<head>
<title>Estudos JavaScript</title>
</head>
<body>

<script type="text/javascript">
  var i = 10;
  
  do{
    document.write(i + "<br>");
    i--;
  }while(i >= 0);  
</script>

</body>
</html>

Agora o resultado do código será:

10
9
8
7
6
5
4
3
2
1
0

Esta dica foi escrita e testada no Internet Explorer 8 e Firefox 3.6.


JavaScript ::: Dicas & Truques ::: Data e Hora

Datas e horas em JavaScript - Como obter o valor do ano em um objeto Date usando a função getFullYear()

Quantidade de visualizações: 7958 vezes
Em algumas situações nós precisamos obter o ano de uma determinada data como um inteiro de quatro dígitos. Para isso nós podemos usar a função getFullYear() do objeto Date da linguagem JavaScript.

Veja o código a seguir:

<html>
<head>
<title>Estudando JavaScript</title>
</head>
<body>

<script type="text/javascript">
  var data = new Date();
  var ano = data.getFullYear();
  document.write("Estamos no ano: " + ano);
</script>
 
</body>
</html>

Ao executarmos este código nós teremos o seguinte resultado:

Estamos no ano: 2021


JavaScript ::: Dicas & Truques ::: Strings e Caracteres

JavaScript para iniciantes - Como converter uma string para letras maiúsculas usando a função toUpperCase() do objeto String do JavaScript

Quantidade de visualizações: 16035 vezes
A função toUpperCase() do objeto String da linguagem JavaScript nos permite transformar todos os caracteres de uma palavra, frase ou texto em letras maiúsculas.

Veja o código completo para o exemplo:

<html>
<head>
<title>Estudando JavaScript</title>
</head>
<body>
 
<script type="text/javascript">
  var frase = "Veja Esta Frase.";
  document.writeln(frase);  
  frase = frase.toUpperCase();
  document.writeln("<br>" + frase);
</script>
 
</body>
</html>

Ao executarmos este código nós teremos o seguinte resultado:

Veja Esta Frase.
VEJA ESTA FRASE.


JavaScript ::: Dicas & Truques ::: Arrays e Matrix (Vetores e Matrizes)

Adicionando três elementos ao final de um vetor em JavaScript usando o método push() do objeto Array - Como adicionar elementos ao final de um vetor usando JavaScript - Revisado

Quantidade de visualizações: 6126 vezes
Neste dica mostrarei como usar o método push() do objeto Array da linguagem JavaScript para adicionar três elementos ao final de um vetor. Veja o código completo, incluindo a página HTML que permite executar o exemplo:

<html>
<head>
  <meta charset="utf-8">
  <title>Estudos JavaScript</title>
</head>
<body>

<script type="text/javascript">
  // vamos declarar e instanciar um vetor com 5 elementos
  var valores = new Array(1, 2, 3, 4, 5);
  document.write("Valores no vetor: " + valores + "<br>");
  
  // agora vamos adicionar mais três elementos
  valores.push(6, 7, 8);
  document.write("Valores no vetor: " + valores);
</script>

</body>
</html>

Ao abrir esta página HTML nós teremos o seguinte resultado:

Valores no vetor: 1,2,3,4,5
Valores no vetor: 1,2,3,4,5,6,7,8


JavaScript ::: Dicas & Truques ::: Recursão (Recursividade)

JavaScript Avançado - Como remover todas as ocorrências de uma substring em uma string usando uma função recursiva

Quantidade de visualizações: 8533 vezes
Esta dica contém um ótimo exercício de recursão. Trata-se de uma função JavaScript recursiva para remover todas as ocorrências de uma substring em uma string. Analise o código cuidadosamente e você conseguirá desenvolver várias funções de recursividade a partir dele.

Veja o código JavaScript completo:

<html>
<head>
<title>Estudando JavaScript</title>
</head>
<body>

<script type="text/javascript">
  // função recursiva que remove todas as ocorrências
  // de uma substring em uma string
  function remover(string, substring){
    // primeiro obtemos o índice da substring
    // dentro da string
    var indice = string.indexOf(substring);
    var resultado = "";
  
    // interromper a recursividade? 
    if(indice == -1){
      return string;
    }
    else{
      resultado += string.substring(0, indice) + 
        remover(string.substring(indice + substring.length),
        substring);
    }    

    return resultado;
  }

  // hora de testar a função recursiva
  var frase = "Ontem comprei duas camisas e uma calça";
  document.writeln("Original: " + frase);
  frase = remover(frase, "duas");
  document.writeln("<br>Nova frase: " + frase);  
</script>
 
</body>
</html>

Ao executar este código nós teremos o seguinte resultado:

Original: Ontem comprei duas camisas e uma calça
Nova frase: Ontem comprei camisas e uma calça


Veja mais Dicas e truques de JavaScript

Dicas e truques de outras linguagens

Quem Somos

Osmar J. Silva
WhatsApp +55 (062) 98553-6711

Goiânia-GO
Full Stack Developer, Professional Java Developer, PHP, C/C++, Python Programmer, wxWidgets Professional C++ Programmer, Freelance Programmer. Formado em Ciência da Computação pela UNIP (Universidade Paulista Campus Goiânia) e cursando Engenharia Elétrica pela PUC-Goiás. Possuo conhecimentos avançados de Java, Python, JavaScript, C, C++, PHP, C#, VB.NET, Delphi, Android, Perl, e várias tecnologias que envolvem o desenvolvimento web, desktop, front-end e back-end. Atuo há mais de 15 anos como programador freelancer, atendendo clientes no Brasil, Portugal, Argentina e vários outros paises.
Entre em contato comigo para, juntos, vermos em que posso contribuir para resolver ou agilizar o desenvolvimento de seus códigos.
José de Angelis
WhatsApp +55 (062) 98243-1195

Goiânia-GO
Formado em Sistemas de Informação pela Faculdade Delta, Pós graduado em Engenharia de Software (PUC MINAS), Pós graduado Marketing Digital (IGTI) com ênfase em Growth Hacking. Mais de 15 anos de experiência em programação Web. Marketing Digital focado em desempenho, desenvolvimento de estratégia competitiva, analise de concorrência, SEO, webvitals, e Adwords, Métricas de retorno. Especialista Google Certificado desde 2011 Possui domínio nas linguagens PHP, C#, JavaScript, MySQL e frameworks Laravel, jQuery, flutter. Atualmente aluno de mestrado em Ciência da Computação (UFG)
Não basta ter um site. É necessário ter um site que é localizado e converte usuários em clientes. Se sua página não faz isso, Fale comigo e vamos fazer uma analise e conseguir resultados mais satisfatórios..

Linguagens Mais Populares

1º lugar: Java
2º lugar: C#
3º lugar: PHP
4º lugar: Delphi
5º lugar: Python
6º lugar: JavaScript
7º lugar: C
8º lugar: C++
9º lugar: VB.NET
10º lugar: JSP (Java Server Pages)



© 2021 Arquivo de Códigos - Todos os direitos reservados | Versión en Español | Versão em Português