二叉树遍历
1.前序遍历(Pre-order Traversal)
①读取当前树根结点
②若存在左子树,对左子树执行①②③
③若存在右子树,对右子树执行①②③
2.中序遍历(In-order Traversal)
①若存在左子树,对左子树执行①②③
②读取当前树根结点
③若存在右子树,对右子树执行①②③
3.后序遍历(Post-order Traversal)
①若存在左子树,对左子树执行①②③
②若存在右子树,对右子树执行①②③
③读取当前树根结点。
逆推重建二叉树
前序遍历序列+中序遍历序列
- 获取前序遍历序列第一个元素A,该元素是二叉树根结点中保存的关键字。
- 凭借该元素查找中序遍历序列,A左侧的元素(GDBHEI)既是原二叉树中A所在结点左子树保存的关键字,A右侧的元素(FC)既是原二叉树中A所在结点右子树保存的关键字。
- 对使用A从中序遍历序列中划分出来的左右两部分子序列,执行上述过程,直到所有元素的在原二叉树中的位置确认。
后续遍历序列+中序遍历序列
- 获取后序遍历序列最后一个元素A,该元素是二叉树根结点中保存的关键字。
- 凭借该元素查找中序遍历序列,A左侧的元素(GDBHEI)既是原二叉树中A所在结点左子树保存的关键字,A右侧的元素(FC)既是原二叉树中A所在结点右子树保存的关键字。
- 对使用A从中序遍历序列中划分出来的左右两部分子序列,执行上述过程,直到所有元素的在原二叉树中的位置确认。
前序遍历序列+后序遍历序列(×)
从前面两种逆推过程可以看出,前序遍历序列和后序遍历序列的作用主要是确定子树根结点元素,结点左右子树包含哪些元素需要借助中序遍历序列才能知道。所以,前序遍历序列+后序遍历序列无法逆推出原二叉树。