Aplicação de arvores binárias

Aplicação de arvores Binárias

É uma estrutura de dados útil quando precisa ser tomadas decisões bidirecionais em cada ponto de um processo . Por exemplo numa lista de números , precisamos encontrar todas as repetições . Uma maneira de fazer isso é comparar todos , cada numero com todos os que procedem , mas isso envolve um grande numero de comparações .
Para reduzir essas comparações pode-ser usado uma arvore binária .O primeiro número na lista é colocado num nó estabelecido com a raiz da arvore binária com suas subarvores esquerda e direita vazias .Cada numero sucessivo na lista é então comparado ao numero da raiz . Se considerado igual teremos uma repetição , se for menor examinamos a subarvore esquerda ; se for maior , examinaremos a subarvore Direita .
Se a subarvore estiver vazia , o numero não será repetido e será colocado num novo nó nesta posição na arvore . Se a subarvore não estiver vazia , compararemos o número ao conteudo da raiz da subarvore e o processo inteiro será repetido com a subarvore .A seguir um algoritmo para fazer essa operação :

/* le o primeiro e o insere */
/* da arvore binaria de nó único */
Scanf(“%d” ,&number);
Tree = maketree(number);
While (há numero na entrada ){ Scanf(“%d” ,&number); P = Q = tree; While (number != info (p) && Q !=null){ P=Q; If (number < info (p)){ Q = left (p); }Else { Q = rigt (p); } }
}//Fim do while If (number ==info(p)) Printf (“%d %s /n “,number , “esta repetido”);
//insere o numero a direita ou a esquerda de p
Else if (number <info(p)) Setleft (p.number);
Else
Set right
}//fim do while

A seguir a representação da arvore construída a partir da entrada 14, 15 , 4 ,9 , 7 , 18 , 3 , 5 , 16 ,4 , 20 ,17 , 9 ,14 , 5.

- Arvore de Busca
Anteriormente não tinha nenhuma restrição quanto as posições de seu nós .Isso dava uma flexibilidade completa para construir a Árvore