二叉树双阶遍历

Question

任何人都可以向我解释双顺序遍历吗？

        A
      /   \
     B     E
   /  \   /  \
  C   D  F    G

双顺序遍历输出:ABCCBDDAEFFEGG

我对解释而不是代码感兴趣.

谢谢

Answer 1

假设您对双顺序遍历的解释感兴趣:

对于每次遍历,你

• 访问节点
• 穿越左边的孩子
• 访问节点
• 横穿右儿童

这里的所有都是它的.如果您没有左子(例如C),则两个"访问节点"操作会重复发生,这就是您在输出中看到两个C的原因.

只是为了可视化(输出为粗体):

• 访问A:A
• 横过左边的孩子B.
• • 访问B:AB
• • 遍历左边的孩子C.
• • • 访问C:ABC
• • • 没有留下的孩子
• • • 访问C:ABCC
• • • 没有合适的孩子
• • 穿越右边的孩子D.
• • • 访问D:ABCCD
• • • 没有留下的孩子
• • • 访问D:ABCCDD
• • • 没有合适的孩子
• 访问A:ABCCDDA
• 穿越右边的孩子E.
• • 访问E:ABCCDDAE

等等