在 Python 3 中走 BST

Question

谁能解释一下计算机是如何到达 walkTree(tree['right']) 的？我相信该函数一直调用自身直到 None 然后递归弹出所有 "left" 堆栈并打印它们，但是当函数调用 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)

A return 位于调用堆栈的底部 returns 到更高一层的调用堆栈，而不是一直到顶部。

在 Python 3 中走 BST

Walking a BST in Python 3

python

recursion

binary-tree

tree-traversal

binary-search-tree