Árvore binária

Programação
#1

Estou tendo problemas para impedir a inserção de nomes iguais em uma árvore binária. Alguém pode me dar uma dica?

public static void Inserir(NO node, String nome) {

    if (node == null) {
        raiz = new NO(nome);
    } 
    
    else if (nome.compareTo(node.nome) < 0) {
        if (node.esquerda != null) {
            Inserir(node.esquerda, nome);
        } else {
            node.esquerda = new NO(nome);

        }
    } else if (node.direita != null) {
        Inserir(node.direita, nome);

    } else {
        node.direita = new NO(nome);
    }
    
    
}

Não consigo criar um laço para descobrir se o nome já existe, e os exemplos que encontrei online não parecem funcionar. Onde estou errando?

#2

Boa tarde Sidmarin,

Aqui mesmo no forum tem um post sobre isso:
http://www.guj.com.br/t/algoritmo-de-arvore-binaria/111779/2

Veja se clareia

#3

Obrigado pela atenção brow, mas preciso criar isso sem o uso de array’s ou linked list, apenas recursividade de código feito assim mesmo , sequencial.

#4

Antes faça assim:

int comparação = nome.compareTo(node.nome);

substitua os ifs por swicth/case:

switch (comparacao) {
 case -1:
  if (node.esquerda != null) {
   Inserir(node.esquerda, nome);
  } else {
   node.esquerda = new NO(nome);
  }
  break;

 case 1:
  if (node.direita != null) {
   Inserir(node.direita, nome);
  } else {
   node.direita = new NO(nome);
  }
  break;

 case 0: // são iguais
}
#5

if (op == 1) {

            System.out.println("Digite o nome a ser inserido : ");
            Scanner entrada2 = new Scanner(System.in);
            Inserir(raiz, entrada2.nextLine());

        }

public static void Inserir(NO node, String nome) {
if (node == null) {
raiz = new NO(nome);
}
else {
int comparacao;
comparacao = nome.compareTo(node.nome);
switch (comparacao) {

        case -1: {
            if (node.esquerda != null) {
            Inserir(node.esquerda, nome);
        } else {
            node.esquerda = new NO(nome);

        }
        }
        case 1: {

            if (node.direita != null) {
                Inserir(node.direita, nome);

            } else {
                node.direita = new NO(nome);
            }
        }

        case 0:

            System.out.println("O número já existe");

    }
}
}

Adaptei o código dessa forma, porém ele passou a ignorar a entrada dos nomes apartir do terceiro inserido, criando um problema na inserção dos nós e consequentemente na exclusão dos nós.

#6

faltou os break;s

#7

Só percebi agora que postei CRTL V errado, mas mesmo com os breaks ele não adiciona mais de dois nomes. Em questão de impedir a inclusão de nomes iguais ele funcionou. :x

#8

Me desculpa, o compareTo não retorna -1, 0 ou 1, terá que usar os ifs:

import java.lang.Math;

public class Arvore {
 static NO raiz;
 public static void Inserir(NO node, String nome) {
  if (node == null) {
   raiz = new NO(nome);
  } else {
   int comparacao;
   comparacao = nome.compareTo(node.nome);
   if (comparacao < 0) {
    if (node.esquerda != null) {
     Inserir(node.esquerda, nome);

    } else {
     node.esquerda = new NO(nome);
    }
   } else if (comparacao > 0) {
    if (node.direita != null) {
     Inserir(node.direita, nome);
    } else {
     node.direita = new NO(nome);
    }
   } else if (comparacao == 0)
    System.out.println("O número já existe " + nome);
  }
 }
 public static void main(String[] args) {
  for (int i = 0; i < 10; i += 1) {
   Inserir(raiz, "" + (char)('A' + ('Z' - 'A') * Math.random()));
  }
  System.out.println(raiz);
 }
}

public class NO {
 NO esquerda;
 NO direita;
 String nome;
 public NO(String nome) {
  this.nome = nome;
 }
 public String toString() {
  String resultado = "";
  if (esquerda != null) resultado += esquerda.toString();
  resultado += nome + " ";
  if (direita != null) resultado += direita.toString();
  return resultado;
 }
}
2 curtidas
#9

Agora sim meu parceiro, muito obrigado pela ajuda. Ajudou a mim e a vários estudantes do futuro que com certeza vão precisar desse apoio também. GG.