Questão 1
class TreeNode{
TreeNode left;
int data;
TreeNode right;
public TreeNode(int d)
{
data = d;
left = right = null;
}
public synchronized void insert(int d)
{
if (left == null)
left = new TreeNode(d);
else
{
if (right == null)
right = new TreeNode(d);else
{
if((left.left != null && left.right != null) && (right.left == null || right.right == null))
right.insert(d);
else
left.insert(d);
}
}
}
}
class Tree{
private TreeNode root;
public Tree() {
root = null;
}
public synchronized void insertNode (intd){
if (root == null)
root = new TreeNode(d);
else
root.insert(d);
}
public synchronized void preorderTraversal()
{
preorderHelper(root);
}
private void preorderHelper(TreeNode node)
{
if (node == null)
return;
System.out.print(node.data + " ");
preorderHelper(node.left);
preorderHelper(node.right);
}
}
importjava.util.Scanner;
public class TreeBinary{
public static void main(String args[])
{
Tree tree = new Tree();
int intVal;
String cont = " ";
Scanner sc = new Scanner(System.in);
System.out.println("Digite um valor a inserir ou '0' para encerrar: ");
intVal = sc.nextInt();
cont = Integer.toString(intVal);
if(intVal == 0){System.out.println("Árvore está vazia.");
return;
}else{
while(intVal != 0){
System.out.print(cont+" ");
tree.insertNode(intVal);
intVal = sc.nextInt();
cont = cont + " " + intVal;
}
}
System.out.println("\nPercorrendo a Árvore em ordem");
tree.preorderTraversal();
System.out.println();
}
}Questão 2
Dados inseridos:
4 3 2 5 7 1 6
Árvore Binária
Árvore Binária de Pesquisa
Pelos exemplos acima, nota-se a diferença pelo desenho entre as árvores. No primeiro exemplo, no algoritmo que a constrói, os elementos são inseridos de forma balanceada, sempre começando pela esquerda e seguindo para a direita nos nós filhos, netos e assim por diante. Ele sempre cria um Nó levandoem consideração a ordem da esquerda para a direita, criando um novo nó na esquerda se o mesmo não existir. Se já o existir, então o nó é criado no lado da direita. Da mesma forma é feito nos nós filhos, onde o da esquerda está preferência na inserção e criação de um novo nó. Quando os seus filhos estiverem preenchidos, então o filho da direita é então preenchido.
No segundo exemplo, ainserção é feita de forma diferente. Não é levado em consideração o balanceamento da árvore, o que pode até acontecer, dependendo dos valores inseridos. O algoritmo faz uma comparação na inserção dos elementos, onde o elemento que já está inserido é comparado com o elemento a inserir, e se este for menor que aquele, o nó é criado do lado esquerdo, e se não for menor, então o lado escolhido é o dadireita. O elemento a ser inserido sempre será comparado com o nó raiz, e depois dependendo do lado que for, será comparado com o filho, se o mesmo existir, e assim por diante, fazendo sempre que os números menores que a raiz sejam inseridos do lado esquerdo da mesma, e os maiores do lado direito. Seguindo a lógica do algoritmo o número será comparado, após a comparação com a raiz, com o nó filho dadireita ou da esquerda, dependendo da comparação com o nó anterior se aquele estiver preenchido, o que pode levar a uma árvore apenas com elementos do lado esquerdo ou apenas do lado direito, levando a um grande desbalanceamento.
Questão 3
class TreeNode{
TreeNode left;
int data;
TreeNode right;
public TreeNode(int d)
{
data = d;
left = right = null;...