Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Рекурсия и бинарные деревья

Автор: freed0m 3.12.2004, 22:21

Народ, беда у меня что-то я с этой рекурсией не могу разобраться(( Читал в книге смысл в том что функция вызывает сама себя и потом столько же раз обратно.. и как-то везде по-разному сформулировано.. просто каша в голове.... Не могли бы Вы мне объяснить на примере распечатки по ЛКП бинарного дерева, вот структура: Код 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 встроено... вообщем проясните если кто сможет. И какой тут порядок действий будет...Заране благодарен!

Автор: sergejzr 3.12.2004, 22:39

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

Автор: Fantasist 3.12.2004, 22:47

Ну вот допустим, у тебя такое дерево: Код      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

Автор: S.A.P. 3.12.2004, 23:10

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

Автор: po-her 3.12.2004, 23:15

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

Автор: freed0m 3.12.2004, 23:17

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)