Ajuda árvore binária

[johnatan.etges]

Olá amigos. Tenho um exercício para resolver aqui estou com alguns problemas. Segue o enunciado:

3-Altere os procedimentos que fazem a travessia na árvore (procedures já implementados por mim sem qualquer problema) para que mostre também o nível em que se encontra o nó que está sendo visitado.

4-Escreva um método que mostra somente os valores dos nós de um determinado nível que deve ser passado como parâmetro.

Aí vai o que eu já implementei:

program exerc_binarythree;uses crt;
type   pno = ^tno;   tno = record     info : integer;     esq, dir, pai : pno;   end;
var  arvore:pno;
  function criano(valor : integer) : pno;  var    temp : pno;  begin    new (temp);    temp^.info := valor;    temp^.esq := nil;    temp^.dir := nil;    criano := temp;  end;  function dna(filho: pno): pno;  begin    dna := filho^.pai;  end;
  procedure preordem(raiz:Pno);  begin    //caso base    if raiz <> nil then    begin      writeln(raiz^.info);      preordem(raiz^.esq);      preordem(raiz^.dir);    end;  end;
  procedure ordemsimetrica(raiz: pno);  begin    if raiz <> nil then    begin      ordemsimetrica(raiz^.esq);      writeln(raiz^.info);      ordemsimetrica(raiz^.dir);    end;  end;
  procedure posordem(raiz: pno);  begin    if raiz <> nil then    begin      posordem(raiz^.esq);      posordem(raiz^.dir);      writeln(raiz^.info);    end;  end;
begin  arvore := criano(9);  arvore^.esq := criano(4);  arvore^.pai := dna(arvore);  arvore^.dir := criano(12);  arvore^.pai := dna(arvore);  arvore^.esq^.esq := criano(2);  arvore^.pai := dna(arvore);  arvore^.esq^.dir := criano(6);  arvore^.pai := dna(arvore);  arvore^.dir^.esq := criano(10);  arvore^.pai := dna(arvore);  arvore^.dir^.dir := criano(14);  arvore^.pai := dna(arvore);  arvore^.esq^.esq^.esq := criano(1);  arvore^.pai := dna(arvore);  arvore^.esq^.esq^.dir := criano(3);  arvore^.pai := dna(arvore);  arvore^.esq^.dir^.esq := criano(5);  arvore^.pai := dna(arvore);  arvore^.esq^.dir^.dir := criano(7);  arvore^.pai := dna(arvore);  arvore^.dir^.esq^.dir := criano(11);  arvore^.pai := dna(arvore);  arvore^.dir^.dir^.dir := criano(15);  arvore^.pai := dna(arvore);  writeln('Percorrendo por pre ordem');  preordem(arvore);  readln;    writeln('Percorrendo por ordem simetrica.');  ordemsimetrica(arvore);    readln;  writeln('Percorrendo por pos ordem');  posordem(arvore);    readln;end.

bem, acredito que se me derem uma ajuda com a questão de número 3 eu já consiga resolver a questão 4 também.

Obrigado desde já!

[Simon Viegas]

Olá amigos. Tenho um exercício para resolver aqui estou com alguns problemas. Segue o enunciado:

3-Altere os procedimentos que fazem a travessia na árvore (procedures já implementados por mim sem qualquer problema) para que mostre também o nível em que se encontra o nó que está sendo visitado.

4-Escreva um método que mostra somente os valores dos nós de um determinado nível que deve ser passado como parâmetro.

Aí vai o que eu já implementei:

uses crt;

type
pno = ^tno;
tno = record
info : integer;
esq, dir, pai : pno;
end;

var
arvore:pno;

function criano(valor : integer) : pno;
var
temp : pno;
begin
new (temp);
temp^.info := valor;
temp^.esq := nil;
temp^.dir := nil;
criano := temp;
end;
function dna(filho: pno): pno;
begin
dna := filho^.pai;
end;

procedure preordem(raiz:Pno);
begin
//caso base
if raiz <> nil then
begin
writeln(raiz^.info);
percorrearvorePO(raiz^.esq);
percorrearvorePO(raiz^.dir);
end;
end;


procedure ordemsimetrica(raiz: pno);
begin
if raiz <> nil then
begin
percorrearvoreos(raiz^.esq);
writeln(raiz^.info);
percorrearvoreos(raiz^.dir);
end;
end;

