Árvore de Busca Binária

[N0vato]

Uma arvore binaria de busca e denida com a propriedade de que em qualquer no n,

todos os elementos da sub-arvore esquerda de n tem valores menores ou iguais ao de n,

e todos os elementos da sub-arvore direita tem valores maiores que o de n. Considere

as classes gabarito arv_bb e no, apresentadas em sala de aula, que implementam uma

arvore binaria de busca:

/* Declarac~ao da classe no */

template <class TIPO>

class no{

TIPO val; /* Valor armazenado */

no<TIPO> *esq, *dir; /* Ponteiros para sub-arvores */

public:

no(TIPO valor); /* Cria um no com o valor fornecido e esq = dir = NULL */

(...)

no<TIPO> * antecessor(const TIPO& valor);

no<TIPO> * sucessor(const TIPO& valor);

void mostra(void);

};

(...)

/* funcao para mostrar valor */

template <class TIPO>

void no<TIPO>::mostra_no(void){

cout << ' ' << this->val << endl;

}

template <class TIPO>

class arv_bb {

no<TIPO> *raiz;

public:

arv_bb(void); /* Criac~ao de uma arvore sem nenhum no */

/* Imprime antecessor, se houver */

void antecessor(const TIPO& valor);

/* Imprime sucessor, se houver */

void sucessor(const TIPO& valor);

};

1. Considere que a arvore n~ao possui valores repetidos. Escreva a função antecessor

da classe no que receba um valor valor e retorne um ponteiro para o no da

arvore que armazena o maior valor menor do que valor. Caso valor não seja

encontrado na arvore ou se ele for o menor valor armazenado na arvore, a função

deve retornar NULL. Por exemplo, se essa função fosse aplicada a seguinte arvore

para valor igual a 10, a função deveria retornar um ponteiro para o no que

armazena o valor 8. Se fosse aplicada para valor igual a 21, a função deveria

retornar um ponteiro para o no 20:

A função deve tirar proveito da ordenac~ao da arvore e obedecer ao seguinte

prototipo:

template <class TIPO>

no<TIPO> * no<TIPO>::antecessor(const TIPO& valor);

Alguém teria alguma ideia de como se faz essa questão, estou tentando fazer desde ontem, mas primeiro que meus conhecimentos de recursão são extremamente limitados, segundo que eu me confundi mais ainda porque eu imagino que tennham de ser fornecidos tratamentos diferentes no caso do valor passado ser maior que val armazenado na raiz, menor que val armazenado na raiz, isso porque eu nem estava contando o caso de val == valor... eu tentei começar um rascunho de uma solução não recursiva que ficaria mais ou menos assim:

template <class TIPO>
no<TIPO> *no<TIPO>::antecessor(const TIPO &valor)
{
  no<TIPO> *p;

  if(valor < val)
   {
     while(val != valor)
      {
        if (esq == NULL) return false;
         if(valor > val)
           {
             p=dir;
            }
         else
           {
             p= esq;
            }
        }
    if(esq != NULL)
     {
       p = esq;
       while(dir != NULL)
         {
           p=dir;
          }
        return p;
      }
    else
     {
      return NULL;
      }
    }

A minha ideia seria a seguinte, se o valor passado for menor que a raiz, ir para a sub-árvore esquerda e achando o valor nela, se o filho do nó que tem val igual a valor não tiver dir, retorna esse filho, se tiver, procurar até a folha desse dir.

Quando eu ia começar a fazer a parte em que valor > val, percebi que o tratamento deveria ser bem diferente.

Se alguém puder ajudar de qualquer forma, mesmo com uma solução recursiva.

[CaioTakano]

Ola N0vato,

Não consegui ler o enunciado do seu problema, entretanto pelo que você postou posso ver qual o seu problema. Primeiro, árvores são estruturas recursivas por natureza, logo se você vai aprender a mexer com árvores você TEM que aprender recursão. Felizmente recursão não é algo tão difícil assim o código seguinte mostra uma função recursiva:

int fib (int n) //calcula o número de fibonacci de ordem n
{
  if (n <= 1)  //condição de parada
    return 1;

  return fib (n - 1) + fib (n - 2);  //recursão
}

O código acima mostra o que uma função recursiva tem, primeiro ela tem uma condição de parada que é um valor para o qual você sabe o valor que a função tem que retornar, nesse caso o número de fibonacci de ordem 0 e 1 que é definido como 1, depois você tem todos os outros casos da função que são calculados a partir de valores que a função assume para valores que podem ser calculados direta ou indiretamente dos casos de parada. Nesse caso o número de fibonacci de ordem 'n' é calculado como a soma do número de fibonacci de ordem 'n-1' e 'n-2'.

Resumindo funções recursivas chamam a si mesmas até que um valor conhecido (o caso de parada) seja atingido, ai ela vai retornando sucessivamente até chegar no caso que você queria calcular.

Para você percorrer a árvore não existe um jeito fácil de fazer sem usar recursão. O código abaixo mostra como percorrer uma árvore binária in-ordem (filho esquerdo - raiz - filho direito)

void in_ordem (no *root) //root é a raiz da árvore
{
   if (root == NULL)
      return;  //condição de parada, se atingiu uma folha os filhos desta são NULL

   in_ordem (root->esq);  //vai para o nó esquerdo de root
   root->mostra_no();     //depois que percorreu o nó esquerdo e voltou para o nó imprime o valor em no
   in_ordem (root->dir);   //depois que imprimiu vai para o nó direito de root
}

O código acima percorre cada nó da árvore e imprime o valor do nó. A ordem de impressão é in-ordem como dito acima.