数据结构:二叉树遍历

Question

嗨，我对这棵树有点困惑，需要帮助来弄清楚我是否选择了正确的答案。

树:

  A
 / 
B   C
   / 
  D   E

让我们先遍历:

1. In-order: BADCE
2. 预订:ABCDE
3. 后序:BDECA

问题:

1. 下面哪个遍历产生BADEC?

。只有按次序的B.仅水平顺序C.仅限后期订购D.仅预购E.预购和关卡订购F.顺序和水平顺序G.以上皆非

回答g

下列哪个是对BST的后序遍历?一个系统。b。ABDCEc。BDECAd。EDCBAe。BADCEf。BADECG.以上之一

回答g

有人可以确认我是否做了正确的遍历，并为两个问题选择了正确的答案。

谢谢

Answer 1

三遍历算法属于递归算法。这意味着为了遍历以节点A为根的整个树，算法将分成三部分完成任务:

1. 遍历以B (A的左子树)为根的子树
2. 遍历根于C (A的右子树)的子树
3. 遍历/访问A本身

这三个任务的顺序取决于你使用的顺序:- In-order(左，根，右)执行task1, task3，然后是task2。- Pre-order (Root, Left, Right)执行task3, task1，然后是task2。- Post-order (Left, Right, Root)执行task1, task2，然后是task3

继续递归算法:为了遍历以B为根的子树，它将进一步拆分任务，遍历以B为根的子树，以B为根的子树，然后是B

"分裂任务"一直持续到要遍历的子树只包含一个根节点。在这种情况下，算法访问根节点并返回到剩余的子任务。同样的事情发生在以C为根的子树上，A的右子树。

下面是以3种不同顺序遍历问题中的树并使用遍历结果回答问题的详细步骤:

1. 序遍历(左，根，右):
   • 遍历以B为根的子树
     • 访问B
   • 访问A
   • 遍历根在C的子树
     • 遍历C的左子树
       • 访问D
     • 访问C
     • 遍历C的右子树
       • 访问E

顺序:BADCE

预购遍历(根，左，右)

• 访问A
• 遍历以B为根的子树
  • 访问B
• 遍历根在C的子树
  • 访问C
  • 遍历C的左子树
    • 访问D
  • 遍历C的右子树
    • 访问E

预购:中的

后序遍历(左，右，根)

• 遍历以B为根的子树
  • 访问B
• 遍历根在C的子树
  • 遍历C的左子树
    • 访问D
  • 遍历C的右子树
    • 访问E
  • 访问C
• 访问

后序:BDECA

您可以检查遍历结果是否与上面相同。

看遍历结果，我们知道问题1的答案是g，问题2的答案是c。