Untitled
raw download clone
C
views 50
,
size 3989 b
#include <stdio.h>
#include <stdlib.h>

struct no{

	int info;

	struct no* prox;

};

typedef struct no* Lista;

struct no_arv{

	int info;

	struct no_arv* esq;
	struct no_arv* dir;

};

typedef struct no_arv* arvore;

int vazia(void* r){
	return (r == NULL);
}

void in_ordem(arvore r){

	if(!vazia(r)){
		in_ordem(r->esq);
		printf("[%d]\n", r->info);
		in_ordem(r->dir);
	}
}

void pre_ordem(arvore r){

	if(!vazia(r)){
		printf("[%d]\n", r->info);
		pre_ordem(r->esq);
		pre_ordem(r->dir);
	}
}

void pos_ordem(arvore r){

	if(!vazia(r)){
		pos_ordem(r->esq);
		pos_ordem(r->dir);
		printf("[%d]\n", r->info);
	}
}

arvore insere(arvore r, int x){

	if(vazia(r)){
		r = (struct no_arv*) malloc(sizeof(struct no_arv));

		r->info = x;
		r->esq = NULL;
		r->dir = NULL;
	}
	else
		if(x < r->info)
			r->esq = insere(r->esq, x);
		else
			r->dir = insere(r->dir, x);

	return r; 
}

int minimo(arvore r){

	while(r->esq != NULL)
		r = r->esq;

	return r->info;
}

int maximo(arvore r){

	while(r->dir != NULL)
		r = r->dir;

	return r->info;
}

arvore remove_arvore_binaria(arvore r, int x){

	if(vazia(r))
		return NULL;

	if(x < r->info)
		r->esq = insere(r->esq, x);
	else if(x > r->info)
			r->dir = insere(r->dir, x);
	else
		if(r->dir == NULL && r->esq == NULL){
			free(r);
			r = NULL;
		}
		else if(r->esq == NULL){
				r->info = minimo(r->dir);
				r->dir = remove_arvore_binaria(r->dir,x);
			}
				else{
					r->info = maximo(r->esq);
					r->esq = remove_arvore_binaria(r->dir, x);
				}
	return r;
}

int soma(arvore r, int n){

	if (r == NULL) 
    	return 0; 
    else {
    	n = soma (r->esq, n) + soma(r->dir, n) + r->info;
		return n;
   }
}

int altura (arvore r, int he, int hd) {
   if (r == NULL) 
      return -1; // altura da árvore vazia
   else {
      he = altura (r->esq, he, hd);
      hd = altura (r->dir, he, hd);
      if (he < hd) return hd + 1;
      else return he + 1;
   }
}

void imprime_nivel(arvore r, int i){

	if(vazia(r))
		return;
	if(i == 1){
		printf("[%d] ", r->info);
		return;
	}
	else if(i > 1){
		imprime_nivel(r->esq, i - 1);
		imprime_nivel(r->dir, i - 1);
	}
}

void imprimir(arvore r){

	int i, h = altura(r, 0, 0);

	for(i = 0; i <= h + 1; i++){
		imprime_nivel(r,i);
		printf("\n");
	}
}

Lista insereLista(Lista P, int x){

	if(vazia(P)){

		Lista novo = (Lista) malloc(sizeof(Lista));

		novo->info = x;
		novo->prox = NULL;

		P = novo;
		return P;
	}

	P->prox = insereLista(P->prox, x);
	return P;
}

Lista getImpar(Lista I, arvore r){

	if(!vazia(r)){
		if(r->info % 2 != 0)
			I = insereLista(I, r->info);
		getImpar(I, r->esq);
		getImpar(I, r->dir);
		return I;
	}
}

Lista impares(arvore r){

	Lista impar = NULL;

	impar = getImpar(impar, r);

	return impar;
}

int getSoma(int S, arvore r, int k){

	if(vazia(r))
		return 0;

	if(r->info < k){
		S = getSoma(S, r->esq, k) + getSoma(S, r->dir, k) + r->info; 
	}
	else
		return getSoma(S, r->esq, k);
}

int somaMenor(arvore r, int k){
	int soma;

	soma = getSoma(0, r, k);

	return soma;
}

int fon(arvore r, int interno, int *folha){
	if(vazia(r))
		return 0;
	if(vazia(r->esq) && vazia(r->dir))
		*folha+=1;
	if(!vazia(r->esq) || !vazia(r->dir))
		interno = fon(r->esq,interno,folha) + fon(r->dir,interno,folha) + 1;
	return interno;
}

int conta(arvore r, int *folhas){
	return fon(r,0,folhas);
}

int main(){

	int n = 0;
	//int vet[] = {9,11,2,5,7,14,22,27,8,1,6,12,20,25,30};
	int vet[] = {5,2,7,1,3,6,8};
	int soma;
	int folhas = 0;

	arvore r = NULL;
	Lista p = NULL;

	while(n < 7){
		r = insere(r, vet[n]);
		n++;
	}

	conta(r,&folhas);

	printf("%d\n", folhas);


	//printf("soma: %d\n", soma(r, 0));

	//in_ordem(r);
	//pre_ordem(r);
	//pos_ordem(r);

	//imprimir(r);

	free(r);

	return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.