❤️

ARCHAI

Undergraduate / Rookie

Back

由遍历序列构造出二叉树

由遍历序列构造出二叉树

仅知道一种遍历序列是无法确定唯一的二叉树的,以中序遍历为例,对于一个中序遍历序列“BDCAE”,其对应的树形结构可能有下面三种:

因此,至少需要两种遍历序列才可以推知树形结构。

1.前序+中序遍历序列

🎈基本步骤 由前序遍历的特性得知,前序遍历中第一个节点必然为根节点,因此根据中序遍历特性,根节点左边为左子树下的所有节点,右边为右子树下的所有节点,然后分别在左子树序列右子树序列中重复进行即可。

🎈示例

  • 前序遍历序列:A D B C E
  • 中序遍历序列:B D C A E

首先能确定根节点为A,根据中序遍历序列可以得到:

对于左子树BDC,根据前序遍历,此子树根节点为D,根据中序遍历序列:

image-20210508165242806

至此,二叉树的还原工作就完成了!至于更复杂的序列,逐步推断即可😋

2.后序+中序遍历序列

🔑与1不用的是,后序遍历中根节点为后序遍历序列尾部的那个节点,其余参照1即可!

3.层序遍历+中序遍历

🔑 根据层序遍历特性,层序遍历中根节点始终在子树前面,“根左右”

🎈示例

  • 层序遍历序列:A D E B C
  • 中序遍历序列:B D C A E

根节点为A,根据中序遍历序列可以得到:

对于左子树BDC,根据前序遍历,此子树根节点为D,根据中序遍历序列:

思考

如果前序,后续,层序两两组合能否确定唯一的树结构?

假设给定序列如下:

  • 前序:A B
  • 后序:B A
  • 层序:A B

其两两组合都满足两种结构:

因此前序,后续,层序两两组合不能确定唯一的树结构

Archai
Built with Hugo
Theme Stack designed by Jimmy