Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2842 palavras )
  • Download(s) : 0
  • Publicado : 16 de novembro de 2011
Ler documento completo
Amostra do texto
Estrutura de Dados

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;...
tracking img