Python中的树遍历如何在打印子节点后确定父节点

Question

在下面的代码中，树有5个元素，其中A有(B，C)和B有(D，E)，我的问题是打印最后一个元素后，该节点是D 节点如何在以下代码中切换到"B"，有人可以解释一下这段代码吗

class trees(object):
def __init__(self,name,left=None,right=None):
self.name = name
self.left = None
self.right = None
def inorderTraversal(root):
res = []
if root:
res = inorderTraversal(root.left) 
print root.name
res = res + inorderTraversal(root.right)
t1=trees('A')
t2=trees('B')
t3=trees('C')
t4=trees('D')
t5=trees('E')
t1.left = t2
t1.right = t3
t2.left= t4
t2.right = t5
inorderTraversal(t1) 
#prints D,B,E,A,C

Answer 1

这只是递归。

与其说"B"打印后会发生什么，不如想想打印"B"之前会发生什么。

让我们考虑包含"B"的节点之前的根t2。(也许你甚至可以将你的树减少到只包含t2，t4和t5。这应该更有启发性)。接下来会发生什么：

1. 无序遍历到 t4，这是 t2 的左子项。最终，这将打印"D"
2. 打印"B">
3. 无序遍历到 T5，这是 T2 的正确子级。最终，这将打印"E">

之后，我们移动到 T2 等的父级。

请注意，对于没有子项的树，将打印根，因为对于其子树，root is None计算结果为 false。因此，在孩子层面上什么也没发生，我们遍历到根，打印它的名字，然后向下穿越到它的孩子，在那里什么都没有发生。

---

关于您的评论：您的代码确保当您打印"D"时，由于递归，您之后也会打印"B"！

假设我们只有树(t2，(t4，t5))，我们称之为inorderTraversal(t2)： 会发生什么(删除不必要的 res) 后：

1. 从 t2 开始

   if t2: (True)
   inorderTraversal(t4)
   print 'B'
   inorderTraversal(t5)
   

2. 执行 inorderTraversal(t4) 并解析 if(t2)

   if t4 (True):
   inorderTraversal(None)
   print 'D'
   inorderTraversal(None) 
   print 'B'
   inorderTraversal(t5)
   

让我们看看大括号中的术语在做什么： inorderTraversal(None) 只是做注释，所以这里唯一发生的事情是打印 t4 的名称。 所以你看，打印"B"比打印"D"出现得更早

3. 让我们再次总结一下递归调用

   print 'D' 
   print 'B'
   inorderTraversal(t5)