c - 了解递归函数

Question

根据下面的二叉树，函数调用 mystery(root) 的输出是什么？

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

 void mystery(struct treenode* root) {
     if (root == NULL) return;

     mystery(root->right);
     mystery(root->left);

     if (root->data%2 == 0) {
         root->data /= 2;
     }
     else {
         int sum = 0;
         if (root->left != NULL) sum += root->left->data;
         if (root->right != NULL) sum += root->right->data;
         root->data += sum;
     }
     printf(“%d “, root->data);
}

二叉树:63 | 47 16 | 86 32 空 9 |空 空 95 空 空 空 53 64 |

这是我对函数的理解:

mystery(63->right)
mystery(63->left)

然后它将检查 root->data (63) 是否为奇数，否则既然奇数，那么

sum += root->left(47)
sum += root->right(16)
root->data(63) += sum, 

所以现在 sum = ?

然后它会递归调用mystery(46)和mystery(16)

这是正确的想法吗？

Answer 1

请注意，对给定节点的子节点的递归调用发生在之前计算该节点的值。 (这对你来说可能很清楚，但我无法从你陈述问题的方式中看出这一点。)因此，在计算根节点(值 63)的总和时，它的两个子节点的值已经修改的。 (见下文)

如果一个节点有一个奇数值，它的新值将是它自己的值和它的 child 的新值的总和，由递归调用分配。奇怪的是，如果给定节点的值是偶开始的，它的新值与其子节点的值无关。它只是其原始值的一半。

由于您的问题似乎是关于理解一般的递归流程，也许这些图表会有所帮助。这是原始树:

             [63]
            /   \
         [47]   [16]
         /  \       \
      [86]  [32]    [9]
         \         /  \
        [95]    [53]  [64]

调用 mystery 函数后的新值如下:

              106+8+63=[177]
                  /         \
    43+16+47=[106]          16/2=[8]
           /      \                 \
    86/2=[43]   32/2=[16]        53+32+9=[94]
           \                            /    \
      95+0=[95]                53+0=[53]  64/2=[32]

要了解事情发生的顺序，请记住每个节点的值都是在递归调用其子节点之后计算和打印的。这称为“后序遍历”，尽管通常您递归地从左到右访问子项，而在这里我们是从右到左访问它们。下图显示了访问节点的顺序。

                 9[177]
               /       \
           8[106]      4[8]
         /      \          \
      7[43]     5[16]      3[94]
         \                 /   \
        6[95]          2[53]   1[32]

打印节点值会产生以下输出:

32 53 94 8 16 95 43 106 177

可能有点矫枉过正，但我​​希望对您有所帮助。