Объясните левого ребенка правого родного брата

Question

У меня есть левый дочерний правый брат, как показано ниже:

    10 
*    | 
*    2 -> 3 -> 4 -> 5 
*              |    | 
*              6    7 -> 8 -> 9  */

Я хочу пройти от root до последнего узла, функция обхода выглядит следующим образом:

void traverseTree(Node * root) 
{ 
    if (root == NULL) 
        return; 

    while (root) 
    { 
        cout << " " << root->data; 
        if (root->child) 
            traverseTree(root->child); 
        root = root->next; 
    } 
} 

Как я понял, если у узла есть дочерний элемент, указатель указывает на его дочерний элемент, в противном случае указывает на одноуровневый элемент (следующий). В этом случае, когда указатель указывает на элемент 6, он будет go к следующему элементу root -> (который равен NULL). Тем не менее, функция все еще может печатать оставшийся элемент (5,7,8,9). Может ли кто-нибудь помочь мне объяснить, как traverseTree работает?

Вот код для воссоздания дерева:

// CPP program to create a tree with left child 
// right sibling representation. 
#include<bits/stdc++.h> 
using namespace std; 

struct Node 
{ 
    int data; 
    struct Node *next; 
    struct Node *child; 
}; 

// Creating new Node 
Node* newNode(int data) 
{ 
    Node *newNode = new Node; 
    newNode->next = newNode->child = NULL; 
    newNode->data = data; 
    return newNode; 
} 

// Adds a sibling to a list with starting with n 
Node *addSibling(Node *n, int data) 
{ 
    if (n == NULL) 
        return NULL; 

    while (n->next) 
        n = n->next; 

    return (n->next = newNode(data)); 
} 

// Add child Node to a Node 
Node *addChild(Node * n, int data) 
{ 
    if (n == NULL) 
        return NULL; 

    // Check if child list is not empty. 
    if (n->child) 
        return addSibling(n->child, data); 
    else
        return (n->child = newNode(data)); 
} 

// Traverses tree in level order 
void traverseTree(Node * root) 
{ 
    if (root == NULL) 
        return; 

    while (root) 
    { 
        cout << " " << root->data; 
        if (root->child) 
            traverseTree(root->child); 
        root = root->next; 
    } 
} 

//Driver code 

int main() 
{ 
    Node *root = newNode(10); 
    Node *n1 = addChild(root, 2); 
    Node *n2 = addChild(root, 3); 
    Node *n3 = addChild(root, 4); 
    Node *n4 = addChild(n3, 6); 
    Node *n5 = addChild(root, 5); 
    Node *n6 = addChild(n5, 7); 
    Node *n7 = addChild(n5, 8); 
    Node *n8 = addChild(n5, 9); 
    traverseTree(root); 
    return 0; 
} 

Answer 1

После выполнения traverseTree(root->child) поток управления продолжится со следующей строки. Вы не возвращаетесь из функции, просто вызываете другую функцию из этой функции.

void traverseTree(Node * root) 
{ 
    if (root == NULL) 
        return; 

    while (root) 
    { 
        cout << " " << root->data; 
        if (root->child) 
            traverseTree(root->child); // First, if child exists, traverse child. No return statement following here.
        root = root->next; // Next, traverse sibling
    } 
} 

Если у вас все еще есть сомнения, было бы полезно прочитать о ходе выполнения программы при вызове функции.

Обновление (совершенно не имеет отношения к вопросу): По запросу OP, решение с использованием стека :

void traverseTree(Node * root) 
{ 
    if (root == NULL) 
        return; 
    stack<Node*> s;
    s.push(root);
    while (!s.empty())
    {
        Node* top = s.top();
        cout << " " << top->data;
        s.pop();
        if (top->next) s.push(top->next);
        if (top->child) s.push(top->child);
    }
}