Ir ao conteúdo
  • Cadastre-se
Regras do Clube do Hardware

C Alguem pode me ajudar nesse exercício de arvore binaria

henrique Souza850

Por henrique Souza850
em C/C#/C++

 Compartilhar

Posts recomendados

henrique Souza850
 

henrique Souza850

Postado
Postado

Alguem poderia me dar uma força nesse exercicio? é sobre arvore binaria, estou tentando mas ta difricl de mais, eu fiz uma implementaçao ate agora mas to empacando

<CODE>

 

#include...

 

int getIdx ( char * str, int si, int ei) {

               

               if (si> ei){

                  retorno - 1 ;

                  Pilha * s = pilha_cria ();

 

for ( int i = si; i <= ei; i ++) {

     

         if (str == ' ( ' )

         pilha_push (s, str );

         

         if else (str == ' ) ' ) {

 

         if ( pilha_top (s) == ' ( ' ) {

             pilha_pop (s);

 

         if ( pilha_vazia (s)) {

             pilha_libera (s);

             return i;

             }

       }

 }

}

 

pilha_libera (s);

return - 1 ;

}

Run codes.docx

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado

Um anexo? E preciso ter um programa específico instalado no computador e então sair do forum, fazer um download, abrir outro programa, ler o enunciado, voltar aqui e tentar recortar o programa no meio do post?

 

Porque não coloca aqui seja lá o que tenha no documento, e coloca seu programa dentro do <> code lá pra que seja mais fácil de ler e copiar sem trazer junto caracteres de controle ou partes do texto?

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado

image.png.a0199da63f074a057630858c10a7f799.png

 

Muito bem.

 

A parte do botão CODE
 

No editor tem esse botão image.png.c980d30f564a3635aa8dec0ebab4cec7.png e está explicado nos tópicos permanentes, que server para abri um formula;rio onde você cola seu código e tem um formatador e ele fica separado do texto.

 

Quando você deixa misturado como fez,  além de ficar mais difícil de separar o código se alguém quer ajudar e por exemplo testar em um compilador, muitas vezes na cópia vem caracteres de controle do próprio post e o código não compila e é preciso ficar procurando onde eles estão.

 

A parte do anexo

 

Você postou um anexo, um documento do tipo docx, supostamente para abrir em um programa como o Word, da Microsoft, e que nada tem a ver com o forum e nada tem a ver com C ou C# ou C++.

 

Para te ajudar eu preciso clicar no botão, salvar isso em meu computador, abrir outro programa para processar texto --- Word é para isso --- só que eu não vou processar, só quero ler. E aí leio o texto, fecho o Word, abro o tópico no forum e tento recortar seu programa.

 

Ajude os outros a ajudarem você... Meu palpite.

 

EXEMPLO 1

 

Veja como fica seu programa ao importar para um compilador: espaço duplo. A toa. Só complica. Poste o programa completo e com os #include. Se eu tiver que completar o seu programa para rodar pode ser que ele fique muito diferente e não vai adiantar nada para você ou para mim.

  

#include...

 

int getIdx ( char * str, int si, int ei) {

               

               if (si> ei){

                  retorno - 1 ;

                  Pilha * s = pilha_cria ();

 

for ( int i = si; i <= ei; i ++) {

     

         if (str == ' ( ' )

         pilha_push (s, str );

         

         if else (str == ' ) ' ) {

 

         if ( pilha_top (s) == ' ( ' ) {

             pilha_pop (s);

 

         if ( pilha_vazia (s)) {

             pilha_libera (s);

             return i;

             }

       }

 }

}

 

pilha_libera (s);

return - 1 ;

}

 

EXEMPLO 2

image.png.13d6b2177ae90ffbbbe96c8f9d610edd.png

 

image.png.3207966012eacd668fcd9bc39ad92359.png

 

Não acha que seria mais fácil se tivesse simplesmente postado isso?

 

Foi o que eu quiz dizer da primeira vez. Acho que não me expressei bem. 

 

Poderia dizer o que está "empacando" você? A teoria? A implementação? O que pretende fazer com essa pilha e esses parenteses? Em geral com árvores é mais simples usar recursão.

 

 

 

 

 

 

  • Haha 1
Link para o comentário
Compartilhar em outros sites
henrique Souza850
 

henrique Souza850

Postado
  • Autor
Postado

@arfneto Opaaa, me desculpa kkkkkkk, é que eu nao sei usar muito bem esse site, ainda estou apredendo a mandar as perguntas, mas muto obrigado, realmente da forma que colocou ficou fácil de mais de entender, mas enfim....Vou mandar o codigo que eu ja fiz ate agora, ainda estou no processo, logo logo ja tenho q entregar, to focado pra terminar logo mas ta difícil kkkk. Aqui esta, bem melhor agora de entender

  

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

typedef struct no{
    int conteudo;
    struct no * esq, *dir;
}No;

typedef struct{
	No *raiz;
}ArvBinaria;

void InserirEsq (No *no, int valor){

	if (no->esq == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    no->esq = novo;
	}

	else {

	    if (valor < no->esq->conteudo)
	        InserirEsq (no->esq, valor);

	    if (valor > no->esq->conteudo)
	        InserirDir (no->esq, valor);
	    }
    }

void InserirDir (No *no, int valor){

	if (no->dir == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    no->dir = novo;
    }

	else {

		if (valor > no->dir->conteudo)
		InserirDir (no->dir, valor);

        if (valor < no->dir->conteudo)
		InserirEsq (no->dir, valor);
	}

}

void inserir (ArvBinaria *arv, int valor){

	if (arv->raiz == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    arv->raiz = novo;
  	}

	else {

		if (valor < arv -> raiz -> conteudo)
		InserirEsq (arv->raiz, valor);

		if (valor > arv -> raiz -> conteudo)
		InserirDir (arv->raiz, valor);
	}

}

void Imprimir (No *raiz){

	if (raiz != NULL){
        Imprimir ( raiz-> esq);
		printf ("%d ", raiz->conteudo);
		Imprimir ( raiz-> dir);
	}

}

int main (){

	int i, n, valor;
	ArvBinaria arv;
	arv.raiz = NULL;

	printf ("Casos de testes: ");
	scanf ("%d", &n);
	
	for (i=0; i<=n; i++){

		printf ("Digite sua Arvore: ");
		scanf ("%d", &valor);
		inserir (&arv, valor);
    }
		
		printf ("\nImpressao da arvore binaria:\n");
		Imprimir (arv.raiz);

    }

 

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado 
typedef struct no{
    int conteudo;
    struct no * esq, *dir;
}No;

typedef struct{
	No *raiz;
}ArvBinaria;

Essa estrutura para a árvore não ajuda muito. Compare com essa e ignore o campo saldo --- é para o caso de balancear, como árvores AVL 

typedef struct _carga _Carga;

 struct _folha
{
	_Carga*         dados;
	char			saldo;
	struct _folha*  L;
	struct _folha*  R;
};
typedef struct _folha _Folha;

 struct _arvore
 {
	 _Folha*    raiz;
	 int        niveis;
	 char*      nome;
 };
 typedef struct _arvore _Arvore;

 

Como te disse, em geral é mais fácil usar recursão do que pilhas para as árvores., mas estará bem com as pilhas.

Se preocupe antes em como consumir os dados naquele formato da entrada, com os grupos de ( e ) e algum método de percurso para saber se a estrutura está ok. E depois percorrer a árvore de algum jeito só pra ver se está tudo certo.

 

Não conheço essa nomenclatura. O que é uma árvore degenerada e que d1@b0 é uma árvore cheia?

 

 

 

 

 

 

Link para o comentário
Compartilhar em outros sites
henrique Souza850
 

henrique Souza850

Postado
  • Autor
Postado

@arfneto Beleza arfneto, eu fiz desse jeito e deu certinho a minha arvore so fiz alguns ajustei, mas a arvore esta dando o resultado certinho, se eu colocar 500 250 750 75  305 ficaria assim: 75 250 305 500 750 perfeito, agora o problema é que eu tenho que responder essas questões no exemplo de saída, agora estou trabalhando nisso...

voce havia perguntado o que seria cheia e degenerada: arvore cheia é quando uma arvore binária, um nó tem sempre ou dois filhos ou nenhum, meu professor explicou, e degenerada é quando um nó tem um ou nenhum nó filho

  • Curtir 1
Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado
4 minutos atrás, henrique Souza850 disse:

@arfneto Beleza arfneto, eu fiz desse jeito e deu certinho a minha arvore so fiz alguns ajustei, mas a arvore esta dando o resultado certinho, se eu colocar 500 250 750 75  305 ficaria assim: 75 250 305 500 750 perfeito, agora o problema é que eu tenho que responder essas questões no exemplo de saída, agora estou trabalhando nisso...

voce havia perguntado o que seria cheia e degenerada: arvore cheia é quando uma arvore binária, um nó tem sempre ou dois filhos ou nenhum, meu professor explicou, e degenerada é quando um nó tem um ou nenhum nó filho

 

Entendo. 

 

Os resultados que faltam vem meio que no atutomático, na verdade:

  • uma BT completa --- cheia --- tem quantos nós? Você sabe quanto tem porque qualquer percurso vai te dizer isso. 2^N-1 nós certo? Onde N é o número de níveis. Mas em cada caso basta contar e ao final do percurso eles estão lá. Ou apenas marque na raiz. É a sua implementação afinal. Mesmo caso dos níveis. Durante o percurso pode usar uma pilha de níveis e a cada vez que "desce" empilha algo. Ao final do percurso o maior tamanho da pilha será o número de níveis.
  • Todos os nós à esquerda da raiz são menores que a raiz e você sabe o valor dela, mesmo caso dos maiores
  • se ela não for completa falta algum nó então não terá 2^N - 1 nós...
Link para o comentário
Compartilhar em outros sites
henrique Souza850
 

henrique Souza850

Postado
  • Autor
Postado

@arfneto 

Por enquanto to tentadno fazer meu codigo com while, tentei fazer do jeito que pede no exercicio mas nao to conseguindo :(, ele nao estava lendo a linha inteira, lia so os dois primeiros elemntos que eu coloco...ai ai



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

typedef struct no{
    int conteudo;
    struct no * esq, *dir;
}No;

typedef struct{
	No *raiz;
	int tam;
}ArvBinaria;

void InserirEsq (No *no, int valor){

	if (no->esq == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    no->esq = novo;
	}

	else {

	    if (valor < no->esq->conteudo)
	        InserirEsq (no->esq, valor);

	    if (valor > no->esq->conteudo)
	        InserirDir (no->esq, valor);
	    }
    }

void InserirDir (No *no, int valor){

	if (no->dir == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    no->dir = novo;
    }

	else {

		if (valor > no->dir->conteudo)
		InserirDir (no->dir, valor);

        if (valor < no->dir->conteudo)
		InserirEsq (no->dir, valor);
	}

}

void inserir (ArvBinaria *arv, int valor){

	if (arv->raiz == NULL){
		No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    arv->raiz = novo;
  	}

	else {

		if (valor < arv -> raiz -> conteudo)
		InserirEsq (arv->raiz, valor);

		if (valor > arv -> raiz -> conteudo)
		InserirDir (arv->raiz, valor);
	}

}

No* inserirnew (No *raiz, int valor){
	
	if (raiz == NULL){
	    No *novo = (No*)malloc(sizeof(No));
	    novo->conteudo = valor;
	    novo->esq = NULL;
	    novo->dir = NULL;
	    return novo;
    }
    
    else {
    	
    	if (valor < raiz->conteudo)
    	raiz->esq = inserirnew (raiz->esq, valor);
    	    
    	if (valor > raiz->conteudo)
        raiz->dir = inserirnew (raiz->dir, valor);
        
        return raiz;
    	    
	    }
    }

int  alturaArv (No * no) {
    
    if(raiz == NULL || raiz->dir == NULL && raiz->esq == NULL){
       return  0;
    }

    else{
        
		int esq = 1 + alturaArv(raiz->esq);
        int dir = 1 + alturaArv(raiz->dir);

        if(esq > dir)
            return esq;
        else
            return dir;
    }

}

int tamanho(No *raiz){
	
	if (raiz == NULL)
	    return 0;
	    
	else 
	    return 1 + tamanho (raiz->esq) + tamanho (raiz->dir);
    }
    
void Imprimir (No *raiz){

	if (raiz != NULL){
        Imprimir ( raiz-> esq);
		printf ("%d ", raiz->conteudo);
		Imprimir ( raiz-> dir);
	}

}

int main (){
	
	int op, valor;
	ArvBinaria arv;
	arv.raiz = NULL;
	
	No *raiz = NULL;

	do{

		printf ("\n0 - Sair\n1 - Inserir\n2 - Imprimir\n");
		scanf ("%d", &op);

		switch (op){

		case 0:
		printf ("\nSaindo...\n");
		break;

		case 1:
		printf ("Digite um valor: ");
		scanf ("%d", &valor);
		arv.raiz = inserirnew (arv.raiz, valor);
		break;

		case 2:
		printf ("\nImpressao da arvore binaria:\n");
		Imprimir (arv.raiz);
        printf ("\n");
        printf ("Tamanho: %d\n", tamanho(arv.raiz));
        printf ("Altura: %d\n", 
		break;

		default:
		printf ("\n opção Invalida...\n");
	}

	} while (op != 0);

 }

 

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado

Quer dizer que não conseguiu ler a tal "notação textual"?

 

Não entendi porque tem uma função para inserir a esquerda e outra a direita. E tantas inserir() afinal.

 

Seu código não parece completo. Veja o final do case 2 acima...

 

main() deve sempre ser a primeira função de seu programa. Em geral em outro arquivo

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado
56 minutos atrás, henrique Souza850 disse:

@arfneto sim sim,eu ainda nao terminei, estou tentando resoler ainda, coloquei o que eu ja fi ate agora...

 

Mas não respondeu sobre a notação e o while() desistiu de implementar aquilo? Que quiz dizer com o lance do "while"

 

E se nem tem um código completo fica difícil de dizer algo.E nada sobre os insert().

 

 :) 

Acho que devia focar na notação e na recursividade ou na pilha. Vai precisar de um dos dois funcionando se quer usar uma árvore. É muito mais difícil sem isso. Acho que não devia insistir

Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora
 Compartilhar
Ir à lista de tópicos

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

Mais

×
×
  • Criar novo...

Ebook grátis: Aprenda a ler resistores e capacitores!

EBOOK GRÁTIS!

CLIQUE AQUI E BAIXE AGORA MESMO!