EDU - BinaryTree

package projetoArvore;

import java.util.Scanner;

public class BinaryTree {

	private BinaryNode root;

	public void add(int info) {

		/**
		 * Metodo para adicionar um no a arvore binaria ordenada
		 */
		BinaryNode newNode = new BinaryNode(info); // Cria um no com o valor
													// recebido

		if (root == null) { // Verifica se a raiz esta vazia
			root = newNode; // Caso esteja, o no sera a raiz
			System.out.println("Raiz adicionada");
		} else {// Caso nao esteja vazia
			BinaryNode aux = root; // Cria um no aux para percorrer a arvore
			while ((aux != null) && (aux.getInfo() != info)) { // Verfica se o
																// no aux e
																// vazio e se a
																// info ja
																// existe na
																// arvore
				if (info < aux.getInfo()) { // Verifica se o no inserido e menor
											// que a raiz
					if (aux.getLeft() == null) { // Verifica se o no a esquerda
													// esta vazio
						aux.setLeft(newNode); // Caso seja entao sera adicionado
												// a esquerda da raiz
						System.out.println("Adicionado a esquerda");
						break;
					} else {// Caso nao esteja vazio
						aux = aux.getLeft();// Aponta o no aux para o no a
											// esquerda da raiz
						System.out.println("Entrou left else");
					}
				} else {// No inserido e maior que a raiz
					if (aux.getRight() == null) { // Verifica se o no a direita
													// esta vazio
						aux.setRight(newNode);// Caso esteja entao sera
												// adicionado a direita da raiz
						System.out.println("Adicionado a direita");
						break;
					} else {// Caso nao esteja vazio
						aux = aux.getRight();// Aponta o no aux para o no a
												// direita da raiz
						System.out.println("Entrou right else");
					}
				}
			}
		}
	}

	public BinaryNode search(int info) {
		/**
		 * Metodo para encontrar o no desejado
		 */

		if (this.exist(info)) {
			BinaryNode aux = root; // Aponta o no aux para a raiz
			while (aux != null) { // Verifica se o aux nao e nulo
				if (aux.getInfo() == info) { // Caso o valor do aux seja igual
												// ao
												// valor recebido
					return aux;
				} else {
					if (info < aux.getInfo()) { // Verifica se o valor recebido
												// e
												// menor que o valor do aux
						aux = aux.getLeft(); // Se for, entao aponta o aux para
												// a
												// esquerda do aux anterior
					} else {
						aux = aux.getRight();// Caso contrario, aponta o aux
												// para a
												// direita do aux anterior
					}
				}
			}

		}
		return null;
	}

	public boolean exist(int info) {
		/**
		 * Metodo para verificar se o no existe na arvore
		 * 
		 */
		BinaryNode aux = root; // Aponta o no aux para a raiz
		while (aux != null) { // Verifica se o aux nao e nulo
			if (aux.getInfo() == info) { // Caso o valor do aux seja igual ao
											// valor recebido
				return true;
			} else {
				if (info < aux.getInfo()) { // Verifica se o valor recebido e
											// menor que o valor do aux
					aux = aux.getLeft(); // Se for, entao aponta o aux para a
											// esquerda do aux anterior
				} else {
					aux = aux.getRight();// Caso contrario, aponta o aux para a
											// direita do aux anterior
				}
			}
		}
		return false;

	}

