Estruturas de Dados: Árvores e suas Propriedades

Árvores conseguem uma representação tanto linear como não linear Possibilita uma hierarquia na hora de armazenar os nós Uma árvore é uma coleção finita de n igual a 0 ou mais elementos onde se n 0 a árvore é denominada vazia se n 0 existe um nó denominado raiz o nó raiz contém referências para outras T árvores denominadas subárvores K P O Y X G Nó pai nó acima e com ligação direta a outro nó No exemplo K é nó pai de G L e P X é nó pai de O e K P é nó pai de Y L K P O Y X G Nó filho nó abaixo e com ligação direta a outro nó o nó pai No exemplo K nó filho de X O é nó filho de X Y é nó filho de P L é nó filho de K L K P O Y X G Nós irmãos são nós que possuem o mesmo nó pai No exemplo G L e P são nós irmãos K e O são nós irmãos L K P O Y X G Nó folha nó que não possui filhos No exemplo G é um nó folha L é um nó folha O é um nó folha Y é um nó folha L K P O Y X G Nó raiz único nó sem pai No exemplo X é o nó raiz L K P O Y X G Nó pai nó acima e com ligação direta a outro nó Nó filho nó abaixo e com ligação direta a outro nó o nó pai Nós irmãos são nós que possuem o mesmo nó pai Nó folha nó que não possui filhos Nó raiz único nó sem pai L 90 53 66 86 54 67 12 Um conjunto T é uma árvore binária se T contém no máximo 1 elemento T possui duas subárvores uma à esquerda e outra à dureita T e T respectivamente T e T são árvores binárias 90 53 66 86 54 67 12 O nível de um nó é o número de ligações entre um nó qualquer e o nó raiz O nível do nó raiz sempre é zero Nível 0 Nível 1 Nível 2 Nível 3 90 53 66 86 54 67 12 A altura da árvore é o nível mais distante da raiz No exemplo ao lado a altura da árvore é 3 Nível 0 Nível 1 Nível 2 Nível 3 90 53 66 86 54 67 12 Uma árvore é binária cuja raiz armazena um elemento X é uma árvore binária de pesquisa se todo elemento armazenado na subárvore esquerda é menor que X todo elemento armazenado na subárvore direita é maior que X as subárvores esquerda e direita também são árvores binárias de pesquisa Para a implementação utilizada nesta aula um nó da árvore binária de pesquisa é definido pela struct typedef struct no int chave Valor de comparação struct no esq Subárvore esquerda struct no dir Subárvore direita No esq dir chave No p