Как работает эта рекурсивная функция, это о вычислительных структурах?

Question

Я работаю с кодом обхода дерева, мне дали псевдокод, и я реализовал его на python, но я до сих пор не могу понять, как он работает

InOrderTraversal(tree):
  if tree = nil:
     return
  InOrderTraversal(tree.left)
  Print(tree.key)
  InOrderTraversal(tree.right)

псевдокодпоказано выше: InOrderTraversal (tree.left): этот код находит самый левый узел дерева, я думал, что на этом остановимся. Но как это может вернуться к родителю? и пройти все узлы дерева. он может вернуться к узлам, это то, что я запутался, это что-то о внутренней структуре компьютера

Answer 1

Если вы вызываете функцию, она запоминает, откуда она была вызвана, и затем возвращается, когда это сделано, поэтому она возвращается к своему родителю, потому что она была вызвана туда, и возвращается туда, когда это сделано. Просто возьмите простое дерево и подумайте, что будет происходить шаг за шагом.

Из кода, который я предполагаю, это для двоичного дерева (где каждый узел может иметь только двух детей)? Возьмите дерево, как это https://commons.wikimedia.org/wiki/File:Sorted_binary_tree_preorder.svg#/media/File:Sorted_binary_tree_preorder.svg, которое показывает порядок, в котором алгоритм будет идти с линией, окружающей его. Он начинается сверху с F в качестве значения для дерева, снова вызывает ту же функцию с B, который вызывает ту же функцию с A. У A нет дочерних элементов, поэтому два его вызова InOrderTraversal срабатывают, если tree = nil, и сразу возвращают с помощью функции, вызванной сДерево as также достигает конца своего функционального блока и возвращается к функции, вызвавшей его. Итак, мы вернулись к узлу B. Там код продолжается и он переходит к узлу D, потому что второй InOrderTraversal предназначен для правого узла.

И так далее, просто пройдите это шаг за шагом в своей голове, и это должно стать ясным. (Или с отладчиком, если необходимо.)

InOrderTraversal (tree.left): этот код находит самый левый узел дерева,

Tree.left простолевый потомок текущего узла, вызов функции будет проходить через левого потомка и всех его потомков.

Answer 2

Приведенный выше псевдокод перебирает Дерево , которое является структурой данных.

Рекурсивные функции - это функции, которые вызывают себя до тех пор, пока не будет выполнено условие завершения.

В дереве есть один корневой узел, и у него будут левый и правый дочерние узлы, у каждого из них могут быть одинаковые правый и левый дочерние узлы (или может не быть или иметь левый или правый дочерний элемент).

Если, скажем, у какого-либо дочернего элемента (или корневого элемента) нет правильного дочернего элемента, то правый дочерний элемент будет нулевым, то же самое верно для левого дочернего элемента.

Таким образом, приведенный выше код называет себя двумяраз, один раз для итерации по левой ветви и второй для итерации по правой ветви.

Я попытаюсь объяснить простым языком, вместо того, чтобы использовать множество технических терминов и запутанных концепций (сохранено просто):

давайте поговорим о левой ветви (например),

предположим, что теперь это похоже на ABCDE

, A is root, первый вызов функции будет вызываться с помощью A as ref, как этоЛевый дочерний элемент не равен нулю (то есть имеет детей), теперь он будет вызывать InOrderTraversal с дочерним элементом A, т.е. B as ref, в то время как наш вызов функции с ref-значением A хранится в call-stack,

и снова, потомком B является C, который также не равен нулю, поэтому функция InOrderTraversal вызывается снова с C's ref, и call-stack сохранит ссылку ref на вызов функции с ref B,

при этомСтек вызовов моментальных вызовов выглядит следующим образом:

 InOrderTraversal(C)
 InOrderTraversal(B)
 InOrderTraversal(A)

, поэтому он продолжается до E, теперь у E нет дочернего элемента, поэтому он вернется к функции, которая его вызвала, то есть к вызову функции с помощью ссылки D, котораязатем вернитесь снова назад, и, наконец, мы перейдем к вызову основной функции, который сгенерировал все вызовы этой функции.

То же самое относится и к правой ветви.

Так что это возможно с call-stack.

Я пытался объяснить ту часть, которая вас смущает.

Надеюсь, это поможет вам понять это.