Main.java

package tsteda;

import java.io.BufferedReader;

import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	Node root;

	public static void main(String[] args) {
		BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));

		Main tree = new Main();

		String line;
		String exit = "";
		try {
			while ((line = bfr.readLine()) != null) {
				if (line.equals("INFIXA")) {
					exit = tree.preOrder();

				} else if (line.equals("PREFIXA")) {
					exit = tree.order();

				} else if (line.equals("POSFIXA")) {
					exit = tree.posOrder();

				} else {
					String[] params = line.split(" ");
					if (params[0].equals("I")) {
						tree.insert(Integer.parseInt(params[1]));
					} else if (params[0].equals("R")) {
						tree.remove(Integer.parseInt(params[1]));
					} else {
						Node searchedNode = tree.search(Integer.parseInt(params[1]));
						if (searchedNode == null) {
							exit = params[1] + " nao existe";
						} else {
							exit = params[1] + " existe";
						}
						System.out.println(exit);
					}
				}

				if (line.equals("INFIXA") || line.equals("PREFIXA") || line.equals("POSFIXA")) {
					System.out.println(exit);
				}

			}
		} catch (IOException e) {
		}

		try {
			bfr.close();
		} catch (IOException e) {
		}
	}

	public Node search(Integer string) {
		return recSearch(string, root);
	}

	private Node recSearch(Integer string, Node node) {
		if (node.getData() == null) {
			return null;
		} else if (node.getData().equals(string)) {
			return node;
		} else {
			if (node.getData().compareTo(string) < 0) {
				return recSearch(string, node.getRight());
			} else {
				return recSearch(string, node.getLeft());
			}
		}
	}

	public Main() {
		root = new Node(null, new Node(), new Node());
	}

	public void insert(Integer data) {
		recursiveInsert(data, root);
	}

	private void recursiveInsert(Integer data, Node node) {
		if (node.getData() == null) {
			node.setData(data);
			node.setLeft(new Node());
			node.setRight(new Node());
		} else {
			if (node.getData().compareTo(data) > 0) {
				recursiveInsert(data, node.getLeft());

			} else if (node.getData().compareTo(data) < 0) {
				recursiveInsert(data, node.getRight());

			}
		}
	}

	public String order() {
		return recOrder(root);
	}

	private String recOrder(Node node) {
		if (node.getData() == null) {
			return "";

		} else {
			Integer order = node.getData();
			String left = recOrder(node.getLeft());
			String right = recOrder(node.getRight());
			
			String res = order.toString();

			if (!(left.trim().equals(""))) {
				res += " " + left;
			}
			if (!(right.trim().equals(""))) {
				res += " " + right;
			}
			return res;
		}
	}

	public String preOrder() {
		return recPreOrder(root);
	}

	private String recPreOrder(Node node) {
		if (node.getData() == null) {
			return "";

		} else {
			String res = "";
			Integer order = node.getData();
			String left = recPreOrder(node.getLeft());
			String right = recPreOrder(node.getRight());

			res += left;

			if (!(res.trim().equals(""))) {
				res += " " + order;
			} else {
				res += order;
			}

			if (!(right.trim().equals("")) && (!(right.equals("")))) {
				res += " " + right;
			}

			return res;
		}
	}

	public String posOrder() {
		return recPosOrder(root);
	}

	private String recPosOrder(Node node) {
		if (node.getData() == null) {
			return "";

		} else {
			String res = "";

			String left = recPosOrder(node.getLeft());
			String right = recPosOrder(node.getRight());
			Integer order = node.getData();

			res += left;

			if (!(res.trim().equals("")) && (!(right.equals("")))) {
				res += " " + right;
			} else {
				res += right;
			}

			if (!(res.trim().equals(""))) {
				res += " " + order;
			} else {
				res += order;
			}

			return res;
		}
	}

	private void swap(Node auxNode, Node node) {
		Integer auxData = auxNode.getData();

		auxNode.setData(node.getData());
		node.setData(auxData);
	}

	public void remove(Integer data) {
		Node node = search(data);
		if (node != null) {
			recursiveRemove(node);
		}
	}

	private void recursiveRemove(Node node) {
		if (node.isLeaf())
			node.setData(null);
		else if (!node.getLeft().isEmpty() && node.getRight().isEmpty()) {
			Node auxNode = node.getLeft();
			swap(auxNode, node);
		} else if ((node.getLeft().isEmpty() && !node.getRight().isEmpty())) {
			Node auxNode = node.getRight();
			swap(auxNode, node);
		} else {
			Node auxNode = recursiveMinimum(node.getRight());

			Integer aux = node.getData();

			node.setData(auxNode.getData());
			auxNode.setData(aux);

			recursiveRemove(auxNode);
		}
	}

	private Node recursiveMinimum(Node node) {
		if (node.isEmpty()) {
			return null;
		} else if (node.getLeft().isEmpty()) {
			return node;
		} else {
			return recursiveMinimum(node.getLeft());
		}
	}
}

class Node {
	private Integer data;
	private Node left;
	private Node right;

	public Node(Integer data, Node left, Node right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}

	public Node() {

	}

	public boolean isEmpty() {
		return this.data == null;
	}

	public boolean isLeaf() {
		return this.data != null && this.left.isEmpty() && this.right.isEmpty();
	}

	public void setLeft(Node left) {
		this.left = left;
	}

	public void setRight(Node right) {
		this.right = right;
	}

	public Node getRight() {
		return this.right;
	}

	public Node getLeft() {
		return this.left;
	}

	public Integer getData() {
		return data;
	}

	public void setData(Integer data) {
		this.data = data;
	}
}