Ходьба BST в Python 3

Question

Кто-нибудь может объяснить, как получается, что компьютер walkTree(tree['right'])? Я считаю, что функция продолжает вызывать себя до None а затем рекурсивно выскакивает все "левые" стеки и печатает их, но когда функция вызывает walkTree(tree['right'])что делает компьютер, когда он проходит мимо walkTree(tree['left']) снова?

def walkTree(tree):
    if tree == None:
        return None
    walkTree(tree['left']
    print(tree['data'])
    walkTree(tree['right'])

Answer 1

BST - это рекурсивная структура данных. Когда вы вызываете функцию со значением 'left', она направляется в левую половину BST. Затем это повторяется и продолжается, пока не достигнет самого левого узла в дереве. Затем он начинает двигаться обратно вверх и переходит к непосредственному правому поддереву своего родителя (родителя самого левого узла). Затем снова тот же процесс продолжается, и он сначала посещает левые поддеревья и действует таким же образом. Когда он, наконец, достигает корня всего дерева во время путешествия обратно вверх (после посещения ВСЕХ узлов в левой половине), наступает время посетить правильное поддерево. Затем он снова переходит к левому поддереву этого корня (справа от абсолютного корня), если таковой имеется. Это левое поддерево является не левым поддеревом основного дерева, а правым узлом основного корня.

Ваш код в основном будет печатать значения во всем BST в порядке возрастания. Кроме того, я думаю, что это должно быть

if tree == None:
    return

Answer 2

Похоже, вы не понимаете, как работает стек вызовов. Возьмите простое дерево:

   2
  / \
 1   3

Стек вызовов будет выглядеть (используя отступ для указания уровня в стеке вызовов):

walkTree(tree)
    walkTree(left)
        walkTree(left)
            return
        print(1)
        walkTree(right)
            return
        return (implicit)
    print(2)
    walkTree(right)
        walkTree(left)
            return
        print(3)
        walkTree(right)
            return
        return (implicit)
    return (implicit)

return в нижней части стека вызовов возвращается к стеку вызовов только на один уровень выше, а не до самого верха.