рекурсия — обход бинарного дерева поиска Переполнение стека

Question

рекурсия — обход бинарного дерева поиска Переполнение стека

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

Вот функция, заданная с присваиванием:

static void deleteAll(BSTNode<Data>* n) {
if (0 == n) return;
deleteAll(n->left);
deleteAll(n->right);
delete n;
}

Чтобы удалить действительно короткое дерево,

    корень
/ \
левша правша

Я звоню deleteAll(root), n != 0 так что теперь я звоню deleteAll(lefty), n != 0 так я звоню deleteAll(lefty->left), Там нет левого узла, конечно. Когда я добавил левый узел, мой конструктор инициализировал левый, правый и родительский указатели на 0, так что теперь n == 0, Поэтому я возвращаюсь из функции и никогда не удаляю права. Как мне добраться до deleteAll(n->right)?

Как я уже сказал, эта функция предоставляется, поэтому я не должен ее менять. Я думал, может быть, мне нужно позвонить deleteAll(b.begin()) или же b.end() начать с левого или самого правого узла, но каждый раз, когда я прохожу его в уме, я нажимаю n == 0,

Пожалуйста, помогите мне понять.

1

binary-search-tree c++recursion

Решение

Другие решения

Возврат только возвращает функцию, которая его вызывала. В случае, если deleteAll(lefty) (если я правильно понимаю, то или deleteAll(root)). deleteAll(n->right) будет вызван после deleteAll(n->left) возвращается. Условие удаления deleteAll таково, что n и все его дочерние элементы будут удалены.

Представьте, что у нас есть следующее дерево:

    a
/ \
b c
/   \
d     e

График вызовов будет выглядеть следующим образом:

deleteAll(a)
deleteAll(a->left)
deleteAll(a->left->left)
deleteAll(a->left->left->left)
deleteAll(a->left->left->right)
deleteAll(a->left->right)
deleteAll(a->right)
deleteAll(a->right->left)
deleteAll(a->right->right)
deleteAll(a->right->right->left)
deleteAll(a->right->right->right)

Или с точки зрения имен узлов:

deleteAll(a)
deleteAll(b)
deleteAll(d)
deleteAll(NULL)
deleteAll(NULL)
deleteAll(NULL)
deleteAll(c)
deleteAll(NULL)
deleteAll(e)
deleteAll(NULL)
deleteAll(NULL)

2

Источник

Accepted Answer

Представьте стрелку, указывающую на текущую строку, которая выполняется. Когда мы звоним deleteAll(root)сначала проверим, root это 0:

--> if (0 == root) return;
deleteAll(root->left);
deleteAll(root->right);
delete root;

Так как root != 0мы тогда позвоним deleteAll(root->left):

    if (0 == root) return;
--> deleteAll(root->left); /*
|-1-> if (0 == lefty) return;
|-2-> deleteAll(lefty->left);
|-3-> deleteAll(lefty->right);
|-4-> delete lefty; */
deleteAll(root->right);
delete root;
}

Теперь стрелка вернется к началу функции и начнет делать то же самое для lefty, пробегая строки 1-4 в моем комментарии (в строке 2 то же самое расширение произойдет снова, пока не будет найден нулевой узел). Но важно то, что это помнит где это было до вызова функции, чтобы она могла возобновиться позже. Так deleteAll(root->left) будет идти и делать то, что он делает, и в конце концов вернется. Затем оригинальный вызов продолжается:

    if (0 == root) return;
deleteAll(root->left);
--> deleteAll(root->right);
delete root;

Теперь правый узел тоже удален. Это происходит на каждом этапе рекурсии. Помни что return возвращает только текущую функцию, а не всю рекурсивную цепочку.

5