	public void remove(int info) {

		if (root == null) { // Verifica se a raiz e nula

		} else if (root.getInfo() == info) {// Verifica se o no a ser excluido e
											// a raiz
			if (root.getLeft() == null) {// Verifica se o lado esquerdo da raiz
											// e nulo
				root = root.getRight();// Exclui a raiz e considera somento seu
										// lado direito
			} /*
				 * else if (root.getRight() == null) {// Verifica se o lado
				 * direito // da raiz e nulo root = root.getLeft();// Exclui a
				 * raiz e considera somente seu // lado esquerdo }
				 */ else {
				BinaryNode father, aux, fatherAux;
				father = root;
				aux = father.getLeft();// Aponta para o maior numero presente no
										// lado esquerdo da arvore
				fatherAux = aux;
				if (aux.getRight() == null) {// Caso o maior no seja o a
												// esquerda da raiz

					father.setLeft(fatherAux.getLeft());// Adiciona o ramo
														// esquerdo do no aux no
														// seu local
				}
				while (aux.getRight() != null) {// Caso o no tenha um no maior
					fatherAux = aux;
					aux = aux.getRight();
				} // Aponta o aux para o maior no do lado
					// esquerdo

				father.setInfo(aux.getInfo());// Atribui o valor do no aux a
												// raiz
				fatherAux.setRight(aux.getLeft()); // Exclui o maior no a
													// esquerda

			}
		} else {
			BinaryNode father, aux;
			aux = root;
			father = aux;
			while (aux.getInfo() != info && aux != null) {
				father = aux;
				aux = (info > aux.getInfo() ? aux.getRight() : aux.getLeft());

			}
			if (aux != null && father != null) {
				if (father.getLeft() == aux) {
					father.setLeft(this.removalProcess(aux));
				} else {
					father.setRight(this.removalProcess(aux));
				}
			}
		}
		System.out.println(root);
	}

	private BinaryNode removalProcess(BinaryNode node) {
		if (node.getLeft() == null) {// Verifica se o lado esquerdo da raiz
										// e nulo
			node = node.getRight();// Exclui a raiz e considera somento seu
									// lado direito
		} /*
			 * else if (node.getRight() == null) {// Verifica se o lado direito
			 * // da raiz e nulo node = node.getLeft();// Exclui a raiz e
			 * considera somente seu // lado esquerdo }
			 */ else {

			BinaryNode father, aux, fatherAux;
			father = node;
			aux = father.getLeft();// Aponta para o maior numero presente no
									// lado esquerdo da arvore
			fatherAux = aux;
			if (aux.getRight() == null) {// Caso o maior no seja o a
											// esquerda da raiz

				father.setLeft(fatherAux.getLeft());// Adiciona o ramo
													// esquerdo do no aux no
													// seu local
			}
			while (aux.getRight() != null) {// Caso o no tenha um no maior
				fatherAux = aux;
				aux = aux.getRight();
			} // Aponta o aux para o maior no do lado
				// esquerdo

			father.setInfo(aux.getInfo());// Atribui o valor do no aux a
											// raiz
			fatherAux.setRight(aux.getLeft()); // Exclui o maior no a esquerda

		}
		return node;
	}

	public void printPreOrder() {
		this.startPrintPreOrder(root);
	}

	private void startPrintPreOrder(BinaryNode node) {
		if (node != null) {
			System.out.println(node.getInfo());
			this.startPrintPreOrder(node.getLeft());
			this.startPrintPreOrder(node.getRight());
		}
	}

	public int depth(int info) throws Exception {
		int contador = 0;
		BinaryNode aux = root;
		while (aux != null) {
			if (aux.getInfo() == info) {
				return contador;
			}
			contador++;
			aux = (info > aux.getInfo() ? aux.getRight() : aux.getLeft());
		}
		throw new Exception();

	}

	public int height(int info) {

		BinaryNode aux = root;
		while (aux != null) {
			if (aux.getInfo() == info) {
				return altura(aux);
			}

			aux = (aux.getInfo() < info ? aux.getRight() : aux.getLeft());
		}
		return -1;
	}

	private int altura(BinaryNode node) {
		if (node == null) {
			return -1;
		}
		return (altura(node.getRight()) > altura(node.getLeft()) ? altura(node.getRight()) + 1
				: altura(node.getLeft()) + 1);
	}
//TODO
	public void printBinaryTree() throws Exception {
		int size = this.height(root.getInfo());
		int depth = 0;
		do {
			this.preOrdPrint(root, depth);
			depth++;

		} while (depth != (size + 1));
	}

	private void preOrdPrint(BinaryNode node, int depth) throws Exception {

		BinaryNode aux = node;

		if (aux != null) {
			int value = this.depth(aux.getInfo());
			if (value == depth) {
				System.out.println(aux.getInfo());
			}
			this.preOrdPrint(node.getLeft(), depth);
			this.preOrdPrint(node.getRight(), depth);
		}
	}

	public void printNephews(int info) throws Exception {
		int depth = this.depth(info);
		BinaryNode node = this.search(info);
		this.preOrdPrintCousins(root, node, depth + 1);

	}

