Question

二叉树前序中序后序

Answer 1

二叉树前序中序后序如下：

①前序遍历的方式是：首先访问根节点，然后访问左子树，最后访问右子树。

前序遍历序列：F C A D B E H G M。

②中序遍历的方式是：首先访问左子树，接着访问根结点，最后访问右子树。

中序遍历序列：A C B D F H E M G。

③后序遍历的方式是：首先访问左子树，接着访问右子树，最后访问根结点。

后序遍历序列：A B D C H M G E F。

④相同的特点：

左子树总是在右子树的之前遍历。

遍历都可以用递归的方式来描述。

中序遍历的序列中任取一个结点，该结点的左子树右子树一定分别在该结点左右，其他遍历序列也是如此。

遍历实质就是看每个结点及其子结点，谁先满足访问的要求，比如上图A结点，在后续遍历整个二叉树中A及其子结点先满足-访问完左右结点-，所以先访问A结点。

⑤由序列逆推二叉树

给定一个序列无法确定二叉树结构。

给定中序+前/后序则可以确定二叉树结构。