Ir para o conteúdo
telele97

Problema com arvores

Mensagens Recomendadas

telele97

Pretendo fazer uma função que me de o nivel em que cada no esta e que o numero de nos abaixo dele. O código que eu fiz foi o seguinte:

int nos(tree *node, int nivel){

int altesq,altdir;
if (node==NULL){
 return 0;
}
node->nosabaixo=1+nos(node->left, altesq)+nos(node->right, altdir);

if(altesq>altdir){
 altesq++;
 node->nivel=altesq;
}else{
 node->lnivel=altdir;
 altdir++;
}
}

Só que isto não está a funcionar correctamente, alguém me pode dar uma ajuda?

Editado por pmg
Falta LP

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

Nao inicializaste altesq nem altdir.

Nao analisei o teu codigo portanto nao sei com que valor inicializar essas variaveis nem se isso chega para resolver o teu problema.

O facto é que usar as variaveis sem inicializacao é errado.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

além do referido pelo @pmg

node->nosabaixo =
                1 +                        // isto não faz sentido, se não tiver nada nem na direita nem na esquerda isto dá 1 = errado
                nos(node->left, altesq) +  // número de níveis existentes na esquerda ?
                nos(node->right, altdir);  // número de níveis existentes na direita ?

a tua função não está a retornar algum valor sequer.

olha bem para os erros/avisos do teu compilador


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

além do referido pelo @pmg

node->nosabaixo =
			 1 +						// isto não faz sentido, se não tiver nada nem na direita nem na esquerda isto dá 1 = errado
			 nos(node->left, altesq) +  // número de níveis existentes na esquerda ?
			 nos(node->right, altdir);  // número de níveis existentes na direita ?

a tua função não está a retornar algum valor sequer.

olha bem para os erros/avisos do teu compilador

Mas inicializo as variaveis com que valor? 0?

node->nosabaixo =
			 1 +						// isto não faz sentido, se não tiver nada nem na direita nem na esquerda isto dá 1 = errado

entao aqui devo fazer uma verificação para ver se tem alguma coisa, so se tiver e que devo executar isto certo?

quando eu chamo a função outra vez e para executar as acções na arvore da esquerda e na arvore da direita. Secalhar em vez da altura devia chamar com o numero de niveis e isso que queres dizer?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

primeiro de tudo deverias alterar o nome da função.

razão : não é esclarecedora do que a função realmente faz.

depois, tens de perceber o que queres.

antes de mais, uma função só retorna um valor. seja ele natural ou uma estrutura.

se queres retornar mais do que um valor, ou usas uma estrutura com os valores ou usas ponteiros nos argumentos

este é o pseudo-código para calcular o número de nós

calcula o numero de nós (no, nivel)
 se não for um nó
   retorna 0

 nos_da_direita  = calcula o numero de nós à direita  (no_da_direita, nível + 1)
 nos_da_esquerda = calcula o número de nós à esquerda (no_da_direita, nível + 1)

 returnar nos_da_direita + nos_da_esquerda + 1 // +1 porque estás a somar este nó


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

primeiro de tudo deverias alterar o nome da função.

razão : não é esclarecedora do que a função realmente faz.

depois, tens de perceber o que queres.

antes de mais, uma função só retorna um valor. seja ele natural ou uma estrutura.

se queres retornar mais do que um valor, ou usas uma estrutura com os valores ou usas ponteiros nos argumentos

este é o pseudo-código para calcular o número de nós

calcula o numero de nós (no, nivel)
se não for um nó
retorna 0

nos_da_direita = calcula o numero de nós à direita (no_da_direita, nível + 1)
nos_da_esquerda = calcula o número de nós à esquerda (no_da_direita, nível + 1)

returnar nos_da_direita + nos_da_esquerda + 1 // +1 porque estás a somar este nó

Basicamente o que eu quero e uma função que me va retornando os nos que estao abaixo daquele e que me armazene na estrutura tree o nivel a que aquele no esta. Ja fiz uma estrutura que e a tree onde e para armzenar os ponteiros , o nivel do no e os nos que estao abaixo dele. Eu sei fazer isto separademente agora nao consigo e fazer tudo numa função ...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

Basicamente o que eu quero e uma função que me va retornando os nos que estao abaixo daquele e que me armazene na estrutura tree o nivel a que aquele no esta. Ja fiz uma estrutura que e a tree onde e para armzenar os ponteiros , o nivel do no e os nos que estao abaixo dele. Eu sei fazer isto separademente agora nao consigo e fazer tudo numa função ...

então é só adicionar uma linha ao pseudo-codigo

