Возвращаемое значение рекурсивной функции

Question

В следующем коде я пытаюсь лучше понять, как работает рекурсия. Я всегда был немного смущен, что это действительно работает. Я хочу знать, какое значение фактически выполняет функция inorder() на каждом шаге. Откуда он получает эти значения 0,0,11,0,0,11,12,0,0,11 соответственно. Может ли кто-нибудь сказать мне логику? Это базовая программа обхода дерева дерева. Причина, по которой я пытаюсь понять эти результаты, состоит в том, что одна и та же логика каким-то образом используется для определения глубины дерева (я думаю), где при каждой рекурсии значение глубины увеличивается без инициализации.

#include<stdio.h> 
#include<stdlib.h> 

struct node 
{ 
    int data; 
    struct node *left; 
    struct node *right; 
}; 

struct node* newNode(int data) 
{ 
    struct node* node=(struct node*)malloc(sizeof(struct node)); 
    node->data=data; 
    node->left=NULL; 
    node->right=NULL; 
    return node; 
} 

int inorder(struct node *temp) { 
    if (temp != NULL) { 
    printf("\nleft %d\n",inorder(temp->left)); 
    printf("\n%d\n", temp->data); 
    printf("\nright %d\n",inorder(temp->right)); 
    } 
} 

int main() 
{ 
    struct node *root=newNode(1); 

    root->left=newNode(2); 

    root->right=newNode(3); 

    root->left->left=newNode(4); 

    root->left->right=newNode(5); 


    inorder(root); 
    getchar(); 
    return 0; 
} 

Answer 1

Эта функция должна быть изменена на следующий (первый и последний печати в исходном коде будет только у вас более запутанный!):

int inorder(struct node *temp) { 
    if (temp != NULL) { 
    inorder(temp->left); 
    printf("%d\n", temp->data); 
    inorder(temp->right); 
    } 
} 

Рекурсия начинается с левой ветви (обычно «root») - рекурсивно (в порядке) печатать все узлы на этой ветви слева, а затем печатать текущий узел, переходя к рекурсивному (упорядоченному) копированию всех узлов в правой ветке.

Кстати, если вы хотите сохранить это дерево «упорядоченным» (что означает, что все узлы в левой ветви меньше узла, а все узлы на правой ветви больше или равны узлу) вы должны изменить:

root->left->left=newNode(4); 
root->left->right=newNode(5); 

к:

root->right->right=newNode(4); 
root->right->right->right=newNode(5);