 |
|
||||
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: 1577 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
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
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);
|
 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 |
|
AutoCAD VBA - Como criar uma linha no AutoCAD usando Autocad VBA e a função AddLine() do objeto ModelSpace C - Como comparar os primeiros n caracteres de duas strings usando a função strncmp() da linguagem C |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |
