C Preciso transformar meu do while em um for da minha arvore binaria

henrique Souza850 · 14 de julho de 2020

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

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

typedef struct{
	No *raiz;
	int tamanho;
	int alturaArv;
}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 *raiz){
    
    if(raiz == NULL || raiz->dir == NULL && raiz->esq == NULL){
       return  0;
    }

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

        if(esq < dir)
            return esq +1;
        else
            return dir +1;
    }
    
	return 0;
}

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);
	}

}

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

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

int main (){
	
	int op, valor, quantidade, i;
	ArvBinaria arv;
	arv.raiz = NULL;
	
	No *raiz = NULL;
    
	do{
		
		printf ("\n1 - Inserir\n2 - Imprimir\n");
		scanf ("%d", &op);

		switch (op){
	
        case 1:
		printf ("Digite um valor: ");
		scanf ("%d", &valor);
		arv.raiz = inserirnew (arv.raiz, valor);
		break;
		
		case 2:
		printf ("\n");
		Imprimir (arv.raiz);
		printf ("\n");
		Imprimirpre (arv.raiz);
		printf ("\n");
        Imprimirpos (arv.raiz);
        printf ("\nQ - %d\n", tamanho(arv.raiz));
        printf ("H - %d\n", alturaArv(arv.raiz));
        break;
        
    }
    
} while (op != 0);

}

Alguém poderia me dar uma ajuda nesse código de arvore binaria?? Estou quebrando a cabeca pra arrumar isso...

Como eu poderia tirar esse do while e usar um for no lugar? usando vetor pra colocar os elementos na arvore?...Tenho que fazer um exercicio que leia a seguinte entrada...

A primeira linha recebe um inteiro N que indica o número de casos de teste.)

As N subsequentes linhas conterão as notações textuais pré ordem das árvores binárias)

Ficaria mais ou menos assim:

2 //casos de testes

1 5 7 8 3 //elementos que foi inserido na arvore

9 2 7 4 5 //elementos inseridos na NOVA arvore

Resultado da arvore binaria:

1 3 5 7 8

2 4 5 7 9

Alguém poderia me ajudar? Os que eu fiz ate agora usando for ele so le o primeiro elemento da linha...ta complicado

arfneto · 14 de julho de 2020

Inclua os protótipos no início de seu arquivo:

int	alturaArv(No*);
void	Imprimir(No*);
void	Imprimirpos(No*);
void	Imprimirpre(No*);
void	inserir(ArvBinaria*, int);
void	InserirDir(No*, int);
void	InserirEsq(No*, int);
No*	inserirnew(No*, int);
int	tamanho(No*);

Basta copiar isso para depois das structs. Ou vai ter sempre para compilar.

E deixe main() no início sempre. Facilita para você e para os outros.

Porque inserir Dir e Esq?

O programa desse modo:

Spoiler


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

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

typedef struct {
	No* raiz;
	int tamanho;
	int alturaArv;
}ArvBinaria;

int  alturaArv(No*);
void Imprimir(No*);
void Imprimirpos(No*);
void Imprimirpre(No*);
void inserir(ArvBinaria*, int);
void InserirDir(No*, int);
void InserirEsq(No*, int);
No* inserirnew(No*, int);
int tamanho(No*);


int main() {

	int op, valor;
	ArvBinaria arv;
	arv.raiz = NULL;

	No* raiz = NULL;

	do {

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

		switch (op) {

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

		case 2:
			printf("\n");
			Imprimir(arv.raiz);
			printf("\n");
			Imprimirpre(arv.raiz);
			printf("\n");
			Imprimirpos(arv.raiz);
			printf("\nQ - %d\n", tamanho(arv.raiz));
			printf("H - %d\n", alturaArv(arv.raiz));
			break;

		}

	} while (op != 0);

}

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* raiz) {

	if (raiz == NULL || raiz->dir == NULL && raiz->esq == NULL) {
		return  0;
	}

	else {

		int esq = alturaArv(raiz->esq);
		int dir = alturaArv(raiz->dir);

		if (esq < dir)
			return esq + 1;
		else
			return dir + 1;
	}

	return 0;
}

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);
	}

}

void Imprimirpre(No* raiz) {

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

void Imprimirpos(No* raiz) {

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

henrique Souza850 · 14 de julho de 2020

@arfneto Ja inclui amigo, bem melhor de visualizar agora, a estrutura esta otima...Agora eu tenho uma duvida, como eu poderia trocar esse do while e colocar tipo um for pra ser uma sequencia de elementos que vai ser inserida na arvore?

Tipo assim:

1 //QTD DE CASOS DE TESTE

1 4 6 8 3 5 //ELEMENTOS QUE vão SER INSERIDOS NA ARVORE

1 3 4 5 6 8 //RESULTADO DA ARVORE

Entende mais ou menos? Eu queria que ele lesse essa linha e colocasse esses numeros ja direto na arvore...

Quando eu tentei fazer ele so lia o primeiro elemento, nao consigo criar uma funçao e tirar esse do while, tentei fazer com vetor ,mas nao consegui

int  main () {
    char str [ 300 ];
    
  int N, i;
    scanf ("%d" , &N);
    for (i=0 ; i<N; i++) {
        scanf ("%s" , str);
        processa (str);
    }
    return  0 ;
}

Tentei implementar isso pra dar certo ...mas mesmo assim nao da

arfneto · 14 de julho de 2020

16 minutos atrás, henrique Souza850 disse:

a inclui amigo, bem melhor de visualizar agora, a estrutura esta otima...Agora eu tenho uma duvida, como eu poderia trocar esse do while e colocar tipo um for pra ser uma sequencia de elementos que vai ser inserida na arvore

Não é apenas uma questão estrutural. O compilador precisa dos protótipos para poder encontrar as declarações das funções e nem sempre é possível colocar todas numa ordem em que compile sem protótipos...

Então o melhor é ir declarando, se possível em alguma ordem objetiva tipo a alfabética...

O lance dos comandos eu acho que não entendi.

Dada uma condição C e um loop while(C){S} ela é igualzinho a um for (;C;){S} que por sua vez equivale a {S}while(C){S} então a menos do fato do {S} rodar ao menos uma vez no terceiro caso vai dar na mesma.

Eu acho que no caso da sua notação podia apenas chamar de novo o processo a cada novo nível, recursivamente ou em loop. Acho já te disse isso: acho que sem recursividade e sem uma pilha vai ficar difícil tratar isso. Árvores são assim.

henrique Souza850 · 14 de julho de 2020

@arfneto É que nesse exercício tenho que fazer igual aos exemplos de entrada que pede nele, se nao pedisse tava suave kkkkk, mas tenho que fazer desse jeito como coloquei ali em cima infelizmente

arfneto · 14 de julho de 2020

2 minutos atrás, henrique Souza850 disse:

É que nesse exercício tenho que fazer igual aos exemplos de entrada que pede nele, se nao pedisse tava suave kkkkk, mas tenho que fazer desse jeito como coloquei ali em cima infelizmente

Não consigo entender o que você quer dizer e onde isso está associado a qual estrutura de loop.

Eis o texto

Você entendeu o que eu expliquei sobre não usar pilha ou recursão? Se está determinado a não usar estude o algoritmo chamado Morris Traversal como descrito aqui

Ou entenda que pode chamar sua rotina de novo a cada '(' que encontra, passando apenas o lado em que está. A tal notação textual como escrita aí é preOrder, primeiro o nó, depois a esquerda e depois a direita. Apenas siga a onda

arfneto · 16 de julho de 2020

Pensando nesse troço, vou te mostrar uma função que consome esse tipo de entrada. Não testei muito, mas não vejo razão pra não funcionar

A partir de (SAE) (SAD) como diz no desenho, e do exemplo

Você vê que do lado esquerdo da raiz tem uma árvore igual, (SAE) seria ( 2 (1) (3) ) certo?

E do lado direito?

Nesse caso seria a árvore com raiz 7, ( 7 (6) (8) )

Só que não termina aí: 8 tem um descendente à direita e então seria ( 7 (6) (8 ( ) (9) ) )

Então você só precisa resolver a primeira parte:

a raiz
depois vai ter, a partir do '(', a árvore esquerda e depois o outro grupo a partir do '(' com a árvore direita. Claro que as duas podem estar vazias por exemplo
```
//		2 ( (1)  (3)  )  ok

//		2 ( ( )  ( )  ) ok

//		2 ok

//		5 ( 2 (1) (3) )  (7  (6)  (8 ()  (9) ) ) o exemplo [*]
```
Mas o que importa é que é a mesma coisa, sempre

Então se você tiver uma rotina
```
	int insere(FILE*);
```
que você chama com o arquivo aberto, apontando para a primeira posição da raiz, e ela retornar o total de nodes que ela conseguiu extrair ela vai fazer quase tudo que precisa: no caso do exemplo [*] ela deve retornar 8. Mas se chamar a partir do node 2 ela retorna 2, se chamar a partir do 7 ela retorna 3, o 6 para a esquerda e o 8 e o 9 pra direita, e assim por diante.

Acho que deu pra entender...

Uma pequena mudança no mecanismo

Seria legal poder usar espaços e mudar de linha para separar exemplos mais complicados

Compare

5(2(1)(3))(7(6)(8()(9)))

Com essa notação textual, digamos, mais estilosa

5
( 2 (1)(3) )
( 7 (6) ( 8( ()(9) ) )

E fica mais fácil de imaginar a árvore e conferir os dados...

Então uma pequena liberalidade em insere() para aceitar espaços e coisas assim faz bem. Eu fiz isso porque é mais simples o programa fazer do que eu ficar rabiscando no papel

Um teste de uma rotina para o exemplo acima

-> Node: '5'
-> Node: '2'
Lido ')' Node: '1'
Lidos 1 nodes a esquerda de '2'
Lido ')' Node: '3'
Lidos 1 nodes a esquerda
Node Terminal
Lidos 0 nodes a direita
Lidos 1 nodes a direita de '2'
Lidos 3 nodes a esquerda de '5'
-> Node: '7'
Lido ')' Node: '6'
Lidos 1 nodes a esquerda de '7'
-> Node: '8'
Node Terminal
Lidos 0 nodes a esquerda
Lido ')' Node: '9'
Lidos 1 nodes a esquerda
Node Terminal
Lidos 0 nodes a direita
Lidos 1 nodes a direita
Lidos 1 nodes a esquerda de '8'
Node Terminal
Lidos 0 nodes a direita de '8'
Lidos 2 nodes a esquerda
Lidos 0 nodes a direita
Lidos 2 nodes a direita de '7'
Lidos 4 nodes a esquerda
Lidos 0 nodes a direita
Lidos 4 nodes a direita de '5'
Inseridos 8 Nodes

E como seria essa função?

int		insere(FILE* F)
{	if (F == NULL) return -1; // sem arquivo
	char campo[80];
	char* p = &campo[0];
	int lNodes = 0;
	int rNodes = 0;
	int n = fgetc(F);

	while (3)
	{
		switch (n)
		{
		case '(':
			if (p != campo)
			{
				*p = 0;
				printf("-> Node: '%s'\n", campo);
				lNodes = insere(F);
				printf("Lidos %d nodes a esquerda de '%s'\n",
					lNodes, campo);
				rNodes = insere(F);
				printf("Lidos %d nodes a direita de '%s'\n",
					rNodes, campo);
				return 1 + lNodes + rNodes;
			};
			// nao tem campo antes desse ()
			lNodes = insere(F);
			printf("Lidos %d nodes a esquerda\n", lNodes);
			rNodes = insere(F);
			printf("Lidos %d nodes a direita\n", rNodes);
			return lNodes + rNodes;

		case ')':
			if (p == campo)
			{	printf("Node Terminal\n");
				return 0;
			}
			else
			{	*p = 0;
				printf("Lido ')' Node: '%s'\n", campo);
				return 1;
			};	// if()
			break;

		case  8: // tab
		case 10: // newline
		case 13: // return
		case 32: // espaco
			break;

		case EOF: 
			if (p == campo)	return 0;
			*p = 0;
			printf("EOF?: Ultimo Node: '%s'\n", campo);
			return 1;
			break;

		default:	// apenas grava
			*p = (char)n;
			p += 1;
			break;
		};
		n = fgetc(F);
	};	// while()
	printf("Final em insere()\n");
	return 0;
};	// insere()

Podia ser mais curta. mas deixei muitas mensagens e coisas supérfluas

E como seria main() para testar um desses?

Pode ser algo bem simples, como

int main(int argc, char** argv)
{
	if (argc < 2)
	{	printf("\nUse: programa nome_do_arquivo\n");
		return -1;
	};
	FILE* F = fopen(argv[1], "r");
	if (F == NULL) return -1;
	printf("Inseridos %d Nodes\n", insere(F));
	fclose(F);
	return 0;
};

Basta chamar na linha de comando e passar o nome do arquivo que tem os dados da árvore, como se faz desde os '70.

O programa "todo"

Spoiler


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

int		insere(FILE*);

int main(int argc, char** argv)
{
	if (argc < 2)
	{	printf("\nUse: programa nome_do_arquivo\n");
		return -1;
	};
	FILE* F = fopen(argv[1], "r");
	if (F == NULL) return -1;
	printf("Inseridos %d Nodes\n", insere(F));
	fclose(F);
	return 0;
};

int		insere(FILE* F)
{	if (F == NULL) return -1; // sem arquivo
	char campo[80];
	char* p = &campo[0];
	int lNodes = 0;
	int rNodes = 0;
	int n = fgetc(F);

	while (3)
	{
		switch (n)
		{
		case '(':
			if (p != campo)
			{
				*p = 0;
				printf("-> Node: '%s'\n", campo);
				lNodes = insere(F);
				printf("Lidos %d nodes a esquerda de '%s'\n",
					lNodes, campo);
				rNodes = insere(F);
				printf("Lidos %d nodes a direita de '%s'\n",
					rNodes, campo);
				return 1 + lNodes + rNodes;
			};
			// nao tem campo antes desse ()
			lNodes = insere(F);
			printf("Lidos %d nodes a esquerda\n", lNodes);
			rNodes = insere(F);
			printf("Lidos %d nodes a direita\n", rNodes);
			return lNodes + rNodes;

		case ')':
			if (p == campo)
			{	printf("Node Terminal\n");
				return 0;
			}
			else
			{	*p = 0;
				printf("Lido ')' Node: '%s'\n", campo);
				return 1;
			};	// if()
			break;

		case  8: // tab
		case 10: // newline
		case 13: // return
		case 32: // espaco
			break;

		case EOF: 
			if (p == campo)	return 0;
			*p = 0;
			printf("EOF?: Ultimo Node: '%s'\n", campo);
			return 1;
			break;

		default:	// apenas grava
			*p = (char)n;
			p += 1;
			break;
		};
		n = fgetc(F);
	};	// while()
	printf("Final em insere()\n");
	return 0;
};	// insere()

// fim

É bem simples. Como eu disse no primeiro tópico, é importante escrever em torno dos dados.

Esse é o trecho mais importante

		case '(':
			if (p != campo)
			{
				*p = 0;
				printf("-> Node: '%s'\n", campo);
				lNodes = insere(F);
				printf("Lidos %d nodes a esquerda de '%s'\n",
					lNodes, campo);
				rNodes = insere(F);
				printf("Lidos %d nodes a direita de '%s'\n",
					rNodes, campo);
				return 1 + lNodes + rNodes;
			};

E veja como dá pra associar de imediato com a tal notação: ao ler um '(' se eu tenho um campo então eu chamo insere() para a esquerda e para a direita e retorno a soma dos dois mais 1 claro, já que a raiz também é um nó...

Pense nisso.

Na prática basta trocar os printf() pelas chamadas às rotinas que inserem na árvore e usar um percurso qualquer e terá as respostas do enunciado. Eu preferi não escrever aqui.

Não me culpe se tiver algo errado. Não testei quase nada. Mas acho que não tem.