procedure posordem(raiz: pno);
begin
if raiz <> nil then
begin
percorrearvorepso(raiz^.esq);
percorrearvorepso(raiz^.dir);
writeln(raiz^.info);
end;
end;

begin
arvore := criano(9);
arvore^.esq := criano(4);
arvore^.pai := dna(arvore);
arvore^.dir := criano(12);
arvore^.pai := dna(arvore);
arvore^.esq^.esq := criano(2);
arvore^.pai := dna(arvore);
arvore^.esq^.dir := criano(6);
arvore^.pai := dna(arvore);
arvore^.dir^.esq := criano(10);
arvore^.pai := dna(arvore);
arvore^.dir^.dir := criano(14);
arvore^.pai := dna(arvore);
arvore^.esq^.esq^.esq := criano(1);
arvore^.pai := dna(arvore);
arvore^.esq^.esq^.dir := criano(3);
arvore^.pai := dna(arvore);
arvore^.esq^.dir^.esq := criano(5);
arvore^.pai := dna(arvore);
arvore^.esq^.dir^.dir := criano(7);
arvore^.pai := dna(arvore);
arvore^.dir^.esq^.dir := criano(11);
arvore^.pai := dna(arvore);
arvore^.dir^.dir^.dir := criano(15);
arvore^.pai := dna(arvore);
writeln('Percorrendo por pre ordem');
preordem(arvore);
readln;
writeln('Percorrendo por ordem simetrica.');
ordemsimetrica(arvore);
readln;
writeln('Percorrendo por pos ordem');
posordem(arvore);
readln;
end.

program exerc_binarythree;

bem, acredito que se me derem uma ajuda com a questão de número 3 eu já consiga resolver a questão 4 também.

Obrigado desde já!

Olá,

1) Chamada dos comandos

Aqui seu código NÃO está compilável, já que cada procedimento está chamando procedimentos que não existem.

Acredito que suas árvores binárias utilizem basicamente de recursividade, logo os procedimentos devem chamar a se mesmo!

2) Recursividade

Creio que você já tenha uma noção do que seja recursividade. Mas em fim.

Um subprograma é recursivo quando chama a si mesmo.

A chave da recursividade está na "pilha de chamadas" e sobretudo nas "variáveis locais", pois cada um desses chamados terá as suas próprias variáveis e consequentemente seus próprios valores individuais. Assim, a medida que o programa vai percorrendo essas chamadas, o programador pode manipular essas variáveis de forma estruturada.

AQUI um bom exemplo de recursividade.

3) Nível na árvore

Em relação ao nível da árvore binária que usa recursividade, o nível vai ser justamente a quantidade de chamadas em cadeia que está ocorrendo por cima da outra, ou seja, quantos chamadas do método está me pilha.

Vide imagem:

4) Somente de determinado nível

Ai eu deixo por tua conta.

Tente ai, qualquer coisa avisa.

No aguardo

Abraços

[johnatan.etges]

Olá,

1) Chamada dos comandos

Aqui seu código NÃO está compilável, já que cada procedimento está chamando procedimentos que não existem.

pois é, eu mudei o nome das procedures antes de postar aqui para ficar mais legível e acabei esquecendo de mudar nas chamadas. Erro já corrigido.

3) Nível na árvore

Em relação ao nível da árvore binária que usa recursividade, o nível vai ser justamente a quantidade de chamadas em cadeia que está ocorrendo por cima da outra, ou seja, quantos chamadas do método está me pilha.

Ok, eu entendi a tua resposta. Colaborou um bocado. Obrigado.

[Simon Viegas]

pois é, eu mudei o nome das procedures antes de postar aqui para ficar mais legível e acabei esquecendo de mudar nas chamadas. Erro já corrigido.

Ok, eu entendi a tua resposta. Colaborou um bocado. Obrigado

.

Olá,

Também conseguiu fazer o quarto? se sim, se puder poste o código para analisarmos, se não pode ficar a vontade para tirar outras dúvidas.

No aguardo

Abraços

[johnatan.etges]

Olá,

Também conseguiu fazer o quarto? se sim, se puder poste o código para analisarmos, se não pode ficar a vontade para tirar outras dúvidas.

No aguardo

Abraços

