valor do no O filho da direita do noO descritor tera o endereco fisico da raiz da arvore.Exemplo: ESQ NO DIR 2 4 3 4 2 5 6 6 7 - 1 - - 3 - - 5 - - 7 - DESCRITOR = 1 Arvores De Pesquisa Binaria(Bst)Ou BINARY SEARCH TREES (BST), E toda arvores binaria aonde as informacoes contidas em todos os nos respeite as seguintes regras: Seja maior do que todas as informacoes contidas em todos os nos da Sub - arvore da esquerda Seja menor que todas as informacoes contidas em todos os nos da Sub - arvores direita. Normalmente nao se permite informacoes iguais em nos diferentes. Consulta.A consulta a uma BST consiste em identificar ou nao a existencia de um no correspondente ao argumento de busca, para tanto procedemos da seguinte forma: Comecamos a busca pela raiz Se o no pesquisado estiver nulo, e porque o argumento nao esta na arvore. Se o argumento de busca for igual ao valor do no , o processo de busca esta concluido. Se o argumento de busca for maior que o valor do no , a busca continua pela Sub - arvore direita do no Se o argumento de busca for menor do que o no , entao a busca continua pela Sub - arvore esquerda do no.INICIO ARGUMENTOS ARVORE : MATRIZ [N] DE REG-ARVOREDESCRITOR:INTEIRON:INTEIROARGUMENTO-DE-BUSCA:INTEIROVARIAVEISREG-ARVORE: REGISTROESQUERDA:INTEIRONO:INTEIRODIREITA:INTEIROFIM-REGISTROCONT:INTEIROPROCEDA CONSULTA-ARVORECONT : = DESCRITORSE CONT = NULOMOSTRE ( "ARVORE VAZIA")SENAOENQUANTO CONT < > NULOSE ARVORE [CONT ].NO = ARGUMENTO-DE-BUSCARETORNE CONTSENAOSE ARGUMENTO-DE-BUSCA > ARVORE [CONT ].NOCONT: = ARVORE [CONT ].DIREITAFIM-SESE ARGUMENTO-DE-BUSCA < ARVORE [CONT ].NOCONT: = ARVORE[ CONT ].ESQUERDAFIM-SEFIM-ENQUANTOMOSTRE ("ARGUMENTO NAO ENCONTRADO")FIM-SEFIM. Consulta RecursivaComo nos vamos ver, as arvores binarias tem uma forte natureza recursiva, isto e , devido a sua simetria entre os nos , pode-se fazer o mesmo tratamento para diferentes nos da mesma arvore. Por este motivo podemos escrever todos os algoritmos de tratamento de arvores de forma recursiva, economizando assim linhas de codigo, e melhorando a performance dos algoritmos.A consulta recursiva tem a mesma estrutura da consulta normal, percorrer a arvore ate que seja encontrado o argumento de busca , ou que seja encontrado um elemento nulo, que indica que o argumento pesquisado nao se encontra na arvore.INICIO ARGUMENTOS ARVORE: MATRIZ[N] DE REG-ARVOREN:INTEIRODESCRITOR:INTEIROELEMENTO:INTEIROVARIAVEISREG-ARVORE: REGISTROESQUERDA:INTEIRONO:INTEIRODIREITA:INTEIROFIM-REGISTROPROCEDA CONSULTA-RECSE DESCRITOR = NULORETORNE "ELEMENTO NAO ENCONTRADO"FIM-SESE ARVORE [ DESCRITOR ].NO = ELEMENTORETORNE DESCRITORSENAOSE ARVORE [ DESCRITOR ].NO > ELEMENTOCONSULTA-REC (ARVORE,N,ARVORE[DESCRITOR].ESQUERDA,ELEMENTO)SENAOCONSULTA-REC (ARVORE,N,ARVORE[DESCRITOR].DIREITA,ELEMENTO)FIM-SEFIM-SEFIM InclusaoA inclusao em uma BST permite anexar um novo no mantendo todas as caracteristicas da arvore. Para tanto procedemos da seguinte forma: Busca-se um registro vazio na matriz, atravessando a arvore pela ordem fisica. Nesta posicao sera colocado o novo elemento (pode ser usado o algoritmo de busca do espaco vazio visto anteriormente). Procura-se o no que sera pai do incluido (esta busca comeca pela raiz) Caso exista elemento de igual valor na arvore o procedimento e interrompido. Os ponteiros do elemento incluido serao sempre nulos. O ponteiro de seu pai (esquerdo ou direito) deve ser alterado para o endereco fisico do elemento que esta sendo incluido.Temos que tomar um cuidado especial se o