Понимание рекурсивных функций - PullRequest
Новая
       4

Понимание рекурсивных функций

1 голос
/ 06 мая 2011

Исходя из приведенного ниже двоичного дерева, каким будет выходной сигнал вызова функции 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);
}

Binary Tree: 63 |47 16 |86 32 NULL 9 |NULL NULL 95 NULL NULL NULL 53 64 |

Это мое понимание функции: 

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

Затем он проверит, является ли root-> data (63) нечетным или нет, так как он нечетный, тогда 

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

так что теперь sum =?

И затем он будет рекурсивно называть тайну (46) и тайну (16)

Это правильная идея?

Ответы [ 2 ]

4 голосов
/ 06 мая 2011

Обратите внимание, что рекурсивные вызовы дочерних элементов данного узла происходят за до вычисления значения этого узла. (Это может быть понятно для вас, но я не могу судить по тому, как вы сформулировали свой вопрос.) Таким образом, к моменту вычисления суммы в корневом узле (значение 63) значения его двух дочерних элементов уже модифицирована. (См. Ниже)

Если узел имеет нечетное значение, его новое значение будет суммой его собственного значения и новых значений его дочерних элементов, назначенных рекурсивными вызовами. Странно, если значение данного узла даже для начала, его новое значение не имеет ничего общего со значениями его потомков. Это будет просто половина его первоначальной стоимости.

Поскольку ваш вопрос, похоже, касается понимания последовательности рекурсии в целом, возможно, эти диаграммы помогут. Вот оригинальное дерево: 

             [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

Возможно, излишнее, но я надеюсь, что это поможет.

0 голосов
/ 06 мая 2011

Для каждого узла этого дерева этот код выполняет следующее.

  1. Если данные узла являются четным значением, они делятся на 2 и печатают результирующее значение.
  2. Если данные узла являются нечетным значением, они добавляют в него данные обоих его дочерних элементов и печатают результирующее значение.

Например, узел, содержащий данные как 86, это печать 43. А для узла, содержащего данные как 47, это печать 47 + 86 + 32 = 165.

...