Jump to content
Fórum Script Brasil
  • 0

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


gutozanin
 Share

Question

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 to comment
Share on other sites

0 answers to this question

Recommended Posts

There have been no answers to this question yet

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share



  • Forum Statistics

    • Total Topics
      150.2k
    • Total Posts
      647.4k
×
×
  • Create New...