package BT;

public class BinaryTree<Key extends Comparable<Key>, Value> {

	private Celula root;
	private int n = 0, depth = 0, height = 0, count = 0;

	public boolean isEmpty() {
		return root == null;
	}

	public int size() {
		return size(root);
	}

	private int size(Celula x) {
		if (x == null)
			return 0;
		return 1 + size(x.getEsquerda()) + size(x.getDireita());
	}

	public Value get(Key key) {
		return get(root, key);
	}

	private Value get(Celula x, Key key) {
		if (x == null)
			return null;
		int cmp = key.compareTo((Key) x.getKey());
		if (cmp < 0) {
			return get(x.getEsquerda(), key);
		} else {
			if (cmp > 0)
				return get(x.getDireita(), key);
			else
				return (Value) x.getVal();
		}
	}

	public void put(Key key, Value valor) {
		depth = 0;
		root = put(root, key, valor);
		n++;
	}

	private Celula put(Celula x, Key key, Value valor) {
		if (x == null) {
			Celula aux = new Celula(key, valor);
			aux.setDepth(depth);

			return aux;
		}
		int cmp = key.compareTo((Key) x.getKey());
		if (cmp < 0) {
			depth++;
			x.setEsquerda(put(x.getEsquerda(), key, valor));
		} else {
			if (cmp > 0) {
				depth++;
				x.setDireita(put(x.getDireita(), key, valor));
			} else
				x.setVal(valor);
		}
		return x;
	}

	public String toString() {
		String str = "";
		str += "Pre ordem: ";
		str += mostrarPre(root);
		str += "\n";
		str += "Pos ordem: ";
		str += mostrarPos(root);
		str += "\n";
		str += "In ordem: ";
		str += mostrarIn(root);
		return str;
	}

	public int getN() {
		return n;
	}

	private String mostrarPre(Celula x) {
		if (x == null)
			return "";
		return (x.getKey() + " - ") + mostrarPre(x.getEsquerda()) + mostrarPre(x.getDireita());
	}

	private String mostrarPos(Celula x) {
		if (x == null)
			return "";
		return mostrarPos(x.getEsquerda()) + mostrarPos(x.getDireita()) + (x.getKey() + " - ");
	}

	private String mostrarIn(Celula x) {
		if (x == null)
			return "";
		return mostrarIn(x.getEsquerda()) + (x.getKey() + " - ") + mostrarIn(x.getDireita());
	}

	public int internalPathLenght() {
		return internalPathLenght(root);
	}

	public int internalPathLenght(Celula x) {
		if (x == null)
			return 0;
		return (x.getDepth()) + internalPathLenght(x.getEsquerda()) + internalPathLenght(x.getDireita());
	}

	public int height() {
		Celula aux = root;
		return height(root, aux);
	}

	public int height(Celula x, Celula aux) {
		if (count == 0) {
			if (x == null) {
				return 0;
			}
		} else {
			if (count > 0) {
				if (x == null) {
					return aux.getDepth();
				}
			}
		}
		count++;
		aux = x;
		if (height(x.getEsquerda(), aux) > height)
			height = x.getDepth();
		if (height(x.getDireita(), aux) > height)
			height = x.getDepth();
		return height;
	}

}




--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------









package BT;

public class Celula<Key, Value> {
	private int depth;
	private Key key;
	private Value val;
	private Celula esquerda, direita;

	public Celula(Key key, Value val) {
		this.key = key;
		this.val = val;
	}

	public Key getKey() {
		return key;
	}

	public void setKey(Key key) {
		this.key = key;
	}

	public Value getVal() {
		return val;
	}

	public void setVal(Value val) {
		this.val = val;
	}

	public Celula getEsquerda() {
		return esquerda;
	}

	public void setEsquerda(Celula esquerda) {
		this.esquerda = esquerda;
	}

	public Celula getDireita() {
		return direita;
	}

	public void setDireita(Celula direita) {
		this.direita = direita;
	}

	public int getDepth() {
		return depth;
	}

	public void setDepth(int depth) {
		this.depth = depth;
	}


}






--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------










package BT;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

import javax.swing.JOptionPane;

public class Cliente {

	public static void main(String[] args) throws IOException {
		BinaryTree<String, Integer> tree = new BinaryTree<String, Integer>();

		String key;
		String[] textS;

		String caminhoS = JOptionPane.showInputDialog("Digite o diretório do tale.txt:\n"
				+ "Exemplo: C:/Users/usuario/Desktop/tale.txt\n" + "Obs: Usar \"/\" ao inves de \"\\\"");
		Path caminho = Paths.get(caminhoS);
		String text = Files.readString(caminho);
		textS = text.split("\n");

		for (int i = 0; i < textS.length; i++)
			textS[i] = textS[i].replaceAll("[^a-zA-Z_0-9]","");

		for (int i = 0; i < textS.length; i++)
			tree.put(textS[i], tree.getN());

		while (true) {
			int op = Integer.parseInt(JOptionPane.showInputDialog("1.Consultar\n2.Informacoes\n0.Sair"));
			switch (op) {
			case 1:
				key = JOptionPane.showInputDialog("Chave:");
				Integer aux = tree.get(key);
				if (aux != null)
					JOptionPane.showMessageDialog(null, aux);
				else
					JOptionPane.showMessageDialog(null, "Nao encontrado");
				break;
			case 2:
				JOptionPane.showMessageDialog(null, "Arvore:\n" + tree);
				JOptionPane.showMessageDialog(null, "Tamanho: " + tree.size());
				JOptionPane.showMessageDialog(null, "Altura: " + tree.height());
				JOptionPane.showMessageDialog(null, "Internal Path Lenght: " + tree.internalPathLenght());
				break;
			default:
				return;
			}
		}
	}

}