二叉树的先序,中序,后序怎么确定

Question

如题所述

Answer 1

二叉树的先序，中序，后序确定的方法如下：

1、根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。

2、观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是r0ot的左子树，G右侧的HMZ必然是root的右子树。

3、观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的rot的lefichild位于root之后，所以左子树的根节点为D。

4、同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。

5、遍历的右子树的第一个节点就是右子树的根节点。观察发现，上面的过程是递归的，先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。

特殊类型：

1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树。完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。