Opa consegui sim.

Segue o código:

 procedure preordem(raiz:Pno; nivel:integer);
  begin
    if raiz <> nil then
    begin
      writeln(raiz^.info: 2,' NIVEL: ', nivel: 2);
      if nivel = 3 then
         writeln('Elemento de n¡vel 3 : ', raiz^.info);
      preordem(raiz^.esq,nivel+1);
      preordem(raiz^.dir,nivel+1);
    end;
  end;


  procedure ordemsimetrica(raiz: pno; nivel:integer);
  begin
    if raiz <> nil then
    begin
      ordemsimetrica(raiz^.esq,nivel+1);
      writeln(raiz^.info: 2, ' NIVEL: ',nivel: 2);
      if nivel = 3 then
         writeln('Elemento de n¡vel 3: ',raiz^.info);
      ordemsimetrica(raiz^.dir,nivel+1);
    end;
  end;

  procedure posordem(raiz: pno; nivel:integer);
  begin
    if raiz <> nil then
    begin
      posordem(raiz^.esq,nivel+1);
      posordem(raiz^.dir,nivel+1);
      writeln(raiz^.info: 2,' NIVEL: ',nivel: 2);
    end;
  end;

Observando que, desta vez, eu postei apenas a parte do código em que se encontra o procedimento.

Se alguém tiver uma ideia melhor de como fazer, estou aberto a opiniões.

[Simon Viegas]

Opa consegui sim.

Segue o código:

begin
if raiz <> nil then
begin
writeln(raiz^.info: 2,' NIVEL: ', nivel: 2);
if nivel = 3 then
writeln('Elemento de n¡vel 3 : ', raiz^.info);
preordem(raiz^.esq,nivel+1);
preordem(raiz^.dir,nivel+1);
end;
end;


procedure ordemsimetrica(raiz: pno; nivel:integer);
begin
if raiz <> nil then
begin
ordemsimetrica(raiz^.esq,nivel+1);
writeln(raiz^.info: 2, ' NIVEL: ',nivel: 2);
if nivel = 3 then
writeln('Elemento de n¡vel 3: ',raiz^.info);
ordemsimetrica(raiz^.dir,nivel+1);
end;
end;

procedure posordem(raiz: pno; nivel:integer);
begin
if raiz <> nil then
begin
posordem(raiz^.esq,nivel+1);
posordem(raiz^.dir,nivel+1);
writeln(raiz^.info: 2,' NIVEL: ',nivel: 2);
end;
end;

 procedure preordem(raiz:Pno; nivel:integer);

Observando que, desta vez, eu postei apenas a parte do código em que se encontra o procedimento.

Se alguém tiver uma ideia melhor de como fazer, estou aberto a opiniões.

Olá,

johnatanlp, vamos à alguns pontos:

1) Sobre a impressão de determinado nível

Faltou uns detalhes.

4-Escreva um método que mostra somente os valores dos nós de um determinado nível que deve ser passado como parâmetro.

No caso o nível escolhido deve ser passado por parâmetro.

4-Escreva um método que mostra somente os valores dos nós de um determinado nível que deve ser passado como parâmetro.

Creio que você deva criar um novo método, e não alterar um existente. Ele só não especifica o tipo, se é preOrdem, ordemSimetrica ou posOrdem. Ai seria algo como:

procedure ordemSimetricaNivel(raiz: pno; nivel, nivelEscolhido:integer);

OBS.: Veja que esse método deve «mostra somente os valores dos nós de um determinado nível...».

Ai no programa principal poderia ficar assim por exemplo:

  writeln('Percorrendo por pre ordem');
  preordem(arvore,0);
  readln;  
  writeln('Percorrendo por ordem simetrica.');
  ordemsimetrica(arvore,0);
  readln;
  writeln('Percorrendo por pos ordem');
  posordem(arvore,0)
  write;
  writeln('Informe o nivel a ser exibido');
  readln(niveEscolhido);
  ordemSimetricaNivel(arvore,0,nivelEscolhido);

Algo mais ou menos assim.

2) Criação da árvore

Por quê você também não cria um método para "inserir um elemento na árvore"?

Algo como:

procedure inserir(raiz: pno; valor:integer);

Ai no caso a própria procedure deve gerenciar onde o novo dado deve ficar.

***

No aguardo