后序,预订,顺序遍历,二进制搜索树

Question

考虑以下树结构.

    A
   / \
  B   C
 / \   \
D   E   F

使用后序,预订和遍历遍历来访问节点的顺序是什么？

Answer 1

我发现它有助于想到postorder,preorder和inorder递归算法.

后序遍历

递归地,这是左,右,自我.换句话说,对左子树进行遍历,然后对右子树进行遍历,然后才访问当前节点.基本情况是节点没有子节点.

对于这个例子:

回答: D, E, B, F, C, A

说明:

1. 从节点A开始.评估左子树.在节点B处.评估左子树.在节点D.没有孩子- > 访问d.
2. 回到B.评估右子树.在节点E.无儿- > 访问ē.
3. 回到B. 访问乙.
4. 返回A.评估正确的子树.在节点C处.没有左子树,因此评估右子树.在节点F.没有孩子- > 参观˚F.
5. 回到C. 访问Ç.
6. 回到A. 访问A.

预订遍历

递归地,这是自我,左,右.

看看你是否可以自己使用逻辑来得到答案postorder traversal.

顺序遍历

递归地,这是左,自,右.

看看你是否可以自己使用逻辑来得到答案postorder traversal.

如果你想检查你的工作,

该Preorder traversal会A, B, D, E, C, F和Inorder traversal会D, B, E, A, C, F.