数据结构与二叉树构建

所谓构建指的是能够唯一确定一棵二叉树的特定方式。

任意n（n>0）个不同节点组成的二叉树，均可通过其**（中序序列配合先序序列）或（中序序列结合后序序列）** 来实现唯一识别。

先序序列：A B D G C E F
中序序列：D G B A E C F
后序序列：G D B E F C A

我们需要了解的是，中序序列中任意节点的左子树与右子树同样属于中序序列；前序序列中任意节点的左子树与右子树也属于前序序列；后序序列中任意节点的左子树与右子树亦属于后序序列。

为何必须借助中序序列来构建二叉树？让我们通过以下步骤进行分析：

先序序列：A B D G C E F
中序序列：D G B A E C F

依据先序序列可以确定，根节点为A。接着在中序序列中定位到该节点A。（需注意，由于是不同节点构成的二叉树，因此在所有序列中仅会出现一个A）
在中序排列里，位于A左侧的部分D G B对应于左子树，并且这部分内容本身也符合中序排列的特性；而位于右侧的部分E C F则对应于右