Árvores Binárias e Árvores Binárias de Busca: definição, representação, propriedades, percursos e operações

Anotacoes

Árvores Binárias E S T R U T U R A S D E D A D O S A V A N Ç A D A Objetivos • Compreender o conceito e as operações sobre árvores binárias e árvores binárias de busca. Tópicos • Conceitos de árvores binárias e árvores binárias de busca. • Operações sobre árvores binárias de busca. Árvores • Árvores são estruturas adequadas para representação de hierarquias Definição Recursiva de Árvore • Um conjunto de nós tal que: – existe um nó r, denominado raiz, com zero ou mais sub- árvores, cujas raízes estão ligadas a r – os nós raízes destas sub-árvores são os filhos de r – os nós internos da árvore são os nós com filhos – as folhas ou nós externos da árvore são os nós sem filhos Formas de representação Representação por parênteses aninhados – ( A (B) ( C (D (G) (H)) (E) (F (I)))) Diagrama de Inclusão Representação Hierárquica Subárvore • Seja a árvore T = {A, B, ...} • A árvore T possui duas subárvores: –Tb e Tc onde Tb = { B } e Tc = {C, D, ...} • A subárvore Tc possui 3 subárvores: –Td, Tf e Te onde Td = {D, G, H}, Tf = {F, I}, Te = {E} • As subárvores Tb, Te, Tg, Th, Ti possuem apenas o nó raiz e nenhuma subárvore. Exemplo (árvore de expressão) • Representação da expressão aritmética: ...