Questão de Tecnologia da Informação

Uma Árvore Binária é uma árvore vazia (sem nós) ou é uma árvore com um nó raiz conectado a um par de árvores binárias, denominadas subárvore esquerda e subárvore direita desse nó. Adaptado de ZIVIANI, N. Projeto de algoritmos: com implementações em JAVA e C++. Porto Alegre: +A Educação – Cengage Learning Brasil, 2012. Uma Árvore de Busca Binária (ABB) é um caso especial de uma árvore binária, em que, para cada nó, a seguinte propriedade é verdadeira: todos os registros com chaves menores do que a chave deste nó estão em sua subárvore esquerda e todos os registros com chaves maiores estão em sua subárvore direita. O caminhamento em uma ABB é uma forma sistemática de “visitar” todos os nós dessa árvore. Há três métodos bem conhecidos para realizar esse caminhamento: 1) pré-ordem, 2) em-ordem e 3) pós-ordem. Considere que os seguintes registros numéricos (50, 30, 70, 20, 40, 10, 35, 60, 80, 65, 5) foram inseridos em uma ABB inicialmente vazia, registro a registro, da esquerda para a direita. O caminhamento pré-ordem irá processar os registros dessa árvore na seguinte ordem: