 |
|
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 JavaScriptQuantidade de visualizações: 1634 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>
|
 Link para compartilhar na Internet ou com seus amigos: |
Desafios, Exercícios e Algoritmos Resolvidos de JavaScript |
Veja mais Dicas e truques de JavaScript |
Dicas e truques de outras linguagens |
|
QGIS - Como definir o título do projeto do QGIS usando PyQGIS e a função setTitle() da classe QgsProject JavaScript - Como converter uma string para letras minúsculas em JavaScript usando a função toLowerCase() do objeto String |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