calcula o numero de nós (nó, nível)
 se não for um nó
   retorna 0

 guardar nível no nó

 nos_da_direita  = calcula o numero de nós à direita  (no_da_direita, nível + 1)
 nos_da_esquerda = calcula o número de nós à esquerda (no_da_direita, nível + 1)

 retornar nos_da_direita + nos_da_esquerda + 1 // +1 porque estás a somar este nó


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

então é só adicionar uma linha ao pseudo-codigo

calcula o numero de nós (nó, nível)
se não for um nó
retorna 0

guardar nível no nó

nos_da_direita = calcula o numero de nós à direita (no_da_direita, nível + 1)
nos_da_esquerda = calcula o número de nós à esquerda (no_da_direita, nível + 1)

retornar nos_da_direita + nos_da_esquerda + 1 // +1 porque estás a somar este nó

so nao percebo porque e que retornas a soma dos dois nos...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não queres saber a quantidade de nós ?

Pretendo fazer uma função que me de o nivel em que cada no esta e que o numero de nos abaixo dele.


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

não queres saber a quantidade de nós ?

Sim, quero. Mas quando a função chega aquela parte ja tem a quantidade de nos correcta?

Eu tenho alguma dificuldade em perceber código recursivo :S

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

chamaste a função para o nó da direita e para o nó da esquerda, logo sim, tens

fiz o seguinte codigo

int varre(tree *node, int nivel){
int no_e=0;
int no_d=0;
if (node==NULL)
return 0;
node->nivel=nivel;
no_e=varre(node->left, nivel+1);
no_d=varre(node->right, nivel+1);
node->nosabaixo=no_e+no_d+1;
return (node->nosabaixo);
}

assim ja esta certo ?

Editado por telele97
Falta LP

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não, e sei claramente que nem compilaste o código:

int varre(tree *node, int nivel){
 int no_e=0;
 int no_d=0;

 if (node==NULL)
   return 0;

 node->level=lev; // <--- "lev" ??

 no_e=varre(node->left, nivel+1);
 no_d=varre(node->right, nivel+1);

 node->nosabaixo=no_e+no_d+1;

 return (node->nosabixo);
}

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

não, e sei claramente que nem compilaste o código:

int varre(tree *node, int nivel){
 int no_e=0;
 int no_d=0;

 if (node==NULL)
return 0;

 node->level=lev; // <--- "lev" ??

 no_e=varre(node->left, nivel+1);
 no_d=varre(node->right, nivel+1);

 node->nosabaixo=no_e+no_d+1;

 return (node->nosabixo);
}

editado.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

e já testaste ?

Sim, mas não dá certo. Por isso estou a perguntar se esta função está feita correctamente. Num dos casos retorna-me lixo. E no outro retorna 3 numeros acima do que devia :S

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

acho

O unico sitio onde podera estar o erro e nesta função que serve para cortar as folhas que são maiores que o numero que lhe e enviado por argumento

int corta(tree *a, double bound){
int b=0;
if(a==NULL)
 return 1;
else
 return 0;

b=corta(a->left,bound);
b=corta(a->right,bound);
if((a->node)>bound &&  b==1){
 free(a);
}
}

A função retorna 1 quando chega a uma folha.

Ou entao nesta função que pretende descobrir se a arvore e balanceada ou nao... Retorna -1 se a arvore nao for balaceada e retorna um valor diferente se ela for balanceada.

int verifica_balanceada(BTree *raiz){
int h1,h2;

if(raiz==0)
 return 0;
h1=verifica_balanceada(raiz->esquerda);
if(h1!=-1)
 h2=verifica_balanceada(raiz->direita);
else
 return -1;
if(h2!=-1){
 if((h1-h2)<=1 && (h1-h2)>=0){
  return h1+1;
 }else if((h1-h2)>=-1 && (h1-h2)<=0){
  return h2+1;
 }else{
  return -1;
 }
}else{
 return -1;
}
}

P.S. como colocam o código com cor e identação?

Editado por thoga31
GeSHi

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

P.S. como colocam o código com cor e identação?

Colocando todo o codigo entre as tags [ code=c ] e [ /code ], sem espacos!

Talvez seja mais facil de fazer o layout do codigo com o modo de edicao simples: clica no primeiro botao da barra das ferramentas que aparece quando comecas a escrever um post (parece um interruptor).

A indentacao tem de ser feita pelo programador. Meter as tags de codigo nao vai automaticamente indentar o codigo!!

Editado por pmg

What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

as funções apresentadas não tem nada haver com o problema inicial

apresenta a inicialização e chamada da função assim como o valor apresentado e o valor que deveria apresentar


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
telele97

as funções apresentadas não tem nada haver com o problema inicial

apresenta a inicialização e chamada da função assim como o valor apresentado e o valor que deveria apresentar

O problema e que a chamada daquela função é feita depois destas ...

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.