recursão e percorrendo uma árvore binomial

Question

Tenho a seguinte estrutura em árvore:

este mostra 3 níveis. Meu problema real terá de 8 a 12 níveis. Eu tenho o seguinte programa que acredito que percorrerá a árvore na ordem correta. Dois nós filhos se reportam a um nó pai. Se conhecermos os dois filhos, podemos encontrar o pai. Essencialmente, queremos percorrer a árvore da direita para a esquerda e de baixo para cima. Os números indicam a ordem em que os nós precisam ser percorridos.

Aqui está o meu código que acredito que fará isso:

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                printf("k loop: %d   ", i * 7 + j * 3 + k);
            }
            printf("\n");
            printf("j loop: %d  \n", i * 7 + j * 3 + 2);
        }
        printf("i loop: %d  \n", i * 7 + 6);
    }
    printf("final node: %d\n", 2 * 2 * 2 * 2 - 2);
}

Isso não é muito bonito e não é muito escalável, pois eu precisaria adicionar outro loop for para cada nível adicional.

três perguntas:

1. como eu faria isso com recursão?
2. Existe uma maneira mais escalável de fazer isso sem recursão?
3. qual será mais rápido uma abordagem de loop for ou uma abordagem de recursão

Answer 1

Você pode fazer isso recursivamente com estas etapas para p(n, level):

• if level > 0, primeiro imprima as sub-estradas com
  • chame n = p(n, level - 1)a subárvore esquerda
  • chame n = p(n, level - 1)a subárvore certa
• depois imprima ne devolvan+1

Aqui está uma implementação ingênua:

#include <stdio.h>

int p(int n, int level) {
    if (level > 0) {
        n = p(n, level - 1);
        n = p(n, level - 1);
    }
    printf("%i\n", n);
    return n + 1;
}

// initial call for a depth of 8:
int main() {
    p(0, 8);
    return 0;
}

Answer 2

1. O que você está procurando é chamado de In-Order Traversal . Geralmente é independente do número de níveis em sua árvore porque é um tipo de Depth-First Traversal .

Geralmente segue o seguinte algoritmo

1. Percorrer recursivamente a subárvore esquerda
2. Visite o nó raiz
3. Percorrer recursivamente a subárvore direita

Aqui está um link para mais informações

---

1. É inteiramente possível, e geralmente recomendado, usar métodos iterativos de travessia de árvore. Embora para pequenas árvores seus efeitos não sejam realmente sentidos, para grandes percursos recursivos ocupam quantidades exponenciais de espaço de memória. Aqui está um exemplo de travessia em ordem usando uma pilha em geekforgeeks

---

1. Embora você não perceba isso em uma árvore pequena, a abordagem recursiva é sempre mais lenta que a iteração.