Implementação de Árvore Binária em Java: Inserção e Percursos

Implementação de Árvore Binária em Java

public class ArvoreBinaria {

private NodoArvore raiz;

public ArvoreBinaria() {
raiz = null;
}

Inserção de Elementos

public void insereArvore(int info) {
NodoArvore nodo = new NodoArvore(info);

if (raiz == null) {
raiz = nodo;
return;
} else {
NodoArvore t = raiz;
while (true) {
if (info < t.getInfo()) {
if (t.getEsquerda() != null) {
t = t.getEsquerda();
} else {
t.setEsquerda(nodo);
return;
}
} else {
if (t.getDireita() != null) {
t = t.getDireita();
} else {
t.setDireita(nodo);
return;
}
}
}
}
}

Inserção Recursiva

public void insereArvoreRecursivo(int v) {
if (this.raiz != null) {
insereArvoreR(this.raiz, v);
} else {
this.raiz = new NodoArvore(v);
}
}

private NodoArvore insereArvoreR(NodoArvore a, int info) {
if (a == null) {
a = new NodoArvore(info);
} else {
if (info < a.getInfo()) {
a.setEsquerda(insereArvoreR(a.getEsquerda(), info));
} else {
a.setDireita(insereArvoreR(a.getDireita(), info));
}
}
return a;
}

Percursos Recursivos

public void imprimePreFixado() {
imprimePreFixadoR(raiz);
}

private void imprimePreFixadoR(NodoArvore a) {
if (a != null) {
System.out.println(a.getInfo());
imprimePreFixadoR(a.getEsquerda());
imprimePreFixadoR(a.getDireita());
}
}

public void imprimeCentral() {
imprimeCentralR(raiz);
}

private void imprimeCentralR(NodoArvore a) {
if (a != null) {
imprimeCentralR(a.getEsquerda());
System.out.println(a.getInfo());
imprimeCentralR(a.getDireita());
}
}

public void imprimePosFixado() {
imprimePosFixadoR(raiz);
}

private void imprimePosFixadoR(NodoArvore a) {
if (a != null) {
imprimePosFixadoR(a.getEsquerda());
imprimePosFixadoR(a.getDireita());
System.out.println(a.getInfo());
}
}

Percursos Não Recursivos

public void preFixadoNR() {
Pilha p = new Pilha();
p.empilha(raiz);
NodoArvore nodo;
while (!p.vazia()) {
nodo = (NodoArvore) p.desempilha();
if (nodo != null) {
System.out.println(nodo.getInfo());
p.empilha(nodo.getDireita());
p.empilha(nodo.getEsquerda());
}
}
}

public void posFixadoNR() {
NodoArvore nodo = raiz;
PilhaComMarca p = new PilhaComMarca();
NodoPilhaComMarca nodoPilha;
NodoArvore nodoArvore;
p.empilha(nodo, false);
while (!p.vazia()) {
nodoPilha = (NodoPilhaComMarca) p.desempilha();
nodoArvore = (NodoArvore) nodoPilha.getElemento();
if (nodoPilha.getElemento() != null) {
if (nodoPilha.isMarca() == false) {
p.empilha(nodoArvore, true);
p.empilha(nodoArvore.getDireita(), false);
p.empilha(nodoArvore.getEsquerda(), false);
} else {
System.out.println(nodoArvore.getInfo());
}
}
}
}

Contagem de Elementos e Folhas

public int contaElementos() {
int conta = 0;
return contaElementosR(raiz, conta);
}

private int contaElementosR(NodoArvore a, int conta) {
if (a != null) {
conta++;
conta = contaElementosR(a.getEsquerda(), conta);
conta = contaElementosR(a.getDireita(), conta);
}
return conta;
}

public int contaFolhas() {
int conta = 0;
return contaFolhasR(raiz, conta);
}

private int contaFolhasR(NodoArvore nodo, int conta) {
if (nodo != null) {
if (nodo.getDireita() == null && nodo.getEsquerda() == null) {
conta++;
}
conta = contaFolhasR(nodo.getEsquerda(), conta);
conta = contaFolhasR(nodo.getDireita(), conta);
}
return conta;
}

Construção a Partir de Cadeia de Caracteres

public void constroiArvore(CadeiaChar c) {
raiz = constroiArvoreR(raiz, c);
}

private NodoArvore constroiArvoreR(NodoArvore raiz, CadeiaChar c) {
char simbolo = c.getProximoChar();
if (simbolo == '*') {
return null;
} else {
raiz = new NodoArvore(simbolo);
raiz.setEsquerda(constroiArvoreR(raiz.getEsquerda(), c));
raiz.setDireita(constroiArvoreR(raiz.getDireita(), c));
return raiz;
}
}

Cópia e Comparação de Árvores

public ArvoreBinaria copia() {
ArvoreBinaria arv2 = new ArvoreBinaria();
if (raiz == null) {
return arv2;
}
return copiaR(raiz, arv2);
}

private ArvoreBinaria copiaR(NodoArvore nodo, ArvoreBinaria arv2) {
if (nodo != null) {
arv2.insereArvore(nodo.getInfo());
copiaR(nodo.getEsquerda(), arv2);
copiaR(nodo.getDireita(), arv2);
}
return arv2;
}

public boolean compara(ArvoreBinaria a2) {
return comparaR(raiz, a2.raiz);
}

private boolean comparaR(NodoArvore nodo, NodoArvore nodo2) {
if ((nodo == null && nodo2 != null) || (nodo != null && nodo2 == null)) {
return false;
}
if (nodo != null && nodo2 != null) {
if (nodo.getInfo() != nodo2.getInfo()) {
return false;
} else {
return comparaR(nodo.getEsquerda(), nodo2.getEsquerda()) && comparaR(nodo.getDireita(), nodo2.getDireita());
}
}
return true;
}

}