Construindo uma Árvore Binária de Busca a Partir de um Vetor

type arvore nodo nodo record dir arvore centro arvore info integer esq arvore end var raiz arvore A C B D raiz VAMOS CONSTRUIR UMA ÁRVORE BINÁRIA DE BUSCA ABB A PARTIR DE DADOS DE UM VETOR QUALQUER 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 17 14 18 4 9 7 15 3 5 17 20 14 18 4 9 7 15 3 5 17 14 18 4 9 7 15 3 5 17 20 20 14 18 4 9 7 15 3 5 17 14 18 4 9 7 15 3 5 17 20 20 VEJAM A CONSTRUÇÃO DA ABB NA MÍDIA A SEGUIR wwwpenjeecom Vamos resolver esse problema recursivamente Será bem mais simples assim Assim como no Exemplo do Fatorial achamos 2 situações em que conseguimos resolver o problema definitivamente caso 1 e 2 PONTOS DE PARADA e achamos também as situações em que vamos decompor o problema em um problema menor através de uma chamada recursiva caso 3 e 4 No caso 3 onde InfoRX não sabemos ainda se X está na árvore mas temos certeza de uma coisa se X estiver na árvore estará na subárvore esquerda Por que Porque em uma árvore binária de busca todas as chaves na subárvore direita da raiz são maiores que a chave da raiz E nosso X é 39 menor do que InfoR que é 50 Logo deve estar à esquerda No caso 4 analogamente também não temos certeza se X está ou não na árvore Mas de uma coisa temos certeza se X estiver na árvore estará na subárvore direita de R Considere que X 39 e a árvore seja a árvore da Figura abaixo Na primeira chamada caímos no caso 3 ou seja InfoRX Assim fazemos uma chamada recursiva para a busca de X na subarvore esquerda de R Na 2ª chamada nosso R aponta para o nó 28 caímos no caso 4 pois InfoRX Então vamos ver se X está na subárvore direita de R Na 3ª chamada caímos no caso 2 X InfoR O resultado é Verdadeiro ou seja X está na lista e encerramos a 3ª chamada Ao encerrar a 3ª chamada voltamos para a 2ª chamada no ponto onde foi feita a chamada recursiva Ou seja o resultado do comando Retorne EstáNaÁrvoreDirR X será Retorne Verdadeiro porque o resultado da 3ª chamada foi verdadeiro Assim o resultado verdadeiro vai também para a 1ª chamada encerrando a execução CASO 1 ÁRVORE VAZIA XestáNaÁrvore Boolean EstánaÁrvorevariável R tipo ABB variável X tipo Inteiro verifica se X está ou não na árvore R O resultado é do tipo verdadeiro está na árvore ou falso Se R nil Então Retorne Falso caso1 árvore vazia X não está na ABB fim XestáNaÁrvoreRABB Xinteiro Se R nil Então Retorne Falso CASO 2 ENCONTRA X NA ABB XestáNaÁrvore Boolean EstánaÁrvorevariável R tipo ABB variável X tipo Inteiro verifica se X está ou não na árvore R O resultado é do tipo verdadeiro está na árvore ou falso Se X InfoR Então Retorne Verdadeiro caso 2 X está na árvore fim XestáNaÁrvoreRABB X inteiro Se X InfoR Então Retorne Verdadeiro CASO 3 X É MENOR QUE InfoR XestáNaÁrvore Boolean EstánaÁrvorevariável R tipo ABB variável X tipo Inteiro verifica se X está ou não na árvore R O resultado é do tipo verdadeiro está na árvore ou falso Se InfoR X Então Retorne EstáNaÁrvoreEsqR X retorna o resultado da chamada recursiva para a busca de X na subárvore esquerda de R caso 3 XestáNaÁrvoreRABBXinteiro Se InfoR X Então Retorne NaÁrvoreEsqR X CASO 4 X É MAIOR QUE InfoR XestáNaÁrvore Boolean EstánaÁrvorevariável R tipo ABB variável X tipo Inteiro verifica se a chave X está ou não na árvore R O resultado é do tipo verdadeiro está na árvore ou falso Se InfoR X Então Retorne EstáNaÁrvoreDirR X retorna o resultado da chamada recursiva para a busca de X na subárvore direita de R caso 4 XestáNaÁrvoreRABB Xinteiro Se InfoR X Retorne NaÁrvoreDirR X JUNTANDO TUDO XestáNaÁrvoreRABB Xinteiro Se R nil Então Retorne Falso Se X InfoR Então Retorne Verdadeiro Se InfoR X Então Retorne NaÁrvoreEsqR X Se InfoR X Retorne NaÁrvoreDirR X XestáNaÁrvoreRABB Xinteiro Se R nil Então Retorne Falso Senão Se X InfoR Então Retorne Verdadeiro Senão Se InfoR X Então Retorne NaÁrvoreEsqR X Senão Retorne NaÁrvoreDirR X BUSCAXRABB Xinteiroboolean IF R nil BUSCAXFalso ELSE IF X InfoR BUSCAXVerdadeiro ELSE IF InfoR X BUSCAXBUSCAXEsqR X ELSE BUSCAXBUSCAXDirR X DE POSSE DAS MARAVILHOSAS E DETALHADAS INFORMAÇÕES FORNECIDAS CONSTRUA UMA FUNÇÃO DE BUSCA DE UM ELEMENTO EM UMA ABB NA LINGUAGEM PASCAL type inteiro integer ABB nodo nodo record dir ABB info inteiro esq ABB end Var Raiz ABB x inteiro Algoritmo de Busca Recursivo Function Busca x inteiro raiz ABBboolean Begin If raiznil Busca false Else If raizinfo x Buscatrue Else If raizinfo x BuscaBuscax raizdir Else BuscaBuscax raizesq End ADESENVOLVA UMA FUNÇÃO QUE RECEBA UMA ABB E DEVOLVA A QUANTIDADE DE NÚMEROS PARES EXISTENTES NA ABB BDESENVOLVA UMA FUNÇÃO QUE RECEBA UMA ABB E DEVOLVA A QUANTIDADE DE NODOS EXISTENTES NA ABB CDESENVOLVA UMA FUNÇÃO QUE RECEBA UMA ABB E DEVOLVA O NÚMERO DE FOLHAS EXISTENTES NA ABB