Народ, беда у меня что-то я с этой рекурсией не могу разобраться(( Читал в книге смысл в том что функция вызывает сама себя и потом столько же раз обратно.. и как-то везде по-разному сформулировано.. просто каша в голове.... Не могли бы Вы мне объяснить на примере распечатки по ЛКП бинарного дерева, вот структура:

Код

struct TreeNode {              int item;         // The data in this node.              TreeNode *left;   // Pointer to the left subtree.              TreeNode *right;  // Pointer to the right subtree.           }

а вот сама рекурсивная функция по ЛКП:

Код

void inorderPrint( TreeNode *root ) {           if ( root != NULL ) {             inorderPrint( root->left );             cout << root->item << " ";               inorderPrint( root->right );        }     }

То есть мы идем сначала до конца налево.. это единственное что я тут понял.. а как выполняется распечатка корня и ход направо не понял.. то есть мне не понятно как может вообще выполняться код ниже inorderPrint( root->left ); это же все в одном If встроено... вообщем проясните если кто сможет. И какой тут порядок действий будет...Заране благодарен!

Попробую объяснить
Представьте себе, что функций inorderPrint на самом деле бесконечное количество



То есть как только мы добрались до вызова, мы не начинаем сначала функции, а выполняем новую

Ждём пока она закончится, а потом выполняем нашу до конца

ПС:
Всё дело в том, что функция существует как обьект и мы имеем указатель на неё, поетому можем выполнять её бесконечное количество раз

Ну вот допустим, у тебя такое дерево:

Код

1    /   \   2    3  /\   /\ 4  5  6 7

Вызовы будут происходить так:

Код

inorderPrint(node1)        inorderPrint(node2) //node1->left       inorderPrint(node4) //node2->left           inorderPrint(NULL) //node4->left               cout << node4->item << " ";               inorderPrint(NULL) //node4->right         cout << node2->item << " ";           inorderPrint(node5) //node2->right           inorderPrint(NULL) //node5->left               cout << node5->item << " ";               inorderPrint(NULL) //node5->right          cout << node1->item << " ";        inorderPrint(node3) //node1->right       inorderPrint(node6) //node3->left           inorderPrint(NULL) //node6->left               cout << node6->item << " ";               inorderPrint(NULL) //node6->right         cout << node3->item << " ";           inorderPrint(node7) //node3->right           inorderPrint(NULL) //node7->left               cout << node7->item << " ";               inorderPrint(NULL) //node7->right

Это сообщение отредактировал(а) Fantasist - 3.12.2004, 22:49

Просто пойми, что TreeNode - это не дерево, а только узел, причем тип узла. Дерево строиться в памяти динамически из объектов типа TreeNode (их много). Узлы связываются между собой через указатель Left и Right c другими узлами, а те в свою очередь тоже имеют указатели на узлы.

Теперь о рекурсии. Уясни для себя, что парамерты функций (в данном случае - это указатель на один из узлов) заносятся в стек друг за другом. Поэтому, если мы вызовем из inorderPrint еще один inorderPrint, то старый параметр сохраняется, но на верхушке стека теперь будет новый указатель, а когда фукция завершиться, стек сдвинется назад, и мы опять получаем преждние параметры.

Вощем здесь объяснить невозможно, нужно самому понять. Можешь нарисовать на листке бумаги дерево и глядя на алгоритм пальцем водить по узлам, отмечая для себя в каком порядке они обрабатываются. А если затруднения с функцией, то можно записывать, что заносится в стек.

Я вот всегда, когда непонятна программа и ход действий, пытаюсь нарисовать как она работает.
Намного легче понять особенно со структурами. Все видно сразу: что куда идет и что за чем следует!

Большое всем спасибо !!!!! Очень помогли