Eu vi a resposta do @pcccj e concordo com o que ele diz, sobre retornar o item, e não apenas escrever seu valor. Existem várias formas se de fazer isso, desde um algoritmo genial que manipule o retorno da função de busca com maestria até um algorítmo simples mas que faça uso das ferramentas do C.
Como eu não sou tão inteligente assim, aqui vai um algoritmo simples ;)
#include<stdio.h>
#include<stdlib.h>
// Declara o formato dos nodos da árvore, e cria o tipo
struct nodo {
int Elemento;
struct nodo *Esquerda;
struct nodo *Direita;
};
typedef struct nodo Nodo;
// Insere elementos na árvore
void InsereNodo(Nodo **raiz, Nodo *item) {
if (!*raiz) {
*raiz = item;
return;
}
if (item->Elemento < (*raiz)->Elemento)
InsereNodo(&(*raiz)->Esquerda, item);
else
InsereNodo(&(*raiz)->Direita, item);
}
// Escreve o valor de cada elemento da árvore, in-order
void ListarEmOrdem(Nodo *raiz){
if (raiz->Esquerda)
ListarEmOrdem(raiz->Esquerda);
printf("%d\n", raiz->Elemento);
if (raiz->Direita)
ListarEmOrdem(raiz->Direita);
}
// Percorre a árvore, por profundidade, parando ao encontrar o n-ésimo elemento
void ProcuraProfundidade(Nodo *raiz, int **posicao, int limite, Nodo **NodoEncontrado){
if (raiz->Esquerda)
ProcuraProfundidade(raiz->Esquerda, posicao, limite, NodoEncontrado);
if (!*NodoEncontrado){
if((**posicao)++ == limite){
*NodoEncontrado = raiz;
return;
}
if (raiz->Direita)
ProcuraProfundidade(raiz->Direita, posicao, limite, NodoEncontrado);
}
}
// Função intermediária de busca; mantém uma assinatura decente e lida com exceções
Nodo* Procura(Nodo *raiz, int posicao){
if (posicao < 1)
return NULL;
else if (!raiz)
return raiz;
else {
Nodo *NodoEncontrado = NULL;
int *inicial = malloc(sizeof(int));
*inicial = 1;
ProcuraProfundidade(raiz, &inicial, posicao, &NodoEncontrado);
return NodoEncontrado;
}
}
int main(int argc, char **argv){
Nodo *raiz, *atual;
int i;
raiz = NULL;
// Cria uma árvore de 7 elementos aleatórios
for (i = 0; i < 7; i++) {
atual = (Nodo*)malloc(sizeof(Nodo));
atual->Esquerda = atual->Direita = NULL;
atual->Elemento = rand();
InsereNodo(&raiz, atual);
}
// Escreve todos os elementos da árvore
printf("Lista de elementos\n----------\n");
ListarEmOrdem(raiz);
// Procura por todas as posições, de 0 a n+1, para cobrir pelo menos 2 casos de erro
printf("\n\nResultado das buscas\n----------\n");
for (i = 0; i <= 8; i++){
atual = Procura(raiz, i);
if (atual)
printf("%d: %d\n", i, atual->Elemento);
else
printf("%d: %p\n", i, atual);
}
return EXIT_SUCCESS;
}
Basicamente, a busca funciona exatamente igual à função de escrita, mas adiciona condições de parada para evitar buscar toda a árvore quando você atinge a posição que gostaria.
Para controle, usa 2 ponteiros-para-ponteiros, para que cada sub-chamada da função controle os mesmos valores. Essa é a parte em que eu troco um algoritmo genial por usar as ferramentas da linguagem de forma efetiva. Funciona que é uma maravilha!
No final das contas, o resultado final é mais próximo do que você imaginaria naturalmente:
percorra a árvore
para cada elemento adicione um ao contador
se o contador for igual à posição que quiser
- retorne o elemento
Se quiser saber mais sobre ponteiros: http://www.mtm.ufsc.br/~azeredo/cursoC/aulas/c600.html