	public void printCousins(int info) throws Exception {
		int depth = this.depth(info);
		BinaryNode node = this.search(info);
		BinaryNode father = this.findParents(node);
		this.preOrdPrintCousins(root, father, depth);

	}

	private void preOrdPrintCousins(BinaryNode root, BinaryNode father, int depth) throws Exception {

		BinaryNode aux = root;
		if (aux != null && father != null) {
			int value = this.depth(aux.getInfo());
			if (father.getLeft() == null && father.getRight() == null) {

			} else if (father.getLeft() == null) {
				if (father.getRight().getInfo() != aux.getInfo()) {
					if (value == depth) {
						System.out.println(aux.getInfo());
					}
				}
			} else if (father.getRight() == null) {
				if (father.getLeft().getInfo() != aux.getInfo()) {
					if (value == depth) {
						System.out.println(aux.getInfo());
					}
				}
			} else if (father.getLeft().getInfo() != aux.getInfo() && father.getRight().getInfo() != aux.getInfo()) {
				if (value == depth) {
					System.out.println(aux.getInfo());
				}
			}
			this.preOrdPrintCousins(aux.getLeft(), father, depth);
			this.preOrdPrintCousins(aux.getRight(), father, depth);

		}

	}

	private BinaryNode findParents(BinaryNode node) throws Exception {
		if (this.exist(node.getInfo())) {
			BinaryNode aux = root; // Aponta o no aux para a raiz
			while (aux != null) { // Verifica se o aux nao e nulo
				if (aux.getLeft() == null && aux.getRight() == null) {
					return null;
				} else if (aux.getInfo() == node.getInfo()) {
					return null;
				} else if (aux.getLeft() == null) {
					if (aux.getRight().getInfo() == node.getInfo()) {
						return aux;
					}

				} else if (aux.getRight() == null) {
					if (aux.getLeft().getInfo() == node.getInfo()) {
						return aux;
					}
				}
				if (aux.getLeft().getInfo() == node.getInfo() || aux.getRight().getInfo() == node.getInfo()) { // Caso
																												// o
																												// valor
																												// do
																												// aux
																												// seja
																												// igual
					// ao
					// valor recebido
					return aux;
				} else {
					if (node.getInfo() < aux.getInfo()) { // Verifica se o valor
															// recebido
						// e
						// menor que o valor do aux
						aux = aux.getLeft(); // Se for, entao aponta o aux para
												// a
												// esquerda do aux anterior
					} else {
						aux = aux.getRight();// Caso contrario, aponta o aux
												// para a
												// direita do aux anterior
					}
				}
			}

		}
		return null;

	}

	public static void main(String[] Args) throws Exception {
		BinaryTree bt = new BinaryTree();
		Scanner sc = new Scanner(System.in);
		int x = 0;

		do {
			System.out.println("\nEscolha uma opcao: ");
			System.out.println("1: Adicionar um no a arvore \n" + "2: Excluir um no\n"
					+ "3: Verificar se existe um no\n" + "4: Procurar um no\n" + "5: Printar a arvore em pre ordem\n"
					+ "6: Calcular a profundidade\n" + "7: Calcular a altura\n" + "8: Printar a arvore \n"
					+ "9: Printar os primos do no\n" + "10: Printar os sobrinhos do no\n" + "Outro: Sair");

			switch (x = sc.nextInt()) {
			case 1:
				bt.add(sc.nextInt());
				break;
			case 2:
				bt.remove(sc.nextInt());
				break;
			case 3:
				System.out.println(bt.exist(sc.nextInt()));
				break;
			case 4:
				System.out.println(bt.search(sc.nextInt()));
				break;
			case 5:
				bt.printPreOrder();
				break;
			case 6:
				System.out.println(bt.depth(sc.nextInt()));
				break;
			case 7:
				System.out.println(bt.height(sc.nextInt()));
				break;
			case 8:
				bt.printBinaryTree();
				break;
			case 9:
				bt.printCousins(sc.nextInt());
				break;
			case 10:
				bt.printNephews(sc.nextInt());
				break;

			default:
				x = 0;
				break;
			}

		} while (x != 0);

	}
}