Skip to main content
adicionou 130 caracteres ao conteúdo
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39

Uma maneira super simples de contornar as dificuldades desse problema é usar umas variáveis globais pra manter o estadopara os parâmetros da busca e pro valor de retorno, o que permite manter a função recursiva focada exclusivamente na iteração:

O legal mesmo seria fazerse pudéssemos declarar a função n_arvorepercorreArvore, etc serem variáveis locais de dentro da função nEsimoElemento e fazer, com percorreArvoren_arvore ser uma função internasendo variáveis locais de nEsimoElemento com acesso. Isso combinaria a essas variáveis mas C não permite que você declare uma função dentrosimplicidade da outra então o jeito é usarversão com variáveis globais mesmo ou criar umacom a localidade da versão com struct explícita pro "closure". Infelizmente, C não conta com essa funcionalidade.

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando. Tem muitas maneiras de fazer isso, essa aqui é só um exemplo:

Uma maneira super simples é usar umas variáveis globais pra manter o estado da iteração:

O legal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo ou criar uma struct explícita pro "closure".

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando.

Uma maneira super simples de contornar as dificuldades desse problema é usar umas variáveis globais para os parâmetros da busca e pro valor de retorno, o que permite manter a função recursiva focada exclusivamente na iteração:

O legal mesmo seria se pudéssemos declarar a função percorreArvore dentro da função nEsimoElemento, com n_arvore sendo variáveis locais de nEsimoElemento. Isso combinaria a simplicidade da versão com variáveis globais com a localidade da versão com struct. Infelizmente, C não conta com essa funcionalidade.

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando. Tem muitas maneiras de fazer isso, essa aqui é só um exemplo:

adicionou 334 caracteres ao conteúdo
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39

Se você preferir evitar denão quiser usar globais, o que você pode fazer é criar uma struct com campos pro n_arvore, k_alvo e k_esimo_elemento, inicializar ela em kEsimoElemento e passar um ponteiro pra essaempacotar o estado numa struct pra percorrerArvore.:

struct kElemState {
    int n_arvore;
    int k_alvo;
    int k_esimo_elemento;
}

void percorrerArvore(struct kElemState *state, Nodo* T){ ... }

void kEsimoElemento(int k, Nodo * T){
    struct kElemState s;
    s.n_arvore = 0;
    s.k_alvo = k;
    percorrerArvore(&s, T);
    if(k < s.n_arvore){
        return s.k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

O ideallegal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo ou criar uma struct explícita pro "closure".

Se você preferir evitar de usar globais, o que você pode fazer é criar uma struct com campos pro n_arvore, k_alvo e k_esimo_elemento, inicializar ela em kEsimoElemento e passar um ponteiro pra essa struct pra percorrerArvore.

O ideal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo ou criar uma struct explícita pro "closure".

Se você não quiser usar globais, você pode empacotar o estado numa struct:

struct kElemState {
    int n_arvore;
    int k_alvo;
    int k_esimo_elemento;
}

void percorrerArvore(struct kElemState *state, Nodo* T){ ... }

void kEsimoElemento(int k, Nodo * T){
    struct kElemState s;
    s.n_arvore = 0;
    s.k_alvo = k;
    percorrerArvore(&s, T);
    if(k < s.n_arvore){
        return s.k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

O legal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo ou criar uma struct explícita pro "closure".

adicionou 57 caracteres ao conteúdo
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39

Uma maneira super simples é usar umas variáveis globais pra manter o estado da iteração:

static int n_arvore;
static int k_alvo;
static int k_esimo_elemento;

void percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(n_arvore == k_alvo){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        percorrerArvore(T->Direita);
    }
}

void kEsimoElemento(int k, Nodo * T){
    n_arvore = 0;
    k_alvo = k;
    percorrerArvore(T);
    if(k < n_arvore){
        return k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

Acho que o usoSe você preferir evitar de usar globais nesse caso é válido, o que assim evitamos de adicionar um montão de argumentosvocê pode fazer é criar uma struct com campos pro n_arvore, k_alvo e k_esimo_elemento, inicializar ela em percorreArvorekEsimoElemento e passar um ponteiro pra essa struct pra percorrerArvore. 

O ideal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo. Só preste atenção pra nenhuma outra função usar essas globais (declarar elas com static ajuda um pouco) ou criar uma struct explícita pro "closure".

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando.

int percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(k_alvo < n_arvore){ return; }

        if(k_alvo == n_arvore){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        if(k_alvo < n_arvore){ return; }

        percorrerArvore(T->Direita);
    }
}

Uma maneira super simples é usar umas variáveis globais pra manter o estado da iteração:

static int n_arvore;
static int k_alvo;
static int k_esimo_elemento;

void percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(n_arvore == k_alvo){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        percorrerArvore(T->Direita);
    }
}

void kEsimoElemento(int k, Nodo * T){
    n_arvore = 0;
    k_alvo = k;
    percorrerArvore(T);
    if(k < n_arvore){
        return k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

Acho que o uso de globais nesse caso é válido, que assim evitamos de adicionar um montão de argumentos em percorreArvore. O ideal seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo. Só preste atenção pra nenhuma outra função usar essas globais (declarar elas com static ajuda um pouco).

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando.

int percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(k_alvo < n_arvore){ return; }

        if(k_alvo == n_arvore){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        if(k_alvo < n_arvore){ return; }

        percorrerArvore(T->Direita);
    }
}

Uma maneira super simples é usar umas variáveis globais pra manter o estado da iteração:

static int n_arvore;
static int k_alvo;
static int k_esimo_elemento;

void percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(n_arvore == k_alvo){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        percorrerArvore(T->Direita);
    }
}

void kEsimoElemento(int k, Nodo * T){
    n_arvore = 0;
    k_alvo = k;
    percorrerArvore(T);
    if(k < n_arvore){
        return k_esimo_elemento;
    }else{
        /* Árvore não tem elementos o suficiente */
    }
}

Se você preferir evitar de usar globais, o que você pode fazer é criar uma struct com campos pro n_arvore, k_alvo e k_esimo_elemento, inicializar ela em kEsimoElemento e passar um ponteiro pra essa struct pra percorrerArvore. 

O ideal mesmo seria fazer n_arvore, etc serem variáveis locais de nEsimoElemento e fazer percorreArvore ser uma função interna de nEsimoElemento com acesso a essas variáveis mas C não permite que você declare uma função dentro da outra então o jeito é usar globais mesmo ou criar uma struct explícita pro "closure".

Fora isso, você também pode adicionar uma otimização para parar a recursão depois que você achar o elemento que você estiver procurando.

int percorrerArvore(Nodo* T){
    if (T != NULL){
        percorrerArvore(T->Esquerda);

        if(k_alvo < n_arvore){ return; }

        if(k_alvo == n_arvore){ k_esimo_elemento = T->Elemento; }    
        +n_arvore;
        
        if(k_alvo < n_arvore){ return; }

        percorrerArvore(T->Direita);
    }
}
removeu 1 caractere do conteúdo
Fonte Link
Gabe
  • 2,5mil
  • 2
  • 25
  • 40
Carregando
adicionou 314 caracteres ao conteúdo
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39
Carregando
adicionou 314 caracteres ao conteúdo
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39
Carregando
Fonte Link
hugomg
  • 9,1mil
  • 27
  • 39
Carregando