//classe com os atrb
package estrutura;
public class No {
public int valor; //chave do no, o valor
public No filhoEsquerdo;
public No filhoDireito;
public No pai;
public No( int valor){
this.valor = valor; //acopla o valor da variavel , instanciando a folha q tem grau 0
}
}
//classe arvoreBinaria com os metodos
public class ArvoreBinaria {
public static No raiz;
public void inserir(int valor) {
inserir(raiz, valor);
}
private void inserir(No node, int valor) {
if (node == null) {
System.out.println("Inserindo na raiz o valor " + valor);
raiz = new No(valor);
raiz.pai = null;
} else if (valor < node.valor) {
if (node.filhoEsquerdo != null) {
inserir(node.filhoEsquerdo, valor);
} else {
System.out.println("Inserindo " + valor + " a esquerda de " + node.valor);
node.filhoEsquerdo = new No(valor);
node.filhoEsquerdo.pai = node;
}
} else if (node.filhoDireito != null) {
inserir(node.filhoDireito, valor);
} else {
System.out.println("Inserindo " + valor + " a direita de " + node.valor);
node.filhoDireito = new No(valor);
node.filhoDireito.pai = node;
}
}
public void preOrdem(No node) {
if (node != null) {
System.out.print(node.valor + " ");
preOrdem(node.filhoEsquerdo);
preOrdem(node.filhoDireito);
}
}
public void emOrdem(No node) {
if (node != null) {
emOrdem(node.filhoEsquerdo);
System.out.print(node.valor + " ");
emOrdem(node.filhoDireito);
}
}
public void posOrdem(No node) {
if (node != null) {
posOrdem(node.filhoEsquerdo);
posOrdem(node.filhoDireito);
System.out.print(node.valor + " ");
}
}
public No busca(int valor) {
return busca(raiz, valor);
}
private No busca(No node, int valor) {
// System.out.println("Percorrendo Nó: "+node.valor);
if (valor == node.valor) {
System.out.println("Valor: " + valor + " encontrado.");
return node;
} else if ((valor < node.valor) && (node.filhoEsquerdo != null)) {
return busca(node.filhoEsquerdo, valor);
} else if ((valor > node.valor) && (node.filhoDireito != null)) {
return busca(node.filhoDireito, valor);
} else {
System.out.println("Valor: " + valor + " não encontrado.");
return null;
}
}
public void verificaGrau(int valor) {
No encontrado = busca(valor);
if (encontrado == null) {
System.out.println("Valor: " + valor + " não encontrado.");
} else if ((encontrado.filhoEsquerdo == null) && (encontrado.filhoDireito == null)) {
System.out.println("Nó: " + encontrado.valor + " tem grau 0.");
} else if ((encontrado.filhoEsquerdo != null) && (encontrado.filhoDireito != null)) {
System.out.println("Nó: " + encontrado.valor + " tem grau 2.");
} else {
System.out.println("Nó: " + encontrado.valor + " tem grau 1.");
}
}
public void verificaAltura(int valor) {
No encontrado = busca(valor);
System.out.println("A altura do nó: " + encontrado.valor + " é :" + verificaAltura(encontrado));
}
private int verificaAltura(No node) {
if (node == null) {
return -1;
} else if ((node.filhoEsquerdo == null) && (node.filhoDireito == null)) { //
return 0;
} else if (node.filhoDireito == null) {
return 1 + verificaAltura(node.filhoEsquerdo);
} else if (node.filhoEsquerdo == null) {
return 1 + verificaAltura(node.filhoDireito);
} else {
return 1 + Math.max(verificaAltura(node.filhoEsquerdo), verificaAltura(node.filhoDireito));
}
}
public void verificaPai(int val) {
No encontrado = busca(val);
System.out.println("este é o valor " + encontrado.valor + " e seu pai é :" + verificaPai(encontrado));
}
private int verificaPai(No node) {
if (node.pai == null) {
return -1;
} else if (node.pai != null) { //se tem pai
return node.pai.valor;
} else {
return 0;
}
}
public void verificaProfundidade(int valor) {
No encontrado = busca(valor);
System.out.println("A profundidade do nó: " + encontrado.valor + " é :" + verificaProfundidade(encontrado));
}
private int verificaProfundidade(No node) {
if (node == null) {
return -1;
} else if (node.pai != null) { //se tem pai
return 1 + verificaProfundidade(node.pai);
} else {
return 0;
}
}
//remover: remove sempre o nó maior a direita da subarvore a esquerda/ ou o no menor da subarvore a direita
public No remover(No node, int valor) {
System.out.println(" Correndo No " + node.valor);
if (valor < node.valor) {
node.filhoEsquerdo = remover(node.filhoEsquerdo, valor);
} else if (valor > node.valor) {
node.filhoDireito = remover(node.filhoDireito, valor);
} else if (node.filhoEsquerdo != null && node.filhoDireito != null) // quando tem 2 filhos dir e esq
{
System.out.println(" Removeu No " + node.valor);
node.valor = encontraMinimo(node.filhoDireito).valor;
node.filhoDireito = removeMinimo(node.filhoDireito); //(node.filhoDireito);
} else {
System.out.println(" Removeu No " + node.valor);
if (node.filhoEsquerdo == null) {
node = node.filhoDireito; //qdo tem o filho direito apenas
} else {
node = node.filhoEsquerdo; //quando tem o filho esquerdo
}
}
return node;
}
public No encontraMinimo(No node) {
if (node != null) {
while (node.filhoEsquerdo != null) {
node = node.filhoEsquerdo;
}
}
return node;
}
public No removeMinimo(No node) {
if (node == null) {
System.out.println("ERRO");
} else if (node.filhoEsquerdo != null) {
node.filhoEsquerdo = removeMinimo(node.filhoEsquerdo);
return node;
} else {
return node.filhoDireito; //caso da subarvore a direita ter filhos ai puxa o filho direito
}
return null;
}
}