Печать из рекурсивной комбинации со списком в C

Question

Я хочу понять следующий код:

struct element{
   element *a1;
   element *a2;
   int value;
};

void main(){
    element e6 = { NULL, NULL, 6 };
    element e2 = { NULL, NULL, 2 };
    element e4 = { NULL, NULL, 4 };
    element e7 = { &e6, NULL, 7 };
    element e9 = { NULL, NULL, 9 };
    element e3 = { &e2, &e4, 3 };
    element e8 = { &e7, &e9, 8 };
    element e5 = { &e3, &e8, 5 };

   cout << CountList(&e5) << endl;

return;}

int CountList(element *e){
   int c=1;
   if(e){
      c=c+CountList(e->a1);
      c=c+CountList(e->a2);
      return c;}
    return 0;
}

количество равно 8. Но как я могу понять строку рекурсии ??Моя идея заключалась в том, что Count должен быть 6, потому что функция рекурсии вызывается только 4 раза.Компилятор говорит 8, что уже является правильным решением.Но почему ??

Answer 1

Это дерево

            e5
           /  \
         e3    e8
        / \    / \
      e2  e4 e7   e9
              |
             e6

Рекурсивная функция начинается с e5, сначала вызывает себя с e3, что, в свою очередь, вызывает с e2, другой вызов с NULL, который возвращает (кe2).

С e2 вызов на другой стороне, который также равен NULL, затем возвращается (e3).

С e3, вызов e4, который имеет только NULL дочерних элементов и возвращает (к e3).

Оттуда e3 возвращается к e5, что вызывает другую сторону (e8) ...

Каждый элемент, отличный от NULL, считается как 1, добавленный к дочерним элементам, отличным от NULL.

, что дает 8 всего.Количество элементов в дереве.

---

Количество обращений к рекурсивной функции составляет не менее 8, чтобы посетить всех детей.Если вы посчитаете количество вызовов с помощью элемента NULL (9), общее количество вызовов составит 17 *.

Answer 2

Это на самом деле не список, а своего рода двоичное дерево.

int CountList(element *e){

Здесь вы считаете текущий элемент (1 элемент):

   int c=1;
   if(e){

Затем вы добавляете количество элементов, подсчитываемых в первом поддереве:

      c=c+CountList(e->a1);

И вы добавляете количество элементов, подсчитанное во втором поддереве:

      c=c+CountList(e->a2);

, что составляет целое число элементов:

      return c;
    }

Если текущий элемент равен NULL (пустое дерево), вернуть 0:

    return 0;
}

Вот и все.