Lista1

Prévia do material em texto

Algoritmos e Estrutura de Dados III
Lista de exercício 1
1.(a)
(b)	A altura do nó de chave 7 é 3. A chave 7 encontra-se no 2º nível considerando a raiz como nível 0. A altura da árvore é igual a 5.
(c)	Existe, e seu comprimento é igual a 3. Não.
(d)	É o nó de chave 27. Os filhos são a chave 5 e 10. 34 e 39 são nós irmãos.
(e)	Pré-Ordem: 22,12,7,5,4,3,6,10,14,27,24,23,25,32,37,34,39.
	In-Ordem: 3,4,5,6,7,10,12,14,22,23,24,25,27,32,34,37,39.
	Pós-Ordem: 3,4,6,5,10,7,14,12,23,25,24,34,39,37,32,27,22.
(f) 
2.
(a)
(b)	( -,4,/,-,*,8,5,2,+,3,*,7,8 ) -> Foi obtida a partir do desenho da árvore, realizada para a expressão infixada. A expressão prefixada consiste em pegar a raiz, imprimir, chave a esquerda, imprimir, chave a direita, imprimir, e assim sucessivamente.
(c)	( 4,8,5,*,2,-,3,7,8,*,+,/,- ) -> 	Foi obtida do mesmo modo que no exercício b, a partir do desenho da árvore, porém, na expressão posfixada, deve-se começar a impressão dos elementos, a partir da esquerda, depois direita, e assim raiz.
3.
int alturaArvore(No* p)
{ 
 if (p == NULL) return -1;
 int alturaEsq = alturaArvore(p->Esq); 
 int alturaDir = alturaArvore(p->Dir); 
 if (alturaEsq > alturaDir)
 return alturaEsq + 1; 
 else return alturaDir + 1; 
} 
4. 
int NRecInsere(Registro x, Apontador *p)
{
 Apontador pAux;
 Apontador pAnt=NULL;
 pAux=*p; 
 while(pAux!=NULL)
 {
 pAnt= pAux;
 if((pAux)->Reg.Chave > x.Chave)
 {
 (pAux)=(pAux)->Esq;
 }else
 if((pAux)->Reg.Chave < x.Chave)
 {
 (pAux)=(pAux)->Dir;
 }else
 {
 printf("Erro : Registro ja existe na arvore\n");
 return -1; 
 }
 }
 
 if(pAux==NULL)
 {
 Apontador pNo = (Apontador)malloc(sizeof(No));
 pNo->Reg = x;
 pNo->Esq = NULL;
 pNo->Dir = NULL;
 if(pAnt==NULL)
 *p=pNo;
 else if(x.Chave < pAnt->Reg.Chave)
			pAnt->Esq = pNo;
		else
			pAnt->Dir = pNo;
 return 0;
 } 
}
5.
 void ListarTabulado(No *p,int nivel)
{
 int i;
 nivel++;
 if (p != NULL)
 {
 for(i=1;i<nivel;i++)
 {
 printf(" ");
 }
 
 printf("%d\n",p->Reg.Chave);
 ListarTabulado(p->Esq,nivel);
 ListarTabulado(p->Dir,nivel);
 }else printf("---\n");
}