Ir para conteúdo
Fórum Script Brasil
  • 0

como computar um pergurso pos-ordem dado os percursos prr-ordem e em o


gutozanin

Pergunta

Resumidamente trabalho trata- se computar o percurso pos-ordem de uma arvore dado que tenho o percurso pre ordem e em-ordem

No entando meu codigo não consegue fazer corretamente pois a eu acho que a inserção dos elementos na arvores esta sendo feita de maneira incorreta, porem não consigo bolar um jeito de inserir o percurso pre e em-ordem na arvore de modo que quando percorre-la me pos odem os elementos estejam de maneria correta

Em anexo esta o enunciado do trabalho e meu codigo.

Por favor me ajudem

Forte abraço

sqtpm

Data limite para envio: 2012/11/18 23:59:59

Multa por dia de atraso: 10%

Trabalho 5 - Pré, Em e Pós

ATENÇÃO: O Trabalho deve ser resolvido utilizando Árvores, caso contrário, a nota será zerada.

Um problema comum em estruturas de dados é determinar o percorrimento de uma árvore binária. Existem três maneiras clássicas de fazer isso:

Pré-ordem: Você deve visitar primeiro a raiz, depois a sub-árvore esquerda e por último a sub-árvore direita.

Em-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a raiz e por último a sub-árvore direita.

Pós-ordem: Você deve visitar primeiro a sub-árvore esquerda, depois a sub-árvore direita e por último a raiz.

Veja a figura abaixo:

A

/ \

B D

/ / \

C E F

O resultado do percurso em pré, em e pós-ordem é, respectivamente: ABCDEF, CBAEDF e CBEFDA. Neste problema, você deve computar o percurso em pós-ordem de uma árvore binária dados os seus percursos em-ordem e pré-ordem.

Entrada

O conjunto de entrada consiste de um número C ≤ 2000, que dá o número de casos de teste e C linhas, uma para cada caso de teste. Cada caso de teste começa com um número 1 ≤ N ≤ 52, o número de nós nessa árvore arbitrária. Depois, há duas cadeias de caracteres S1 e S2 que descrevem o resultado do percurso da árvore em pré-ordem e em-ordem. Os nós da árvore são rotulados com caracteres diferentes no intervalo a..z e A..Z. Os valores de N, S1 e S2 são separados por um espaço em branco.

Saída

Para cada conjunto de entrada, você deve imprimir uma linha contendo o percorrimento em pós-ordem da árvore correspondente.

Exemplo

Entrada:

3

3 xYz Yxz

3 abc cba

6 ABCDEF CBAEDF

Saída:

Yzx

cba

CBEFDA

sqtpm

Aqui esta meu codigo

#include<stdio.h>
#include<stdlib.h>
#include<string.h>




typedef struct No{
    char dado;
    struct No *esquerda;
    struct No *direita;
}No;


void criarArvore(No **pRaiz){
    *pRaiz = NULL;
}



void inserir(No **pRaiz, int entrada){
    if(*pRaiz == NULL){
        *pRaiz = (No *) malloc(sizeof(No));
        (*pRaiz)->esquerda = NULL;
        (*pRaiz)->direita = NULL;
        (*pRaiz)->dado = entrada;
    }else{
        if(entrada > (*pRaiz)->dado)
            inserir(&(*pRaiz)->direita, entrada);
        if(entrada < (*pRaiz)->dado)
            inserir(&(*pRaiz)->esquerda, entrada);
    }
}



void exibirPosOrdem(No *pRaiz){
    if(pRaiz != NULL){
           
        exibirPosOrdem(pRaiz->esquerda);  
        
        exibirPosOrdem(pRaiz->direita);
             printf("%c", pRaiz->dado);
        
    }
}


int main (void){
    
    char preord[52], inord[52];
    int nos, vezes;
    int i,j;
    scanf("%d",&vezes);

    
    No *arvore;
    
    
    
    for(j = 0; j < vezes; j++){
    criarArvore(&arvore);
    scanf("%d", &nos);
    scanf("%s", &preord);
    scanf("%s", &inord);
    
    for(i = 0; i < nos; i++){
    
            inserir(&arvore, preord[i]);
            
            }

                 exibirPosOrdem(arvore);
                 printf("\n");


}

system("pause");

}

Link para o comentário
Compartilhar em outros sites

0 respostass a esta questão

Posts Recomendados

Até agora não há respostas para essa pergunta

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152k
    • Posts
      651,8k
×
×
  • Criar Novo...